ACFHarbinger
Back to Posts

Combinatorial Optimization: An Introduction

Date: 2024-10-28
Categories: ML, RL, CO

Introduction

To understand what exactly Combinatorial Optimization means, we can start by understanding each term of the expression: Combinatorial and Optimization.

Combinatorial Problems

CO deals with a class of problems called combinatorial problems. These are a particular case of discrete problems - which are problems where the variables are assumed to take discrete values - that involve finding a ordered or unordered grouping which, given a finite (and usually large) set of objects, satisfy a given set of conditions.

Combinations of elements from the set that may be encountered when trying to formulate a solution to a instance of this class of problems are called candidate or feasible solutions. Then, the solutions to this kind of problem are the feasible solutions that satisfy all required conditions.

The Traveling Salesman Problem

One of the most well known combinatorial problems is the Traveling Salesman Problem (TSP), where, given a graph $$G(N, E): N = \{v_1, ..., v_n\} \wedge E \subseteq \{(u, v): u, v \in N\},$$ the objective is to find shortest path possible $$s^* = \{\bar{s} \subseteq E: \forall s \subseteq E, \ \text{dist}(\bar{s}) \leq \text{dist}(s)\}$$ that visits each of the nodes $v \in N$ once and only once.

Optimization

Colloquially, optimization refers to the process of optimizing something, i.e., making it the best. What that means can vary, depending on the task at hand. For example, if we want to optimize the path to a location, then we may want to minimize the distance travelled or the travel time. However, if we want to optimize our wealth, than that may involve both maximizing our income and minimizing our expenses.

Formally, an optimization problem consists of:

  • Objective function $f(x): X \rightarrow Y$, which gives us the output we are trying to optimize;
  • Variable set $X = \{x_1, ..., x_n\}$, which are the inputs to $f(x)$;
  • A set of constraints $C = \{h_1(x), ..., h_n(x), g_1(x), ..., g_n(x)\}$, which are (equality $h_k(x)$ and inequality $g_k(x)$) equations that place limits on the values that some variables may take.

Mathematical Optimization

Mathematical Optimization is the branch of applied mathematics and numerical analysis that aims to develop and analyse algorithms that, given a objective function and a set of variables, seek to find the optimal solution(s) from the set containing all feasible solutions.

Mathematical Optimization deals with problems that can be categorized according to:

  • Whether the set of constraints is empty or not: Unlimited vs. Limited;
  • What values the variables can take: Discrete vs. Continuous;
  • Whether the problem state changes or not over time: Dynamic vs. Static;
  • Whether randomness is involved or not: Stochastic vs. Deterministic;
  • Whether equations map graphs to lines or to curves: Linear vs. Non-Linear.

Combinatorial Optimization (CO)

Now knowing the meaning of both Combinatorial (problems) and (mathematical) Optimization, we can define CO as a subfield of Discrete Optimization with the aim of developing algorithms that, given a finite set of discrete variables $X$ and constraints $C$, searches for the maxima or minima of an objective function $f(x)$.

Bibliography