Estimates and Bounds on Computational Effort in the Accelerated and Bound-and-Scan Algorithm
Bruce Faaland · Defense Technical Information Center (DTIC) · 1972
Methods for obtaining estimates and bounds on computational effort in the Accelerated bound-and-scan algorithm are presented. The basic tools of analysis used are various results from the theory of partitions of numbers, and central-limit theorem, and geometric interpretations of the algorithm. The results of the analysis are used to provide partial answers to questions such as (a) What is the greatest amount of time the algorithm could require to solve a given problem. (b) What is the expected computation time. (c) How should the variables and constraints be ordered. (d) How does the computation time depend on the number of variables. and (E) How is the computation time affected by the quality of the starting solution.