The Role of Ceiling Points in General Integer Linear Programming

This report examines the role played by several kinds of ceiling points in solving the pure, general integer linear programming problem ILP. While no assumptions are made concerning the structure or signs of the data of the problem, it is assumed that the feasible region for ILP is non-empty and bounded. A ceiling point with respect to a single constraint maybe thought of as an integer solution on or close to the boundary of the feasible region defined by the constraint. The definition of a ceiling point with respect to a single constraint is extended to take multiple constraints into consideration simultaneously, defining what is called a feasible ceiling point. It is shown that the set all feasible ceiling points contains at least one optimal solution for ILP. A related class of solutions called feasible 1-ceiling points is also characterized and shown to contain all optimal solutions for ILP. Moreover, 1- ceiling points are computationally easier to identify than ordinary ceiling points and may be sought with respect to one constant at a time. It is also demonstrated that solving ILP requires only enumerating feasible 1-ceiling points with respect to a subset of all functional constraints. Keywords Integer variables Enumeration algorithms.