Premium
An exact ceiling point algorithm for general integer linear programming
Author(s) -
Saltzman Robert M.,
Hillier Frederick S.
Publication year - 1991
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199102)38:1<53::aid-nav3220380107>3.0.co;2-d
Subject(s) - integer programming , mathematics , integer (computer science) , backtracking , linear programming , mathematical optimization , ceiling (cloud) , bounded function , feasible region , algorithm , set (abstract data type) , relaxation (psychology) , linear programming relaxation , discrete mathematics , computer science , mathematical analysis , psychology , social psychology , physics , meteorology , programming language
We present an algorithm called the exact ceiling point algorithm (XCPA) for solving the pure, general integer linear programming problem (P). A recent report by the authors demonstrates that, if the set of feasible integer solutions for (P) is nonempty and bounded, all optimal solutions for (P) are “feasible 1‐ceiling points,” roughly, feasible integer solutions lying on or near the boundary of the feasible region for the LP‐relaxation associated with (P). Consequently, the XCPA solves (P) by implicitly enumerating only feasible 1‐ceiling points, making use of conditional bounds and “double backtracking.” We discuss the results of computational testing on a set of 48 problems taken from the literature.