Laurent Perron
Laurent Perron is working on Operations Research.
His contribution are visible in the OR-Tools package.
Authored Publications
Sort By
Parallelising Lazy Clause Generation with Trail Sharing
Toby Davies
Peter J Stuckey
Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2025), Springer Nature Switzerland, Cham, pp. 205-221
Preview abstract
We investigate the effectiveness of splitting the search space in parallelising the state-of-the-art CP-SAT solver. One of the key barriers to effective search-space splitting in learning solvers is the generated sub-problems are not independent, leading to substantial communication-related overhead, substantial redundant work, or both. Our contributions attempt to mitigate this issue: job reassignment; and trail sharing. Jobs (sub-trees) are reassigned to new workers if the clause database of the currently assigned worker appears ill-suited to the region of the search-space, when doing so workers can share some of the state from their local trail. We argue a trail prefix can be viewed as a lossy compressed representation of much of the relevant information a worker has learnt about a job, this information can be exploited by the next worker assigned the same subtree to avoid some redundant work. We show these approaches complement standard portfolio and clause-sharing approaches, improving CP-SAT’s performance on MiniZinc challenge benchmarks with a moderate number of worker threads. To enable these approaches, we also introduce “Buffered Work Stealing,” which can be parameterised to emulate the two main existing approaches to search-space splitting in the literature: Work Stealing and Embarassingly Parallel Search, as well as an intermediate configuration between these two extremes that slightly outperforms both.
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
A Contextual Bandit Approach for Learning to Plan in Environments with Probabilistic Goal Configurations
Sohan Rudra
Saksham Goel
Fei Xia
Gaurav Aggarwal
NeurIPS 5th Robot Learning Workshop: Trustworthy Robotics (2022) (to appear)
