Thibaut Cuvelier
Research Areas
Authored Publications
Sort By
Preview abstract
JuMP and MathOptInterface.jl give access to many solvers, both very common in the industry and more specialised. Google offers its own in-house solvers as part of the open-source package OR-Tools: Glop, a simplex solver; CP-SAT, an award-winning constraint-programming solver; PDLP, a first-order solver for large-scale linear programming.
ORTools.jl is a recent package that gives access to these solvers through MathOptInterface.jl. It supports both local and remote use, meaning that users do not need a local installation to solve linear and integer problems thanks to Google Cloud. More recently, ORTools.jl started offering a native interface for constraint programming building upon the work in MathOptInterface.jl.
However, OR-Tools have more than this to offer, including a scalable routing solver for large-scale VRPs or state-of-the-art set-cover solver. MathOptInterface.jl does not yet propose an interface for these problems and we would like to gauge the community’s interest in these specific solvers.
View details
Preview abstract
Julia's strength in mathematical computation and high performance makes it a popular choice across scientific fields, mostly due to its focus on mathematics in a broad sense and execution performance. It is a language of choice to implement new numerical algorithms, but it really shines in modelling for optimisation thanks to JuMP.jl and MathOptInterface.jl.
These libraries are, first and foremost, made for mathematical optimisation (linear, mixed-integer, conic, etc.), yet they are now generic enough to support more paradigms, such as constraint programming. This talk will introduce the basic principles behind the current implementation of JuMP.jl and explain why and how they are very good matches for modelling using constraint programming… and solving using any kind of mixed-integer-programming solver.
Constraint-programming solvers can also be implemented using linear programming, in a great collaboration between discrete and continuous optimisation. This talk will briefly explain the connection and its implementation in Google’s CP-SAT, a leading, award-winning constraint solver that uses linear programs in its solving process — a solver that will soon be available in Julia too.
View details
Preview abstract
Google has a long tradition of open-source software, which encompasses the field of operations research with OR-Tools. In development since 2008, it offers several solvers useful to many OR practitioners:
- PDLP, a revolutionary first-order linear solver that is reshaping the landscape of linear optimisation;
- CP-SAT, an award-winning constraint-programming solver;
- Glop, an accurate linear solver;
- Routing, a vehicle routing solver underpinning Google Maps Platform Route Optimization.
OR-Tools has long had its features accessible from other languages: the core algorithms are implemented in C++ for performance, but users can tap into them in Python, Java, C#, or Go.
It is recently available in Julia too, with a current focus on the linear and constraint solvers, either locally or remotely.
We provide a wrapper for our solvers that brings them to JuMP.jl through MathOptInterface.jl.
This tutorial will walk you through the features of OR-Tools and its solvers, then show examples of using OR-Tools from within Julia, either through JuMP or a lower-level interface.
We will also share our experience of C++-Julia interop.
View details
Preview abstract
Google has a long tradition of open-source software, which encompasses the field of operations research with OR-Tools. In development since 2008, it offers several solvers useful to many OR practitioners:
- PDLP, a revolutionary first-order linear solver that is reshaping the landscape of linear optimisation;
- CP-SAT, an award-winning constraint-programming solver;
- Glop, an accurate linear solver;
- Routing, a vehicle routing solver underpinning Google Maps Platform Route Optimization.
OR-Tools has long had its features accessible from other languages: the core algorithms are implemented in C++ for performance, but users can tap into them in Python, Java, C#, or Go.
It is recently available in Julia too, with a current focus on the linear and constraint solvers, either locally or remotely.
We provide a wrapper for our solvers that brings them to JuMP.jl through MathOptInterface.jl.
This tutorial will walk you through the features of OR-Tools and its solvers, then show examples of using OR-Tools from within Julia, either through JuMP or a lower-level interface.
We will also share our experience of C++-Julia interop.
View details
Preview abstract
In Julia, JuMP is the go-to modelling package for mathematical optimisation. As of this writing, Google's award-winning solvers have not been accessible through JuMP; which offers Julia's ease of use. ORTools.jl is changing this. Julia users will now have access to Google's Glop, CP-SAT, and PDLP solvers through JuMP as provided by the ORTools.jl package.
This talk offers an introduction to the features of the package and an overview of the difficulties we encountered.
View details
Preview abstract
To tackle the challenge of optimizing middle-mile logistics, the crucial link between warehouses and final deliveries, we introduce a novel instance generator that aims to create a rich and adaptable dataset of diverse instances to empower researchers and developers. The instance defines a logistics network with hubs, vehicles, routes, lines, and rotations. Additionally, it specifies a list of shipments that need to be transported through this network. To customize the instance, the user can adjust various parameters, such as the number of hubs, density of the space graphs, distribution of shipment weights, or the maximum number of vehicles.
The generator reflects real-world complexities through variations in network size and structure. We developed a random graph generator to mimic real-world middle mile networks, by generating space graphs for hubs. Subsequently, lines and routes are randomly constructed on the generated space graphs, while adhering to user-defined constraints.
The tool is in the form of an optimized C++ library that enables the generation of instances with a large number of hubs and shipments. It offers the immense potential for advancing middle-mile logistics optimization by providing a comprehensive and adaptable dataset for benchmarking optimization approaches, training machine learning models, and analyzing the impact of network configurations and shipments characteristics on overall efficiency.
View details
Preview abstract
Middle-mile logistics describes the problem of routing shipments through a network of hubs while respecting deadlines upon arrival. We consider that the hubs are linked by predefined lines, to which we have to assign vehicles. A very challenging aspect of the problem comes from the finite capacity of the vehicles: allocating a shipment to a given vehicle might block another one from using the same vehicle.
Typical exact solution methods, based on a multicommodity-flow formulation, scale poorly with the problem size and real-world instances become quickly intractable. Instead, we turn to reinforcement learning (RL) by rephrasing the middle-mile problem as a multi-objective Markov decision process, where the state is a graph: the lines (edges) between the hubs and the parcels (nodes). At each round, we assign one shipment to a vehicle or decide that it stays in the same hub. The key ingredients of our proposed method are the extraction of small feature graphs from the state and the combination of graph neural networks (GNN) with model-free RL.
We use the PPO (proximal policy optimization) algorithm, which maintains both an actor and a critic, while being able to cope with a varying number of actions depending on the state. We compare linear functions and GraphNet (a particular kind of GNN) to approximate the policy and value functions. GNNs can deliver up to 40% more shipments than a linear function and both approaches scale well with the number of shipments per truck.
View details
Preview abstract
Reinforcement can be a useful tool to solve combinatorial problems, even in the presence of constraints. This presentation details two use cases: one industrial application in the field of logistics, one of a more abstract problem in combinatorial optimization.
View details
OR-Tools' Vehicle Routing Solver: a Generic Constraint-Programming Solver with Heuristic Search for Routing Problems
Steven Agostino Gay
Congrès de la Société française de recherche opérationnelle et d’aide à la décision (ROADEF) (2023) (to appear)
Preview abstract
OR-Tools is the general-purpose optimisation toolbox open-sourced by Google in 2015, being in development since 2008. This toolkit provides a uniform interface to several solvers, both first- and third-party. In particular, it offers a high-level interface for vehicle-routing problems (VRPs). OR-Tools contains several solvers, in particular two CP solvers, CP* (since the first open-source release) and CP-SAT (gold-medal winner at several MiniZinc competitions, developed since 2009), but also two linear solvers: the simplex-based Glop (since 2014), and PDLP, a first-order large-scale linear solver. OR-Tools is being actively developed, with approximately quarterly releases. Outside Google, the solver suite is easily accessible via Google Cloud, either for solving VRPs or mixed-integer linear programs, although the latter API is not yet in general access.
The routing component has historically played a strong role in the development of the overall solver; its major focus is on solving large-scale industrial vehicle-routing problems with complex constraints: vehicle capacities with various starting/ending depots, client time windows considering road traffic and driver breaks, pick-up-and-delivery precedence rules, incompatible shipments within the same vehicle, solution similarity to a previous call to the solver, etc. To this end, a high-level modelling API is proposed to the users in Python, C++, Java, and C#, using only routing concepts, even though the user has access to the underlying constraint-programming model.
From an algorithmic point of view, the routing solver is organised in three parts: (i) first-solution heuristics generate good potential vehicle tours; (ii) local search improves the first solutions, with metaheuristics to guide the search; (iii) a CP engine proves the optimality of the best solution or improves upon it. The main difference with many academic solvers is the focus on generality in the solver, including its heuristics.
View details
Middle-Mile Logistics Through the Lens of Goal-Conditioned Reinforcement Learning
Onno Eberhard
Michal Valko
NeurIPS 2023 Workshop on Goal-Conditioned Reinforcement Learning
Preview abstract
Middle-mile logistics describes the problem of routing parcels through a network of hubs, which are linked by a fixed set of trucks. The main challenge comes from the finite capacity of the trucks. The decision to allocate a parcel to a specific truck might block another parcel from using the same truck. It is thus necessary to solve for all parcel routes simultaneously. Exact solution methods scale poorly with the problem size and real-world instances are intractable. Instead, we turn to reinforcement learning (RL) by rephrasing the middle-mile problem as a multi-object goal-conditioned Markov decision process. The key ingredients of our proposed method for parcel routing are the extraction of small feature graphs from the environment state and the combination of graph neural networks with model-free RL. There remain several open challenges and we provide an open-source implementation of the environment to encourage stronger cooperation between the reinforcement learning and logistics communities.
View details
