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) : Jeroslow,R. J.

Report Date : MAR 1973

Pagination or Media Count : 10

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 :   *Linear programming, Algorithms, Computations

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE