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.