SC 99-03 Alexander Martin: Integer Programs with Block Structure
Abstract: In this thesis we study and solve integer programs with block
structure, i.e., problems that after the removal of certain rows (or
columns) of the constraint matrix decompose into independent
subproblems. The matrices associated with each subproblem are called
blocks and the rows (columns) to be removed linking constraints
(columns). Integer programs with block structure come up in a natural
way in many real-world applications.
The methods that are widely used to tackle integer programs with block
structure are decomposition methods. The idea is to decouple the
linking constraints (variables) from the problem and treat them at a
superordinate level, often called master problem. The resulting
residual subordinate problem then decomposes into independent
subproblems that often can be solved more efficiently. Decomposition
methods now work alternately on the master and subordinate problem and
iteratively exchange information to solve the original problem to
optimality.
In Part I we follow a different approach. We treat the
integer programming problem as a whole and keep the linking
constraints in the formulation. We consider the associated polyhedra
and investigate the polyhedral consequences of the involved linking
constraints. The variety and complexity of the new inequalities that
come into play is illustrated on three different types of real-world
problems. The applications arise in the design of electronic
circuits, in telecommunication and production planning. We develop a
branch-and-cut algorithm for each of these problems, and our
computational results show the benefits and limits of the polyhedral
approach to solve these real-world models with block structure.
Part II of the thesis deals with general mixed integer
programming problems, that is integer programs with no apparent
structure in the constraint matrix. We will discuss in Chapter 5
the main ingredients of an LP based branch-and-bound algorithm for the
solution of general integer programs. Chapter 6 then asks the
question whether general integer programs decompose into certain block
structures and investigate whether it is possible to recognize such a
structure. The remaining two chapters exploit information about the
block structure of an integer program. In Chapter 7 we parallelize
parts of the dual simplex algorithm, the method that is commonly used
for the solution of the underlying linear programs within a
branch-and-cut algorithm. In Chapter 8 we try to detect small
blocks in the constraint matrix and to derive new cutting planes that
strengthen the integer programming formulation. These inequalities may
be associated with the intersection of several knapsack problems. We
will see that they significantly improve the quality of the general
integer programming solver introduced in Chapter 5.
(only electronic version available)
Keywords: integer programming,
cutting planes,
block structure
MSC: 90C10, 90C05, 90C11, 90C27