to search most of the search space. As reported in [22], IP finds optimal solutions much faster than any previous algorithm designed for this purpose.

As regards the approximate algorithms, in [26] it has been proposed **a solution**
based on a genetic algorithm, which performs well when there is some **regularity** in the search space. Indeed, the authors assume, in order to apply their algorithm, that the value of a coalition is dependent of other coalitions in the CS, **making the** algorithm not well suited for the general case. A new solution [13] is based on a Simulated Annealing algorithm [14], a widely used stochastic local search method. At each iteration the algorithm selects a random neighbour solution s
′ **of a CS** s.

The search proceeds with an adjacent CS s
′ **of the original CS** s if s
′ **yields a better**
social welfare than s**. Otherwise, the search is continued with** s
′ **with probability**
e
(V (s
′
)−V (s))/t, where t **is the temperature parameter that decreases according to**
the annealing schedule t = αt.

## 5. Grasp For The Csg Problem

The resource limits posed by some intelligent systems, such as the time for finding a solution, require to have approximation algorithms able to quickly find solutions that are within a specific factor of an optimal solution. In this section we firstly present the anytime algorithm for CSG proposed in [4] with some improvements and then its extension with path-relinking.

A method to find high-quality solutions for a combinatorial problem is a **two steps**
approach consisting of a greedy construction phase followed by a perturbative1**local search [11]. Namely, the greedy construction method starts the process from**
an empty candidate solution and at each construction step adds the best ranked component according to a heuristic selection function. Successively, a perturbative local search algorithm is used to improve the candidate solution thus **obtained. Advantages of this search method, over other stochastic local search algorithms, are**
the much better solution quality and fewer perturbative improvement steps to reach the local optimum. Greedy Randomized Adaptive Search Procedures (GRASP) [6] solve the problem of the limited number of different candidate solutions generated by a greedy construction search methods by randomising the construction method. GRASP is an iterative process, in which each iteration consists of a construction phase, producing a feasible solution, and a local search phase, finding a local optimum in the neighborhood of the constructed solution. The best overall solution is returned.

Algorithm 2 reports the outline of the GRASP procedure for the CSG **problem,**
denoted in the following with GRASP**. In each iteration, it computes a solution** C by using a randomised constructive search procedure and then applies a local search procedure to C **yielding an improved solution. The main procedure is made up of** two components: a constructive phase (lines 7-13) and a local search phase (line 15). The constructive search algorithm used in GRASP **iteratively adds a solution** component by randomly selecting it, according to a uniform distribution, from a set, named restricted candidate list **(RCL), of highly ranked solution components**
with respect to a greedy function g : C → R**. The probabilistic component of**
GRASP is characterized by randomly choosing one of the best candidates in the RCL. In our case the greedy function g **corresponds to the characteristic function** v