Combinatorial Optimization

Combinatorial optimization is a branch of discrete mathematics and plays an important role in many fields including operations research , computer science , artificial intelligence, and engineering .

Informal definition

As the name suggests, combinatorial optimization is about constructing a subset from a large amount of discrete elements (objects, locations) that corresponds to certain constraints and is optimal with regard to a cost function (smallest weight, shortest distances, ...) . Such questions play a major role in practice. The optimal route planning of a drill on a circuit board, the cost-optimal occupancy of machines or the cheapest possible route planning are all representatives of this problem class.

Formal definition

An instance of a combinatorial optimization problem is a pair in which the set denotes a countable set of all possible solutions and the function represents a mapping that assigns an objective function value (cost, profit, ...) to each element . The goal is a globally optimal solution to be found, so no to exist (for a minimization problem). ${\displaystyle (L,f)}$ ${\displaystyle L}$ ${\displaystyle f}$ ${\displaystyle f\colon L\rightarrow \mathbb {R} }$ ${\displaystyle L}$ ${\displaystyle i\in L}$ ${\displaystyle u\in L}$ ${\displaystyle f(u)<f(i)}$

Algorithms and Complexity

The problems that one deals with in combinatorial optimization are usually very difficult ( NP-difficult ).

The algorithms that are supposed to generate the solutions therefore usually try to limit the search space. Representatives of these algorithms are, for example, branch-and-bound or branch-and-cut , which generate exact, guaranteed optimal solutions. For this, the problem is formulated as an integer optimization problem, in which the assignment of decision variables then decides whether certain elements belong to the solution or not.

Other algorithms use special knowledge about the problem structure, so-called heuristics or meta-heuristics . This includes B. the local search with its characteristics simulated cooling or taboo search . However, these procedures usually cannot guarantee that a globally optimal solution can be found.

known problems

• The traveling salesman problem
• Spanning tree
• Backpack problem
• Equalization of variable-weight products in the process of sorting and packaging (business administration)
• Container problem (bin packing)

literature

• William J. Cook , William H. Cunningham, William R. Pulleyblank, Alexander Schrijver : Combinatorial Optimization . 1st edition. John Wiley & Sons, 1997, ISBN 047155894X .
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger: A compendium of NP optimization problems .
• Bernhard Korte , Jens Vygen : Combinatorial Optimization: Theory and Algorithms. 2nd Edition. Springer Spectrum, Berlin 2012, ISBN 978-3-642-25400-0 .
• Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization: Algorithms and Complexity . Dover Publications Inc., 1998, ISBN 0486402584 .
• Eugene Lawler : Combinatorial Optimization: Networks and Matroids , Oxford University Press 1995 (first 1976)
• Alexander Schrijver : Combinatorial optimization - polyhedra and efficiency , 3 volumes, Springer 2003