A small overview of principles used in various combinatorial optimisation algorithms
Roland Pihlakas, 21. November 2017
Pushpak Bhandari, https://unsplash.com/photos/9s5D3NaWlIk
Abstract.
An introduction to combinatorial optimisation strategies that I have used the most during my experiments and also in my work.
Introduction.
Various combinatorial optimisation problems can be described by the following properties:
First — concepts. I will use two main concepts:
- Slot — represents, for example, “a square on the puzzle board”, “a potential path leg (edge) in a graph”, “a task at a particular time and place that needs an employee to be assigned to”, etc.
- Element — represents, for example “a piece in a puzzle (to be put into a square on the puzzle board)”, “selected path leg in a graph”, “a particular employee working with a selected task at a particular time at a particular place”, etc.
The properties of problems and optimisation criteria (this list is of course not conclusive):
- Is the ordering of elements’ assignments to slots important (regarding a particular optimisation criteria or rule)?
For example:
A) In the case of a travelling salesman, the sequence of cities to visit is important.
B) In the case of a 1D knapsack problem, the sequence of items is not important. - Is the element’s assignment relation to particular slots important (regarding a particular optimisation criteria or rule)?
For example:
A) Element-to-slot associations are important, for example, in the case of puzzle problems with fixed hint pieces or border patterns, and also for workforce planning (due to employee competence requirements for different tasks, or due to employee preferences, etc).
B) Element-to-slot associations are not important, for example, for the n-queens problem, for puzzles without fixed hint pieces or border patterns, and for workforce planning in case all employees are of the same competence. - Are element-to-element relations important? This is not quite the same as the travelling salesman case above, since in the current case not all elements need to have important relations.
For example:
A) Employees should have proper rest times in the(ir) schedule. In this case the total order is not important, but there are still constraints between certain individual assignments. - Can we consider the first and last slot as spatially nearby (in case the elements’ order or element-to-element relations apply).
For example:
A) The travelling salesman, in case the salesman needs to return to the source city. - Are there more elements than slots?
For example:
A) N-queens with unlimited number of queens.
B) Workforce planning with more available employees than is strictly necessary. - Do we need to group the elements into classes so that we can compute sums over the elements in that class? For example, do we need rule violations to be computed per class and then should they be equalised over classes?
For example:
A) In workforce planning there are multiple employees, each of them with many work schedule assignments. Each of these employees may end up having some soft or hard rules violated by these assignments (soft rules are preferences, hard rules are laws and agreements). The violations might be equalised over employees so that employees get a similar amount of violations.
B) Knapsack problem with multiple bins.
Based on the above properties a very efficient local-search based solver can be built for many combinatorial problems (though not for all).
Creating the algorithm.
“Local search” means starting from some partial or non-ideal solution and then modifying that solution step by step so that it becomes better. A local search can start from:
- An entirely empty solution by adding elements one by one to slots chosen by the algorithm (described below).
- From a randomly, analytically, or heuristically assigned initial solution, or from a non-ideal solution originating from another meta-heuristic — for example, from ant-colony, simulated annealing, monte-carlo etc approaches, or from non-ideal solution provided by method (1) above, then improving it with the algorithm described below.
The heuristics for local search can be grouped into two groups, working in turns:
- Method for deciding which element or slot to choose next (for assignment or for modification, depending on whether the element or slot is currently assigned).
- Method for deciding how to assign this element or slot (so given an element, which slot would be heuristically the best assignment considering other data in the current state of the solution, or given a slot, which element would be heuristically best considering the current state).
NB! The heuristically best elements or slots at turn (2) above do not have to be unassigned at the moment they are chosen. In case they are already assigned, a “chain reaction” will occur, where the already existing assignment is removed and then a new assignment is found for the now-unassigned element or slot. Which may in turn cause a third step in the chain etc. For most of the combinatorial problems the chains stay one-dimensional in the sense that each step of the chain generates only one problem in the solution that needs immediate fixing in the next step of the chain. The remaining newly generated problems can usually be solved later when the current chain is complete.
The “links” in the chain of assignments and un-assignments are ultimately evaluated together. When the whole chain does not provide enough improvement (which can also be decided stochastically) to the previous state of solution, the whole chain is abandoned, the moves rolled back, and a new chain is generated by heuristics.
The heuristics for choosing elements or slots, and then for choosing the heuristically best assignment for them can be derived from the questions on the first page.
So the local search can generate multiple-step rearrangements in order to fix or improve each single issue at the current state of partial solution.
Each step sequence is produced based on “understanding” what needs to be changed and how, and also which subgoals need to be solved in order to solve the initially selected problem without creating too many new complications.
The length of chains can vary depending on various rules. The simplest rule would be to start with a limited chain length of some small constant. In the case the progress is slow, the solver’s search depth will be increased for the time being and longer chain lengths will be considered.
In more detail, the local search improves the initial solution by using more detailed insights into which assignments and relations are good or bad in the current solution, and why, based on the questions listed in the beginning of the article. For example:
- Where are the conflicting nearby (not necessarily adjacent) assignments, and which assignments would fit better (element-to-element relations)?
- Where are the bad and good (or better) assignments (slot to element relations)?
- Do some sums over properties of the assignments over- or undershoot their destinations (grouping elements into classes)?
Such heuristics can work in parallel and their results can be summed.
This has the most important property of such an approach: it enables using any number of different weighted rules and optimisation criteria in parallel, and any number of new rules or criteria can be added or disabled in the future without modifying the code for existing rules and optimisation criteria.
Various interesting data structures exist (for example, monoid trees) that enable very efficient computation of the above mentioned heuristics, and also very efficient re-scoring of the whole solution after local changes.
Also there are data structures that enable modifying the state of the solution so that the modifications can be efficiently rolled back if necessary.
For various optimisation criteria it is also possible to compute the upper bound of potential improvements, considering the current non-ideal solution and the progress so far while using the current algorithm configuration. So if the upper bound of possible improvements happens to be too low (according to various possible criteria, for example, by comparing to the progress of other parallel solvers), the search can be abandoned early on and restarted either on the current non-ideal solution using a bigger local search depth, or from an entirely new non-ideal solution. This provides the capability to jump out of a too steep local minima early on.
I have efficiently run algorithms based on such principles on a few cores and also in more massive systems, including using MPI based parallel computing.
