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 cei ling points are defined and analyzed and one kind called "feasible 1-c eiling points" proves to be of special interest. We demonstrate that a ll optimal solutions for a problem (P) whose feasible region is nonemp ty and bounded are feasible 1-ceiling points. Consequently, such a pro blem may be solved by enumerating just its feasible 1-ceiling points. The paper then describes an algorithm called the Heuristic Ceiling Poi nt Algorithm (HCPA) which approximately solves (P) by searching only f or feasible 1-ceiling points relatively near the optimal solution for the LP-relaxation; such solutions are apt to have a high (possibly eve n optimal) objective function value. The results of applying the HCPA to 48 test problems taken from the literature indicate that this appro ach usually yields a very good solution with a moderate amount of comp utational effort.