A Heuristic Ceiling Point Algorithm for General Integer Linear Programming
定义并分析了整数线性规划中的“可行1-天花板点”，证明所有最优解都是此类点，并据此提出启发式天花板点算法（HCPA），通过搜索靠近LP松弛最优解的可行1-天花板点来近似求解问题，在48个测试问题上表现良好。
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.