Implementing Generic Heuristics in DecisionBrain MIP Modeler
DecisionBrain S.A.S.
Paris 10e
Internship
The internship can take place in Paris or MontpellierThe start of the internship is flexible but is expected to be in Spring 2024.
Subject
DecisionBrain develops for its customers optimization engines to solve problems which vary from routing problems to scheduling problems to very complex multi-level lot-sizing problems. For these optimization engines, based on MIP solvers, DecisionBrain has developed a MIP Modeler in Java which allows to easily model Mixed Integer Programming problems. Thanks to this MIP Modeler, the same optimization model can currently be solved using IBM Cplex, Gurobi or XPRESS-MP. This modeler aims at performing benchmarks between the different available solvers in order to define the best one to solve for the mathematical problems faced at DecisionBrain. A second objective is to develop generic optimization approaches. These approaches can be inspired by the ones currently used at DecisionBrain in the different optimization engines developed (to solve production planning, workforce routing and scheduling or maintenance problems).
Part of this internship consists in improving the interaction between the modeler, the solver and the user. This aspect is oftentimes neglected in the solvers currently available, where a lot of specific information detained by the user can be lost. How to define this interaction will be one of the key points of the internship. An idea would be to add tags on the variables or on the constraints in order to provide additional information that could be used by the modeler to:
• Define priorities to sort the constraints (to relax the least important ones for feasibility studies)
• Introduce indicators to define which constraints to relax and use it to develop a Lagrangian relaxation framework
• Define scores to the variables and use it to develop a generic iterative heuristic (such as the Relax-and-Fix heuristic
The internship consequently consists in:
• Performing a state of the art on generic heuristic
• Implement heuristic(s) on the MIP Modeler based on the information provided by the user
• Run a benchmark between the different solvers available and an additional open-source solver such as GLPK. This benchmark will be applied to real industrial instances in production planning and maintenance planning problems
Profile
Candidates must be M2 level students (2nd year of MSc or last year of “cycle ing ́enieur”). They must have a solid background in computer science, good programming skills, and a particular liking for operational research.
Candidates must send their CV, a letter of motivation and their grades to [email protected].