Estimates and Bounds on Computational Effort in the Accelerated and Bound-and-Scan Algorithm

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 15, 1972
Accession Number
AD0743129

Entities

People

  • Bruce H. Faaland

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Coefficients
  • Computations
  • Computer Programming
  • Computer Programs
  • Contractors
  • Contracts
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Normal Distribution
  • Operations Research
  • Probability
  • Random Variables
  • Stochastic Processes
  • United States Government

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Statistical inference.
  • Systems Analysis and Design