DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click

HERE to register or log in.

# 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.

# Distribution Statement:

## APPROVED FOR PUBLIC RELEASE

#