## 9 Local Search by Swapping Ties  
In previous sections, we have presented two local search algorithms that start from a random marriage and try to converge to a stable marriage with a maximum size by removing blocking pairs. In this section, we present another local search approach suggested by [PERSON] to find the largest stable marriage of a given SMTI instance, \(I\). This approach is based on the observation that, by breaking all ties, \(I\) becomes an SMI instance, say \(I^{\prime}\), and a stable marriage in \(I^{\prime}\) is also stable in \(I\), since we are considering weak stability. Furthermore, we recall that all stable marriages of a given SMI have the same size, and one of them can be found in polynomial time using the Gale Shapley algorithm.  
More precisely, we consider SMTIs with ties of a length of two (the problem of finding a maximum size stable matching still remains NP-hard in this special case of SMTI [4]), and we associate a weight in [0,1] to each way of breaking a tie. Initially, such weights are all set to 0.5.  
Our method, which is described in Algorithm LST, works as follows. It takes as input an SMTI instance, \(P\), an integer, \(max\_steps\), and a random walk probability, \(p\). First, it breaks the ties in \(P\), thus obtaining the SMI instance, \(Q\); then, it repeats a sequence of actions as long as the number of steps is lower than \(max\_steps\). The first of these actions is to compute _GS(Q)_, which finds the male optimal stable matching \(M\) of \(Q\) by applying the Gale Shapley algorithm to the SMI instance, \(Q\). If the returned marriage, \(M\), is perfect, then the algorithm returns this marriage. Otherwise, if _rand()_\(\leq p\), _i.e._, if the random number in interval [0,1] generated by the function, _rand()_, is lower than or equal to the random walk probability, \(p\), then it selects a random tie in \(P\) and assigns this tie to _tie_neighbest_. It applies the procedure, _swap_tie(\(Q,t_{i}\))_, which returns an SMI instance, \(Q\), that is obtained by \(Q\), where the order of the elements in tie \(ti\) in \(P\) is swapped. Then, it finds the male optimal stable matching \(M\) of \(Q\), assigns the size of \(M\) to _max_neighb size_ and assigns \(M\) to _M_neighbest_. Otherwise, if \(\textit{rand}(p)>p\), for every allowed tie (see the next paragraph) in \(P\), it applies the procedure, _swap_tie(\(Q,t_{i}\))_, which returns an SMI instance, \(R\), which is obtained by \(Q\), where the order of the elements in tie \(ti\) in \(P\) is swapped. Then, it finds the male optimal stable matching \(M\) of \(R\). If \(M\) is the best stable matching found in the neighborhood, then it recalls that tie as _tie_neighbest_ and that marriage as _M_neighbest_. After having considered all the allowed ties, it moves to a new SMI instance \(Q\) obtained from \(Q\) and _tie_neighbest_ by applying the procedure, _swap_tie(Q,tie_neighbest)_. If the size of the obtained stable matching is larger than the overall best one obtained so far, it increases the weight of _tie_neighbest_ by 0.05; otherwise it decreases the weight of _tie_neighbest_ by 0.05.  
We can have different versions of the algorithm (Algorithm 1) LST depending on the meaning of the sentence, _allowed tie \(t\) in \(P\)_, in line 12. We consider as \"allowed\" the ties that have a weight greater than a fixed threshold or a certain percentage of ties with the highest weight. In this way, we speed up the search by reducing the size of the neighborhood. We call LSTt (where \(t\) is the threshold) the algorithm that limits the neighborhood via a threshold and LSTk (where \(k\) is the percentage of best ties considered) the other one.