Accession Number:

AD0743128

Title:

The Accelerated Bound-and-Scan Algorithm for Integer Programming

Descriptive Note:

Technical rept.

Corporate Author:

STANFORD UNIV CA DEPT OF OPERATIONS RESEARCH

Report Date:

1972-05-15

Pagination or Media Count:

39.0

Abstract:

This paper presents a new implicit enumeration algorithm for solving the pure integer linear programming problem. The theory of equivalent integer programming problems is first used to reformulate the problem. A technique, originally used with particular success in the bound-and-scan algorithm to deal with only a subset of the variables, is extended to all of the variables in the restructured problem. In addition to the resulting basic enumeration scheme, the algorithm includes a scanning procedure and a method for identifying constraints which become redundant during the course of the algorithm. Computational experience on standard test problems is reported.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE