Heuristic Ceiling Point Algorithm for General Integer Linear Programming

摘要

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. (kr)