Zurück zu den Preprints des Jahres 2004


Extended Formulations for Gomory Corner Polyhedra

by Köppe, Matthias, Louveaux, Quentin, Weismantel, Robert, Wolsey, Laurence A..

Series: 2004-04, Preprints

90C10 Integer programming

We present several types of extended formulations for integer programs, based on irreducible integer solutions to Gomory's group relaxations. We present an algorithm based on an iterative reformulation technique using these extended formulations. We give computational results for benchmark problems, which illustrate the primal and dual effect of the reformulation.

Group relaxation, reformulation techniques, integral generating sets