An exact ceiling point algorithm for general integer linear programming

Robert M. Saltzman and Frederick S. Hillier

Naval Research Logistics (NRL), 1991, vol. 38, issue 1, 53-69

Abstract: 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.

Date: 1991
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199102)38:13.0.CO;2-D

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:38:y:1991:i:1:p:53-69

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().