Le 20/01/2022 par Youcef :
Internship Position: Constraint-Programming approach for traffic routing problems
The Network and Traffic Optimization research team of the Paris Research Center is looking for internship candidates. The topic consists in investigating the advantages of constraint-programming formulations in solving the traffic routing problems.
This internship topic is research-oriented where the intern will have to conduct a deep bibliography study, model the traffic routing problem using constraint-programming and linear programming formulations. The intern will have to investigate the best methods to solve the problem for each approach and implement the associated algorithms.
In recent years, telecommunication network size has significantly increased, and new applications emerged leading to new traffic routing protocols and new requirements (small end-to-end delay, resilient to link-fault ?etc.). Many researchers attempt to develop efficient optimization algorithms that handle all technical constraints through diverse approaches: Heuristics, linear-programming, non-linear-programming?etc.
In linear-programming (LP), several constraints appeared to be hard to model, requiring exponential number of constraints, BigM parameter or several intermediate variables. Constraint programming (CP), on the other side, allows a great flexibility in the types of constraints that can be considered as it is not bound by any space property or paradigm. This is why a lot of ad-hoc global constraints has been designed to model entire complex sub-problems in industrial contexts. However, CP performance is highly related to the global constraints? implementation (namely filtering and propagation), and branching strategy. Previous studies on specific problems showed that it was possible to benefit from the best of the two paradigms and fill the gap between the search for optimality (LP relaxed problems) and feasibility (CP hard constraints).
In this context, the main challenge is to design an efficient method to solve the traffic routing problem under some difficult constraints. The main objectives of the internship are the following:
Duration: 6 months
Location: Boulogne-Billancourt, Paris Area
Required Level: Msc in Computer science / Applied mathematics / Operations Research
Technical Skills Requirements:
Candidates must be highly motivated and have the following skills:
Demassey S., Pesant G. & Rousseau L-M. (2005). Constraint programming based column generation for employee timetabling. CPAIOR 2005, 140-154.
Grönkist M. (2005). Accelerating column generation for aircraft scheduling using constraint propagation. Computers & Operations Research, 33, 2918-2934.
Hartert R., Vissicchio S., Schauss P., Bonaventure O., Filsfils C., Telkamp T. & François P. (2015). A declarative and expressive approach to control forwarding paths in carrier-grade networks. SIGCOMM 15.
Kinable, J., van Hoeve, W. J., & Smith, S. F. (2020). Snow plow route optimization: A constraint programming approach. IISE Transactions, 53(6), 685-703.
Layeghy S., Pakzad F. & Portmann M. (2016). SCOR: Constraint Programming-based Northbound Interface for SDN. ITNAC 26.
Vlk, M., Hanzálek, Z., & Tang, S. (2021). Constraint programming approaches to joint routing and scheduling in time-sensitive networks. Computers & Industrial Engineering, 157, 107317.