Role of Ceiling Points in General Integer Linear Programming
Defense Technical Information Center, 1988 - Programming (Mathematics) - 36 pages
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. (kr).
5 pages matching ordinary ceiling points in this book
Results 1-3 of 5
What people are saying - Write a review
We haven't found any reviews in the usual places.
1-ceiling 1-ceiling point algorithm all-integer vertices Assume ceiling point condition cone C2 constraint constraints binding contradicting the assumption contradicting the optimality convex hull coordinate axis CP(FR CP(i d-CP(FR DUHC[y edge of UHC[x edges of C2 empty extreme points Feasibility cone C2 feasible ceiling point feasible integer solutions feasible l-CP(i feasible region feasible solutions Figure 3(a function of LPr functional constraint Hillier hull of feasible hyperplane hypersphere infeasible Integer Linear Programming integer points Integer Programming integer vector ith constraint LHS(lb linear programming relaxation non-empty and bounded nonnegativity constraint objective function value Operations Research optimal solution Optimality cone C3 ordinary ceiling points point with respect possesses an optimal Proof Role of Ceiling Saltzman and Frederick Search Constraints set of feasible set of l-CP(FP)'s shown in Figure single constraint solution for ILP solve ILP STANFORD UNIVERSITY strictly better subset Suppose the set Theorem unbounded unit hypercube variables western edge