1.1.1. Linear programming relaxation

A simple way to approximately solving an ILP using mathematical programming techniques is as follows:

a) Relax the integer constraints [1.3], obtaining the following continuous linear programming problem in the standard form:

ILP-c is called the linear programming relaxation of ILP. It is the problem that arises by the replacement of the integer constraints [1.3] by weaker constraints that state that each variable x_j may assume any non-negative real value. As already mentioned, ILP-c can be solved by applying, for example, the simplex method [NEM 88]. Let x^∗ and be the optimal solution and the optimal objective function value for ILP-c, respectively. Similarly, let and be the optimal solution and the optimal objective function value for ILP, respectively.

Note that since X ⊂ P, we have:

therefore, is a lower bound for .

b) If , then x^∗ is also an optimal solution for ILP, i.e.

The procedure described above generally results in failure, as the optimal solution x^∗ to the linear programming relaxation typically does not have all integer components, except for in special cases such as problems whose formulation is characterized by a totally unimodular matrix A (see the transportation problem, the assignment problem and shortest path problems with non-negative arc lengths). Furthermore, it is wrong to try to obtain a solution x_I for ILP by rounding all non-integer components of x^∗, because it may lead to infeasible solutions, as shown in Example 1.1 below.

The corresponding feasible set X is depicted in Figure 1.3. Optimal solutions of its linear relaxation are all points , with and . Therefore, . Moreover, , since either x_I = (0, 2) or x_I = (1, 2).

Summarizing, the possible relations between ILP and its linear programming relaxation ILP-c are listed below and X^∗ and P^∗ denote the set of optimal solutions for ILP and ILP-c, respectively:

1. 1)
2. 2) (not possible in the case of combinatorial optimization problems);
3. 3) (lower bound);
4. 4) and
   
5. 5) X = ∅, but P^∗ = ∅, as for the problem described in Example 1.1, whose feasible set is depicted in Figure 1.3;
6. 6) X = ∅, but (not possible in the case of combinatorial optimization problems), as for the following problem, whose feasible set is shown in Figure 1.4:

Even if it almost always leads to failure while finding an optimal solution to ILP, linear programming relaxation is very useful in the context of many exact methods, as the lower bound that it provides avoids unnecessary explorations of portions of the feasible set X. This is the case with branch and bound (B&B) algorithms, as explained in section 1.1.2.1. Furthermore, linear programming relaxation is a standard technique for designing approximation algorithms for hard optimization problems [HOC 96, VAZ 01, WIL 11].

1.1.2. Cutting plane techniques

Historically, cutting plane techniques were the first algorithms developed for ILP that could be proved to converge in a finite number of steps. A cutting plane algorithm iteratively finds an optimal solution x^∗ following linear programming relaxation ILP-c. If x^∗ has at least one fractional component, a constraint satisfied by all integer solutions belonging to P, but not satisfied by x^∗, is identified. This constraint, which is violated by x^∗ and is added to the mathematical formulation of ILP-c, is called a cut. Formally, given x^∗ ∈ P, a ∈ ⁿ and b ∈ , the constraint a′x ≤ b is a cut if the following two conditions hold:

1. 1)
2. 2) a′x* > b.

Any cutting plane algorithm proceeds in iterations, as shown in Algorithm 1.1. Different cutting plane algorithms differ from each other in the method they adopt to identify the cut to be added to the current linear programming formulation ILP-c_k at each iteration. Since the number of iterations performed corresponds to the number of cuts needed, it is intuitive that stronger cuts imply fewer iterations. Unfortunately, most state-of-the-art cutting plane techniques can cut only small portions of P.

A feasible solution x ∈ ⁿ of a system Ax = b of equality constraints, A ∈ ^m×n and b ∈ ^m, is a basic solution if the n components of x can be partitioned into m non-negative basic variables and n − m non-basic variables in a way such that the m columns of A, corresponding to the basic variables, form a non-singular submatrix B (basis matrix), and the value of each non-basic variable is 0. In 1958, Gomory [GOM 58] proposed the most famous and well-known cutting plane method, whose basic idea is to exploit important information related to the m×m non-singular submatrix B of A corresponding to the m currently basic variables in the optimal continuous solution x^∗.

