# Consistent Neighborhood Search for Combinatorial Optimization

Authors: Michel Vasquez; Nicolas Zufferey
Journal: ISRN Computational Mathematics
 (2012)

---

## Abstract

Many optimization problems (from academia or industry) require the use of a local search to find a satisfying solution in a reasonable amount of time, even if the optimality is not guaranteed. Usually, local search algorithms operate in a search space which contains complete solutions (feasible or not) to the problem. In contrast, inConsistent Neighborhood Search (CNS), after each variable assignment, the conflicting variables are deleted to keep the partial solution feasible, and the search can stop when all the variables have a value. In this paper, we formally propose a new heuristic solution method, CNS, which has a search behavior between exhaustive tree search and local search working with complete solutions. We then discuss, with a unified view, the great success of some existing heuristics, which can however be considered within the CNS framework, in various fields: graph coloring, frequency assignment in telecommunication networks, vehicle fleet management with maintenance constraints, and satellite range scheduling. Moreover, some lessons are given in order to have guidelines for the adaptation of CNS to other problems.


---

## Body

## 1. Introduction

Anexact method (e.g., branch-and-bound, dynamic programming, Lagrangian relaxation-based methods) guarantees the optimality of the provided solution. However, for a large number of applications and most real-life optimization problems, such methods need a prohibitive amount of time to find an optimal solution, because such problems are NP-hard [1]. For these difficult problems, one should prefer to quickly find a satisfying solution, which is the goal of heuristic solution methods. There mainly exist three families of heuristics: constructive heuristics (a solution is built step by step from scratch, like the greedy algorithm), local search heuristics (a solution is iteratively modified: this will be discussed below), and evolutionary heuristics (a population of solutions is managed, like genetic algorithms and ant algorithms). In this paper, only the context of local search methods will be considered.Alocal search heuristic starts with an initial solution and tries to improve it iteratively. At each iteration, a modification, called move, of the current solution is performed in order to generate a neighbor solution. The definition of a move, that is, the definition of the neighborhood structure, depends on the considered problem. The most popular local search methods are simulated annealing [2], tabu search [3], threshold algorithms [4], variable neighborhood search [5], and guided local search [6].Within a local search context, the usual approach consists in working with complete solutions, that is, each variable has a value and the solution might be feasible or not. In the latter case, a penalty function is often used, which depends on the number of violated constraints. In contrast, inConsistent Neighborhood Search (CNS), partial feasible solutions are used. Thus, not every variable has a value, but there is no constraint violation. In such a case, the goal is to minimize the number of nonassigned variables, and a move is performed in at least two phases: (1) give a value to an unassigned variable si, and (2) delete the value of the created conflicting variables (i.e., the variables different from si involved in a constraint violation). An intermediate phase might occur between these two phases, which consists in adjusting the value of conflicting variables under some specific conditions. In this paper, which is an extension of [7] and [8], we formally introduce the CNS methodology and the adaptation of tabu search within its framework, then we discuss, with a unified terminology, the great success of some existing heuristics, which can however be considered as belonging to the CNS methodology, for various NP-hard constrained combinatorial problems. For each problem, the reader is referred to the associated paper to have references on the NP-hard aspect, the literature review, and the detailed experimental conditions (computer, language, etc.). For each problem, comparisons have to be done carefully because the conditions of experimentation were not always the same. Remember however that a heuristic is generally performed until the potential to improve the best encountered solution becomes poor. In addition, for each considered problem, the CNS approach will always be compared with state-of-the-art methods, even if such methods are not very recent.The paper is organized as follows. In Section2, the CNS methodology is proposed. Then, heuristics for various problems are presented within a CNS framework: graph coloring (Section 3), frequency assignment with polarization (Section 4), car fleet management with maintenance constraint (Section 5), and satellite range scheduling (Section 6). We end up the paper with a conclusion.


## 2. Consistent Neighborhood Search

In this section, we introduce the CNS methodology and situate it within the optimization methods.


### 2.1. Presentation of the Method

Let(P) be the considered problem with n variables s1,…,sn, let f be the objective function to minimize, and let C be the set of constraints to satisfy. Each variable si can only have a value in its value domain Di. A solution of (P) is denoted s=(s1,…,sn), where si∈Di. Solution s is feasible if it satisfies all the constraints in C. In most local search methods, the search space contains complete solutions; that is, each variable si has a value in Di, and the solutions can be feasible or not. If the search space only contains feasible solutions, the goal is generally to directly minimize the given objective function f associated with (P); otherwise, the aim often consists in minimizing f(s)+α·p(s), where p(s) penalizes the constraint violations associated with s and α is a parameter which gives more or less importance to the constraint violations. In contrast, a specificity of CNS consists in working with partial and feasible solutions, that is, where some si’s do not have a value but all the constraints are satisfied. In such a case, the goal is to minimize the number f^(s) of nonassigned variables in s, and the process stops of course if f^(s)=0.Therefore, three search spaces are possible: (1) the complete and feasible search spaceS(feasible), (2) the complete and unecessarily feasible search space S(penalty), where unfeasible solutions are penalized, and (3) the partial and feasible search space S(partial). When working in S(feasible), it can be very difficult to define a move which maintains the feasibility of the solution. When working in S(penalty), it is challenging to: define a move which does not augment too much p(s), tune the above-mentioned parameter α, and find a feasible solution because S(penalty) is much larger than S(feasible). We will see that such drawbacks are avoided when working in S(partial).An important feature of CNS is the definition of the neighborhood structure inS(partial). In most local search methods, in order to generate a neighbor solution s′ from the current solution s, a move m consists in changing the value of one (or more) variable(s) of s. The set of neighbor solutions of s is denoted N(s). Let d(s,s′) be the distance between s and s′∈N(s). Usually, d(s,s′) is proportional to the number of modified variables when moving from s to s′; thus d(s,s′) is a constant for all s′∈N(s).In contrast, any movem is performed in at least two phases in CNS. (1)
Assignment phase: a value of Di is assigned to a non assigned variable si. Let C(m) be the set of conflicting variables (excluding si) created by move m (a variable is in conflict if it is involved in at least a constraint violation).(2)
Reassignment phase (optional): reduce the set C(m) as follows: for each variable of C(m), if it is possible to assign a new admissible value to it without creating new conflicts, do it.(3)
Repairing phase: in order to keep the partial solution feasible, remove the value of all the variables of C(m).Therefore, the distance betweens and a neighbor solution in N(s) is usually not a constant.In most local search algorithms, the selected neighbor solutions′ of the current solution s is usually (one of) the best (according to f or f+α·p) solution chosen among a sample of N(s). Sampling is usually unavoidable because it is too much time consuming to evaluate all the neighbor solutions of s, either because N(s) is too large or because it is cumbersome to evaluate a single move m. An important issue is thus to determine the sample (random or not) as well as the size of the sample.In contrast, in CNS,all the neighbor solutions can be considered at each iteration. This is possible in a reasonable amount of time because of two reasons: (1) it is quick to evaluate a neighbor solution by incremental computation: it is simply |C(m)|; (2) the number of nonassigned variables in the current solution s is in general small when compared for example, with the size |N(s)| of the neighbor solutions of s in a standard local search approach (working in S(feasible) or in S(penalty)).We have now all the ingredients to formulate a pseudo-code of CNS in Algorithm1.Algorithm 1:CNS.
Initialization: generate an initial solution s, set s*=s and f^*=f^(s);
While a stopping time condition is not met and
f
^
*
>
0
, do
1.  initialize the value of the best move: setg=+∞;
2.  generate the best move: for each non assigned variablesi and each value dj∈Di, test move m=(si,dj) on s as follows:
(a)assignment phase: give value dj to variable si and compute the associated set C(m) of conflicting variables;
(b)reassignment phase (optional): for each variable sr of C(m), if it is possible to assign another admissible value to sr
without augmenting the number of violations, do it and removesr from C(m);
(c) letscand be the so obtained candidate neighbor solution (which might be non feasible at this stage);
(d) update the best candidate move: if|C(m)|<g, set s'=scand and g=|C(m)|;
3.repairing phase on the best move: remove the value of the g conflicting variables of s' and let s be the
resulting new current solution;
4.  update the record: iff^(s)<f^*, set s*=s and f^*=f^(s)
Output: solution s* (which is a complete feasible solution if f^*=0);In summary, CNS is an approach dealing with partial feasible solutions, which can explore the whole neighborhood of the current solution at each iteration because a straightforward incremental computation can be designed. Many local search methods (e.g., tabu search, simulated annealing, random walk, threshold algorithms, etc.) can be adapted within the framework of CNS.The adaptation of tabu search within the framework of CNS is now discussed. A generic and standard version of tabu search can be described as follows, assuming thatf has to be minimized. First, tabu search needs an initial solution as input. Then, the algorithm generates a sequence of neighbor solutions. When a move is performed from s to s′, the inverse of that move is forbidden during the following t (parameter) iterations (with some exceptions). The solution s′ is computed as s′=argmins′′∈N′(s)f(s′’), where N′(s) is a subset of N(s) containing all solutions s′ which can be obtained from s either by performing a move that is not tabu or such that f(s′)<f(s*), where s* is the best solution encountered along the search so far. Usually, N′(s) is too large, and only a sample of neighbor solutions are selected from N′(s) to be evaluated. The choice of the sample often has a strong impact on the final results. The process is stopped, for example, when an optimal solution is found (when it is known), or when a fixed number of iterations have been performed. Many variants and extensions of this basic algorithm can be found, for example, in [9].Tabu search adapted within the framework of CNS has the following specificities: working inS(feasible), minimizing f^ instead of f, exploring the whole neighborhood of the current solution, using an efficient and straightforward incremental computation after each move when a value is given to a variable si and other values might be adjusted or deleted, and it is then tabu to remove the value of si for a certain number of iterations.


### 2.2. Search Characteristics of CNS

