
Exact Anytime MultiAgent Path Finding Using BranchandCutandPrice and Large Neighborhood Search
Edward Lam, Daniel Harabor, Peter J. Stuckey and Jiaoyang Li
International Conference on Automated Planning and Scheduling (ICAPS), 2023
Abstract  Preprint PDF  Source code
Given a set of agents on a grid, the multiagent path finding problem aims to find a path that moves each agent from its given start location to its target location such that they do not collide and that the sum of arrival times is minimized. LNS2 is a stateoftheart algorithm for anytime, suboptimal solving. It is an upperbounding algorithm that repeatedly adjusts an existing solution and, being a local search, is oblivious to optimality. BCP is a stateoftheart algorithm for exact solving. It is a lowerbounding tree search that attempts to tighten the lower bound until a solution appears. As BCP operates on the lower bound, the first solution it finds is optimal or nearly optimal, and therefore has poor anytime behavior. This paper proposes to tightly couple LNS2 and BCP to achieve better anytime, suboptimal solving while retaining the optimality guarantee of BCP. Experiments indicate that the combination achieves better anytime behavior than BCP in general and better suboptimal performance than LNS2 on congested maps.

Exact MultiAgent Pickup and Delivery Using BranchandCutandPrice
Edward Lam, Peter J. Stuckey and Daniel Harabor
Workshop on MultiAgent Path Finding at AAAI, 2023
Abstract  Preprint PDF  Web site
Given a set of cooperating agents and a set of pickupdelivery requests located on a 2dimensional grid, the MultiAgent Pickup and Delivery (MAPD) problem assigns the requests to the agents such that every agent moves from its start position to the positions of its assigned requests and finally to its end position without colliding into other agents and that the sum of arrival times is minimized. This paper proposes an exact branchandcutandprice algorithm that performs a threelevel search. A highlevel integer programming problem is solved using a branchandbound tree search to select an optimal subset of paths from a large collection of paths, a midlevel routing problem is solved to find the sequence of requests assigned to each agent, and a lowlevel path finding problem is solved to find the movements that navigate each agent to the locations of its assigned requests. A small preliminary experiment indicates that the algorithm, believed to be the first exact method, can solve instances with up to 25 agents and 50 requests.

BranchandCutandPrice for the Electric Vehicle Routing Problem with Time Windows, PiecewiseLinear Recharging and Capacitated Recharging Stations
Edward Lam, Guy Desaulniers and Peter J. Stuckey
Computers & Operations Research, vol. 145, pp. 105870, 2022
Abstract  Preprint PDF  Instances  Publisher
The Electric Vehicle Routing Problem with Time Windows, PiecewiseLinear Recharging and Capacitated Recharging Stations aims to design minimumcost routes for a fleet of electric vehicles subject to intraroute and interroute constraints. Every vehicle is equipped with a rechargeable battery that depletes while it transports goods along its route. A vehicle must detour to a recharging station to recharge before draining its battery. To approximate a real recharging process, the amount of energy restored is modeled as a piecewiselinear function of the time spent recharging. Furthermore, each station has a small number of chargers, and hence, when and where a vehicle can recharge must be scheduled around the availability of a charger. This interaction between vehicles does not appear in classical vehicle routing problems and motivates the development of new methods that can exploit the joint routing and scheduling structure. This paper proposes a branchandcutandprice algorithm that designates the routing to integer programming using DantzigWolfe decomposition and the scheduling to constraint programming using logicbased Benders decomposition. Experimental results indicate that this hybrid method solves 34% of the instances with 100 customers.

BranchandCutandPrice for MultiAgent Path Finding
Edward Lam, Pierre Le Bodic, Daniel Harabor and Peter J. Stuckey
Computers & Operations Research, vol. 144, pp. 105809, 2022
Abstract  Preprint PDF  Supplementary material  Source code  Publisher
The MultiAgent Path Finding problem aims to find a set of collisionfree paths that minimizes the total cost of all paths. The problem is extensively studied in artificial intelligence due to its relevance to robotics, video games and logistics applications, but is seldom considered in the mathematical optimization community. This paper tackles the problem using a branchandcutandprice algorithm that incorporates a shortest path pricing problem for finding paths for every agent independently and thirteen classes of constraints for resolving different types of conflicts. Experimental results show that this mathematical approach solves 2402 of 4430 instances compared to 2039 and 1939 by the stateoftheart solvers Lazy CBS and CBSH2RTC published in artificial intelligence venues.

