Message > Primal linearization methods for fair assignment/matching problems

  • Forum 'Stages' - Sujet créé le 07/01/2019 par nguyenh (118 vues)

Le 07/01/2019 par nguyenh :


We are looking for a candidate to an M2 internship located at LIP6, Sorbonne Université, Paris 5ème.

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.

More details will be found here:

Best regards,

Viet Hung


Moteur de recherche