Edward is a Research Fellow in the Department of Data Science and Artificial Intelligence in the Faculty of Information Technology at Monash University, and contributes to the Analytics and Decision Sciences program at CSIRO Data61. His research in combinatorial optimization spans the disciplines of operations research in mathematics and artificial intelligence in computer science. He specializes in branch-and-cut-and-price for decompositions and hybridizations of integer programming and constraint programming.

Prior to joining Monash University, Edward completed his PhD studies at the University of Melbourne under the supervision of Pascal Van Hentenryck at the Georgia Institute of Technology. His thesis proposed novel techniques to hybridize integer programming, constraint programming and Boolean satisfiability; winning him the 2019 Doctoral Research Award from the Association for Constraint Programming.

Research Interests

---

• Branch-and-cut-and-price: Edward's main interest is branch-and-cut-and-price which includes diverse elements of mixed integer linear programming such as Dantzig-Wolfe decomposition, column generation, cutting planes and polyhedral analysis.
• Routing and scheduling: Edward investigates transport and logistics problems with joint routing and scheduling structure and especially focuses on problems featuring electric vehicles and autonomous vehicles.
• Hybrid solvers: Edward develops hybrid algorithms that exploit the strengths of integer programming at routing and constraint programming at scheduling to solve joint routing and scheduling problems faster than either technology alone.
• Neuro-symbolic artificial intelligence: Edward studies discrete and constraint reasoning in deep neural networks for end-to-end decision-making pipelines that feature a mixture of machine learning and optimisation.
• Optimal control of energy systems: Edward contributes towards the RACE for 2030 by developing online optimisation models for autonomous control of power consumption and distributed power generation in microgrids.

Publications

---

• 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 | Preprint 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.

• Exact Multi-Agent Pickup and Delivery Using Branch-and-Cut-and-Price
  Edward Lam, Peter J. Stuckey and Daniel Harabor
  Workshop on Multi-Agent Path Finding at AAAI, 2023
  Abstract | Preprint PDF | Web site

  Given a set of co-operating agents and a set of pickup-delivery requests located on a 2-dimensional grid, the Multi-Agent 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 branch-and-cut-and-price algorithm that performs a three-level search. A high-level integer programming problem is solved using a branch-and-bound tree search to select an optimal subset of paths from a large collection of paths, a mid-level routing problem is solved to find the sequence of requests assigned to each agent, and a low-level 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.

• 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 | Preprint 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 | Preprint 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.

• 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 state-of-the-art academic solver SCIP.

• 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 | Preprint 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 | 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. 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 | 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 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 | 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.

• 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 | 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 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 | Preprint 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 | Preprint 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 | 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 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 | Preprint 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 | Preprint 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 | 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 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 | 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 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.

Links

---

• Google Scholar
• DBLP
• ResearchGate
• GitHub
• Mastodon
• LinkedIn