An exact ceiling point algorithm for general integer linear programming
作者:
Robert M. Saltzman,
Frederick S. Hillier,
期刊:
Naval Research Logistics (NRL)
(WILEY Available online 1991)
卷期:
Volume 38,
issue 1
页码: 53-69
ISSN:0894-069X
年代: 1991
DOI:10.1002/1520-6750(199102)38:1<53::AID-NAV3220380107>3.0.CO;2-D
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractWe 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 t
点击下载:
PDF
(907KB)
返 回