Ph.d. explainability of The Optimal Solutions of

**About the role**:

- General context and problem statement
The assignment problem is a well-known optimization problem in which, for instance, agents are assigned to task (in a 1-to-1 fashion), so as to maximize the sum of individual assignment weights. In the M-to-M variant of this problem, M agents must be assigned to M tasks [6] (the M can vary from one agent or task to another). The assignment problem benefits from a particular structure (namely, the constraint matrix is Totally Unimodular or TU). This well-known property greatly facilitates the resolution of the problem.

At Orange, problems of this type are regularly solved, for instance to decide which offer is send to which clients, or which technician is assigned to which field operations. The assignment problems considered at Orange are generally of very large size but approaches have been derived to solve it efficiently. However, there are many issues concerning the post-optimal analysis, checking parameters and equity criteria in the choice of provided solutions, together with the many questions a non-expert end-user could ask. The generation of explanations is indeed an important expectation of users since it helps to improve the trust and control to engage the company into its transformation concerning algorithms. It also contributes to deploy the AI Ethics engagements of Orange.
- Scientific objectives - expected results and dead-locks
The goal of the thesis is to provide innovative methods for post-optimal analysis of a large-scale assignment problem. We will investigate the sensitivity analysis of the problem, try to produce all optimal solutions or even build synthetic structures (for instance, trees [7] [8] ) in order to summarize all these solutions. All these problems are aiming at answering explicability questions (why, how have solution be obtained?) and address fairness or human control issues (obtaining more fair solutions, proposes different choices or simulations in order to evaluate a set of solutions)[9].

**About you**:

- Scientific, technical and personal skills required
- Operations Research and general mathematical modeling, with a special focus on combinatorial and continuous optimization, graph theory;
- Development skills (python, Julia, Java, C++); familiarity with classical OR and AI libraries and tools;
- Some knowledge about ethics issues in computer science and equity in optimization models;
- Ability to read and understand scientific articles written in English
- Autonomy, rigor, curiosity, dedication, persistence and initiative are highly recommended qualities for completing a Ph.D.
- Educational background and diploma
- Research Master (M2) or engineering degree in applied mathematics/Operation Research, Bac+5 level.
- Desired experiences
- One or more research internships completed in the field of Operations Research or optimization would be a plus.

**Additional information**:
Références:
[6] Zhu, H. et al. (2016). Solving the Many to Many assignment problem by improving the Kuhn-Munkres algorithm with backtracking, Theoretical Computer Science, Volume 618, Pages 30-41.

[7] E. Danna et al. (2007), « Generating multiple solutions for mixed integer programming problems », Proceedings of the 12th international IPCO Conference, Ithaca, NY, USA.

[8] Serra, T., & Hooker, J. N. (2020). Compact representation of near-optimal integer programming solutions. In Mathematical Programming (Vol. 182, Issues 1-2). Springer Berlin Heidelberg.

[9] Solnon, C. et ail. (2020). HAL Id : hal-02864885 Éthique des algorithmes. 7-10.

[10] Gijswijt, D. (2005). Integer decomposition for polyhedra defined by nearly totally unimodular matrices. SIAM Journal on Discrete Mathematics, 19(3), 798-806.

**Department**:
Orange Innovation brings together the research and innovation activities and expertise of the Group's entities and countries. We work every day to ensure that Orange is recognized as an innovative operator by its customers and we create value for the Group and the Brand in each of our projects. With 720 researchers, thousands of marketers, developers, designers and data analysts, it is the expertise of our 6,000 employees that fuels this ambition every day.

Orange Innovation anticipates technological breakthroughs and supports the Group's countries and entities in making the best technological choices to meet the needs of our consumer and business customers.

Within Innovation, you will be part of MORE (Mathematical models for Optimization and peRformance Evaluation), a research team hosting a dozen permanent engineers and researchers whose mission is to build models and methods to minimize costs, energy consumption, or optimize Quality of Service and performances of the various Orange networks. The team also hosts a dozen Ph.D; students, apprentices and interns.

**Contract**:
Thesis