in M if m and w find acceptable each other and m is either single in M or he strictly prefers w to M(m), and w is either single in M or she strictly prefers m to M(w).

Definition 4 (Weakly Stable Marriages). Given a SMTI problem P, a marriage M for P is weakly stable if it has no blocking pairs.

As we will consider only weakly stable marriages, we will simply call them stable marriages. Given a SMTI problem, there may be several stable marriages of different size. If the size of a marriage coincides with the size of the problem, it is said to be a perfect matching.

In the above example, the marriage 2 3 1 4 (where the number in position i indicates the woman married to man miin that marriage) is stable and its size is 4, so it is a perfect matching.

Solving a SMTI problem means finding a stable marriage with maximal size.

This problem is NP-hard [3].

## 2.2 Local Search

Local search [9, 10] is one of the fundamental paradigms for solving computationally hard combinatorial problems. Local search methods in many cases represent the only feasible way for solving large and complex instances. Moreover, they can naturally be used to solve optimization problems.

Given a problem instance, the basic idea underlying local search is to start from an initial search position in the space of all solutions (typically a randomly or heuristically generated candidate solution, which may be infeasible, sub-optimal or incomplete), and to improve iteratively this candidate solution by means of typically minor modifications. At each search step we move to a position selected from a local neighborhood, chosen via a heuristic evaluation function. The evaluation function typically maps the current candidate solution to a real number and it is such that its global minima correspond to solutions of the given problem instance. The algorithm moves to the neighbor with the smallest value of the evaluation function.

This process is iterated until a termination criterion is satisfied. The termination criterion is usually the fact that a solution is found or that a predetermined number of steps is reached, although other variants may stop the search after a predefined amount of time.

Different local search methods vary in the definition of the neighborhood and of the evaluation function, as well as in the way in which situations are handled when no improvement is possible. To ensure that the search process does not stagnate in unsatisfactory candidate solutions, most local search methods use randomization: at every step, with a certain probability a random move is performed rather than the usual move to the best neighbor.

## 3 Local Search On Smtis

We adapt the classical local search schema to SMTI problems as follows. Given a SMTI problem P, we start from a randomly generated marriage M for P. At