Decomposition in Integer Programming.
Abstract
Linear programming models in which the constraint matrix has a block angular structure arise frequently in many applications. While much work has been devoted to exploiting this special structure when the problem variables are assumed to be continuous, little consideration has been given to models of this type in which the variables are required to take on only integer values. In this report, an algorithm for the decomposition of block angular integer programs is presented. The block angular integer program consists of several subproblems which would operate independently except that they are tied together by a set of linking constraints. Conceptually, these linking constraints are viewed as representing common resources which the subproblems must share. The problem thus becomes that of determining an optimal allocation of these resources among the subproblems. Toward this end, a branch-and-bound search routine is developed. It is shown how the LP-optimal dual multipliers and any slacks which appear in the optimal integer solutions to the subproblems can be used to guide the search, as well as for bounding and fathoming purposes. Special structures which arise when there is only a single linking constraint are discussed in detail. Since the problem decomposes completely once an allocation of the linking resources is specified, only the subproblems ever need be solved explicitly. Computational results obtained with the decomposition algorithm are reported. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1976
- Accession Number
- ADA033104
Entities
People
- Gary A. Kochman
Organizations
- Stanford University