An Exact Ceiling Point Algorithm for General Integer Linear Programming
Abstract
This report describes an exact algorithm for the pure, general integer linear programming problem (ILP). Common applications of this model occur in capital budgeting (project selection), resource allocation and fixed- charge (plant location) problems. The central theme of our algorithm is to enumerate a subset of all solutions called feasible 1-ceiling points. A feasible 1-ceiling point may be thought of as an integer solution lying on or near the boundary of the feasible region for the LP-relaxation associated with (ILP). Precise definitions of 1-ceiling points and the role they play in an integer linear program are presented in a recent report by the authors. One key theorem therein demonstrates that all optimal solutions for an (ILP) whose feasible region is non-empty and bounded are feasible 1-ceiling points. Consequently, such a problem may be solved by enumerating just its feasible 1-ceiling points. Our approach is to implicitly enumerate 1-ceiling points with respect to one constraint at a time while simultaneously considering feasibility. Computational results from applying this incumbent-improving Exact Ceiling Point Algorithm to 48 test problems taken from the literature indicate that this enumeration scheme may hold potential as a practical approach for solving problems with certain types of structure.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1988
- Accession Number
- ADA202286
Entities
People
- Frederick Stanton Hillier
- Robert M. Saltzman
Organizations
- Stanford University