Let us consider a generic iteration k of Gomory’s algorithm. Suppose that the optimal continuous solution has at least one fractional component. Let x_h be such a variable. Clearly, x_h must be a basic variable and let us suppose it is carried in the t^th row of the optimal table. We can observe that the equation associated with the t^th row of the optimal table can be stated as follows:

where:

• – N is the set of non-basic variables;
• – ā_tj, j ∈ N are the elements of the t^th row of the optimal table corresponding to the columns of the non-basic variables;
• – is a fractional constant, by hypothesis.

Since x_j ≥ 0, for all j = 1, 2, … , n, we have:

Moreover, since x_j must assume an integer value, the following inequality holds:

[1.4]

The t^th row of the optimal table is referred to as the row generating the cut and inequality [1.4] is the cut that Gomory’s algorithm uses at each iteration, until it is not obtained in an optimal continuous solution . It can easily be proved that the cut [1.4] is still satisfied by all feasible integer solution, but violated by , since the current value of the h^th component of is , the components of corresponding to the non-basic variables are zero, and .

1.1.2.1. Branch and Bound

An alternative exact approach is B&B, which is an implicit enumeration technique because it can prove the optimality of a solution without explicitly visiting all valid solutions when it finishes. Almost always outperforming the cutting plane approach, it is a divide and conquer framework that addresses ILP by dividing it into a certain number of subproblems, which are “simpler” because they are smaller in size.

Given the following ILP:

with feasible set X₀ and optimal objective function value given by:

we obtain ILP₀ B&B partitions in a certain number of subproblems ILP₁, … , ILP_n0, whose totality represents ILP₀. Such a partition is obtained by partitioning X₀ into the subsets X₁, … , X_n0 such that:

• – for i = 1, … , n₀, X_i is the feasible set of subproblem ILP_i;
• – for i = 1, … , n₀, is the optimal objective function value of subproblem ILP_i;
• – .

Note that, since any feasible solution of ILP₀ is feasible for at least one subproblem among ILP₁, … , ILP_n0, it clearly results that:

Therefore, ILP₀ is solved by solving ILP₁, … , ILP_n0, i.e. for each ILP_i, i = 1, … , n₀. One of the three options given below will hold true:

• – an optimal solution to ILP_i is found; or
• – it can be proved that ILP_i is unfeasible (X_i = ∅); or
• – it can be proved that an optimal solution to ILP_i is not better than a known feasible solution to ILP₀ (if any).

Each ILP_i subproblem, i = 1, … , n₀, has the same characteristics and properties as ILP₀. Hence, the procedure described above can be applied to solve it, i.e. its feasible set X_i is partitioned and so on.

The whole process is usually represented dynamically by means of a decision tree, also called a branching tree (see Figure 1.5), where:

• – the choice of the term branching refers to the partitioning operation of X_i sets;
• – the choice of the classical terms used in graph and tree theory include:
  • - root node (corresponding to the original problem ILP₀),
  • - father and children nodes,
  • - leaves, each corresponding to some ILP_i subproblem, i > 0, still to be investigated.

It is easily understandable and intuitive that the criterion adopted to fragment every ILP_i (sub)problem, i = 0, 1, … , n₀, has a huge impact on the computational performance of a B&B algorithm. In the literature, several different criteria have been proposed to perform this task, each closely connected to some specific procedure, called a relaxation technique. Among the well-known relaxation techniques, those that ought to be mentioned are:

• – linear programming relaxation;
• – relaxation by elimination;
• – surrogate relaxation;
• – Lagrangian relaxation;
• – relaxation by decomposition.

