A Heuristic Ceiling Point Algorithm for General Integer Linear Programming
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.
Volume (Year): 38 (1992)
Issue (Month): 2 (February)
|Contact details of provider:|| Postal: |
Web page: http://www.informs.org/
More information through EDIRC
When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:38:y:1992:i:2:p:263-283. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc)
If references are entirely missing, you can add them using this form.