Accession Number:

ADA202286

Title:

An Exact Ceiling Point Algorithm for General Integer Linear Programming

Descriptive Note:

Technical rept.

Corporate Author:

STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB

Report Date:

1988-11-01

Pagination or Media Count:

81.0

Abstract:

This report describes an exact algorithm for the pure, general integer linear programming problem ILP. Common applications of this model occur in capital budgeting project selection, resource allocation and fixed- charge plant location problems. The central theme of our algorithm is to enumerate a subset of all solutions called feasible 1-ceiling points. A feasible 1-ceiling point may be thought of as an integer solution lying on or near the boundary of the feasible region for the LP-relaxation associated with ILP. Precise definitions of 1-ceiling points and the role they play in an integer linear program are presented in a recent report by the authors. One key theorem therein demonstrates that all optimal solutions for an ILP whose feasible region is non-empty and bounded are feasible 1-ceiling points. Consequently, such a problem may be solved by enumerating just its feasible 1-ceiling points. Our approach is to implicitly enumerate 1-ceiling points with respect to one constraint at a time while simultaneously considering feasibility. Computational results from applying this incumbent-improving Exact Ceiling Point Algorithm to 48 test problems taken from the literature indicate that this enumeration scheme may hold potential as a practical approach for solving problems with certain types of structure.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE