Internship - Designing Explanations for Lot-Sizing Problems
Context
DecisionBrain is a software company that specializes in providing analytics and optimization solutions, primarily in the fields of production planning and workforce management. The range of optimization problems
solved at DecisionBrain varies from routing problems to scheduling ones to very complex multi-level lot-sizing
problems.
Lot-Sizing Problems (LSP) aim at determining a production or distribution plan that satisfies demands over a planning horizon discretized into periods [1, 2]. The objective is to find a production plan that minimizes the total production, inventory and setup costs. LSP are very common in manufacturing and
logistics [3], and the complexity of the problems varies depending on the constraints that are considered, but problems with production capacity are usually NP-hard. This implies that oftentimes heuristics are designed to solve these problems [4].
DecisionBrain actually develops for its customers an optimization engine, called the Planning Engine, which is based on IBM ILOG CPLEX. Customer companies can then use the Planning Engine in order to
solve a large variety of LSP. However, most often, the end-users of the Planning Engine are not experts in operations research and thus do not have the necessary background to understand the mathematical
modeling or the algorithmic principles on which the Planning Engine is built. From their point of view, the engine is similar to a black box which outputs solutions, i.e. production plans, from given LSP instances. As a consequence, when provided with production plans, end-users may be surprised by some unexpected
outcomes observed in the solutions. They may want to challenge the solutions with questions and wish to
obtain additional explanations in response.
For DecisionBrain, providing such explanations requires a lot of time and effort as it involves getting familiar with the LSP instance and its corresponding solution, investigating the data of a highly combinatorial problem and finding concise pieces of explanations to provide to the customer. Still, providing
such explanations is necessary as it helps to preserve the customers’ trust in the company as well as to enhance the end-users’ understanding of the results. Thus, designing a framework for automatically generating explanations in response to end-users’ questions would benefit both end-users and DecisionBrain.
Automatic generation of explanations in the context of decision-support tools falls within the field of
eXplainable Artificial Intelligence (XAI) [5] and has been heavily studied by the machine learning community
over the past decade [6]. However, few works addressed this topic in the context of optimization problems.
Among them, the work developed by Lerouge et al. [7] aims precisely at tackling this topic in the context of
a combinatorial optimization problem called the Workforce Scheduling and Routing Problem.
Internship
Developing an explanation framework in order to simplify the interaction between the end-user and the Planning Engine would be of great industrial use. On a theoretical aspect, designing explanations in response to end-user’s questions is a subject of great interest that has not been studied in the LSP literature. Three research directions will be explored during this internship.
-
1. Which parts of the production plans can be questioned by the end-users? The range of questions about production plans that can be asked by end-users of the Planning Engine needs to be defined and a framework allowing such end-users to raise questions needs to be developed.
2. What do the explanations consist of? The content of the explanations for answering the end-users’questions needs to be defined. This content must not only be modeled but also intelligible for the end-users. A framework for presenting explanations to the end-users then needs to be developed.
3. How to compute explanations? Techniques for computing explanations need to be designed and implemented. For instance, these techniques may be metaheuristics using the Planning Engine.
This internship could be followed by a Ph.D. thesis on the subject of designing explanations for LSP.
Practical information
Environment: This internship will take place in DecisionBrain (75010, Paris) under the supervision of Daniel Godard, Mehdi Charles and Mathieu Lerouge. It will also be a collaboration with the MICS laboratory of CentraleSup´elec (91190, Gif-sur-Yvette), more specifically with Wassila Ouerdane, Céline Gicquel and Vincent Mousseau.
Date: The start of the internship is flexible but is expected to be in Spring 2023.
Profile Candidates: Candidates must be M2 level student (2nd year of MSc or last year of “cycle ingénieur”). They
must have a solid background in computer science, good programming skills, and a particular liking for
operational research as well as artificial intelligence.
Contact: Candidates must send their CV, a letter of motivation and their master marks to:
References
[1] Ford W. Harris. How Many Parts to Make at Once. Factory, The Magazine of Management, 10(2):135–
136, 1913.
[2] Yves Pochet and Laurence A. Wolsey. Production planning by mixed integer programming. Springer series
in operations research and financial engineering. Springer, New York; Berlin, 2006.
[3] Raf Jans and Zeger Degraeve. Modeling industrial lot sizing problems: a review. International Journal
of Production Research, 46(6):1619–1643, March 2008.
[4] Lisbeth Buschkuhl, Florian Sahling, Stefan Helber, and Horst Tempelmeier. Dynamic capacitated lot-sizing problems: a classification and review of solution approaches. Or Spectrum, 32(2):231–261, 2010.
[5] David Gunning and David Aha. DARPA’s explainable artificial intelligence (XAI) program. AI magazine,
40(2):44–58, 2019.
[6] Alejandro Barredo Arrieta, Natalia Díaz-Rodríguez, Javier Del Ser, Adrien Bennetot, Siham Tabik, Alberto Barbado, Salvador García, Sergio Gil-López, Daniel Molina, Richard Benjamins, et al. Explainable
Artificial Intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AI.
Information fusion, 58:82–115, 2020.
[7] Mathieu Lerouge, Celine Gicquel, Vincent Mousseau, and Wassila Ouerdane. Explaining solutions stemming from optimization systems solving the workforce scheduling and routing problem to their end-users.
Working paper, https://hal.archives-ouvertes.fr/hal-03795653, 2022.
Application
Speak with an Expert
