Matteo Fischetti
Department of Information Engineering, University of Padova
Friday, July 1, 2005
2:00 – 3:30 pm
388 Posner Hall
Mixed-Integer Cuts from Cyclic Groups: a Computational Study
Abstract:
We analyze a separation procedure for Mixed-Integer Programs related to the
work of Gomory and Johnson on interpolated subadditive functions. This
approach has its roots in the Gomory-Johnson characterization on the master
cyclic group polyhedron. To our knowledge, the practical benefit that can
be obtained by embedding interpolated subadditive cuts in acutting plane
algorithm was not investigated computationally by previous authors. Indeed,
a number of recent papers deals only implicitly with cyclic-group cuts
(e.g., those based on the so-called Gomory’s shooting experiment), or they
consider only a subfamily of subadditive cuts (e.g., Gomory mixed-integer
cuts, k-cuts, etc.). In this paper we compute, for the first time, the
lower bound value obtained when adding (implicitly all the interpolated
subadditive cuts that can be derived from the individual rows of an optimal
LP tableau, thus approximating the optimization over the so-called Gomory’s
Corner polyhedron. The computed bound is compared with that obtained when
only Gomory mixed-integer cuts are used, on a large test-bed of MIPLIB
instances.