We now compare the general strategy of three kinds of optimization methods: tree search, standard local search, and CNS. These methods have a very different way to visit the search tree, where theroot (the top node in Figures 1 to 4) is the empty solution (no variable is assigned), and the leaves (the bottom nodes in Figures 1 to 4) are complete solutions (all the variables have a value), which can be feasible or not. In such four figures, an empty node is not visited by the considered method; on the contrary a black node is visited, and a black arrow indicates a performed move from one node to another. Let S be the set of all the possible nodes in the search tree, and let X be subset of S which is mainly visited by a specific algorithm. We will see that X differs drastically from one method to the other.Figure 1
Xfor depth-first search.Tree search algorithms visit neighbor nodes in the search tree. The visited subtreeX is likely to be vertical for Depth-First Search as illustrated in Figure 1, where only a few leaves might be visited. In contrast, Breadth-First Search usually focuses on the top of the search tree because it often needs a prohibitive amount of time to go down, as illustrated in Figure 2 where no leaves are visited.Figure 2
X for breadth-first search.A very different strategy characterizes standard local search methods: as illustrated in Figure3, only leaves are visited, which is a major advantage when compared to tree search methods. However, standard local search algorithms usually have the following drawbacks. On the one hand, if constraint violation is forbidden, the search space X is not necessarily connected; that is, it is not always possible to join two leaves with a sequence of moves. In such a case, the search might be trapped in a connected component of S which does not contain good solutions. On the other hand, if constraint violation is allowed but penalized during the search, the number of leaves is drastically augmented, and the search might mainly focus on nonfeasible leaves, as it can be challenging to define the penalty function p and to tune its associated parameter α.Figure 3
X for a standard local search.Figure 4
X for CNS.Even if CNS can be considered as a local search method, it mainly explores nodes which are close to the leaves, as illustrated in Figure4. Because all the leaves correspond to complete and feasible solutions, CNS stops as soon as a leaf is reached.CNS can start its search from the root, that is, no variable has a value. In such a case, its first iterations would basically consist in greedily assigning a value to a variable until the current solution becomessaturated, that is, when the repairing phase becomes unavoidable. CNS can also start its search from a node located below the root if an external procedure is used to generate the initial solution of CNS. The more efficient is such external procedure, the closer will be the first explored node to the bottom of S. Last but not least, CNS can perform jumps in S. Thus, the search space X is likely to be connected.Therefore, CNS does not encounter the above-described drawbacks associated with tree search and standard local search methods. Notice however that there exists an implicit enumeration method able to perform jumps overS, called Resolution Search and proposed in [10].


## 2.1. Presentation of the Method

Let(P) be the considered problem with n variables s1,…,sn, let f be the objective function to minimize, and let C be the set of constraints to satisfy. Each variable si can only have a value in its value domain Di. A solution of (P) is denoted s=(s1,…,sn), where si∈Di. Solution s is feasible if it satisfies all the constraints in C. In most local search methods, the search space contains complete solutions; that is, each variable si has a value in Di, and the solutions can be feasible or not. If the search space only contains feasible solutions, the goal is generally to directly minimize the given objective function f associated with (P); otherwise, the aim often consists in minimizing f(s)+α·p(s), where p(s) penalizes the constraint violations associated with s and α is a parameter which gives more or less importance to the constraint violations. In contrast, a specificity of CNS consists in working with partial and feasible solutions, that is, where some si’s do not have a value but all the constraints are satisfied. In such a case, the goal is to minimize the number f^(s) of nonassigned variables in s, and the process stops of course if f^(s)=0.Therefore, three search spaces are possible: (1) the complete and feasible search spaceS(feasible), (2) the complete and unecessarily feasible search space S(penalty), where unfeasible solutions are penalized, and (3) the partial and feasible search space S(partial). When working in S(feasible), it can be very difficult to define a move which maintains the feasibility of the solution. When working in S(penalty), it is challenging to: define a move which does not augment too much p(s), tune the above-mentioned parameter α, and find a feasible solution because S(penalty) is much larger than S(feasible). We will see that such drawbacks are avoided when working in S(partial).An important feature of CNS is the definition of the neighborhood structure inS(partial). In most local search methods, in order to generate a neighbor solution s′ from the current solution s, a move m consists in changing the value of one (or more) variable(s) of s. The set of neighbor solutions of s is denoted N(s). Let d(s,s′) be the distance between s and s′∈N(s). Usually, d(s,s′) is proportional to the number of modified variables when moving from s to s′; thus d(s,s′) is a constant for all s′∈N(s).In contrast, any movem is performed in at least two phases in CNS. (1)
Assignment phase: a value of Di is assigned to a non assigned variable si. Let C(m) be the set of conflicting variables (excluding si) created by move m (a variable is in conflict if it is involved in at least a constraint violation).(2)
Reassignment phase (optional): reduce the set C(m) as follows: for each variable of C(m), if it is possible to assign a new admissible value to it without creating new conflicts, do it.(3)
Repairing phase: in order to keep the partial solution feasible, remove the value of all the variables of C(m).Therefore, the distance betweens and a neighbor solution in N(s) is usually not a constant.In most local search algorithms, the selected neighbor solutions′ of the current solution s is usually (one of) the best (according to f or f+α·p) solution chosen among a sample of N(s). Sampling is usually unavoidable because it is too much time consuming to evaluate all the neighbor solutions of s, either because N(s) is too large or because it is cumbersome to evaluate a single move m. An important issue is thus to determine the sample (random or not) as well as the size of the sample.In contrast, in CNS,all the neighbor solutions can be considered at each iteration. This is possible in a reasonable amount of time because of two reasons: (1) it is quick to evaluate a neighbor solution by incremental computation: it is simply |C(m)|; (2) the number of nonassigned variables in the current solution s is in general small when compared for example, with the size |N(s)| of the neighbor solutions of s in a standard local search approach (working in S(feasible) or in S(penalty)).We have now all the ingredients to formulate a pseudo-code of CNS in Algorithm1.Algorithm 1:CNS.
Initialization: generate an initial solution s, set s*=s and f^*=f^(s);
While a stopping time condition is not met and
f
^
*
>
0
, do
1.  initialize the value of the best move: setg=+∞;
2.  generate the best move: for each non assigned variablesi and each value dj∈Di, test move m=(si,dj) on s as follows:
(a)assignment phase: give value dj to variable si and compute the associated set C(m) of conflicting variables;
(b)reassignment phase (optional): for each variable sr of C(m), if it is possible to assign another admissible value to sr
without augmenting the number of violations, do it and removesr from C(m);
(c) letscand be the so obtained candidate neighbor solution (which might be non feasible at this stage);
(d) update the best candidate move: if|C(m)|<g, set s'=scand and g=|C(m)|;
3.repairing phase on the best move: remove the value of the g conflicting variables of s' and let s be the
resulting new current solution;
4.  update the record: iff^(s)<f^*, set s*=s and f^*=f^(s)
Output: solution s* (which is a complete feasible solution if f^*=0);In summary, CNS is an approach dealing with partial feasible solutions, which can explore the whole neighborhood of the current solution at each iteration because a straightforward incremental computation can be designed. Many local search methods (e.g., tabu search, simulated annealing, random walk, threshold algorithms, etc.) can be adapted within the framework of CNS.The adaptation of tabu search within the framework of CNS is now discussed. A generic and standard version of tabu search can be described as follows, assuming thatf has to be minimized. First, tabu search needs an initial solution as input. Then, the algorithm generates a sequence of neighbor solutions. When a move is performed from s to s′, the inverse of that move is forbidden during the following t (parameter) iterations (with some exceptions). The solution s′ is computed as s′=argmins′′∈N′(s)f(s′’), where N′(s) is a subset of N(s) containing all solutions s′ which can be obtained from s either by performing a move that is not tabu or such that f(s′)<f(s*), where s* is the best solution encountered along the search so far. Usually, N′(s) is too large, and only a sample of neighbor solutions are selected from N′(s) to be evaluated. The choice of the sample often has a strong impact on the final results. The process is stopped, for example, when an optimal solution is found (when it is known), or when a fixed number of iterations have been performed. Many variants and extensions of this basic algorithm can be found, for example, in [9].Tabu search adapted within the framework of CNS has the following specificities: working inS(feasible), minimizing f^ instead of f, exploring the whole neighborhood of the current solution, using an efficient and straightforward incremental computation after each move when a value is given to a variable si and other values might be adjusted or deleted, and it is then tabu to remove the value of si for a certain number of iterations.


## 2.2. Search Characteristics of CNS

We now compare the general strategy of three kinds of optimization methods: tree search, standard local search, and CNS. These methods have a very different way to visit the search tree, where theroot (the top node in Figures 1 to 4) is the empty solution (no variable is assigned), and the leaves (the bottom nodes in Figures 1 to 4) are complete solutions (all the variables have a value), which can be feasible or not. In such four figures, an empty node is not visited by the considered method; on the contrary a black node is visited, and a black arrow indicates a performed move from one node to another. Let S be the set of all the possible nodes in the search tree, and let X be subset of S which is mainly visited by a specific algorithm. We will see that X differs drastically from one method to the other.Figure 1
Xfor depth-first search.Tree search algorithms visit neighbor nodes in the search tree. The visited subtreeX is likely to be vertical for Depth-First Search as illustrated in Figure 1, where only a few leaves might be visited. In contrast, Breadth-First Search usually focuses on the top of the search tree because it often needs a prohibitive amount of time to go down, as illustrated in Figure 2 where no leaves are visited.Figure 2
X for breadth-first search.A very different strategy characterizes standard local search methods: as illustrated in Figure3, only leaves are visited, which is a major advantage when compared to tree search methods. However, standard local search algorithms usually have the following drawbacks. On the one hand, if constraint violation is forbidden, the search space X is not necessarily connected; that is, it is not always possible to join two leaves with a sequence of moves. In such a case, the search might be trapped in a connected component of S which does not contain good solutions. On the other hand, if constraint violation is allowed but penalized during the search, the number of leaves is drastically augmented, and the search might mainly focus on nonfeasible leaves, as it can be challenging to define the penalty function p and to tune its associated parameter α.Figure 3
X for a standard local search.Figure 4
X for CNS.Even if CNS can be considered as a local search method, it mainly explores nodes which are close to the leaves, as illustrated in Figure4. Because all the leaves correspond to complete and feasible solutions, CNS stops as soon as a leaf is reached.CNS can start its search from the root, that is, no variable has a value. In such a case, its first iterations would basically consist in greedily assigning a value to a variable until the current solution becomessaturated, that is, when the repairing phase becomes unavoidable. CNS can also start its search from a node located below the root if an external procedure is used to generate the initial solution of CNS. The more efficient is such external procedure, the closer will be the first explored node to the bottom of S. Last but not least, CNS can perform jumps in S. Thus, the search space X is likely to be connected.Therefore, CNS does not encounter the above-described drawbacks associated with tree search and standard local search methods. Notice however that there exists an implicit enumeration method able to perform jumps overS, called Resolution Search and proposed in [10].


## 3. Graph Coloring

The main reference associated with this section is [11]. The authors proposed a tabu search heuristic for the graph coloring problem, which we denote CNS-GCP for the sake of simplicity.


### 3.1. Description of the Problem

