# Accession Number:

## AD0773321

# Title:

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

# Descriptive Note:

## Research rept.,

# Corporate Author:

## CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

# Personal Author(s):

# Report Date:

## 1973-03-01

# Pagination or Media Count:

## 10.0

# 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

# Descriptors:

# Subject Categories:

- Operations Research