(definition)
Definition: A computational problem in which the object is to find the best of all possible solutions. More formally, find a solution in the feasible region which has the minimum (or maximum) value of the objective function.
See also decision problem, optimal solution, optimal value, geometric optimization problem, witness, local optimum, global optimum, Classical optimization problems: bin packing problem, knapsack problem, cutting stock problem, Chinese postman problem, traveling salesman, vehicle routing problem, prisoner's dilemma, Solution methods: dynamic programming, metaheuristic, relaxation, simulated annealing.
Note: An optimization problem asks, what is the best solution? A decision problem asks, is there a solution with a certain characteristic? For instance, the traveling salesman problem is an optimization problem, while the corresponding decision problem asks if there is a Hamiltonian cycle with a cost less than some fixed amount k.
From Algorithms and Theory of Computation Handbook, pages 29-20 and 34-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 10 January 2005.
HTML page formatted Mon Sep 11 09:46:05 2006.
Cite this as:
Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "optimization problem", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 10 January 2005. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/optimization.html
