Combinatorial Optimization

from Wikipedia, the free encyclopedia

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).

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