A Bounding Technique for Integer Linear Programming with Binary Variables.

Abstract

We present a bounding technique for use in implicit enumeration algorithms for solving the integer linear programming problem with binary variables. The main assumptions used by this technique are the associated linear program, obtained by dropping the integrality constraints on the variables, possesses a unique optimal solution, this optimal solution is not binary, and a good feasible solution to the original problem is available. An alternative to the last assumption which is weaker is also presented. We show that joint bounds can be obtained on the values of a subset of the variables. In addition we given an efficient method to implement this bounding technique. Finally, a class of problems particularly well-suited to this bounding procedure is specified. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1979
Accession Number
ADA075575

Entities

People

  • Frederick Stanton Hillier
  • Nancy Eileen Jacqmin

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Evolutionary Algorithms
  • Heuristic Methods
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • New York
  • Notation
  • Operations Research
  • Universities

Fields of Study

  • Mathematics

Readers

  • Operations Research