is sketched in algorithm 1.

Algorithm 1 **Reduced variable neighborhood search (VNS)**
1: Generate initial solution S**, set** P
approx = {S}

2: **repeat**
3: **Randomly select some** S ∈ P
approx 4: Randomly select some neighborhood nhifrom the set of neighborhoods N H = {nh1**, . . . , nh**q}
5: **Compute neighboring solution** S
′ **by applying** nhi to S
6: **Update** P
approx **with** S
′

7: until **termination criterion is met** 8: **Return** P
approx
In contrast to established methods of variable neighborhood search [2], algorithm 1 maintains a set P
approx **containing alternatives of equal quality with the aim of allowing the identification of a**
whole set of optimal solutions.

## 3.2 Maximizing The Total Utility

Experiments have been carried out for a real world problem instance 'n34' with n **= 34 students**
applying for m **= 15 topics. In order to study the behavior of the neighborhoods when facing**
problems with differing characteristics, instances from n = 30 to n **= 45 students have been generated**
by randomly discarding or adding students from the instance n34.

Each neighborhood has been tested on each problem instance starting from an initial randomly generated solution, and average values of the total utility **as given in expression (1) have been**
computed over a total of 25 test runs for each problem instance/neighborhood structure combination.

The termination criterion has been set to 100,000 evaluations. On an Intel Pentium IV processor running at 3 GHz each test run takes less than 3 seconds. The running time is independent from the size of the problem instance as evaluation of alternatives is possible in constant time.

The average results of the total utility are given in table 1 with the real world instance n34 marked ⋆**. It can be seen that VNS outperforms the simple local search approaches in almost all**
problem instances with the only exception being n30**. For the problem instance taken from the**
real world case, an optimal solution is known with a total utility of 282, and the VNS successfully identifies one or several optimal alternatives in almost every test run. The single neighborhood with