Given a graphG=(V,E) with vertex set V and edge set E, the k-coloring problem (k-GCP) consists in assigning an integer (called color) in {1,…,k} to every vertex such that two adjacent vertices have different colors. The Graph Coloring Problem (GCP) consists in finding a k-coloring with the smallest possible value of k (called the chromatic number and denoted χ). Both problems are NP-hard [1], and many heuristics were proposed to solve them. For a recent survey, the reader is referred to [12]. Starting at most with k=|V|, an upper bound on the chromatic number of G can be determined by solving a series of k-GCPs with decreasing values of k until no feasible k-coloring can be obtained. Only such a strategy, which leads to the best results, will be considered below.


### 3.2. Description of the Method within a CNS Framework

The bestk-coloring heuristics are based on two approaches. In S(penalty), the constraint that the endpoints of an edge should have different colors is relaxed. Thus, the strategy consists in allowing conflicts (a conflict occurs if two adjacent vertices have the same color) while minimizing the number of conflicts. In a local search context, a straightforward move is thus to change the color of a conflicting vertex, as proposed in [13].In contrast, inS(partial), the constraint imposing that all vertices should be colored is relaxed, but conflicts are forbidden. We have Di={1,…,k} for each si. In such a case, the value si of a solution s=(s1,…,sn) in S(partial) indicates the color of vertex i, which is in the set {1,…,k}, and there is no value (or an artificial value 0) if vertex i is not colored. The goal is to minimize the number of uncolored vertices. A move m=(si;c) consists in first assigning a color c to a uncolored vertex i (assignment phase), and then (repairing phase) to remove the color of the created conflicting vertices (i.e., all the vertices adjacent to i which have color c). Then, all the moves which will remove the color c of vertex i are tabu for a certain number of iterations. This number is dynamically managed and is proportional to the variation of the objective function f^(s)=|s|=|{si|si>0}|. At each iteration, the best nontabu move is performed (ties are randomly broken).


### 3.3. Numerical Comparison with Other Methods

