Constraint Optimization Literature Review

Report No. ARL-CR-0787
Authors: Peter J Schwartz
Date/Pages: November 2015; 44 pages
Abstract: The Constraint Optimization Problem (COP) is a commonly used mathematical formalism that can express many real-world situations. When the COP contains discrete variables, however, the number of combinations of variable assignments to consider is exponential in the number of variables. For example, adding just 20 binary variables to a COP multiplies the number of combinations to consider by over one million. This means that even if standard hardware and software efficiency techniques can provide orders of magnitude in increased speed, they can become quickly overwhelmed as problems become larger. A variety of techniques have been developed to address the complexity of COPs. Unfortunately, the COP is nondeterministic polynomial time hard (NP-hard) in general, meaning that for any algorithm there exists a problem instance for which the runtime is exponential in the size of the problem input. This report reviews the literature on COPs.
Distribution: Approved for public release
  Download Report ( 0.420 MBytes )
If you are visually impaired or need a physical copy of this report, please visit and contact DTIC.

Last Update / Reviewed: November 1, 2015