The most frequently applied relaxation technique is linear programming relaxation. To understand the idea underlying this technique, let us consider ILP₀ with feasible set X₀ depicted in Figure 1.6. The optimal solution to its linear programming relaxation (with feasible set P₀) is , with . Clearly, in the optimal integer solution it must be either x₁ ≤ 1 or x₁ ≥ 2. Therefore, one can proceed by separately adding to the original integer formulation of ILP₀ the constraints x₁ ≤ 1 and x₁ ≥ 2, respectively. By adding constraint x₁ ≤ 1, the subproblem ILP _x1≤1 is generated, with the optimal solution . Similarly, by adding constraint x₁ ≥ 2, the subproblem ILP _x1≥2 is generated, with the optimal solution . In this way, ILP₀ is partitioned into the two subproblems ILP _x1≤1 and ILP _x1≥2, whose feasible sets (see Figure 1.7) are X₁ and X₂ such that X₁ ∪ X₂ = X₀ and . An optimal solution to ILP₀ is obtained with the best solution between and .

More generally, given ILP₀, one needs to solve its linear programming relaxation:

with feasible set P₀. Let be an optimal solution to ILP₀-c. If all components of are integer, then is an optimal solution to ILP₀. Otherwise, (see Figure 1.8) a fractional component is chosen and the following two subproblems are identified:

and

Identifying subproblems ILP₁ and ILP₂ starting from ILP₀ corresponds to performing a branching operation. Variable x_h is called the branching variable. Subproblems ILP₁ and ILP₂ are children of ILP₀ as they are obtained by adding the branching constraints and , respectively to the formulation of ILP₀.

Since ILP₁ and ILP₂ are still integer problems, they are approached with the same procedure, i.e. for each of them its linear relaxation is optimally solved and, if necessary, further branching operations are performed. Proceeding in this way, we obtain a succession of hierarchical subproblems that are more constrained and hence easier to solve. As already underlined, the whole process is represented dynamically by means of a decision tree, also called a branching tree, whose root node corresponds to the original problem, ILP₀. Any child node corresponds to the subproblem obtained by adding a branching constraint to the formulation of the problem corresponding to its father node.

Generally speaking, the constraints of any subproblem ILP_t corresponding to node t in the branching tree are the following ones:

1. 1) the constraints of the original problem, ILP₀;
2. 2) the branching constraints that label the unique path in the branching tree from the root node to node t (node t “inherits” the constraints of its ancestors).

In principle, the branching tree could represent all possible branching operations and, therefore, be a complete decision tree that enumerates all feasible solutions to ILP₀. Nevertheless, as explained briefly, thanks to the bounding criterion, entire portions of the feasible region X₀ that do not contain the optimal solution are not explored or, in other words, a certain number of feasible solutions are not generated, since they are not optimal.

Let us suppose that the B&B algorithm is evaluating subproblem ILP_t and let x_opt be the best current solution (incumbent solution) to ILP₀ (i.e. x_opt is an optimal solution to at least one subproblem, ILP_k, k > 0 and among those subproblems already investigated). Let z_opt = z(x_opt), where initially z_opt := +∞ and x_opt := ∅.

Recalling the possible relations existing between a linear integer program and its linear programming relaxation described in section 1.1.1, it is useless to operate a branch from ILP_t if any of the following three conditions holds:

1. 1) The linear programming relaxation ILP_t-c is infeasible (hence, ILP_t is infeasible as well). This happens when the constraints of the original problem, ILP₀, and the branching constraints from the root of the branching tree to node t are inconsistent;
2. 2) The optimal solution to linear programming relaxation ILP_t-c is integer. In this case, if necessary, x_opt and z_opt are updated.
3. 3) The optimal solution to linear programming relaxation ILP_t-c is not integer, but:

[1.5]

In the latter case, it is clearly useless to keep partitioning X_t. This is because none of the feasible integer solutions are better than the incumbent solution x_opt, since it always holds that . Inequality [1.5] is called the bounding criterion.

1.1.2.2. Choice of branching variable

Suppose that the B&B algorithm is investigating subproblem ILP_t and that a branching operation must be performed because none of the three conditions listed above is verified. Let be an optimal solution to ILP_t-c and suppose that it has at least two fractional components, i.e.

The most commonly used criteria adopted to choose the branching variable x_h are as follows:

1. 1) h is randomly selected from set F;
2. 2) (h is the minimum index in F);
3. 3) (h is the index in F corresponding to the minimum fractional value).

1.1.2.3. Generation/exploration of the branching tree

A further issue that still remains to be determined is the criterion for generating/exploring the branching tree. At each iteration, a B&B algorithm maintains and updates a list Q of live nodes in the branching tree, i.e. a list of the current leaves that correspond to the active subproblems:

Two main techniques are adopted to decide the next subproblem in Q to be investigated:

• – Depth first: recursively, starting from the last generated node t corresponding to subproblem ILP_t whose feasible region X_t must be partitioned, its left child is generated/explored, until node k corresponding to subproblem ILP_k is generated from which no branch is needed. In the latter case, backtracking is performed to the first active node j < k that has already been generated. Usually, set Q is implemented as a stack and the algorithm stops as soon as Q = ∅, i.e. when a backtrack to the root node must be performed.

This technique has the advantages of being relatively easier to implement and of keeping the number of active nodes low. Moreover, it produces feasible solutions rapidly, which means that good approximate solutions are obtained even when stopped rather early (e.g. in the case of the running time limit being reached). On the other hand, deep backtracks must often be performed.

• – Best bound first: at each iteration, the next active node to be considered is the node associated with subproblem ILP_t corresponding to the linear programming relaxation with the current best objective function value, i.e.

The algorithm stops as soon as Q = ∅. This technique has the advantage of generating a small number of nodes, but rarely goes to very deep levels in the branching tree.

1.1.3. General-purpose ILP solvers

The techniques described in the previous section, among others, are implemented as components of general-purpose ILP solvers that may be applied to any ILP. Examples of such ILP solvers include IBM ILOG CPLEX [IBM 16], Gurobi [GUR 15] and SCIP [ACH 09]. The advantage of these solvers is that they are implemented in an incredibly efficient way and they incorporate all cutting-edge technologies. However, for some CO problems it might be more efficient to develop a specific B&B algorithm, for example.

1.1.4. Dynamic programming

Dynamic programming is an algorithmic framework for solving CO problems. Similar to any divide and conquer scheme, it is based on the principle that it is possible to define an optimal solution to the original problem in terms of some combination of optimal solutions to its subproblems. Nevertheless, in contrast to the divide and conquer strategy, dynamic programming does not partition the problem into disjointed subproblems. It applies when the subproblems overlap, i.e. when subproblems share themselves. More formally, two subproblems (ILP_h) and (ILP_k) overlap if they can be divided into the following subproblems:

where (ILP_h) and (ILP_k) share at least one subproblem.

A CO ILP problem can be solved by the application of a dynamic programming algorithm if it exhibits the following two fundamental characteristics:

1. 1) ILP exhibits an optimal substructure, i.e. an optimal solution to ILP contains optimal solutions to its subproblems. This characteristic guarantees there is a formula that correctly expresses an optimal solution to ILP as combination of optimal solutions to its subproblems.
2. 2) ILP must be divisible into overlapping subproblems. From a computational point of view, any dynamic programming algorithm takes advantage of this characteristic. It solves each subproblem, ILP_l, only once and stores the optimal solution in a suitable data structure, typically a table. Afterwards, whenever the optimal solution to ILP_l is needed, this optimal solution is looked up in the data structure using constant time per lookup.

When designing a dynamic programming algorithm for a CO ILP problem, the following three steps need to be taken:

1. 1) Verify that ILP exhibits an optimal substructure.
2. 2) Recursively define the optimal objective function value as combination of the optimal objective function value of the subproblems (recurrence equation). In this step, it is essential to identify the elementary subproblems, which are those subproblems that are not divisible into further subproblems and thus are immediately solvable (initial conditions).
3. 3) Write an algorithm based on the recurrence equation and initial conditions stated in step 2.

1.2.1. Ant colony optimization

ACO [DOR 04] is a metaheuristic which was inspired by the observation of the shortest-path finding behavior of natural ant colonies. From a technical perspective, ACO algorithms are extensions of constructive heuristics. Valid solutions to the problem tackled are assembled as subsets of the complete set C of solution components. In the case of the traveling salesman problem (TSP), for example, C may be defined as the set of all edges of the input graph. At each iteration of the algorithm, a set of n_a solutions are probabilistically constructed based on greedy information and on so-called pheromone information. In a standard case, for each solution with components c ∈ C, the algorithm considers a pheromone value τ_c ∈ , where is the set of all pheromone values. Given a partial solution, S^p ⊆ C, the next component c′ ∈ C to be added to S^p is chosen based on its pheromone value τ_c′ and the value η(c′) of a greedy function η(·). Set is commonly called the pheromone model, which is one of the central components of any ACO algorithm. The solution construction mechanism together with the pheromone model and the greedy information define a probability distribution over the search space. This probability distribution is updated at each iteration (after having constructed n_a solutions) by increasing the pheromone value of solution components that appear in good solutions constructed in this iteration or in previous iterations.

In summary, ACO algorithms attempt to solve CO problems by iterating the following two steps:

• – candidate solutions are constructed by making use of a mechanism for constructing solutions, a pheromone model and greedy information;
• – candidate solutions are used to update the pheromone values in a way that is deemed to bias future sampling toward high-quality solutions.

In other words, the pheromone update aims to lead the search towards regions of the search space containing high-quality solutions. The reinforcement of solution components depending on the quality of solutions in which they appear is an important ingredient of ACO algorithms. By doing this, we implicitly assume that good solutions consist of good solution components. In fact, it has been shown that learning which components contribute to good solutions can – in many cases – help to assemble them into better solutions. A high-level framework of an ACO algorithm is shown in Algorithm 1.3. Daemon actions (see line 5 of Algorithm 1.3) mainly refer to the possible application of local search to solutions constructed in the AntBasedSolutionConstruction() function.

A multitude of different ACO variants have been proposed over the years. Among the ones with the best performance are (1) MAX–MIN Ant System (MMAS) [STÜ 00] and (2) Ant Colony System (ACS) [DOR 97]. For more comprehensive information, we refer the interested reader to [DOR 10].

1.2.2. Evolutionary algorithms

Evolutionary algorithms (EAs) [BÄC 97] are inspired by the principles of natural evolution, i.e. by nature’s capability to evolve living beings to keep them well adapted to their environment. At each iteration, an EA maintains a population P of individuals. Generally, individuals are valid solutions to the problem tackled. However, EAs sometimes also permit infeasible solutions or even partial solutions. Just as in natural evolution, the driving force in EAs is the selection of individuals based on their fitness, which is – in the context of combinatorial optimization problems – usually a measure based on the objective function. Selection takes place in two different operators of an EA. First, selection is used at each iteration to choose parents for one or more reproduction operators in order to generate a set, P^off, of offspring. Second, selection takes place when the individuals in the population of the next iteration are chosen from the current population P and the offspring generated in the current iteration. In both operations, individuals with higher fitness have a higher probability of being chosen. In natural evolution this principle is known as survival of the fittest. Note that reproduction operations, such as crossover, often preserve the solution components that are present in the parents. EAs generally also make use of mutation or modification operators that cause either random changes or heuristically-guided changes in an individual. This process described above is pseudo-coded in Algorithm 1.4.

A variety of different EAs have been proposed over the last decades. To mention all of them is out of the scope of this short introduction. However, three major lines of EAs were independently developed early on. These are evolutionary programming (EP) [FOG 62, FOG 66], evolutionary strategies (ESs) [REC 73] and genetic algorithms (GAs) [HOL 75, GOL 89]. EP, for example, was originally proposed to operate on discrete representations of finite state machines. However, most of the present variants are used for CO problems. The latter also holds for most current variants of ESs. GAs, however are still mainly applied to the solution of CO problems. Later, other EAs – such as genetic programming (GP) [KOZ 92] and scatter search (SS) [GLO 00b] – were developed. Despite the development of different strands, EAs can be understood from a unified point of view with respect to their main components and the way in which they explore the search space. This is reflected, for example, in the survey by Kobler and Hertz [HER 00].

1.2.3. Greedy randomized adaptive search procedures

The greedy randomized adaptive search procedure (GRASP) [RES 10a] is a conceptually simple, but often effective, metaheuristic. As indicated by the name, the core of GRASP is based on the probabilistic construction of solutions. However, while ACO algorithms, for example, include a memory of the search history in terms of the pheromone model, GRASP does not make use of memory. More specifically, GRASP – as pseudo-coded in Algorithm 1.5 – combines the randomized greedy construction of solutions with the subsequent application of a local search. For the following discussion let us assume that, given a partial solution S^p, set Ext(S^p) ⊆ C is the set of solution components that may be used to extend S^p. The probabilistic construction of a solution using GRASP makes use of a so-called restricted candidate list L, which is a subset of Ext(S^p), at each step. In fact, L is determined to contain the best solution components from Ext(S^p) with respect to a greedy function. After generating L, a solution component c^∗ ∈ L is chosen uniformly at random. An important parameter of GRASP is α, which is the length of the restricted candidate list L. If α = 1, for example, the solution construction is deterministic and the resulting solution is equal to the greedy solution. In the other extreme case – that is, when choosing α = |Ext(S^p)| – a random solution is generated without any heuristic bias. In summary, α is a critical parameter of GRASP which generally requires a careful fine-tuning.

As mentioned above, the second component of the algorithm consists of the application of local search to the solutions constructed. Note that, for this purpose, the use of a standard local search method such as the one from Algorithm 1.2 is the simplest option. More sophisticated options include, for example, the use of metaheuristics based on a local search such as simulated annealing. As a rule of thumb, the algorithm designer should take care that: (1) the solution construction mechanism samples promising regions of the search space: and (2) the solutions constructed are good starting points for a local search, i.e. the solutions constructed fall into basins of attraction for high-quality local minima.

1.2.4. Iterated local search

Iterated local search (ILS) [LOU 10] is – among the metaheuristics described in this section – the first local search extension. The idea of ILS is simple: instead of repeatedly applying local search to solutions generated independently from each other, as in GRASP, ILS produces the starting solutions for a local search by randomly perturbing the incumbent solutions. The requirements for the perturbation mechanism are as follows. The perturbed solutions should lie in a different basin of attraction with respect to the local search method utilized. However, at the same time, the perturbed solution should be closer to the previous incumbent solution than a randomly generated solution.

More specifically, the pseudo-code of ILS – as shown in Algorithm 1.6 – works as follows. First, an initial solution is produced in some way in the GenerateInitialSolution() function. This solution serves as input for the first application of a local search (see ApplyLocalSearch(S) function in line 2 of the pseudo-code). At each iteration, first, the perturbation mechanism is applied to the incumbent solution S; see Perturbation(S,history) function. The parameter history refers to the possible influence of the search history on this process. The perturbation mechanism is usually non-deterministic in order to avoid cycling, which refers to a situation in which the algorithm repeatedly returns to solutions already visited. Moreover, it is important to choose the perturbation strength carefully. This is, because: (1) a perturbation that causes very few changes might not enable the algorithm to escape from the current basin of attraction; (2) a perturbation that is too strong would make the algorithm similar to a random-restart local search. The last algorithmic component of ILS concerns the choice of the incumbent solution for the next iteration; see function Choose(S, S′, history). In most cases, ILS algorithms simply choose the better solution from among S and S′. However, other criteria – for example, ones that depend on the search history – might be applied.

1.2.5. Simulated annealing

Simulated annealing (SA) [NIK 10] is another metaheuristic that is an extension of local search. SA has – just like ILS – a strategy for escaping from the local optimal of the search space. The fundamental idea is to allow moves to solutions that are worse than the incumbent solution. Such a move is generally known as an uphill move. SA is inspired by the annealing process of metal and glass. When cooling down such materials from the fluid state to a solid state, the material loses energy and finally assumes a crystal structure. The perfection – or optimality – of this crystal structure depends on the speed at which the material is cooled down. The more carefully the material is cooled down, the more perfect the crystal structure. The first times that SA was presented as a search algorithm for CO problems was in [KIR 83] and in [CER 85].

SA works as shown in Algorithm 1.7. At each iteration, a solution S′ ∈ N(S) is randomly selected. If S′ is better than S, then S′ replaces S as incumbent solution. Otherwise, if S is worse than S′ – that is, if the move from S to S′ is an uphill move – S′ may still be accepted as new incumbent solution with a positive probability that is a function of a temperature parameter T_k – in analogy to the natural inspiration of SA – and the difference between the objective function value of S′ and that of S (f(s′) − f(s)). Usually this probability is computed in accordance with Boltzmann’s distribution. Note that when SA is running, the value of T_k gradually decreases. In this way, the probability of accepting an uphill move decreases during run time.

Note that the SA search process can be modeled as a Markov chain [FEL 68]. This is because the trajectory of solutions visited by SA is such that the next solution is chosen depending only on the incumbent solution. This means that – just like GRASP – basic SA is a memory-less process.

1.2.6. Other metaheuristics

Apart from the five metaheuristics outlined in the previous sections, the literature offers a wide range of additional algorithms that fall under the metaheuristic paradigm. Examples are established metaheuristics, such as Tabu search [GLO 97, GEN 10b], particle swarm optimization [KEN 95, JOR 15], iterated greedy algorithms [HOO 15] and variable neighborhood search (VNS) [HAN 10]. More recent metaheuristics include artificial bee colony optimization [KAR 07, KAR 08] and chemical reaction optimization [LAM 12].

1.2.7. Hybrid approaches

Quite a large number of algorithms have been reported in recent years that do not follow the paradigm of a single traditional metaheuristic. They combine various algorithmic components, often taken from algorithms from various different areas of optimization. These approaches are commonly referred to as hybrid metaheuristics. The main motivation behind the hybridization of different algorithms is to exploit the complementary character of different optimization strategies, i.e. hybrids are believed to benefit from synergy. In fact, choosing an adequate combination of complementary algorithmic concepts can be the key to achieving top performance when solving many hard optimization problems. This has also seen to be the case in the context of string problems in bioinformatics, for example in the context of longest common subsequence problems in Chapter 3. In the following section, we will mention the main ideas behind two generally applicable hybrid metaheuristics from the literature: large neighborhood search (LNS), and construct, merge, solve & adapt (CMSA). A comprehensive introduction into the field of hybrid metaheuristics is provided, for example, in [BLU 16e].

1.2.7.2. Construct, merge, solve and adapt

The CMSA algorithm was introduced in [BLU 16b] with the same motivation that had already led to the development of LNS as outlined in the previous section. More specifically, the CMSA algorithm is designed in order to be able to profit from an efficient complete solver even in the context of problem that are too large to be directly solved by the complete solver. The general idea of CMSA is as follows. At each iteration, solutions to the problem tackled are generated in a probabilistic way. The components found in these solutions are then added to a sub-instance of the original problem. Subsequently, an exact solver such as, for example, CPLEX is used to solve the sub-instance to an optimal level. Moreover, the algorithm is equipped with a mechanism for deleting seemingly useless solution components from the sub-instance. This is done such that the sub-instance has a moderate size and can be quickly and optimally solved.

The pseudo-code of the CMSA algorithm is provided in Algorithm 1.9. Each algorithm iteration consists of the following actions. First, the best-so-far solution S_bsf is set to NULL, indicating that no such solution yet exists. Moreover, the restricted problem, C′, which is simply a subset of the complete set, C, of solution components is set to the empty set². Then, at each iteration, n_a solutions are probabilistically generated in function ProbabilisticSolutionGeneration(C); see line 6 of Algorithm 1.9. The components found in the solutions constructed are then added to C′. The so-called age of each of these solution components (age[c]) is set to 0. Next, a complete solver is applied in function ApplyExactSolver(C′) to find a possible optimal solution to the restricted problem C′. If is better than the current best-so-far solution S_bsf, solution is taken as the new best-so-far solution. Next, sub-instance C′ is adapted on the basis of solution in conjunction with the age values of the solution components; see function Adapt(C′, , age_max) in line 14. This is done as follows. First, the age of each solution component in C′ is incremented while the age of each solution component in ⊆ C′ is re-set to zero. Subsequently, those solution components from C′ with an age value greater than age_max – which is a parameter of the algorithm – are removed from C′. This means that solution components that never appear in solutions derived by the complete solver do not slow down the solver in subsequent iterations. Components which appear in the solutions returned by the complete solver should be maintained in C′.