ML4CO submission EFPP
Edward Lam, Frits de Nijs, Pierre Le Bodic and Peter J. Stuckey
Machine Learning for Combinatorial Optimization (ML4CO) Competition Proceedings at NeurIPS, 2021
Abstract  Preprint PDF  Web site
This paper presents our submission to ML4CO, a branching rule that exploits the structure within a problem class via a graph neural network that is trained using a distributional reinforcement learning algorithm. The learned branching rule participated in the dual bound challenge, ranking third among 23 entries. Experiments on the ML4CO instances show that it performs between 16% and 34% better on average than the default reliability pseudocost branching in the stateoftheart academic solver SCIP.

An Adaptive Charging Scheduling for Electric Vehicles Using Multiagent Reinforcement Learning
XianLong Lee, HongTzer Yang, Wenjun Tang, Adel N. Toosi and Edward Lam
International Conference on ServiceOriented Computing (ICSOC), 2021
Abstract  Preprint PDF  Publisher
Scheduling when, where, and under what conditions to recharge an electric vehicle poses unique challenges absent in internal combustion vehicles. Charging scheduling of an electric vehicle for time and costefficiency depends on many variables in a dynamic environment, such as the timeofuse price and the availability of charging piles at a charging station. This paper presents an adaptive charging scheduling strategy that accounts for the uncertainty in the charging price and the availability of charging stations. We consider the charging scheduling of an electric vehicle in consideration of these variables. We develop a Multiagent Rainbow Deep Q Network with Imparting Preference where the two agents select a charging station and determine the charging quantity. An imparting preference technique is introduced to share experience and learn the charging scheduling strategy for the vehicle en route. Realworld data is used to simulate the vehicle and to learn the charging scheduling. The performance of the model is compared against two reinforcement learningbased benchmarks and a humanimitative charging scheduling strategy on four scenarios. Results indicate that the proposed model outperforms the existing approaches in terms of charging time, cost, and stateofcharge reserve assurance indices.

A Scalable Two Stage Approach to Computing Optimal Decision Sets
Alexey Ignatiev, Edward Lam, Peter J. Stuckey and Joao MarquesSilva
Association for the Advancement of Artificial Intelligence Conference on Artificial Intelligence (AAAI), 2021
Abstract  Preprint PDF  Source code
Machine learning (ML) is ubiquitous in modern life. Since it is being deployed in technologies that affect our privacy and safety, it is often crucial to understand the reasoning behind its decisions, warranting the need for explainable AI. Rulebased models, such as decision trees, decision lists, and decision sets, are conventionally deemed to be the most interpretable. Recent work uses propositional satisfiability (SAT) solving (and its optimization variants) to generate minimumsize decision sets. Motivated by limited practical scalability of these earlier methods, this paper proposes a novel approach to learn minimumsize decision sets by enumerating individual rules of the target decision set independently of each other, and then solving a set cover problem to select a subset of rules. The approach makes use of modern maximum satisfiability and integer linear programming technologies. Experiments on a wide range of publicly available datasets demonstrate the advantage of the new approach over the state of the art in SATbased decision set learning.

Nutmeg: a MIP and CP Hybrid Solver Using BranchandCheck
Edward Lam, Graeme Gange, Peter J. Stuckey, Pascal Van Hentenryck and Jip J. Dekker
SN Operations Research Forum, vol. 1, no. 3, pp. 22, 2020
Abstract  Preprint PDF  Slides  Source code  Publisher
This paper describes the implementation of Nutmeg, a solver that hybridizes mixed integer linear programming and constraint programming using the branchandcut style of logicbased Benders decomposition known as branchandcheck. Given a highlevel constraint programming model, Nutmeg automatically derives a mixed integer programming master problem that omits global constraints with weak linear relaxations, and a constraint programming subproblem identical to the original model. At every node in the branchandbound search tree, the linear relaxation computes dual bounds and proposes solutions, which are checked for feasibility of the omitted constraints in the constraint programming subproblem. In the case of infeasibility, conflict analysis generates Benders cuts, which are appended to the linear relaxation to cut off the candidate solution. Experimental results show that Nutmeg's automatic decomposition outperforms pure constraint programming and pure mixed integer programming on problems known to have successful implementations of logicbased Benders decomposition, but performs poorly on general problems, which lack specific decomposable structure. Nonetheless, Nutmeg outperforms the standalone approaches on one problem with no known decomposable structure, providing preliminary indications that a handtailored decomposition for this problem could be worthwhile. On the whole, Nutmeg serves as a valuable tool for novice modelers to try hybrid solving and for expert modelers to quickly compare different logicbased Benders decompositions of their problems.

