
Accession Number : AD0773321
Title : A One Constraint, 149Variable ZeroOne Program Requiring Nine Million Years Computing Time by BranchandBound.
Descriptive Note : Research rept.,
Corporate Author : CARNEGIEMELLON 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 enumerativetype algorithms some special problem can be constructed for which the given algorithm behave poorly. The paper gives one very simple class of oneconstraint zeroone integer programs on which any branchandbound 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 (n1) 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 enumerativetype algorithms to exhibit exponential computing time. (Author)
Descriptors : *Linear programming, Algorithms, Computations
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE