Zurück zu den Preprints des Jahres 2004


2004-04

Extended Formulations for Gomory Corner Polyhedra

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


Series: 2004-04, Preprints

MSC:
90C10 Integer programming

Abstract:
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.

Keywords:
Group relaxation, reformulation techniques, integral generating sets