Accession Number : ADA625107


Title :   Constraint Optimization Literature Review


Descriptive Note : Final rept. Jun-Dec 2013


Corporate Author : ORSA CORP ABERDEEN MD


Personal Author(s) : Schwartz, Peter J


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a625107.pdf


Report Date : Nov 2015


Pagination or Media Count : 44


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.


Descriptors :   *OPTIMIZATION , ALGORITHMS , HIGH PERFORMANCE COMPUTING , MATHEMATICS , POLYNOMIALS


Subject Categories : Operations Research


Distribution Statement : APPROVED FOR PUBLIC RELEASE