A Heuristic Ceiling Point Algorithm for General Integer Linear Programming

Robert M. Saltzman and Frederick S. Hillier
Additional contact information
Robert M. Saltzman: School of Business, San Francisco State University, San Francisco, California 94132
Frederick S. Hillier: Department of Operations Research, Stanford University, Stanford, California 94305

Management Science, 1992, vol. 38, issue 2, 263-283

Abstract: This paper first examines the role of ceiling points in solving a pure, general integer linear programming problem (P). Several kinds of ceiling points are defined and analyzed and one kind called "feasible 1-ceiling points" proves to be of special interest. We demonstrate that all optimal solutions for a problem (P) whose feasible region is nonempty and bounded are feasible 1-ceiling points. Consequently, such a problem may be solved by enumerating just its feasible 1-ceiling points. The paper then describes an algorithm called the Heuristic Ceiling Point Algorithm (HCPA) which approximately solves (P) by searching only for feasible 1-ceiling points relatively near the optimal solution for the LP-relaxation; such solutions are apt to have a high (possibly even optimal) objective function value. The results of applying the HCPA to 48 test problems taken from the literature indicate that this approach usually yields a very good solution with a moderate amount of computational effort.

Keywords: integer linear programming; general integer variables; heuristic algorithm; ceiling points; linear programming relaxation; enumeration algorithms (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.38.2.263 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:38:y:1992:i:2:p:263-283

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().