Joint Vehicle and Crew Routing and Scheduling
Edward Lam, Pascal Van Hentenryck and Philip Kilby
Transportation Science, vol. 54, no. 2, pp. 488511, 2020
Abstract  Preprint PDF  Publisher
Traditional vehicle routing problems implicitly assume that only one crew operates a vehicle for the entirety of its journey. However this assumption is violated in many applications arising in humanitarian and military logistics. This paper considers a Joint Vehicle and Crew Routing and Scheduling Problem, in which crews are able to interchange vehicles, resulting in space and time interdependencies between vehicle routes and crew routes. The problem is formulated as Mixed Integer Programming (MIP) and a Constraint Programming (CP) models that overlay crew routing constraints over a standard vehicle routing problem. The constraint program uses a novel optimization constraint to detect infeasibility and to bound crew objectives. The paper also explores methods using large neighborhood search over the MIP and CP models. Experimental results indicate that modeling the vehicle and crew routing problems jointly and supporting vehicle interchanges for crews may bring significant benefits in cost reduction compared to a method that sequentializes these decisions.

Branchandcutandprice for the cardinalityconstrained multicycle problem in kidney exchange
Edward Lam and Vicky MakHau
Computers & Operations Research, vol. 115, pp. 104852, 2020
Abstract  Preprint PDF  Publisher
The establishment of kidney exchange programs has dramatically improved rates for kidney transplants by matching donors to compatible patients who would otherwise fail to receive a kidney for transplant. Rather than simply swapping kidneys between two patientdonor pairs, having multiple patientdonor pairs simultaneously donate kidneys in a cyclic manner enables more patients to receive a kidney for transplant. For practicality reasons, the cycles must be limited to short lengths. Finding these cycles can be accomplished by solving the Cardinalityconstrained Multicycle Problem, which generalizes the Prizecollecting Assignment Problem with constraints that bound the length of the subtours. This paper presents a series of additions to existing works—new constraints, some polyhedral results, new separation algorithms and a new pricing algorithm—and integrates them in the first branchandcutandprice model of the problem. The model is shown to empirically outperform the stateoftheart by solving 149 of 160 standard benchmarks, compared to 115 by the positionindexed chainedge formulation and 114 by the positionindexed edge formulation.

New Valid Inequalities in BranchandCutandPrice for MultiAgent Path Finding
Edward Lam and Pierre Le Bodic
International Conference on Automated Planning and Scheduling (ICAPS), vol. 30, pp. 184192, 2020
Abstract  Preprint PDF  Source code  Publisher
BCP, a stateoftheart algorithm for optimal Multiagent Path Finding, uses the branchandcutandprice framework to decompose the problem into (1) a master problem that selects a set of collisionfree lowcost paths, (2) a pricing problem that adds lowercost paths to the master problem, (3) separation problems that resolve various kinds of conflicts in the master problem, and (4) branching rules that split the nodes in the highlevel branchandbound search tree. This paper focuses on the separation aspects of the decomposition by introducing five new classes of fractional conflicts and valid inequalities that remove these conflicts to tighten the linear programming relaxation in the master problem. Experimental results on 12820 instances across 16 maps indicate that including the five families of inequalities allows BCP to solve an additional 585 instances, optimize the same instances 41% faster, and solve 2068 more instances than CBSHRM and 157 more than Lazy CBS.

