-
Exact Anytime Multi-Agent Path Finding Using Branch-and-Cut-and-Price and Large Neighborhood Search
Edward Lam, Daniel Harabor, Peter J. Stuckey and Jiaoyang Li
International Conference on Automated Planning and Scheduling (ICAPS), 2023
Abstract | PDF | Source code
Given a set of agents on a grid, the multi-agent 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 state-of-the-art algorithm for anytime, suboptimal solving. It is an upper-bounding algorithm that repeatedly adjusts an existing solution and, being a local search, is oblivious to optimality. BCP is a state-of-the-art algorithm for exact solving. It is a lower-bounding 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.
-
Branch-and-Cut-and-Price for the Electric Vehicle Routing Problem with Time Windows, Piecewise-Linear Recharging and Capacitated Recharging Stations
Edward Lam, Guy Desaulniers and Peter J. Stuckey
Computers & Operations Research, vol. 145, pp. 105870, 2022
Abstract | PDF | Instances | Publisher
The Electric Vehicle Routing Problem with Time Windows, Piecewise-Linear Recharging and Capacitated Recharging Stations aims to design minimum-cost routes for a fleet of electric vehicles subject to intra-route and inter-route 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 piecewise-linear 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 branch-and-cut-and-price algorithm that designates the routing to integer programming using Dantzig-Wolfe decomposition and the scheduling to constraint programming using logic-based Benders decomposition. Experimental results indicate that this hybrid method solves 34% of the instances with 100 customers.
-
Branch-and-Cut-and-Price for Multi-Agent Path Finding
Edward Lam, Pierre Le Bodic, Daniel Harabor and Peter J. Stuckey
Computers & Operations Research, vol. 144, pp. 105809, 2022
Abstract | PDF | Supplementary material | Source code | Publisher
The Multi-Agent Path Finding problem aims to find a set of collision-free 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 branch-and-cut-and-price 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 state-of-the-art solvers Lazy CBS and CBSH2-RTC published in artificial intelligence venues.
-
An Adaptive Charging Scheduling for Electric Vehicles Using Multiagent Reinforcement Learning
Xian-Long Lee, Hong-Tzer Yang, Wenjun Tang, Adel N. Toosi and Edward Lam
International Conference on Service-Oriented Computing (ICSOC), 2021
Abstract | PDF | Publisher
Scheduling when, where, and under what conditions to re-charge an electric vehicle poses unique challenges absent in internal combustion vehicles. Charging scheduling of an electric vehicle for time- and cost-efficiency depends on many variables in a dynamic environment, such as the time-of-use 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. Real-world data is used to simulate the vehicle and to learn the charging scheduling. The performance of the model is compared against two reinforcement learning-based benchmarks and a human-imitative charging scheduling strategy on four scenarios. Results indicate that the proposed model outperforms the existing approaches in terms of charging time, cost, and state-of-charge reserve assurance indices.
-
A Scalable Two Stage Approach to Computing Optimal Decision Sets
Alexey Ignatiev, Edward Lam, Peter J. Stuckey and Joao Marques-Silva
Association for the Advancement of Artificial Intelligence Conference on Artificial Intelligence (AAAI), 2021
Abstract | 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. Rule-based 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 minimum-size decision sets. Motivated by limited practical scalability of these earlier methods, this paper proposes a novel approach to learn minimum-size 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 SAT-based decision set learning.
-
Nutmeg: a MIP and CP Hybrid Solver Using Branch-and-Check
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 | 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 branch-and-cut style of logic-based Benders decomposition known as branch-and-check. Given a high-level 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 branch-and-bound 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 logic-based 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 hand-tailored 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 logic-based 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. 488-511, 2020
Abstract | 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.
-
Branch-and-cut-and-price for the cardinality-constrained multi-cycle problem in kidney exchange
Edward Lam and Vicky Mak-Hau
Computers & Operations Research, vol. 115, pp. 104852, 2020
Abstract | 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 patient-donor pairs, having multiple patient-donor 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 Cardinality-constrained Multi-cycle Problem, which generalizes the Prize-collecting 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 branch-and-cut-and-price model of the problem. The model is shown to empirically outperform the state-of-the-art by solving 149 of 160 standard benchmarks, compared to 115 by the position-indexed chain-edge formulation and 114 by the position-indexed edge formulation.
-
New Valid Inequalities in Branch-and-Cut-and-Price for Multi-Agent Path Finding
Edward Lam and Pierre Le Bodic
International Conference on Automated Planning and Scheduling (ICAPS), vol. 30, pp. 184-192, 2020
Abstract | PDF | Source code | Publisher
BCP, a state-of-the-art algorithm for optimal Multi-agent Path Finding, uses the branch-and-cut-and-price framework to decompose the problem into (1) a master problem that selects a set of collision-free low-cost paths, (2) a pricing problem that adds lower-cost 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 high-level branch-and-bound 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 CBSH-RM and 157 more than Lazy CBS.
-
Exact Approaches to the Multi-Agent 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. 743-758, 2020
Abstract | PDF | Publisher
The multi-agent collective construction problem tasks agents to construct any given three-dimensional 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 highly-exploitable 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. 603-619, 2020
Abstract | 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 branch-and-bound 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.
-
Branch-and-Cut-and-Price for Multi-Agent Pathfinding
Edward Lam, Pierre Le Bodic, Daniel Harabor and Peter J. Stuckey
International Joint Conference on Artificial Intelligence (IJCAI), pp. 1289-1296, 2019
Abstract | PDF | Source code | Publisher
There are currently two broad strategies for optimal Multi-agent Pathfinding (MAPF): (1) search-based methods, which model and solve MAPF directly, and (2) compilation-based solvers, which reduce MAPF to instances of well-known 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 branch-and-cut-and-price, a decomposition framework developed for mathematical optimization. We formalize BCP and compare it empirically against CBSH and CBSH-RM, two leading search-based solvers. Conclusive results on standard benchmarks indicate that its performance exceeds the state-of-the-art: solving more instances on smaller grids and scaling reliably to 100 or more agents on larger game maps.
-
Branch-and-Check 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. 579-595, 2017
Abstract | PDF | Publisher
This paper proposes the framework of branch-and-check with explanations (BCE), a branch-and-check method where combinatorial cuts are found by general-purpose 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 conflict-based branching rules and strengthens cuts in a post-processing step. Experimental results on the Vehicle Routing Problem with Time Windows show that BCE is a potential alternative to branch-and-cut. In particular, BCE dominates branch-and-cut, both in proving optimality and in finding high-quality solutions quickly.
-
A branch-and-price-and-check model for the vehicle routing problem with location congestion
Edward Lam and Pascal Van Hentenryck
Constraints, vol. 21, no. 3, pp. 394-412, 2016
Abstract | 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 resource-constrained project scheduling problem. The main contribution of this paper is a branch-and-price-and-check model that uses a branch-and-price 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 branch-and-price-and-check 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. 654-670, 2015
Abstract | 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 vehicle-then-crew 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 minimal-cost 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 cost-based filtering. The two integrated models are solved using a branch-and-bound 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 branch-and-price-and-check model, which hybridizes column generation and constraint programming with nogood learning.
This thesis concludes with a hybrid method, named Branch-and-Check 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 proof-of-concept solver for the Vehicle Routing Problem with Time Windows and is shown to be competitive against a branch-and-cut model while avoiding the intricacies involved in developing the cutting planes and separation algorithms required in branch-and-cut.
