Optimization problem

In an optimization problem, a solution space ( set of possible solutions) and an evaluation function are (also objective or fitness function) given. One wants to find a solution with the largest possible value, or make statements about the values ​​of the solutions.

In this case, would be in front of a maximization problem, in a minimization problem solutions are sought with as small, but this case can be explained by simple negation of the previous one.

There are three problems:

• Decision-making problems in which, in addition, a limit value is given, and to be determined, whether there is a with.
• Actual optimization problems where one wishes to know the value of the best solution, ie.
• Search problems in which an optimal solution is searched for ( ), or a solution with a given minimum quality, ie with a. Or you just want the best possible solution, see ( approximation).

In theoretical computer science is meant by optimization problem is usually a real optimization problem, ie one in which only the best value and not the solution itself is searched. Also, one usually considers the special case of a discrete valuation function, as this usually does not make a significant difference and you can handle real numbers less well, for example, approximated as floating point numbers.

Mostly you look in theoretical computer science but decision problems. For an optimization problem can easily generate a decision problem, we add the limit or to issue position. Conversely, one can show for most practically interesting problems that one approach for the decision problem can be modified to a solution of the corresponding search or optimization problem, which is not critical needs more computing time or storage space.

In practical applications one usually has to do with search problems, because the value of an optimal solution without knowledge of good is this solution usually nothing. An algorithm solving, an optimization problem, called optimization algorithm. Analogously, speaks at the minimization and maximization problem in more detail by the minimization or maximization algorithm. An algorithm which solves an optimization problem approximately, called approximation algorithm.