Constraint Optimization Literature Review
Final rept. Jun-Dec 2013
ORSA CORP ABERDEEN MD
Pagination or Media Count:
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.
- Operations Research