A One Constraint, 149-Variable Zero-One Program Requiring Nine Million Years Computing Time by Branch-and-Bound.

Abstract

It is known to many researchers that, for most of the known enumerative-type algorithms some special problem can be constructed for which the given algorithm behave poorly. The paper gives one very simple class of one-constraint zero-one integer programs on which any branch-and-bound scheme, regardless of heuristics used to choose the next linear program, behaves exponentially badly, in that it requires at least square root of (2) sup (n-1) linear programs to complete computation, where n is the number of variables. In all programs of this class, the right hand side is the number n, and all other coefficients are no more than 2 in absolute value. The same class of problems causes many other enumerative-type algorithms to exhibit exponential computing time. (Author)

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1973
Accession Number
AD0773321

Entities

People

  • R. J. Jeroslow

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Coefficients
  • Computational Complexity
  • Computations
  • Evolutionary Algorithms
  • Heuristic Methods
  • Linear Programming
  • Mathematical Analysis
  • Mathematics
  • Numbers
  • Simplex Method
  • Square Roots

Fields of Study

  • Computer science

Readers

  • Approximation Theory.
  • Operations Research