Internship Position: Constraint-Programming approach for traffic routing problems

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.

Major Responsibilities

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:

• Bibliography study on Constraint-programming for Network optimization
• Investigate a constraint-programming formulation for the traffic routing problem
• Investigate a linear programming formulation for the traffic routing problem
• Implementation of the proposed algorithms for the two approaches
• Propose and implement hybrid solutions
• Benchmark existing algorithms on some realistic instances

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:

• Good operation research and combinatorial optimization skills
• Good knowledge on constraint-programming
• Good mathematical background
• Good programming skills in C++ (Python and Golang will be a plus)
• Knowledge of networking is a plus but not necessary (IP, routing protocols like OSPF)

Please send your applications to Dr. Youcef Magnouche (youcef.magnouche@huawei.com) and Dr. Pierre Bauguion  (pierre.bauguion@huawei.com). Successful applicants will be contacted within one month.

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.