It is shown in [14] and in [11] that the most difficult benchmark instances from the DIMACS Challenge (see ftp://dimacs.rutgers.edu/pub/challenge/graph/) are the ones presented in Table 1. Below, CNS-GCP is compared with other state-of-the-art coloring heuristics, which are Tabucol [13], GH [15], MOR [16], and MMT [17]. Tabucol is a standard tabu search working in S(penalty). GH, MOR, and MMT are all population-based methods which use local search procedures. GH uses Tabucol to improve offspring solutions, whereas MMT uses a procedure close to CNS-GCP. MOR works in the same search space as CNS-GCP but uses simulated annealing instead of tabu search, and much more sophisticated moves.Table 1
Comparisons between CNS-GCP and state-of-the-art coloring algorithms.
Graph
n
χ
,
k
*
CNS-GCP
Tabucol
MMT
GH
MOR
DSJC1000.1
1000
?, 20
21
20
20
20
21
DSJC1000.5
1000
?, 83
89
89
83
83
88
DSJC1000.9
1000
?, 224
226
227
226
224
226
DSJC500.1
500
?, 12
12
12
12
12
12
DSJC500.5
500
?, 48
49
49
48
48
49
DSJC500.9
500
?, 126
127
127
127
126
128
DSJR500.1c
500
?, 85
85
85
85
—
85
DSJR500.5
500
?, 122
126
126
122
—
123
flat1000_50_0
1000
50, 50
50
50
50
50
50
flat1000_60_0
1000
60, 60
60
60
60
60
60
flat1000_76_0
1000
76, 82
88
88
82
83
89
flat300_28_0
300
28, 28
28
31
31
31
31
le450_15c
450
15, 15
15
16
15
15
15
le450_15d
450
15, 15
15
15
15
15
15
le450_25c
450
25, 25
27
26
25
26
25
le450_25d
450
25, 25
27
26
25
26
25A CPU time limit of 60 minutes on a Pentium 4 (2 GHZ, 512 MB of RAM) was considered for CNS-GCP. The first two columns of Table1, respectively, indicate the name and the number n of vertices of the graph. The third column contains two numbers, the first one being the chromatic number (a “?” is put when it is not known), and the second one the best upper bound k⋆ ever found by a heuristic. Then, for every algorithm, the smallest k such that a feasible k-coloring was found is reported. We can observe that CNS-GCP is rather competitive with the best coloring methods. However, it is much simpler!


## 3.1. Description of the Problem

Given a graphG=(V,E) with vertex set V and edge set E, the k-coloring problem (k-GCP) consists in assigning an integer (called color) in {1,…,k} to every vertex such that two adjacent vertices have different colors. The Graph Coloring Problem (GCP) consists in finding a k-coloring with the smallest possible value of k (called the chromatic number and denoted χ). Both problems are NP-hard [1], and many heuristics were proposed to solve them. For a recent survey, the reader is referred to [12]. Starting at most with k=|V|, an upper bound on the chromatic number of G can be determined by solving a series of k-GCPs with decreasing values of k until no feasible k-coloring can be obtained. Only such a strategy, which leads to the best results, will be considered below.


## 3.2. Description of the Method within a CNS Framework

The bestk-coloring heuristics are based on two approaches. In S(penalty), the constraint that the endpoints of an edge should have different colors is relaxed. Thus, the strategy consists in allowing conflicts (a conflict occurs if two adjacent vertices have the same color) while minimizing the number of conflicts. In a local search context, a straightforward move is thus to change the color of a conflicting vertex, as proposed in [13].In contrast, inS(partial), the constraint imposing that all vertices should be colored is relaxed, but conflicts are forbidden. We have Di={1,…,k} for each si. In such a case, the value si of a solution s=(s1,…,sn) in S(partial) indicates the color of vertex i, which is in the set {1,…,k}, and there is no value (or an artificial value 0) if vertex i is not colored. The goal is to minimize the number of uncolored vertices. A move m=(si;c) consists in first assigning a color c to a uncolored vertex i (assignment phase), and then (repairing phase) to remove the color of the created conflicting vertices (i.e., all the vertices adjacent to i which have color c). Then, all the moves which will remove the color c of vertex i are tabu for a certain number of iterations. This number is dynamically managed and is proportional to the variation of the objective function f^(s)=|s|=|{si|si>0}|. At each iteration, the best nontabu move is performed (ties are randomly broken).


## 3.3. Numerical Comparison with Other Methods

It is shown in [14] and in [11] that the most difficult benchmark instances from the DIMACS Challenge (see ftp://dimacs.rutgers.edu/pub/challenge/graph/) are the ones presented in Table 1. Below, CNS-GCP is compared with other state-of-the-art coloring heuristics, which are Tabucol [13], GH [15], MOR [16], and MMT [17]. Tabucol is a standard tabu search working in S(penalty). GH, MOR, and MMT are all population-based methods which use local search procedures. GH uses Tabucol to improve offspring solutions, whereas MMT uses a procedure close to CNS-GCP. MOR works in the same search space as CNS-GCP but uses simulated annealing instead of tabu search, and much more sophisticated moves.Table 1
Comparisons between CNS-GCP and state-of-the-art coloring algorithms.
Graph
n
χ
,
k
*
CNS-GCP
Tabucol
MMT
GH
MOR
DSJC1000.1
1000
?, 20
21
20
20
20
21
DSJC1000.5
1000
?, 83
89
89
83
83
88
DSJC1000.9
1000
?, 224
226
227
226
224
226
DSJC500.1
500
?, 12
12
12
12
12
12
DSJC500.5
500
?, 48
49
49
48
48
49
DSJC500.9
500
?, 126
127
127
127
126
128
DSJR500.1c
500
?, 85
85
85
85
—
85
DSJR500.5
500
?, 122
126
126
122
—
123
flat1000_50_0
1000
50, 50
50
50
50
50
50
flat1000_60_0
1000
60, 60
60
60
60
60
60
flat1000_76_0
1000
76, 82
88
88
82
83
89
flat300_28_0
300
28, 28
28
31
31
31
31
le450_15c
450
15, 15
15
16
15
15
15
le450_15d
450
15, 15
15
15
15
15
15
le450_25c
450
25, 25
27
26
25
26
25
le450_25d
450
25, 25
27
26
25
26
25A CPU time limit of 60 minutes on a Pentium 4 (2 GHZ, 512 MB of RAM) was considered for CNS-GCP. The first two columns of Table1, respectively, indicate the name and the number n of vertices of the graph. The third column contains two numbers, the first one being the chromatic number (a “?” is put when it is not known), and the second one the best upper bound k⋆ ever found by a heuristic. Then, for every algorithm, the smallest k such that a feasible k-coloring was found is reported. We can observe that CNS-GCP is rather competitive with the best coloring methods. However, it is much simpler!


## 4. Frequency Assignment with Polarization

The main reference associated with this section is [18], where the frequency assignment problem with polarization (FAPP) was considered. The authors proposed that a tabu search approach working in S(partial) denoted CNS-FAPP below.


### 4.1. Description of the Problem

The FAPP concerns a Hertzian telecommunication network made up of antennae located at a set of geographical sites. A Hertzian liaison joins two sites by one or more paths. Hence, apath is a unidirectional radioelectric bond, established between antennae at distinct sites, which has a given frequency and polarization. Let Fi and Pi, respectively, be the allowed frequency set and polarization set for path i, where Pi∈{{-1},{1},{-1,1}}. The FAPP consists in finding, for each path, a frequency and a polarization satisfying the following set of constraints.LetIC be the set of the imperative constraints, which are of four types: pi=pj, pi≠pj, |fi-fj|=εij, and |fi-fj|≠εij, where εij≥0. In addition, some electromagnetic compatibility constraints (ECCs) require a minimal distance between frequencies of two paths: |fi-fj|≥γij if pi=pj and |fi-fj|≥δij if pi≠pj. This constraint controls the interference phenomenon, which is why the required distance between frequencies depends on their polarizations; it is smaller if the polarizations are different (i.e., δij≤γij). Unfortunately, most problems do not have feasible solutions because the domains are too restrictive or the requirements too numerous. Consequently, some deterioration is allowed by permitting some interference, which have to be minimized. With this aim, for the ECC constraints, a progressive relaxation is authorized and expressed by relaxation levels; level 0 corresponds to no relaxation, and going from level k to level k+1 involves the relaxation of some or all the frequency gaps, the maximum relaxation level being 10. Formally, we have:
(1)|fi-fj|≥{γij0≥⋯≥γijk≥⋯≥γij10ifpi=pjδij0≥⋯≥δijk≥⋯≥δij10ifpi≠pj
since in the 11th level, γij11=δij11=0, so there is no ECC.LetECCk be the set of ECC constraints at level k (for 0≤k≤10). This means that each constraint belonging to ECCk is affected to its γijk and δijk gaps. More precisely, |fi-fj|≥(|pi+pj|/2)γij(k)+(|pi-pj|/2)δij(k). Accordingly, a feasible solution at level k is an assignment of all the paths satisfying all the strong constraints IC and all the ECCk constraints. If such a solution exists, the problem is said to be k-feasible. Every problem is assumed to be 11-feasible.Consequently, the objective function of the problem is, in order of priority to (1) minimize the lowest relaxation levelk for which a k-feasible solution exists (2) minimize V(k-1): the number of constraints of ECC(k-1) violated at level k-1, and (3) minimize ∑0≤i<k-1V(i): the sum of the constraints of ECCi violated at all levels i less than k-1.


### 4.2. Description of the Method within a CNS Framework

The strategy adopted for the resolution consists in transforming the FAPP optimization problem into 11 decision problems according to the relaxation level on theECC; each FAPP(k) contains both the IC and the ECCk constraints. This enables us to introduce some filtering treatments to reduce the frequency and the polarization domains. Starting from level k=11 where an initial solution is provided by a greedy constructive method, the general algorithm works in a downward fashion: each time a k-feasible solution is found, a lower level is considered.A solutions=(s1,…,sn) indicates for each path i its associated resource (fi,pi), where fi∈Fi and pi∈Pi. Thus, Di=Fi×Pi. In the assignment phase, a pair (fi,pi) is given to the chosen nonassigned candidate path i. Then, in the repairing phase, this affectation is propagated to its neighbors in the constraint network, and, if necessary, the conflicting neighboring values are deleted in order to satisfy the IC and ECCk constraints. This was done efficiently using incremental computing on specific data structures, allowing variable domains to be dynamically reduced.A tabu list is needed to prevent cycling, which occurs when there is an attempt to instantiate the last deleted variables in the current partial solution. Indeed, all the values (fj,pj) likely to delete the variable si=(fi,pj) affected by the move are classified tabu during some iterations; the tabu tenure is proportional to the number of times this resource was affected.The considered problem was the subject of the Challenge ROADEF 2001 (organized by the French Society of Operations Research and Decision Analysis), involving 27 research teams (seehttp://uma.ensta-paristech.fr/conf/roadef-2001-challenge/). In Table 2 are presented the results obtained by the five best teams. During the competition, only one run was allowed, and the computing time was limited to one hour on a Pentium 3 (500 MHZ, 128 MB of RAM). Table 2 details the hierarchical objective function, by giving first the relaxation level k, then the sum of all the unsatisfied ECCk-1, and finally the sum of all the unsatisfied ECCi, where i varies from 0 to k-2. The first column indicates the instance names with the instance number and the number n of considered paths. For example, 02-0250 is instance 2 with 250 paths.Table 2
Comparison of CNS-FAPP with others methods.
FAPP
TS-VN
H+CP
LS-CC
Tabu
CNS-FAPP
k
V
1
S
V
2
k
V
1
S
V
2
k
V
1
S
V
2
k
V
1
S
V
2
k
V
1
S
V
2
01-0200
4
4
56
4
6
279
4
14
165
5
1
281
4
14
233
02-0250
2
7
86
2
18
248
2
21
160
11
1
1274
2
20
195
03-0300
7
10
341
7
27
1076
7
16
420
7
13
589
7
32
892
04-0300
1
31
0
1
164
0
3
9
224
7
1
3678
1
184
0
05-0350
11
1
372
11
892
12364
11
1
1467
11
7
2284
11
364
5694
06-0500
5
12
246
5
53
1029
7
15
879
7
15
1210
5
31
811
07-0600
9
22
714
9
132
4419
10
28
3070
9
33
1585
9
106
3375
08-0700
5
16
266
5
53
1359
5
37
691
5
26
625
5
73
1225
09-0800
3
28
195
3
63
937
4
24
573
10
1
3678
3
104
846
10-0900
6
18
475
6
82
2365
6
39
1146
8
5
2871
6
103
2003
11-1000
8
8
1015
8
119
5206
9
30
3736
10
1
5108
8
119
4191
12-1500
3
83
1698
7
180
6538
11
17
2634
9
70
7682
2
62
1310
13-2000
3
49
2003
7
229
7503
11
59
6164
10
13
9651
5
132
3645
14-2500
4
35
3485
8
18
10661
11
3
5574
10
101
15718
5
217
5045
15-3000
5
15
1569
7
333
9988
11
46
9523
10
61
14010
5
192
4727
16-0260
11
5
56
11
572
5779
11
67
913
11
5
57
11
514
5189
17-0300
4
4
34
4
4
36
4
4
35
4
4
34
4
4
36
18-0350
8
4
55
8
4
55
8
4
57
8
4
55
8
4
59
19-0350
6
2
51
6
3
79
6
2
53
6
2
51
6
3
70
20-0420
10
5
97
10
6
145
10
5
99
10
5
97
10
7
142
21-0500
4
2
10
4
2
12
4
2
11
4
2
10
4
2
12
22-1750
7
15
187
7
16
356
7
16
194
7
15
187
7
25
503
23-1800
9
16
187
9
17
197
9
16
189
9
16
187
9
17
197
24-2000
7
6
71
7
7
90
7
7
79
7
6
71
7
9
91
25-2230
3
7
32
3
7
33
3
7
33
3
7
32
3
7
33
26-2300
7
9
74
7
10
81
7
9
74
7
9
74
7
10
86
27-2550
11
4
64
5
7
46
5
8
37
5
4
20
5
11
54
28-2800
3
13
32
3
32
129
3
25
58
3
13
32
3
42
142
29-2900
6
25
239
6
28
351
6
25
212
6
25
212
6
25
310
30-3000
11
1166
12029
7
17
602
7
16
190
7
13
148
7
48
1045
31-0400
5
4
1180
5
161
2131
5
34
1151
5
16
1400
5
117
1896
32-0550
10
52
1739
6
16
388
6
5
71
11
25
2166
6
10
235
33-0650
5
7
66
5
16
332
5
7
77
11
5
1310
5
10
235
34-0750
4
2
46
4
35
767
4
6
213
10
1
1701
4
22
565
35-1500
7
3
1280
6
74
1919
6
16
431
11
24
5870
6
62
1375
36-2000
7
99
2153
9
3
2478
8
25
970
11
16
4652
7
63
1643
37-2250
11
3
12229
5
56
1745
8
13
975
11
14
10353
5
51
1288
38-2500
11
79
14058
3
39
572
3
14
174
11
53
13355
9
125
6717
39-2750
3
356
2844
3
2567
10470
3
747
4603
11
36
13267
11
3947
40473
40-3000
11
39
16755
4
77
1562
8
20
1261
11
867
13684
4
64
1252The first approach, developed by Bisaillon’s team and referred to asTS-VN, is a local search based on tabu search with a variable neighborhood. The algorithm H+CP, developed by Caseau, combines constraint propagation with heuristics such as Large Neighborhood Search and Limited Discrepancy Search. The third method, LS-CC, developed by Gavranovic, is a typical local search guided by the constraint cost; at each level, it builds frequency trees, ignoring the polarization constraints, and then it tries to optimize the polarization allocation. In a similar way, classical tabu search procedures (simply denoted Tabu) working with complete solutions were implemented by Schindl’s team. Finally, the last column gives the results obtained by CNS-FAPP.We can observe the efficiency of CNS-FAPP when compared to the other methods. Care is needed because the indicated values are the best among 10. CNS-FAPP finds the optimalk level for 37 instances out of 40. And last but not least, CNS-FAPP was the winner of the Challenge!


## 4.1. Description of the Problem

The FAPP concerns a Hertzian telecommunication network made up of antennae located at a set of geographical sites. A Hertzian liaison joins two sites by one or more paths. Hence, apath is a unidirectional radioelectric bond, established between antennae at distinct sites, which has a given frequency and polarization. Let Fi and Pi, respectively, be the allowed frequency set and polarization set for path i, where Pi∈{{-1},{1},{-1,1}}. The FAPP consists in finding, for each path, a frequency and a polarization satisfying the following set of constraints.LetIC be the set of the imperative constraints, which are of four types: pi=pj, pi≠pj, |fi-fj|=εij, and |fi-fj|≠εij, where εij≥0. In addition, some electromagnetic compatibility constraints (ECCs) require a minimal distance between frequencies of two paths: |fi-fj|≥γij if pi=pj and |fi-fj|≥δij if pi≠pj. This constraint controls the interference phenomenon, which is why the required distance between frequencies depends on their polarizations; it is smaller if the polarizations are different (i.e., δij≤γij). Unfortunately, most problems do not have feasible solutions because the domains are too restrictive or the requirements too numerous. Consequently, some deterioration is allowed by permitting some interference, which have to be minimized. With this aim, for the ECC constraints, a progressive relaxation is authorized and expressed by relaxation levels; level 0 corresponds to no relaxation, and going from level k to level k+1 involves the relaxation of some or all the frequency gaps, the maximum relaxation level being 10. Formally, we have:
(1)|fi-fj|≥{γij0≥⋯≥γijk≥⋯≥γij10ifpi=pjδij0≥⋯≥δijk≥⋯≥δij10ifpi≠pj
since in the 11th level, γij11=δij11=0, so there is no ECC.LetECCk be the set of ECC constraints at level k (for 0≤k≤10). This means that each constraint belonging to ECCk is affected to its γijk and δijk gaps. More precisely, |fi-fj|≥(|pi+pj|/2)γij(k)+(|pi-pj|/2)δij(k). Accordingly, a feasible solution at level k is an assignment of all the paths satisfying all the strong constraints IC and all the ECCk constraints. If such a solution exists, the problem is said to be k-feasible. Every problem is assumed to be 11-feasible.Consequently, the objective function of the problem is, in order of priority to (1) minimize the lowest relaxation levelk for which a k-feasible solution exists (2) minimize V(k-1): the number of constraints of ECC(k-1) violated at level k-1, and (3) minimize ∑0≤i<k-1V(i): the sum of the constraints of ECCi violated at all levels i less than k-1.


## 4.2. Description of the Method within a CNS Framework

The strategy adopted for the resolution consists in transforming the FAPP optimization problem into 11 decision problems according to the relaxation level on theECC; each FAPP(k) contains both the IC and the ECCk constraints. This enables us to introduce some filtering treatments to reduce the frequency and the polarization domains. Starting from level k=11 where an initial solution is provided by a greedy constructive method, the general algorithm works in a downward fashion: each time a k-feasible solution is found, a lower level is considered.A solutions=(s1,…,sn) indicates for each path i its associated resource (fi,pi), where fi∈Fi and pi∈Pi. Thus, Di=Fi×Pi. In the assignment phase, a pair (fi,pi) is given to the chosen nonassigned candidate path i. Then, in the repairing phase, this affectation is propagated to its neighbors in the constraint network, and, if necessary, the conflicting neighboring values are deleted in order to satisfy the IC and ECCk constraints. This was done efficiently using incremental computing on specific data structures, allowing variable domains to be dynamically reduced.A tabu list is needed to prevent cycling, which occurs when there is an attempt to instantiate the last deleted variables in the current partial solution. Indeed, all the values (fj,pj) likely to delete the variable si=(fi,pj) affected by the move are classified tabu during some iterations; the tabu tenure is proportional to the number of times this resource was affected.The considered problem was the subject of the Challenge ROADEF 2001 (organized by the French Society of Operations Research and Decision Analysis), involving 27 research teams (seehttp://uma.ensta-paristech.fr/conf/roadef-2001-challenge/). In Table 2 are presented the results obtained by the five best teams. During the competition, only one run was allowed, and the computing time was limited to one hour on a Pentium 3 (500 MHZ, 128 MB of RAM). Table 2 details the hierarchical objective function, by giving first the relaxation level k, then the sum of all the unsatisfied ECCk-1, and finally the sum of all the unsatisfied ECCi, where i varies from 0 to k-2. The first column indicates the instance names with the instance number and the number n of considered paths. For example, 02-0250 is instance 2 with 250 paths.Table 2
Comparison of CNS-FAPP with others methods.
FAPP
TS-VN
H+CP
LS-CC
Tabu
CNS-FAPP
k
V
1
S
V
2
k
V
1
S
V
2
k
V
1
S
V
2
k
V
1
S
V
2
k
V
1
S
V
2
01-0200
4
4
56
4
6
279
4
14
165
5
1
281
4
14
233
02-0250
2
7
86
2
18
248
2
21
160
11
1
1274
2
20
195
03-0300
7
10
341
7
27
1076
7
16
420
7
13
589
7
32
892
04-0300
1
31
0
1
164
0
3
9
224
7
1
3678
1
184
0
05-0350
11
1
372
11
892
12364
11
1
1467
11
7
2284
11
364
5694
06-0500
5
12
246
5
53
1029
7
15
879
7
15
1210
5
31
811
07-0600
9
22
714
9
132
4419
10
28
3070
9
33
1585
9
106
3375
08-0700
5
16
266
5
53
1359
5
37
691
5
26
625
5
73
1225
09-0800
3
28
195
3
63
937
4
24
573
10
1
3678
3
104
846
10-0900
6
18
475
6
82
2365
6
39
1146
8
5
2871
6
103
2003
11-1000
8
8
1015
8
119
5206
9
30
3736
10
1
5108
8
119
4191
12-1500
3
83
1698
7
180
6538
11
17
2634
9
70
7682
2
62
1310
13-2000
3
49
2003
7
229
7503
11
59
6164
10
13
9651
5
132
3645
14-2500
4
35
3485
8
18
10661
11
3
5574
10
101
15718
5
217
5045
15-3000
5
15
1569
7
333
9988
11
46
9523
10
61
14010
5
192
4727
16-0260
11
5
56
11
572
5779
11
67
913
11
5
57
11
514
5189
17-0300
4
4
34
4
4
36
4
4
35
4
4
34
4
4
36
18-0350
8
4
55
8
4
55
8
4
57
8
4
55
8
4
59
19-0350
6
2
51
6
3
79
6
2
53
6
2
51
6
3
70
20-0420
10
5
97
10
6
145
10
5
99
10
5
97
10
7
142
21-0500
4
2
10
4
2
12
4
2
11
4
2
10
4
2
12
22-1750
7
15
187
7
16
356
7
16
194
7
15
187
7
25
503
23-1800
9
16
187
9
17
197
9
16
189
9
16
187
9
17
197
24-2000
7
6
71
7
7
90
7
7
79
7
6
71
7
9
91
25-2230
3
7
32
3
7
33
3
7
33
3
7
32
3
7
33
26-2300
7
9
74
7
10
81
7
9
74
7
9
74
7
10
86
27-2550
11
4
64
5
7
46
5
8
37
5
4
20
5
11
54
28-2800
3
13
32
3
32
129
3
25
58
3
13
32
3
42
142
29-2900
6
25
239
6
28
351
6
25
212
6
25
212
6
25
310
30-3000
11
1166
12029
7
17
602
7
16
190
7
13
148
7
48
1045
31-0400
5
4
1180
5
161
2131
5
34
1151
5
16
1400
5
117
1896
32-0550
10
52
1739
6
16
388
6
5
71
11
25
2166
6
10
235
33-0650
5
7
66
5
16
332
5
7
77
11
5
1310
5
10
235
34-0750
4
2
46
4
35
767
4
6
213
10
1
1701
4
22
565
35-1500
7
3
1280
6
74
1919
6
16
431
11
24
5870
6
62
1375
36-2000
7
99
2153
9
3
2478
8
25
970
11
16
4652
7
63
1643
37-2250
11
3
12229
5
56
1745
8
13
975
11
14
10353
5
51
1288
38-2500
11
79
14058
3
39
572
3
14
174
11
53
13355
9
125
6717
39-2750
3
356
2844
3
2567
10470
3
747
4603
11
36
13267
11
3947
40473
40-3000
11
39
16755
4
77
1562
8
20
1261
11
867
13684
4
64
1252The first approach, developed by Bisaillon’s team and referred to asTS-VN, is a local search based on tabu search with a variable neighborhood. The algorithm H+CP, developed by Caseau, combines constraint propagation with heuristics such as Large Neighborhood Search and Limited Discrepancy Search. The third method, LS-CC, developed by Gavranovic, is a typical local search guided by the constraint cost; at each level, it builds frequency trees, ignoring the polarization constraints, and then it tries to optimize the polarization allocation. In a similar way, classical tabu search procedures (simply denoted Tabu) working with complete solutions were implemented by Schindl’s team. Finally, the last column gives the results obtained by CNS-FAPP.We can observe the efficiency of CNS-FAPP when compared to the other methods. Care is needed because the indicated values are the best among 10. CNS-FAPP finds the optimalk level for 37 instances out of 40. And last but not least, CNS-FAPP was the winner of the Challenge!


## 5. Fleet Management with Maintenance Constraints

The main reference associated with this section is [19], where a rather complex solution method was proposed for a problem which can be formulated as a car fleet management problem with maintenance constraints (but denoted CAR for the sake of simplicity). The particularity of the problem is that feasible solutions are very easy to find, but can cost a lot. Thus, S(partial) was designed to avoid to assign the most expensive value to each variable.


### 5.1. Description of the Problem

The problem retained for the Challenge ROADEF 1999 was an inventory management problem (seehttp://www.roadef.org/content/roadef/challenge.htm  for the details), where a cost function has to be minimized. A car rental company manages a stock of cars of different types. It receives requests from customers asking for cars of specific types for a given time horizon. Basically a request is characterized by its start and end times, by a required car type, and by the number of required cars. All requests are supposed to be known for the considered time horizon. The satisfaction of all customer requests is mandatory. If there are not enough cars available in stock, the company can react in three different ways: (1) upgrading: it can offer a better car type to the customer (but the company encounters the additional associated cost); (2) subcontracting: the company can decide to subcontract some requests to other providers, which is generally the most expensive alternative; (3) purchasing new cars, which then belong to the stock of the company for the rest of the time horizon.Two types of maintenance constraints make the problem difficult: (1) a maximum time of use without maintenance is given for each car type (each maintenance has a duration, a cost and a number of workers needed to perform it); (2) the company has a fixed number of maintenance workers, which means that the maintenances should be scheduled so that the capacity of the workshop is never exceeded. In addition, the following costs are also known: the costs (fixed and time dependent) associated with the assignment of a car to a request, and the inventory cost per day of a car in stock (rented or not). The goal is to satisfy all the requests while minimizing the total cost.


### 5.2. Description of the Method within a CNS Framework

The general pseudocode of the method, denoted CNS-CAR, is summarized in Algorithm2. First, an initial solution is greedily generated. Step 1 of the main loop tries to improve the current solution without changing the set of purchased cars (with the use of two tabu search procedures working in S(partial), denoted TS1-CAR and TS2-CAR below), while the second step generates a new solution with a different set of purchased cars. The stopping criterion is a time limit of one hour, as imposed by the organizers of the Challenge.Algorithm 2:Algorithm CNS-CAR.
Initialization: generate an initial solution s;
While the time limit is not reached, do
1.  try to improves without changing the set of purchased cars, with the successive use of TS1-CAR and TS2-CAR;
2.  updates by purchasing a car or by removing a previously purchased car (the requests associated with a removed car
are initially subcontracted).In TS1-CAR, a solutions can be modeled as follows. Let sr=t if request r is performed by a car of type t of the fleet (purchased or not), and sr has no value (or an artificial value, say 0) if request r is subcontracted to another provider. Thus, S(partial) is defined in order to minimize the number of subcontracted requests. A neighbor s′ of a solution s is obtained by assigning a car c of type t to a subcontracted request r (i.e., the corresponding sr equals t instead of 0). To make such a change feasible, in the repairing phase, requests covered by c that overlap with r are subcontracted (i.e., the associated sj values are set to 0), and the maintenances of car c are possibly rescheduled in a greedy fashion while satisfying the maintenance constraints. If it is not possible, other sj’s such that sj=t might be set to 0 in order to create more room to schedule the maintenances. If it is still not possible to generate a feasible schedule for the maintenances (because of the maintenances schedule of the other car types), such a move is not considered further.TS2-CAR is an extension of TS1-CAR in the following sense: (1) it works on several car types during the same move; (2) it tries to reduce the total cost not only by assigning cars to subcontracted requests, but also by avoiding upgrades; (3) a reassignment phase is performed; (4) the repairing phase has more options to validate the move proposed in the assignment phase. A neighbors′ of a solution s is obtained by assigning a car of type t to a request r, where r is subcontracted or covered by a car of type t′≠t in s, where type t′ is an upgrade of type t. In other words, sr equals t instead of 0 or t′. The reassignment and repairing phases are performed simultaneously as follows: all the requests Ct covered by the cars of type t might be reassigned within car type t (while considering an exact method for a specific case of the graph coloring problem), and it is allowed to subcontract some requests of Ct. In such a phase, the maintenance schedule of all the cars might change (in a greedy fashion or by the use of an exact method). In the two tabu procedures, when a request r is assigned to a car type t (i.e., sr is set equal to t), it is then tabu to remove the value t from sr for a certain number of iterations.Diversification procedures were also used, based on the following idea: the requests which were not subcontracted from a large number of iterations are subcontracted, in order to make room for other requests in the schedule.


### 5.3. Numerical Comparison with Other Methods

In Tables3 and 4 the results for the 16 benchmark instances of the Challenge are reported. CNS-CAR is compared with the four best methods (among the thirteen proposed heuristics) of the Challenge. The winners of the contest were Briant and Bouzgarrou. Their algorithm mainly combines linear programming ignoring the maintenance constraints and then adjust the solution according to the maintenance constraints. The name of an instance is coded with a vector (x,y,z,w), where x is the number of requests, y is the number of car types, z is the capacity of the workshop, and w is equal to b if purchases are allowed, and to nb otherwise. The time horizon of all instances is [0,730] corresponding to a period of 2 years.Table 3
Results for the instances without purchase.
Instance
Best
BB
AGHKU
B
DD
CNS-CAR
(80, 8, 2,nb)
1162285
*
0.00%
0.05%
1.31%
8.47%
0.00%
(150, 7, 2,nb)
3280230
*
0.87%
5.85%
5.03%
9.73%
0.00%
(160, 12, 2,nb)
3333599
*
14.63%
19.68%
29.56%
20.51%
0.81%
(200, 12, 2,nb)
5450785
*
7.77%
22.56%
25.52%
26.02%
2.59%
(200, 7, 2,nb)
5156915
*
6.36%
12.61%
21.02%
31.93%
3.62%
(200, 7, 4,nb)
4558728
*
0.00%
0.66%
3.26%
14.45%
0.00%
(210, 9, 2,nb)
5810288
*
5.67%
10.76%
18.48%
27.11%
2.42%
(210, 9, 4,nb)
5135237
*
1.82%
1.44%
3.46%
13.09%
0.12%
Average
4236008
4.64%
9.20%
13.46%
18.91%
1.20%Table 4
Results for the instances with purchase.
Instance
Best
BB
AGHKU
B
DD
CNS-CAR
(80, 8, 2,b)
1145181
*
0.00%
1.55%
2.82%
7.23%
0.04%
(150, 7, 2,b)
2811138
0.00%
9.40%
3.98%
13.23%
0.01%
(160, 12, 2,b)
3064397
*
11.99%
29.40%
26.08%
21.98%
1.47%
(200, 12, 2,b)
4517706
*
12.42%
34.97%
35.93%
38.13%
4.88%
(200, 7, 2,b)
4990499
*
6.88%
15.36%
27.76%
31.38%
4.98%
(200, 7, 4,b)
4092002
*
0.00%
3.00%
3.46%
12.76%
0.01%
(210, 9, 2,b)
5380588
*
7.38%
18.91%
29.31%
34.15%
3.52%
(210, 9, 4,b)
4147087
*
8.71%
10.92%
9.19%
14.91%
0.01%
Average
3787302
5.92%
15.44%
17.32%
21.72%
1.86%The algorithm was run with the time limit equivalent to one hour on a Pentium Pro (200 MHZ, 64 MB of RAM), as imposed by the organizers of the challenge. The results are shown in Table3 (for instances where purchases are forbidden) and Table 4 (associated with the same instances, but where purchases are allowed). The column labeled Best contains the best known solution for each instance. An asterisk is put when CNS-CAR was able to equal or improve the previous best known solution. Some of these best results have been obtained when using different parameters from those mentioned above (for tuning purposes) or by running CNS-CAR for more than one hour. The next four columns contain the percentage gap with respect to Best obtained by the four best methods, labeled with the initials of the members of each team, namely, BB (for Briant and Bouzgarrou), AGHKU (for Asdemir, Karslioğlu, Gürbüz, and Ünal), B (for Bayrak), and DD (for Dhaenens-Flipo and Durand). The next column contains the percentage gap with respect to Best obtained with CNS-CAR. For each instance, ten runs of CNS-CAR were executed, and average results are reported. The last line of each column indicates average results. We can observe that CNS-CAR gives in average better results than those obtained by the four best competitors of the Challenge.


## 5.1. Description of the Problem

The problem retained for the Challenge ROADEF 1999 was an inventory management problem (seehttp://www.roadef.org/content/roadef/challenge.htm  for the details), where a cost function has to be minimized. A car rental company manages a stock of cars of different types. It receives requests from customers asking for cars of specific types for a given time horizon. Basically a request is characterized by its start and end times, by a required car type, and by the number of required cars. All requests are supposed to be known for the considered time horizon. The satisfaction of all customer requests is mandatory. If there are not enough cars available in stock, the company can react in three different ways: (1) upgrading: it can offer a better car type to the customer (but the company encounters the additional associated cost); (2) subcontracting: the company can decide to subcontract some requests to other providers, which is generally the most expensive alternative; (3) purchasing new cars, which then belong to the stock of the company for the rest of the time horizon.Two types of maintenance constraints make the problem difficult: (1) a maximum time of use without maintenance is given for each car type (each maintenance has a duration, a cost and a number of workers needed to perform it); (2) the company has a fixed number of maintenance workers, which means that the maintenances should be scheduled so that the capacity of the workshop is never exceeded. In addition, the following costs are also known: the costs (fixed and time dependent) associated with the assignment of a car to a request, and the inventory cost per day of a car in stock (rented or not). The goal is to satisfy all the requests while minimizing the total cost.


## 5.2. Description of the Method within a CNS Framework

The general pseudocode of the method, denoted CNS-CAR, is summarized in Algorithm2. First, an initial solution is greedily generated. Step 1 of the main loop tries to improve the current solution without changing the set of purchased cars (with the use of two tabu search procedures working in S(partial), denoted TS1-CAR and TS2-CAR below), while the second step generates a new solution with a different set of purchased cars. The stopping criterion is a time limit of one hour, as imposed by the organizers of the Challenge.Algorithm 2:Algorithm CNS-CAR.
Initialization: generate an initial solution s;
While the time limit is not reached, do
1.  try to improves without changing the set of purchased cars, with the successive use of TS1-CAR and TS2-CAR;
2.  updates by purchasing a car or by removing a previously purchased car (the requests associated with a removed car
are initially subcontracted).In TS1-CAR, a solutions can be modeled as follows. Let sr=t if request r is performed by a car of type t of the fleet (purchased or not), and sr has no value (or an artificial value, say 0) if request r is subcontracted to another provider. Thus, S(partial) is defined in order to minimize the number of subcontracted requests. A neighbor s′ of a solution s is obtained by assigning a car c of type t to a subcontracted request r (i.e., the corresponding sr equals t instead of 0). To make such a change feasible, in the repairing phase, requests covered by c that overlap with r are subcontracted (i.e., the associated sj values are set to 0), and the maintenances of car c are possibly rescheduled in a greedy fashion while satisfying the maintenance constraints. If it is not possible, other sj’s such that sj=t might be set to 0 in order to create more room to schedule the maintenances. If it is still not possible to generate a feasible schedule for the maintenances (because of the maintenances schedule of the other car types), such a move is not considered further.TS2-CAR is an extension of TS1-CAR in the following sense: (1) it works on several car types during the same move; (2) it tries to reduce the total cost not only by assigning cars to subcontracted requests, but also by avoiding upgrades; (3) a reassignment phase is performed; (4) the repairing phase has more options to validate the move proposed in the assignment phase. A neighbors′ of a solution s is obtained by assigning a car of type t to a request r, where r is subcontracted or covered by a car of type t′≠t in s, where type t′ is an upgrade of type t. In other words, sr equals t instead of 0 or t′. The reassignment and repairing phases are performed simultaneously as follows: all the requests Ct covered by the cars of type t might be reassigned within car type t (while considering an exact method for a specific case of the graph coloring problem), and it is allowed to subcontract some requests of Ct. In such a phase, the maintenance schedule of all the cars might change (in a greedy fashion or by the use of an exact method). In the two tabu procedures, when a request r is assigned to a car type t (i.e., sr is set equal to t), it is then tabu to remove the value t from sr for a certain number of iterations.Diversification procedures were also used, based on the following idea: the requests which were not subcontracted from a large number of iterations are subcontracted, in order to make room for other requests in the schedule.


## 5.3. Numerical Comparison with Other Methods

In Tables3 and 4 the results for the 16 benchmark instances of the Challenge are reported. CNS-CAR is compared with the four best methods (among the thirteen proposed heuristics) of the Challenge. The winners of the contest were Briant and Bouzgarrou. Their algorithm mainly combines linear programming ignoring the maintenance constraints and then adjust the solution according to the maintenance constraints. The name of an instance is coded with a vector (x,y,z,w), where x is the number of requests, y is the number of car types, z is the capacity of the workshop, and w is equal to b if purchases are allowed, and to nb otherwise. The time horizon of all instances is [0,730] corresponding to a period of 2 years.Table 3
Results for the instances without purchase.
Instance
Best
BB
AGHKU
B
DD
CNS-CAR
(80, 8, 2,nb)
1162285
*
0.00%
0.05%
1.31%
8.47%
0.00%
(150, 7, 2,nb)
3280230
*
0.87%
5.85%
5.03%
9.73%
0.00%
(160, 12, 2,nb)
3333599
*
14.63%
19.68%
29.56%
20.51%
0.81%
(200, 12, 2,nb)
5450785
*
7.77%
22.56%
25.52%
26.02%
2.59%
(200, 7, 2,nb)
5156915
*
6.36%
12.61%
21.02%
31.93%
3.62%
(200, 7, 4,nb)
4558728
*
0.00%
0.66%
3.26%
14.45%
0.00%
(210, 9, 2,nb)
5810288
*
5.67%
10.76%
18.48%
27.11%
2.42%
(210, 9, 4,nb)
5135237
*
1.82%
1.44%
3.46%
13.09%
0.12%
Average
4236008
4.64%
9.20%
13.46%
18.91%
1.20%Table 4
Results for the instances with purchase.
Instance
Best
BB
AGHKU
B
DD
CNS-CAR
(80, 8, 2,b)
1145181
*
0.00%
1.55%
2.82%
7.23%
0.04%
(150, 7, 2,b)
2811138
0.00%
9.40%
3.98%
13.23%
0.01%
(160, 12, 2,b)
3064397
*
11.99%
29.40%
26.08%
21.98%
1.47%
(200, 12, 2,b)
4517706
*
12.42%
34.97%
35.93%
38.13%
4.88%
(200, 7, 2,b)
4990499
*
6.88%
15.36%
27.76%
31.38%
4.98%
(200, 7, 4,b)
4092002
*
0.00%
3.00%
3.46%
12.76%
0.01%
(210, 9, 2,b)
5380588
*
7.38%
18.91%
29.31%
34.15%
3.52%
(210, 9, 4,b)
4147087
*
8.71%
10.92%
9.19%
14.91%
0.01%
Average
3787302
5.92%
15.44%
17.32%
21.72%
1.86%The algorithm was run with the time limit equivalent to one hour on a Pentium Pro (200 MHZ, 64 MB of RAM), as imposed by the organizers of the challenge. The results are shown in Table3 (for instances where purchases are forbidden) and Table 4 (associated with the same instances, but where purchases are allowed). The column labeled Best contains the best known solution for each instance. An asterisk is put when CNS-CAR was able to equal or improve the previous best known solution. Some of these best results have been obtained when using different parameters from those mentioned above (for tuning purposes) or by running CNS-CAR for more than one hour. The next four columns contain the percentage gap with respect to Best obtained by the four best methods, labeled with the initials of the members of each team, namely, BB (for Briant and Bouzgarrou), AGHKU (for Asdemir, Karslioğlu, Gürbüz, and Ünal), B (for Bayrak), and DD (for Dhaenens-Flipo and Durand). The next column contains the percentage gap with respect to Best obtained with CNS-CAR. For each instance, ten runs of CNS-CAR were executed, and average results are reported. The last line of each column indicates average results. We can observe that CNS-CAR gives in average better results than those obtained by the four best competitors of the Challenge.


## 6.  Satellite Range Scheduling

The main reference associated with this section is [20], in which the problem is referred to as the daily photograph scheduling of an earth observation satellite (but only denoted SAT below). The authors proposed a tabu search approach working in S(partial) denoted CNS-SAT below. Note that CNS kind of approaches were also very successfully adapted to other satellite range scheduling problems: the multi-resource satellite range scheduling problem [21] where more than one resource are available, and a satellite range scheduling with partial acquisition and transition times [22].


### 6.1. Description of the Problem

The considered satellite range scheduling problem can be described as follows [23]. Let P={p1,…,pn} be the set of n candidate photographs which can be scheduled to be taken on the next day. A set of possibilities is associated with each photograph pi corresponding to the different ways to take pi: (1) for a mono pi, there are three possibilities because a monophotograph can be taken by any of the three cameras (front, middle, and rear) on the satellite; (2) for a stereo pi, there is one single possibility because a stereo photograph requires simultaneously the front and the rear camera. With each monophotograph pi∈P are associated three pairs of elements (pi,camera_1),(pi,camera_2), and (pi,camera_3). Similarly, with each stereo photograph pi∈P is associated one pair (pi,camera_13). Letting n1 and n2 be, respectively, the number of mono- and stereophotographs in P (where n=n1+n2), there are in total m=3·n1+n2 possible pairs of elements for the given set P of candidates. Now, associating a binary (decision) variable si with each such pair, a photograph schedule corresponds to a binary vector: s=(s1,s2,…,sm), where si=1 if the corresponding pair (photo, camera) is present in the schedule, and si=0 otherwise. For example, if P={p1,p2,p3} where p1 and p2 are monophotographs and p3 is a stereophotograph, then s=(1,0,0,0,0,0,1) represents a schedule in which p1 is taken by camera 1, p2 is rejected, and p3 is taken by cameras 1 and 3.The SAT is to find a subsetP′ of P which satisfies all the imperative constraints and maximizes the sum of the profits of the photographs in P′. The objective function can be defined as follows. First, the profit of a pair (p, camera) (or its 0-1 variable) is defined as the profit of the photograph p. The total profit of all the pairs of the given set P is then represented by a vector: g=(g1,g2,…,gm), where gi=gj(i≠j) if gi and gj correspond to two different pairs of elements involving the same photograph p, that is, (p, camera_x) and (p, camera_y). Then the total profit value of a schedule s=(s1,s2,…,sm) is the sum of the profits of the photographs in s, that is, f(s)=∑i=1mgi·si.A capacity constraint is the following. A size is associated with each photographpi, which represents the amount of memory required to record pi when it is taken. The size of a pair (p, camera) (or its 0-1 variable) is defined as the size of the photograph p. The total size of all the pairs of the given set P is then represented by a vector: c=(c1,c2,…,cm), where ci=cj(i≠j) if ci and cj correspond to two different pairs of elements involving the same photograph p, that is, (p, camera_x) and (p, camera_y). The capacity constraint states that the sum of the sizes of the photographs in a schedule s=(s1,s2,…,sm) cannot exceed the maximal recording capacity on board, which is expressed as ∑i=1mci·si≤Max_capacity.Binary constraints involving the nonoverlapping of two trials and the minimal transition time between two successive trials of a camera, and also some constraints involving limitations on instantaneous data flow are conveniently expressed by simple relations over two pairs (photo and camera). A binary constraint forbids the simultaneous presence of a pair(pi,ki) and another pair (pj,kj) in a schedule. If si and sj are the corresponding decision variables of such two pairs, then a binary constraint is defined as follows: si+sj≤1. Let C2 denote the set of all such pairs (si,sj) which should verify the above binary constraint.Some constraints involving limitations on instantaneous data flow cannot be expressed in the form of binary constraints as above. These remaining constraints may however be expressed by relations over three pairs (photo and camera). A ternary constraint forbids the simultaneous presence of three pairs(pi,ki),(pj,kj), and (pl,kl). Letting si,sj, and sl be the decision variables corresponding to these pairs, then such a ternary constraint is written as follow si+sj+sl≤2. Let C3_1 denote the set of all such triplets (si,sj,sl) which should verify this ternary constraint.Finally, we need to be sure that a schedule contains no more than one pair from{(p,ki),(p,kj),(p,kl)} for any (mono) photograph p. Letting si,sj and sl be the decision variables corresponding to these pairs, then this ternary constraint is expressed as si+sj+sl≤1. Clearly there are exactly n1 ternary constraints of this type. Let C3_2 denote the set of all such triplets (si,sj,sl) which verify this second type of ternary constraints. C3 denotes the union of C3_1 and C3_2, that is, C3 = C3_1 ∪ C3_2.


### 6.2. Description of the Method

In contrast with the previous problems where all the constraints are considered to define the search space, a partially constrained search space C is considered here, which is composed of all binary vectors ofm elements satisfying constraints C2 and C3 above. The relaxation of the capacity constraint helps to obtain better results and to accelerate the search. Let s=(s1,s2,…,sm)∈ C and s′=(s1′,s2′,…,sm′), and then s′ is a neighbor of s, that is, s′∈N(s), if and only if the following conditions are verified: (1)
there is only onei such that si=0 and si′=1, for 1≤i≤m,(2)
for the abovei, for all (si,sj)∈ C2, sj′=0 for 1≤j≤m, and(3)
for the abovei, for all (si,sj,sk)∈ C3_1, sj′+sk′≤1 for 1≤j,k≤m.Thus, a neighbor ofs can be obtained by adding a pair (photo and camera) (i.e., flipping a variable si from 0 to 1) in the current schedule and then dropping some pairs (photo and camera) (i.e., flipping some sj’s from 1 to 0) to repair binary and ternary constraint violations.During the search, the capacity constraint may be violated by the current solutions=(s1,s2,…,sm); that is, the total size of s may exceed the maximal allowed capacity. To satisfy the capacity constraint, the following mechanism is used. Each time the current solution is improved, the capacity constraint is checked. If the constraint is violated, the solution is immediately repaired by suppressing the elements si which have the worst ratio gi/ci until the capacity constraint is satisfied.Each time a move is carried out, a single variablesi flips from 0 to 1, and several sj’s flip from 1 to 0. It is then tabu to flip again these sj values from 0 to 1 during tabu(j) iterations, where tabu(j)=C(j)+α·freq(j), where C(j) is the number of binary and ternary constraints involving the element sj, freq(j) the number of times sj is flipped from 1 to 0 from the beginning of the search, and α is an instance-dependent coefficient which defines a penalty factor for each move. To explain this, a variable involved in a large number of constraints has naturally more risk to be flipped during a move than a variable having few constraints on it. It is thus logic to give a longer tabu tenure for a move whose variable has many constraints on it. The second part of the function aims to penalize a move which repeats too often. Note that intensification and diversification procedures were also used to enhance the efficiency of the general method.


### 6.3. Numerical Comparison with Other Methods

Experiments are carried out on a set of 20 realistic instances provided by the CNES (French National Space Agency) and described in details in [23]. These instances belong to two different sets: without capacity constraint (13 instances) and with capacity constraint (7 instances). The instances without capacity constraints, as well as one instance with capacity constraint, will not be commented; it is very easy to solve them, either with an exact method or with the above-described CNS-SAT algorithm. The other six instances have from 488 to 1057 candidate photographs, giving up to 2355 binary variables and 35933 constraints. Existing exact algorithms are unable to solve optimally these instances.The best known nonexact algorithm was a tabu search TS-SAT proposed by the CNES. The main differences with CNS-SAT algorithm are the following. (1) TS-SAT uses a different (integer) formulation of the problem; (2) it manipulates only feasible solutions (the search space is thusS(feasible)); (3) it uses a different neighborhood structure; (4) it considers only a sample of neighbor solutions to make a move; (5) the tabu tenure for each move is randomly taken from predefined (very small) ranges.To solve an instance, CNS-SAT is allowed to run 9 million iterations on a PC (200 MHZ, 32 MB of RAM), which is considered as reasonable by the CNES. CNS-SAT was run 100 times on each instance with different random seeds, and the average value is returned for each instance. The first three columns of Table5 give the name of the instance, the number of candidate photographs n, and the number of 0-1 variables m. Columns 4 and 5, respectively, show the best profit fTS* and the associated computing time timeTS (in seconds) obtained with TS-SAT. Columns 6-7 give the average profit value f¯CNS and the average time timeCNS needed by CNS-SAT to find such a solution. It is easy to see that CNS-SAT is much more efficient and quicker than TS-SAT (see also the line labeled “Average”).Table 5
Comparison between TS-SAT and CNS-SAT.
Instance
n
m
f
TS
*
TimeTS
f
-
CNS
TimeCNS
1401
488
914
174058
846
176055
120
1403
665
1317
174137
1324
176134
332
1405
855
1815
174174
1574
176175
1314
1021
1057
2355
174238
2197
176241
2422
1504
605
1253
124238
1011
124241
405
1506
940
2060
165244
1945
168224
1423
Average
164348.17
1272.86
166178.33
859.57


## 6.1. Description of the Problem

The considered satellite range scheduling problem can be described as follows [23]. Let P={p1,…,pn} be the set of n candidate photographs which can be scheduled to be taken on the next day. A set of possibilities is associated with each photograph pi corresponding to the different ways to take pi: (1) for a mono pi, there are three possibilities because a monophotograph can be taken by any of the three cameras (front, middle, and rear) on the satellite; (2) for a stereo pi, there is one single possibility because a stereo photograph requires simultaneously the front and the rear camera. With each monophotograph pi∈P are associated three pairs of elements (pi,camera_1),(pi,camera_2), and (pi,camera_3). Similarly, with each stereo photograph pi∈P is associated one pair (pi,camera_13). Letting n1 and n2 be, respectively, the number of mono- and stereophotographs in P (where n=n1+n2), there are in total m=3·n1+n2 possible pairs of elements for the given set P of candidates. Now, associating a binary (decision) variable si with each such pair, a photograph schedule corresponds to a binary vector: s=(s1,s2,…,sm), where si=1 if the corresponding pair (photo, camera) is present in the schedule, and si=0 otherwise. For example, if P={p1,p2,p3} where p1 and p2 are monophotographs and p3 is a stereophotograph, then s=(1,0,0,0,0,0,1) represents a schedule in which p1 is taken by camera 1, p2 is rejected, and p3 is taken by cameras 1 and 3.The SAT is to find a subsetP′ of P which satisfies all the imperative constraints and maximizes the sum of the profits of the photographs in P′. The objective function can be defined as follows. First, the profit of a pair (p, camera) (or its 0-1 variable) is defined as the profit of the photograph p. The total profit of all the pairs of the given set P is then represented by a vector: g=(g1,g2,…,gm), where gi=gj(i≠j) if gi and gj correspond to two different pairs of elements involving the same photograph p, that is, (p, camera_x) and (p, camera_y). Then the total profit value of a schedule s=(s1,s2,…,sm) is the sum of the profits of the photographs in s, that is, f(s)=∑i=1mgi·si.A capacity constraint is the following. A size is associated with each photographpi, which represents the amount of memory required to record pi when it is taken. The size of a pair (p, camera) (or its 0-1 variable) is defined as the size of the photograph p. The total size of all the pairs of the given set P is then represented by a vector: c=(c1,c2,…,cm), where ci=cj(i≠j) if ci and cj correspond to two different pairs of elements involving the same photograph p, that is, (p, camera_x) and (p, camera_y). The capacity constraint states that the sum of the sizes of the photographs in a schedule s=(s1,s2,…,sm) cannot exceed the maximal recording capacity on board, which is expressed as ∑i=1mci·si≤Max_capacity.Binary constraints involving the nonoverlapping of two trials and the minimal transition time between two successive trials of a camera, and also some constraints involving limitations on instantaneous data flow are conveniently expressed by simple relations over two pairs (photo and camera). A binary constraint forbids the simultaneous presence of a pair(pi,ki) and another pair (pj,kj) in a schedule. If si and sj are the corresponding decision variables of such two pairs, then a binary constraint is defined as follows: si+sj≤1. Let C2 denote the set of all such pairs (si,sj) which should verify the above binary constraint.Some constraints involving limitations on instantaneous data flow cannot be expressed in the form of binary constraints as above. These remaining constraints may however be expressed by relations over three pairs (photo and camera). A ternary constraint forbids the simultaneous presence of three pairs(pi,ki),(pj,kj), and (pl,kl). Letting si,sj, and sl be the decision variables corresponding to these pairs, then such a ternary constraint is written as follow si+sj+sl≤2. Let C3_1 denote the set of all such triplets (si,sj,sl) which should verify this ternary constraint.Finally, we need to be sure that a schedule contains no more than one pair from{(p,ki),(p,kj),(p,kl)} for any (mono) photograph p. Letting si,sj and sl be the decision variables corresponding to these pairs, then this ternary constraint is expressed as si+sj+sl≤1. Clearly there are exactly n1 ternary constraints of this type. Let C3_2 denote the set of all such triplets (si,sj,sl) which verify this second type of ternary constraints. C3 denotes the union of C3_1 and C3_2, that is, C3 = C3_1 ∪ C3_2.


## 6.2. Description of the Method

In contrast with the previous problems where all the constraints are considered to define the search space, a partially constrained search space C is considered here, which is composed of all binary vectors ofm elements satisfying constraints C2 and C3 above. The relaxation of the capacity constraint helps to obtain better results and to accelerate the search. Let s=(s1,s2,…,sm)∈ C and s′=(s1′,s2′,…,sm′), and then s′ is a neighbor of s, that is, s′∈N(s), if and only if the following conditions are verified: (1)
there is only onei such that si=0 and si′=1, for 1≤i≤m,(2)
for the abovei, for all (si,sj)∈ C2, sj′=0 for 1≤j≤m, and(3)
for the abovei, for all (si,sj,sk)∈ C3_1, sj′+sk′≤1 for 1≤j,k≤m.Thus, a neighbor ofs can be obtained by adding a pair (photo and camera) (i.e., flipping a variable si from 0 to 1) in the current schedule and then dropping some pairs (photo and camera) (i.e., flipping some sj’s from 1 to 0) to repair binary and ternary constraint violations.During the search, the capacity constraint may be violated by the current solutions=(s1,s2,…,sm); that is, the total size of s may exceed the maximal allowed capacity. To satisfy the capacity constraint, the following mechanism is used. Each time the current solution is improved, the capacity constraint is checked. If the constraint is violated, the solution is immediately repaired by suppressing the elements si which have the worst ratio gi/ci until the capacity constraint is satisfied.Each time a move is carried out, a single variablesi flips from 0 to 1, and several sj’s flip from 1 to 0. It is then tabu to flip again these sj values from 0 to 1 during tabu(j) iterations, where tabu(j)=C(j)+α·freq(j), where C(j) is the number of binary and ternary constraints involving the element sj, freq(j) the number of times sj is flipped from 1 to 0 from the beginning of the search, and α is an instance-dependent coefficient which defines a penalty factor for each move. To explain this, a variable involved in a large number of constraints has naturally more risk to be flipped during a move than a variable having few constraints on it. It is thus logic to give a longer tabu tenure for a move whose variable has many constraints on it. The second part of the function aims to penalize a move which repeats too often. Note that intensification and diversification procedures were also used to enhance the efficiency of the general method.


## 6.3. Numerical Comparison with Other Methods

Experiments are carried out on a set of 20 realistic instances provided by the CNES (French National Space Agency) and described in details in [23]. These instances belong to two different sets: without capacity constraint (13 instances) and with capacity constraint (7 instances). The instances without capacity constraints, as well as one instance with capacity constraint, will not be commented; it is very easy to solve them, either with an exact method or with the above-described CNS-SAT algorithm. The other six instances have from 488 to 1057 candidate photographs, giving up to 2355 binary variables and 35933 constraints. Existing exact algorithms are unable to solve optimally these instances.The best known nonexact algorithm was a tabu search TS-SAT proposed by the CNES. The main differences with CNS-SAT algorithm are the following. (1) TS-SAT uses a different (integer) formulation of the problem; (2) it manipulates only feasible solutions (the search space is thusS(feasible)); (3) it uses a different neighborhood structure; (4) it considers only a sample of neighbor solutions to make a move; (5) the tabu tenure for each move is randomly taken from predefined (very small) ranges.To solve an instance, CNS-SAT is allowed to run 9 million iterations on a PC (200 MHZ, 32 MB of RAM), which is considered as reasonable by the CNES. CNS-SAT was run 100 times on each instance with different random seeds, and the average value is returned for each instance. The first three columns of Table5 give the name of the instance, the number of candidate photographs n, and the number of 0-1 variables m. Columns 4 and 5, respectively, show the best profit fTS* and the associated computing time timeTS (in seconds) obtained with TS-SAT. Columns 6-7 give the average profit value f¯CNS and the average time timeCNS needed by CNS-SAT to find such a solution. It is easy to see that CNS-SAT is much more efficient and quicker than TS-SAT (see also the line labeled “Average”).Table 5
Comparison between TS-SAT and CNS-SAT.
Instance
n
m
f
TS
*
TimeTS
f
-
CNS
TimeCNS
1401
488
914
174058
846
176055
120
1403
665
1317
174137
1324
176134
332
1405
855
1815
174174
1574
176175
1314
1021
1057
2355
174238
2197
176241
2422
1504
605
1253
124238
1011
124241
405
1506
940
2060
165244
1945
168224
1423
Average
164348.17
1272.86
166178.33
859.57


## 7. Conclusion

In this paper, we propose and discuss a generic method for combinatorial optimization problems. Its consideration within various fields shows that CNS is very efficient, robust, quick, and relatively easy to implement. Note that other heuristic solution methods which were not discussed here could be considered within the CNS framework (e.g., [24, 25]). On the contrary to tree search, CNS mainly focuses on the bottom part of the search tree (i.e., it evolves close to the leaves). In contrast with standard local search methods, on the one hand, it can perform jumps in the search tree, which means that the search space is likely to be connected. On the other hand, there is no need to extend the search space by considering unfeasible solutions and penalizing them with a function which can be difficult to design and to tune.CNS is especially well adapted when the optimization problem can be divided into a series of decision problems. It was the case for three of the presented applications.(i)
Graph coloring can be tackled by the search ofk-colorings with decreasing values of k.(ii)
The frequency assignment problem can be approached at levelk by only considering interference constraints at level k and imperative constraints. Then, if a feasible solution is found at level k, level k-1 is considered.(iii)
The car fleet management problem can be considered with a fixed numberk of cars in stock (k being first equal to the existing cars in stock), and the provided solution will be the less costly solution among the different considered k values (k can augment if cars are purchased).CNS is a very flexible method for at least four reasons.(i)
It can manage various ways of representing a solution; the componenti of solution s, denoted si, can involve only one information (e.g., the color of a vertex, the car type of a client request, a binary decision value associated with a selection of a photograph or not), or several data of different nature (e.g., a frequency and a polarization, a binary decision value for the selection of a photograph, and the associated camera). This allows to better manage the repairing phase.(ii)
It can consider various types of constraints. It is well adapted for constraints linking two or three variables together, because the repairing phase is usually straightforward in such situations. If a specific constraint involves several variables, such a constraint can be relaxed (at least to save CPU time), as it was the case for the satellite range scheduling problem when the capacity constraint was only considered at specific iterations.(iii)
It is also well adapted for some problems where the unassigned variables actually correspond to an expensive assignment for the considered problem (e.g., a nonassigned variable corresponds to a subcontracted request for the car rental company).(iv)
Other significant ingredients can be easily added within the framework of CNS to enhance its efficiency, such as intensification or diversification procedures.CNS can be easily combined with evolutionary heuristics, like genetic or adaptive memory algorithms. We can consider that it was already successfully performed for graph coloring [17] and a satellite range scheduling problem [21]. In both cases, the resulting methods are the best for the considered problems. Therefore, a relevant avenue of research would consist in hybridizing CNS with other techniques for other optimization problems.



---

*Source: 671423-2012-09-13.xml*