Combinatorial optimization

What is combinatorial optimization?

Combinatorial optimization is a branch of mathematical optimization that has applications in artificial intelligence, theoretical computer science, applied mathematics, machine learning, software engineering, and many other domains.

It is related to computational complexity theory, algorithm theory, and operations research.

It is the process of identifying maxima or minima for an objective function that has a discreet domain with a large configuration space.

Combinatorial optimization refers mainly to the methods employed to solve optimization problems and generally does not offer guidelines on how to convert real-world problems into abstract mathematical questions, and vice versa.

The whole field of combinatorial optimization pretty much has its origin in graph theoretic concerns such as edge colorings in undirected graphs and matchings in bipartite graphs.

A lot of the early progress in combinatorial optimization is because of theorems in graph theory as well as their duals.

When linear programming first came into being, combinatorial optimization started getting applied on problems like assignment, maximal flow, and transportation.

Today, combinatorial optimization is especially used to study algorithms, particularly the ones used in artificial intelligence, machine learning, and operations research.

‍

What is combinatorial problem?

A combinatorial optimization problem A is a quadruple (I, f, m, g)

Here,

I is a set of instances.

If an instance x ∈ I, then f(x) is the finite set of feasible solutions.

If y is a feasible solution for instance x, then m(x,y) signifies the measure of y. This tends to be a positive real.

The goal function g is either min or max.

The goal is to find an optimal or feasible solution y for instance x with

m(x,y) = g{m(x,y’) | y’ ∈  f(x)}

Every combinatorial optimization problem has a decision problem that corresponds to it and asks if there is a feasible solution for some particular measure m₀.

‍

What is combinatorial optimization used for?

The field of combinatorial optimization is at the leading edge of combinatorics and theoretical computer science. Combinatorial optimization is essentially used for solving discrete optimization problems by employing combinatorial techniques. These discrete optimization problems are basically problems that aim to figure out the best solution that is possible from a finite set of possibilities.

In computer science, combinatorial optimization is used to enhance algorithms by employing mathematical methods for the purpose of reducing the size of the set of solutions available, or even speeding up the search itself.

From the combinatorics point of view, combinatorial optimization is used for the purpose of interpreting particularly complex questions in terms of a finite set of objects about which quite a lot is already known, like sets, graphs, polytopes, and matroids.

What are combinatorial optimization problems?

In practice, combinatorial optimization problems (COP) usually integrate two or more subproblems.

Some examples of combinatorial optimization problems are:

Traveling Salesman Problem (TSP)

This is probably the most famous combinatorial optimization problem. It involves a complete graph on n vertices, with a weight function defined on the edges. The aim of this problem is to construct a tour or a circuit that passes through every vertex that has the minimum total weight.

The TSP is considered to be a hard combinatorial optimization problem.

Cutting Stock Problem

The one-dimensional cutting stock problem seeks to find out how to cut rolls of paper of fixed-width into customer orders for smaller widths to minimize wastage.

It can be formulated as an integer linear programming problem and can be solved with column generation.

Packing Problems

These problems can be considered to be complementary to cutting problems. They seek to fill a large space with smaller shapes in the most profitable manner.

Geometric packing problems arise in one-dimension, two-dimensions, and three dimensions.

Minimum Spanning Tree

The Minimum Spanning Tree problem (MST problem) is also a famous combinatorial problem. This is an easy combinatorial optimization problem (COP). 

On a connected, undirected graph, a spanning tree is a subgraph that is a tree and connects all the vertices. Weights are assigned to every edge, and a minimum spanning tree is a spanning tree that has a weight that is less than or equal to the weight of every other spanning tree.

The Marriage Problem

In its traditional formulation, the marriage problem aims to identify a set of n couples from a set of n men and n women so that every couple is made up of one man and one woman and no two people would prefer each other in comparison to their own respective partners. Every woman has a hierarchy of preferences regarding men and every man has a hierarchy of preferences regarding women.

When there is a set of preferences for the n men and n women, will there be a solution that could exist? How do you find that soution?

There will always be an existing solution, this is known as Hall’s Marriage Theorem. This kind of problem is known as a matching problem. It’s one of the few central types of problems for which combinatorial optimization is used.

‍

What are combinatorial algorithms?

Two of the algorithms that are used to solve combinatorial optimization problems are:

• Prim’s algorithm
• Kruskal’s algorithm
  

Prim’s algorithm offers you a way to solve one of the simplest combinatorial optimization problems. It helps you find a minimum spanning tree on a (weighted) graph.

It leverages the the fact that tress are minimally connected graphs and that graphs have a matroid structure. This means that they are susceptible to particular implementations of the greedy algorithm. Here’s how it works:

• Pick a vertex on the graph
• Among the edges that connect the picked vertices to the rest of the graph, choose the edge with the least weight (and the associated vertex).
• Now you have to keep performing the second step till every one of the vertices are in the tree.
  

Kruskal’s deals with the same problem by leveraging the the fact that trees are maximally acyclic graphs. Here’s how it works:

• You need to order the edges starting with minimal weight and going towards maximal weight, beginning with an empty set of edges.
• Then you have to add the edge of minimal weight which does not cause the set to contain any cycles.
• Then you need to keep performing the second step till the set determines a spanning tree.