Combinatorial optimization
Combinatorial optimization is a branch of (mathematical) optimization that seeks an optimal solution from a finite set of alternatives defined by prescribed constraints and the use of discrete variables. For this reason, it is often also referred to as discrete optimization.
It originally emerged to solve problems arising in graph theory and was based on theoretical results from this field. Later, formulations and algorithms from linear programming found their application in it. Combinatorial optimization is closely related to operations research and integer linear programming, and it is also connected to theoretical computer science, particularly algorithm theory and computational complexity theory.
Typical problems include, for example, minimum spanning tree problems, optimal network flows, the knapsack problem, the traveling salesman problem (TSP), cutting problems, scheduling problems, and others. For some of these problems, fast exact algorithms are known, while others have exponential complexity and belong to the class of NP-complete problems. Therefore, the field also deals with approximation algorithms, often referred to as heuristics.