Exploring structure and reformulations in different integer programming algorithms
In this thesis we consider four topics all related to using problem reformulations
in order to solve integer programs, i.e. optimization problems in which the decision
variables must be integer.
We first consider the polyhedral approach.
We start by addressing the question of lifting valid inequalities, i.e. finding a
valid inequality for a set Y from the knowledge of a valid inequality for
a lower-dimensional restriction X of Y. We simplify and clarify the presentation of
the procedure. This allows us to derive conditions under which the computation
of the lifting is tractable.
The second topic is the study of valid inequalities for the single node flow set.
The single node flow set is the problem obtained by considering one node
of a fixed charge network flow problem. We derive valid inequalities for this
set and various generalizations. Our approach is a systematic
procedure using only basic tools of integer programming: fixing and
complementing variables, mixed-integer rounding and lifting. The method allows
us to explain and generate a large range of inequalities describing the convex hull of
The last two topics are based on non-standard approaches for integer programming.
We first show how the group relaxation approach can be used to provide reformulations
for the integral basis method. This is based on a study of extended formulations
for the group problem. We present four extended formulations and show that the projections of three
of these formulations provide the convex hull of the original group problem.
Initial computational tests of the approach are also reported.
Finally we consider a problem that is difficult for the standard
branch-and-bound approach even for small instances. A reformulation based
on lattice basis reduction is known to be more effective. However
the step to compute the reduced basis is O(n^4) and becomes a bottleneck
for small to medium instances. By using the structure of the problem,
we show that we can decompose the problem and obtain the basis by
taking the kronecker product of two smaller bases easier to compute. Furthermore,
if the two small bases are reduced, the kronecker product is also reduced
up to a reordering of the vectors. Computational results show the gain from such an approach.
School:Université catholique de Louvain
Source Type:Master's Thesis
Keywords:lifting group problem integer programming lattice basis reduction
Date of Publication:06/17/2004