Combinatorial optimization

In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.

It has important applications in several fields, including artificial intelligence, machine learning, auction theory, software engineering, VLSI, applied mathematics and theoretical computer science.

Basic applications of combinatorial optimization include, but are not limited to: There is a large amount of literature on polynomial-time algorithms for certain special classes of discrete optimization.

A considerable amount of it is unified by the theory of linear programming.

Some examples of combinatorial optimization problems that are covered by this framework are shortest paths and shortest-path trees, flows and circulations, spanning trees, matching, and matroid problems.

For NP-complete discrete optimization problems, current research literature includes the following topics: Combinatorial optimization problems can be viewed as searching for the best element of some set of discrete items; therefore, in principle, any sort of search algorithm or metaheuristic can be used to solve them.

Widely applicable approaches include branch-and-bound (an exact algorithm which can be stopped at any point in time to serve as heuristic), branch-and-cut (uses linear optimisation to generate bounds), dynamic programming (a recursive solution construction with limited search window) and tabu search (a greedy-type swapping algorithm).

The usual decision version is then an inadequate definition of the problem since it only specifies acceptable solutions.

[8] Note that the below referred polynomials are functions of the size of the respective functions' inputs, not the size of some implicit set of input instances.

A problem is additionally called a P-optimization (PO) problem, if there exists an algorithm which finds optimal solutions in polynomial time.

Often, when dealing with the class NPO, one is interested in optimization problems for which the decision versions are NP-complete.

Due to the connection between approximation algorithms and computational optimization problems, reductions which preserve approximation in some respect are for this subject preferred than the usual Turing and Karp reductions.

For this reason, optimization problems with NP-complete decision versions are not necessarily called NPO-complete.