Combinatorial Optimization Problems— Before Selecting the Optimization Algorithm
Combinatorial Optimization (CO) aspires to understand the behavior and provide efficient solutions to some of the most challenging problems tightly associated with a multitude of industry operations. However, the inherent combinatorial nature of such problems is the main obstacle in developing appropriate means for tackling them.
This story is a part of a series meant to serve as a brief introduction to Combinatorial Optimization Problems (COPs), their wide application and ways to efficiently approach them. By revealing the intractability many COPs are characterized by, one can easily grasp the reasoning behind the different techniques developed to address them.
In the following, we go through the solving of a simple COP. This is an essential part of this read that familiarizes us with common terms and notions within the discussed research domain. Moreover, I suggest a specific process that needs to be followed before solving a COP; the latter is logically unfolded while discussing the given problem. In this way, we will be ready to elaborate on three different families of algorithms — along with the pros and cons they entail — that can be utilized to efficiently tackle a COP (in a future post).
Despite you are the ones to determine the value of this story, I would be pleased if I manage to:
- motivate undecided graduates and restless professionals to get involved with a challenging domain that, quite well combines Mathematics and Computer Science (it is not only Machine Learning that does so😇) and/or,
- disclose or remind the existance of computationally intelligent tools that are more than appropriate and efficient to solve some of the most hard problems we later discuss upon and/or,
- encourage businesses and organizations, that might be unaware of this field of study and its tools, to model their problems as COPs and control the randomness within their algorithms in a sophisticated manner.
Solving a Combinatorial Optimization Problem
Whenever I am asked to solve a COP, I start by identifying and determining the following:
- Problem’s Parameters
- Solution Representation and Solution/Search Space
- Objective/Score Function
- Optimization Algorithm (discussed in a future story)
This is probably not the only way to go. However, it helps me structure my thought on the problem solving and that is why I suggest it.
Next, we use a simple COP instance to help us comprehend these terms.
Problem Definition
Assume three workers, namely A, B and C and three tasks, namely 1,2 and 3. Each worker must be assigned exactly one task (or each task must be completed by a single worker). In the figure that follows, the vectors below workers indicate the time interval they require to complete each one of the tasks. For instance, the vector [1,3,2] below worker B means that the latter requires 1 time unit, e.g., 1 hour, to complete task 1, 3 time units for the completion of task 2 and 2 time units for task 3. If we are asked to optimally map workers with tasks, we basically deal with an assignment problem, one of the most well-known COPs.
Problem’s Parameters
The first step we need to take is to write down the parameters of the problem, i.e., information that we can take for granted while designing our algorithmic solution. In our example, there are three workers, three tasks and the respective time requirements of each worker for the completion of each task.
It is convenient to denote these parameters in a strict mathematical way. This enables us to better understand our problem’s nature and avoid possible mistakes and misconceptions in future steps. Hence, let us denote with W={a,b,c} the set of workers, with T={1,2,3} the set of tasks and with cʷₜ the time required for a worker w ∈ W to complete a task t ∈ T. For instance, cᶜ₂= 3 since worker ‘c’ needs 3 time units for completing the second task. We have just identified and formulated our problem’s parameters.
Solution Representation
Let’s continue by figuring out a possible solution’s structure. That is, we have to jump several steps ahead and imagine what we expect as an answer to our problem. In our case, ending up with something like:
“workers ‘a’, ‘b’ and ‘c’ are assigned tasks 1, 3 and 2, respectively”
makes some sense. For brevity reasons, we can denote the same solution with the vector s=[1,3,2]. Essentially, we can agree that the first value in s represents the task assigned to worker ‘a’, the second value represents the task assigned to worker ‘b’ and the third value indicates the task assigned to worker ‘c’. In general, we can conceive a random solution:
s = [x,y,z]
where x,y and z ∈ T and x,y and z are different per two. With such a notation, we are consistent with the mathematical modelling we chose to follow and, more importantly, we can leverage mathematical tools during our attempt of addressing the assignment problem. The way we interpret s sums up our solution representation.
Search Space
Now, a solution s is expected to have a very specific structure. The vector s=[1,1,3], for instance, does not represent a valid solution to our problem since task 1 is assigned to both workers ‘a’ and ‘b’. The set that contains all the feasible solutions to our problem is called its search space and it is usually denoted by the Greek letter Ω. Formally, and according to the aforementioned definitions and notations, we can define the set Ω as:
to represent our search space. In our specific example, by enumerating all the permutations of the three tasks, we end up with 6 solutions included in Ω, as shown in the following figure:
That is, |Ω|= 6. Just for reference, with 50 workers and 50 tasks the respective assignment problem has |Ω|= 3.0414093e+64 possible solutions. In general, the typical assignment problem with n workers and n tasks yields a search space Ω with |Ω|=n!. This is indicative of how bad COPs scale with the problem’s size.
Objective/Score Function
We made clear the problem’s parameters, its solution representation and search space. Now it is time to define an objective/score function. This function will be used to evaluate the quality of a solution and, in extension, to find out if one solution is better from another. Since we are asked to find an optimal mapping between workers and tasks, it is important to ask ourselves what optimal means.
I intentionally omitted a detailed description of the problem’s objective in order to underline the uncertainties emerging during this step. So, are we asked to provide an optimal assignment from the workers’ or from their employer’ perspective, are we perhaps looking for a fair tradeoff or are there any additional objectives we can solve this problem with?
Essentially, we need to identify the objective before formulating the objective function (which makes a lot of sense). Let’s agree to solve this particular problem instance from an employer’s point of view, assuming that they pay their workers on an hourly rate. Therefore, the employer wants the three tasks completed by paying as few as possible. We receive this instruction and translate it into our objective; the minimization of the aggregated time for the completion of all tasks.
Therefore, the objective function, denoted by F, should receive a solution s=[x,y,z] as an argument and calculate its quality according to the following:
If s₁=[1,2,3] and s₂=[1,3,2], then:
and we can say that s₂ is better than s₁ (according to the objective we agreed upon).
That’s it, we have defined our objective function. It should be noticed once again that the definition of an objective/score function is one of the most, if not the most, difficult part in solving a COP. The main reason for that is the critical impact it has upon the process of exploring the search space since, to put it simply, it is the element that indicates whether the search process is doing well or badly. Moreover, there is a multitude of COPs that are formulated as multi-objective ones and, in addition, these objectives are usually contradictory. That is, the objective function needs to be designed to offer a fair tradeoff between the different objectives. Last, in real-life COPs, mathematical models (like the one we defined during this problem) are overwhelmed with parameters. Consequently, the objective function should be meticulously designed to successfully address the problem.
Optimization Algorithm (more on that in a future story)
It’s now time to select an optimization algorithm. This algorithm, in cooperation with the objective function, will determine to a great extend the final outcome.
But, let’s be honest, our search space consists of only 6 solutions. So, a brute-force algorithm, i.e., an exhaustive search of the this space, will not be too time consuming. Furthermore, it will guarantee an optimal solution. What would we do, though, if we were asked to solve the same problem with 50 workers? The same brute-force algorithm will have to evaluate 3.0414093e+64 different solutions. Even with current hardware standards, it would take ridiculously great computational effort for finding the optimal solution. This reveals the critical need for efficiently searching the solution spaces typically encountered in combinatorial optimization problems.
Some well-known techniques that we can leverage, namely Mathematical Programming, Heuristics and Meta-heuristics, will be discussed in future stories of this series. In addition, we will solve our problem and some larger instances of the same problem, with all three of them. This will help us realize their purpose and value. Finally, the next story will also contain a section with many well-known COPs and intriguing real-life applications each of them is associated with.
That was it for my first post in Medium. We have basically wrapped up the fundamental elements and notions involved in the process of solving a combinatorial optimization problem. Furthermore, we have noticed the limits of exhaustive search in vast solution spaces. Thus, we are ready to learn some computationally intelligent methods that can methodically manage such search spaces.
