What is Combinatorial Optimization?
Combinatorial optimization is a class of methods to find an optimal object from a finite set of objects when an exhaustive search is not feasible. These optimization steps are the building blocks of most AI algorithms, regardless of the program’s ultimate function. This entire approach of optimizing outcomes is often referred to as “heuristic programming” in machine learning.
How is Combinatorial Optimization Used?
While there are countless optimization problems and solutions, some of the most common applications include:
- Shortest Path Problems - Finding a path between two vertices or nodes so that the sum of the weights of its constituent edges are minimized.
- Transportation Networks – Determining the most efficient flows or circulation across any form of network.
- Spanning Trees – Improve backup links and remove logic loops in any graphically represented problem.
- Matching – Matching graphs without common vertices.
- Matroid Problems
– Establishes linear independence in vector spaces.
