Primal linearization methods for fair assignment/matching problems

The internship will experiment new methods of linearization in order to improve
the exact solution of the fair assignment problem. In particular, it is expected to
reformulate the problem of maximization of $W(x)$ to a contrained 0/1 quadratic minimization problem. Then several linearization methods can be experimented directly without dualizing permutation variables such as
the classical method \cite{Fortet}, the QCR method \cite{BILLIONNET}, the bilinear methods \cite{Sherali} and in particular the methods \cite{Liberti}, \cite{Mallach} that takes into account the assignment constraints in the linearization.
The objective of the internship is to adapt the above linearization methods for the fair assignment problems. It is also required to experiment the proposed method for
various instances and to compare their performance to each other and to the performance of the "dual" linearization methods in \cite{orgy}, \cite{chassein}.
Extensions of the work are expected to other fair combinatorial optimization problems such as fair matching, fair TSP, fair MST,...

The internship is to be realized within 6 months from mid-February to mid-August 2018 at LIP6.
The remuneration is 554.40 euros monthly with (+ possibly at most 35 euros of transport compensation ).

The work done during the internship is expected to be pursued in a PhD thesis
in France or in Shanghai, China.