The SRAP problem can be seen as a node partitioning problem, whereas IDP, as an edge partitioning problem for the graph described above, subject to capacity constraints. These graph partitioning problems have been introduced in [6] and [7].

Both of these problems are N P-hard (see O. Goldschmidt, A. Laugier and E. Olinick in 2003, [6],
and O. Goldschmidt, D. Hochbaum, A. Levin and E. Olinick in 2003, [7] for details). The principal constraint, the load constraint, is similar to a capacity constraint, yet different: a capacity constraint holds on the variables in the sum, while the load constraint holds on the variables *below* the sum. The question is how to choose the duv (which are data) that count for the load.

## 1.2 Brief Introduction Of Local Search

In order to efficiently and quickly solve these two combinatorial optimization problems, we decided to use Local Search instead of an exact algorithm. Indeed, it permits to search in a efficiently way among all the candidate solutions, by performing steps from a solution to another.

Principles Local search is a metaheuristic based on iterative improvement of an objective function. It has been proved very efficient on many combinatorial optimization problems like the Maximum Clique Problem (L. Cavique, C. Rego and I. Themido in 2001 in [9]), or the Graph Coloring Problem (J.P.

Hansen and J.K. Hao in 2002 in [10]). It can be used on problems which formulated either as mere optimization problems, or as constrained optimization problems where the goal is to optimize an objective function while respecting some constraints. Local search algorithms perform local moves in the space of candidate solutions, called the search space, trying to improve the objective function, until a solution deemed optimal is found or a time bound is reached. Defining the neighborhood graph and the method to explore it are two of the key ingredients of local search algorithms.

The approach for solving combinatorial optimization problems with local search is very different from the systematic tree search of constraint and integer programming. Local search belongs to the family of metaheuristic algorithms, which are incomplete by nature and cannot prove optimality. However on many problems, it will isolate a optimal or high-quality solution in a very short time: local search sacrifices optimality guarantees to performance. In our case, we can compute the lower bound to either prove that the obtained solution is optimum, or estimate its optimality, hence local search is well suited.

Basic algorithm A local search algorithm starts from a candidate solution and then iteratively moves to a neighboring solution. This is only possible if a neighborhood relation is defined on the search space. Typically, for every candidate solution, we define a subset of the search space to be the neighborhood. Moves are performed from neighbors to neighbors, hence the name local search. The basic principle is to choose among the neighbors the one with the best value for the objective function. The problem is then that the algorithm will be stuck in local optima. Metaheuristics, such as Tabu Search, are added to avoid this. In Tabu Search, the last t visited configurations are left out of the search (t being a parameter of the algorithm): this ensures that the algorithm can escape local optima, at least at order t. A pseudo-code is given on figure 1.

Termination of local search can be based on a time bound. Another common choice is to terminate when the best solution found by the algorithm has not been improved in a given number of iterations. Local search algorithms are typically incomplete algorithms, as the search may stop even if the best solution found by the algorithm is not optimal. This can happen even if termination is due to the impossibility of improving the solution, as the optimal solution can lie far from the neighborhood of the solutions crossed by the algorithms.