Combinatorial optimization

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

Informal definition

As the name suggests, it comes in the combinatorial optimization aim is to construct from a large set of discrete elements ( objects, places ) a subset that certain constraints corresponding to and with respect to a cost function is optimal (minimum weight, shortest routes ... ). Such questions play an important role in practice. The optimal path planning of a drill on a circuit board, the cost-optimal allocation of machines or the best possible route planning are all representatives of this class of problems.

Formal definition

An instance of a combinatorial optimization problem is a pair in which the amount referred to a countable set of all possible solutions and to feature a picture shows that assigns to each element of an objective function value (cost, profit, ... ). The goal is to find a globally optimal solution, so that no exists with (for a minimization problem ).

Algorithms and Complexity

The problems which are being tackled in combinatorial optimization, are usually very difficult ( NP-hard ).

The algorithms to generate the solutions therefore usually try to restrict the search space. Representatives of these algorithms, for example, branch- and-bound or branch-and -cut, which produce precise, guarantees optimal solutions. For this, the problem is formulated as an integer optimization problem in which the assignment of decision variables then decide whether certain elements belong to the solution or not.

Other algorithms use special knowledge of the problem structure, so-called heuristics or meta- heuristics. This includes, for example, local search with its forms Simulated cooling or Tabu Search. However, these methods can not guarantee that a globally optimal solution can be found mostly.

Known Issues

• The problem of the traveling salesman
• Spanning tree
• Knapsack problem
• Leveling of variable - weight products in the process of sorting and packing (Business )
• Tank problem ( bin packing )