<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 are combinatorial optimization problems?",
   "acceptedAnswer": {
     "@type": "Answer",
     "text": "1. Traveling Salesman Problem (TSP).
2. Cutting Stock Problem.
3. Packing Problems.
4. Minimum Spanning Tree."
   }
 }]
}
</script>

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.

What is the formal definition of a 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 are combinatorial optimization problems?

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

Some examples of combinatorial optimization problems are:

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


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


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


4. Minimum Spanning Tree

The Minimum Spanning Tree problem (MST problem) is also a famous combinatorial problem. This is an easy 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.


Thanks for reading! We hope you found this helpful.

Ready to level-up your business? Click here.

About Engati

Engati powers 45,000+ chatbot & live chat solutions in 50+ languages across the world.

We aim to empower you to create the best customer experiences you could imagine. 

So, are you ready to create unbelievably smooth experiences?

Check us out!

Combinatorial optimization

October 14, 2020

Table of contents

Key takeawaysCollaboration platforms are essential to the new way of workingEmployees prefer engati over emailEmployees play a growing part in software purchasing decisionsThe future of work is collaborativeMethodology

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.

What is the formal definition of a 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 are combinatorial optimization problems?

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

Some examples of combinatorial optimization problems are:

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


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


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


4. Minimum Spanning Tree

The Minimum Spanning Tree problem (MST problem) is also a famous combinatorial problem. This is an easy 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.


Thanks for reading! We hope you found this helpful.

Ready to level-up your business? Click here.

Share

Continue Reading