Exact Approaches to the MultiAgent Collective Construction Problem
Edward Lam, Peter J. Stuckey, Sven Koenig and T. K. Satish Kumar
International Conference on Principles and Practice of Constraint Programming (CP)
Lecture Notes in Computer Science, vol. 12333, pp. 743758, 2020
Abstract  Preprint PDF  Publisher
The multiagent collective construction problem tasks agents to construct any given threedimensional structure on a grid by repositioning blocks. Agents are required to also use the blocks to build ramps in order to access the higher levels necessary to construct the building, and then remove the ramps upon completion of the building. This paper presents a mixed integer linear programming model and a constraint programming model of the problem, either of which can exactly optimize the problem, as previous efforts have only considered heuristic approaches. The two models are evaluated on several small instances with a large number of agents. The plans clearly show the swarm behavior of the agents. The mixed integer linear programming model is able to find optimal solutions faster than the constraint programming model and even some existing incomplete methods due to its highlyexploitable network flow substructures.

Large Neighborhood Search for Temperature Control with Demand Response
Edward Lam, Frits de Nijs, Peter J. Stuckey, Donald Azuatalam and Ariel Liebman
International Conference on Principles and Practice of Constraint Programming (CP)
Lecture Notes in Computer Science, vol. 12333, pp. 603619, 2020
Abstract  Preprint PDF  Publisher
Demand response is a control problem that optimizes the operation of electrical loads subject to limits on power consumption during times of low power supply or extreme power demand. This paper studies the demand response problem for centrally controlling the space conditioning systems of several buildings connected to a microgrid. The paper develops a mixed integer quadratic programming model that encodes trained deep neural networks that approximate the temperature transition functions. The model is solved using standard branchandbound and a large neighborhood search within a mathematical programming solver and a constraint programming solver. Empirical results demonstrate that the large neighborhood search coupled to a constraint programming solver scales substantially better than the other methods.

BranchandCutandPrice for MultiAgent Pathfinding
Edward Lam, Pierre Le Bodic, Daniel Harabor and Peter J. Stuckey
International Joint Conference on Artificial Intelligence (IJCAI), pp. 12891296, 2019
Abstract  Preprint PDF  Source code  Publisher
There are currently two broad strategies for optimal Multiagent Pathfinding (MAPF): (1) searchbased methods, which model and solve MAPF directly, and (2) compilationbased solvers, which reduce MAPF to instances of wellknown combinatorial problems, and thus, can benefit from advances in solver techniques. In this work, we present an optimal algorithm, BCP, that hybridizes both approaches using branchandcutandprice, a decomposition framework developed for mathematical optimization. We formalize BCP and compare it empirically against CBSH and CBSHRM, two leading searchbased solvers. Conclusive results on standard benchmarks indicate that its performance exceeds the stateoftheart: solving more instances on smaller grids and scaling reliably to 100 or more agents on larger game maps.

BranchandCheck with Explanations for the Vehicle Routing Problem with Time Windows
Edward Lam and Pascal Van Hentenryck
International Conference on Principles and Practice of Constraint Programming (CP)
Lecture Notes in Computer Science, vol. 10416, pp. 579595, 2017
Abstract  Preprint PDF  Publisher
This paper proposes the framework of branchandcheck with explanations (BCE), a branchandcheck method where combinatorial cuts are found by generalpurpose conflict analysis, rather than by specialized separation algorithms. Specifically, the method features a master problem that ignores combinatorial constraints, and a feasibility subproblem that uses propagation to check the feasibility of these constraints and performs conflict analysis to derive nogood cuts. The BCE method also leverages conflictbased branching rules and strengthens cuts in a postprocessing step. Experimental results on the Vehicle Routing Problem with Time Windows show that BCE is a potential alternative to branchandcut. In particular, BCE dominates branchandcut, both in proving optimality and in finding highquality solutions quickly.

