The Accelerated Bound-and-Scan Algorithm for Integer Programming

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 15, 1972
Accession Number
AD0743128

Entities

People

  • Bruce H. Faaland
  • Frederick S. Hiller

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Coefficients
  • Computer Programming
  • Computers
  • Dacron
  • Elimination
  • Equations
  • Integer Programming
  • Linear Programming
  • Military Research
  • Operations Research
  • Pets
  • Probability
  • Random Variables
  • Scanning
  • Simplex Method
  • Standards

Fields of Study

  • Computer science

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Software Verification and Validation.