Combinatorial optimization

Table of contents

Automate your business at $5/day with Engati

REQUEST A DEMO
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.

combinatorial optimization
Source: Wikipedia

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?

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.
Close Icon
Request a Demo!
Get started on Engati with the help of a personalised demo.
Thanks for the information.
We will be shortly getting in touch with you.
Oops! something went wrong!
For any query reach out to us on contact@engati.com
Close Icon
Congratulations! Your demo is recorded.

Select an option on how Engati can help you.

I am looking for a conversational AI engagement solution for the web and other channels.

I would like for a conversational AI engagement solution for WhatsApp as the primary channel

I am an e-commerce store with Shopify. I am looking for a conversational AI engagement solution for my business

I am looking to partner with Engati to build conversational AI solutions for other businesses

continue
Finish
Close Icon
You're a step away from building your Al chatbot

How many customers do you expect to engage in a month?

Less Than 2000

2000-5000

More than 5000

Finish
Close Icon
Thanks for the information.

We will be shortly getting in touch with you.

Close Icon

Contact Us

Please fill in your details and we will contact you shortly.

Thanks for the information.
We will be shortly getting in touch with you.
Oops! Looks like there is a problem.
Never mind, drop us a mail at contact@engati.com

<script type="application/ld+json">
{
 "@context": "https://schema.org",
 "@type": "FAQPage",
 "mainEntity": [{
   "@type": "Question",
   "name": "What is combinatorial optimization?",
   "acceptedAnswer": {
     "@type": "Answer",
     "text": "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."
   }
 },{
   "@type": "Question",
   "name": "What is combinatorial optimization used for?",
   "acceptedAnswer": {
     "@type": "Answer",
     "text": "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."
   }
 },{
   "@type": "Question",
   "name": "What are combinatorial optimization problems?",
   "acceptedAnswer": {
     "@type": "Answer",
     "text": "1. Traveling Salesman Problem (TSP)
2. Cutting Stock Problem
3. Packing Problems
4. Minimum Spanning Tree
5. The Marriage Problem"
   }
 }]
}
</script>