A Heuristic Ceiling Point Algorithm for General Integer Linear Programming
Robert M. Saltzman, Frederick S. Hillier
Management Science · 1992 · Volume 38 · Issue 2
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
Enable JavaScript for citation tools and additional paper interactions.