A Heuristic Ceiling Point Algorithm for General Integer Linear Programming
Abstract
This report describes a heuristic algorithm for the pure, general integer linear programming problem (ILP). In attempting to quickly obtain a near-optimal solution (with-out concern for establishing optimality), the algorithm searches for a feasible 1-ceiling point. 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 the 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 heuristic approach is based upon the idea that a feasible 1-ceiling point found relatively near the optimal solution for the LP-relaxation is apt to have a high (possibly even optimal) objective function value. Having applied this Heuristic Ceiling Point Algorithm to 48 test problems taken from the literature, it appears that searching for such 1-ceiling points usually does provide a very good solution with a moderate amount of computational effort. Keywords: Subroutines, General integer variables.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1988
- Accession Number
- ADA202285
Entities
People
- Robert M. Saltzman
Organizations
- Stanford University