Constraint Optimization Literature Review

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 2015
Accession Number
ADA625107

Entities

People

  • Peter J. Schwartz

Tags

Communities of Interest

  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Evolutionary Algorithms
  • Genetic Algorithms
  • Literature Surveys
  • Mathematics
  • Natural Languages
  • Optimization
  • Polynomials
  • Probability
  • Real Numbers
  • Standards
  • Theoretical Computer Science

Readers

  • Computational Modeling and Simulation
  • Mathematical Modeling and Probability Theory.
  • Parallel and Distributed Computing.