Editing Combinatorial optimization (section)

==Methods==
There is a large amount of literature on [[polynomial-time algorithm]]s 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 path]]s and [[shortest-path tree]]s, [[flow network|flows and circulations]], [[spanning tree]]s, [[Matching (graph theory)|matching]], and [[matroid]] problems.

For [[NP-complete]] discrete optimization problems, current research literature includes the following topics:
* polynomial-time exactly solvable special cases of the problem at hand (e.g. [[fixed-parameter tractable]] problems)
* algorithms that perform well on "random" instances (e.g. for the [[Traveling salesman problem#Path length for random sets of points in a square|traveling salesman problem]])
* [[approximation algorithm]]s that run in polynomial time and find a solution that is close to optimal
* [[parameterized approximation algorithm]]s that run in [[Fixed-parameter tractability|FPT]] time and find a solution close to the optimum
* solving real-world instances that arise in practice and do not necessarily exhibit the worst-case behavior of in NP-complete problems (e.g. real-world TSP instances with tens of thousands of nodes<ref>{{harvnb|Cook|2016}}.</ref>).

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|branch-and-bound]] (an exact algorithm which can be stopped at any point in time to serve as heuristic), [[Branch and cut|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). However, generic search algorithms are not guaranteed to find an optimal solution first, nor are they guaranteed to run quickly (in polynomial time). Since some discrete optimization problems are [[NP-complete]], such as the traveling salesman (decision) problem,<ref>{{Cite web|title=Approximation-TSP|url=https://www.csd.uoc.gr/~hy583/papers/ch11.pdf|access-date=2022-02-17|archive-date=2022-03-01|archive-url=https://web.archive.org/web/20220301220806/https://www.csd.uoc.gr/~hy583/papers/ch11.pdf|url-status=live}}</ref> this is expected unless [[P=NP]].

For each combinatorial optimization problem, there is a corresponding [[decision problem]] that asks whether there is a feasible solution for some particular measure <math>m_0</math>. For example, if there is a [[Graph (discrete mathematics)|graph]] <math>G</math> which contains vertices <math>u</math> and <math>v</math>, an optimization problem might be "find a path from <math>u</math> to <math>v</math> that uses the fewest edges". This problem might have an answer of, say, 4. A corresponding decision problem would be "is there a path from <math>u</math> to <math>v</math> that uses 10 or fewer edges?" This problem can be answered with a simple 'yes' or 'no'.

The field of [[approximation algorithm]]s deals with algorithms to find near-optimal solutions to hard problems. The usual decision version is then an inadequate definition of the problem since it only specifies acceptable solutions. Even though we could introduce suitable decision problems, the problem is then more naturally characterized as an optimization problem.<ref name="Ausiello03">{{citation|last1=Ausiello|first1=Giorgio|title=Complexity and Approximation|year=2003|edition=Corrected|publisher=Springer|isbn=978-3-540-65431-5|display-authors=etal}}</ref>