A One Constraint, 149-Variable Zero-One Program Requiring Nine Million Years Computing Time by Branch-and-Bound.
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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
- Operations Research