A branchandpriceandcheck model for the vehicle routing problem with location congestion
Edward Lam and Pascal Van Hentenryck
Constraints, vol. 21, no. 3, pp. 394412, 2016
Abstract  Preprint PDF  Publisher
This paper considers a vehicle routing problem with pickup and delivery, time windows and location congestion. Locations provide a number of cumulative resources that are utilized by vehicles either during service (e.g., forklifts) or for the entirety of their visit (e.g., parking bays). Locations can become congested if insufficient resources are available, upon which vehicles must wait until a resource becomes available before proceeding. The problem is challenging from a computational standpoint since it incorporates the vehicle routing problem and the resourceconstrained project scheduling problem. The main contribution of this paper is a branchandpriceandcheck model that uses a branchandprice algorithm that solves the underlying vehicle routing problem, and a constraint programming subproblem that checks the feasibility of the location resource constraints, and then adds combinatorial nogood cuts to the master problem if the resource constraints are violated. Experimental results show the benefits of the branchandpriceandcheck approach.

Joint Vehicle and Crew Routing and Scheduling
Edward Lam, Pascal Van Hentenryck and Philip Kilby
International Conference on Principles and Practice of Constraint Programming (CP)
Lecture Notes in Computer Science, vol. 9255, pp. 654670, 2015
Abstract  Preprint PDF  Publisher
Traditional vehicle routing problems implicitly assume only one crew operates a vehicle for the entirety of its journey. However, this assumption is violated in many applications arising in humanitarian and military logistics. This paper considers a Joint Vehicle and Crew Routing and Scheduling Problem, in which crews are able to interchange vehicles, resulting in space and time interdependencies between vehicle routes and crew routes. It proposes a constraint programming model that overlays crew routing constraints over a standard vehicle routing problem. The constraint programming model uses a novel optimization constraint that detects infeasibility and bounds crew objectives. Experimental results demonstrate significant benefits of using constraint programming over mixed integer programming and a vehiclethencrew sequential approach.

PhD thesis: Hybrid optimization of vehicle routing problems
Edward Lam
University of Melbourne, 2017
Abstract  Download  University archive
Vehicle routing problems are combinatorial optimization problems that aspire to design vehicle routes that minimize some measure of cost, such as the total distance traveled or the time at which the last vehicle returns to a depot, while adhering to various restrictions. Vehicle routing problems are of profound interest in both academia and industry because they are opportunities to study graph structures and algorithms, and because they underpin practical applications in a multitude of industries, but notably, the transportation and logistics industries. This dissertation presents two applications relevant to industry and develops a fully hybrid method for solving a classical vehicle routing problem.
The first application combines vehicle routing with crew scheduling. In industry, vehicle routing and crew scheduling are usually performed in stages due to the large search space of integrated models. The first stage finds minimalcost vehicle routes with little consideration to crew constraints and objectives. The second stage schedules crews on the routes from the first stage. Disregarding crew constraints in the first stage can lead to suboptimality or even infeasibility of the overall problem in the second stage. To quantify the suboptimality of staged optimization models, two formulations of the integrated problem are developed. The first is an ordinary mixed integer programming model, and the second is a constraint programming model containing a linear relaxation global constraint that performs costbased filtering. The two integrated models are solved using a branchandbound search and a highly specialized large neighborhood search. The large neighborhood search exploits the substructures linking the vehicle routing and crew scheduling elements of the problem, and when executed on the constraint programming model, is shown to perform significantly better than the other approaches.
The second application introduces a number of scheduling constraints to the Vehicle Routing Problem with Pickup and Delivery and Time Windows. The scheduling constraints arise from a lack of loading bays or equipment that unloads and loads incoming vehicles. These constraints limit the number of vehicles present or in service at any particular site by requiring the arrival of vehicles to be scheduled around the availabilities of a scarce resource. A mixed integer programming model, a constraint programming model and a sequential model are implemented for the problem but are shown to be inferior to a branchandpriceandcheck model, which hybridizes column generation and constraint programming with nogood learning.
This thesis concludes with a hybrid method, named BranchandCheck with Explanations, that unifies linear programming, constraint programming and Boolean satisfiability. The method begins with a linear programming model that omits several critical constraints. The solver uses the linear programming model to find objective bounds and candidate solutions, which are checked by a constraint programming model for feasibility of the omitted constraints. A Boolean satisfiability model performs conflict analysis on infeasible candidate solutions to derive nogood cuts, which are placed into the linear programming model and the constraint programming model. The method is implemented in a proofofconcept solver for the Vehicle Routing Problem with Time Windows and is shown to be competitive against a branchandcut model while avoiding the intricacies involved in developing the cutting planes and separation algorithms required in branchandcut.