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