ROADEF/EURO challenge 2012: Machine reassignment

The aim of this challenge was to improve the usage of a set of machines. A machine has several resources such as RAM and CPU, and runs processes which consume these resources. In order to improve machine usage, processes can be moved from one machine to another. Possible moves are limited by hard constraints like resource capacity constraints, and have a cost. A solution to this problem is a new process-machine assignment which satisfies all hard constraints and minimizes a composite cost involving load, balance and move costs. The instances contain up to 5,000 machines and 50,000 processes and the running time was limited to 5 minutes on a specific 2-cores machine.
[more details on the subject]

We have proposed a local search-based heuristic with two phases. In the first one, we generate some smart moves specifically targeting a decrease in the load cost. In the second phase, we apply very fast random moves that exploit the structure of the problem to explore a large number of solutions. In the two phases, moves are actually applied only if the resulting assignment remains feasible and its total cost decreases. Moreover, in order to have various staring points for our local search, we have worked on generating other feasible solutions. We have decomposed the problem on the machine neighborhoods and proposed some vector bin packing inspired heuristics to solve the neighborhoods subproblems.
[report] [source code]

With Michaƫl Gabay (PhD student at GSCOP laboratory).
Qualification for the final stage over 82 teams. Final rank: 8 in the junior category and 11 in the open-source category.


FFJM/SCM competition 2010: A network design problem

For a given set of cities with known demand in electricity and a set of power plants with known capacities, the goal of this competition was to design an electricity distribution network of minimal cost. The network had to satisfy several constraints as in particular the tolerance to the failure of any component.
[more details]

We have modeled the problem as a mixed integer linear program with an exponential number of constraints (corresponding to the failure tolerance). Our resolution algorithm iterates between two steps. First, we solve a relaxation of the problem ignoring the exponential constraints (using CPLEX solver). Then, we test the feasibility of the solution regarding the ignored constraints, using Ford and Fulkerson algorithm in some appropriate graph. The violated constraints are then added to the relaxed problem.
[report]

With Florian Ramis and Hugo Straziota, under the supervision of Prof. Denis Naddef.
Ranked 1st in the group category.