# 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.