ABSTRACT This paper studies a combined delivery strategy involving a private vehicle and external carriers under stochastic customer demands. The routing problem focuses on a single private vehicle, while external carriers are allowed to determine their own routes independently and are compensated with a fixed price per unit demand served. A strategy incorporating routing re‐optimization is proposed, along with a new recourse mechanism that leverages outsourcing through external carriers. To enable routing re‐optimization, a novel approximate linear programming (ALP) approach is introduced. This offers a new pathway for addressing vehicle routing problems (VRPs) under stochastic demand considerations. The ALP approach is adapted to the specific structure of routing under stochastic demands, leading to the development of a decomposition‐based ALP solution framework. This adaptation arises from changes in the decision sequence of routing and restocking at each step of the Markov decision process (MDP), which differs from previous formulations of vehicle routing under stochastic demands. Additionally, further adaptations are made to facilitate the computation of the proposed strategy by exploring the relationships among variables and constraints specific to the problem context, as well as by developing a constraint sampling procedure designed to mimic the near‐optimal heuristic policy. Our numerical results show that the proposed outsourcing‐based policy yields notable operating‐cost savings, with an average improvement of 4.06% over the traditional recourse strategy in midpoint‐depot instances. Moreover, in small instances where the optimal policy within the traditional partial re‐optimization framework can be computed, the proposed price‐directed (PD) policy still provides cost advantages over this re‐optimization scheme, demonstrating the value of our ALP‐based framework.

Lagrangian decomposition (LD) is a relaxation method that provides a dual bound for constrained optimization problems by decomposing them into more manageable sub-problems. This bound can be used in branch-and-bound algorithms to prune the search space effectively.In brief, a vector of Lagrangian multipliers is associated with each sub-problem, and an iterative procedure (e.g., a sub-gradient optimization) adjusts these multipliers to find the tightest bound. Initially applied to integer programming, Lagrangian decomposition also had success in constraint programming due to its versatility and the fact that global constraints provide natural sub-problems. However, the non-linear and combinatorial nature of sub-problems in constraint programming makes it computationally intensive to optimize the Lagrangian multipliers with sub-gradient methods at each node of the tree search. This currently limits the practicality of LD as a general bounding mechanism for constraint programming. To address this challenge, we propose a self-supervised learning approach that leverages neural networks to generate multipliers directly, yielding tight bounds. This approach significantly reduces the number of sub-gradient optimization steps required, enhancing the pruning efficiency and reducing the execution time of constraint programming solvers. This contribution is one of the few that leverage learning to enhance bounding mechanisms on the dual side, a critical element in the design of combinatorial solvers. This work presents a generic method for learning valid dual bounds in constraint programming. We validate our approach on two challenging combinatorial problems: The multi-dimensional knapsack problem and the shift scheduling problem. The results show that our approach can solve more instances than the standard application of LD to constraint programming, reduce execution time by more than half, and has promising generalization ability through fine-tuning.

Constraint programming is known for being an efficient approach to solving combinatorial problems. Important design choices in a solver are the branching heuristics, designed to lead the search to the best solutions in a minimum amount of time. However, developing these heuristics is a time-consuming process that requires problem-specific expertise. This observation has motivated many efforts to use machine learning to automatically learn efficient heuristics without expert intervention. Although several generic variable-selection heuristics are available in the literature, the options for value-selection heuristics are more scarce. We propose to tackle this issue by introducing a generic learning procedure that can be used to obtain a value-selection heuristic inside a constraint programming solver. This has been achieved thanks to the combination of a deep Q-learning algorithm, a tailored reward signal, and a heterogeneous graph neural network. Experiments on graph coloring, maximum independent set, and maximum cut problems show that this framework competes with the well-known impact-based and activity-based search heuristics and can find solutions close to optimality without requiring a large number of backtracks.

Patient scheduling is a difficult task involving stochastic factors, such as the unknown arrival times of patients. Similarly, the scheduling of radiotherapy for cancer treatments needs to handle patients with different urgency levels when allocating resources. High-priority patients may arrive at any time, and there must be resources available to accommodate them. A common solution is to reserve a flat percentage of treatment capacity for emergency patients. However, this solution can result in overdue treatments for urgent patients, a failure to fully exploit treatment capacity, and delayed treatments for low-priority patients. This problem is especially severe in large and crowded hospitals. In this paper, we propose a prediction-based approach for online dynamic radiotherapy scheduling that dynamically adapts the present scheduling decision based on each incoming patient and the current allocation of resources. Our approach is based on a regression model trained to recognize the links between patients’ arrival patterns and their ideal waiting time in optimal off-line solutions when all future arrivals are known in advance. When our prediction-based approach is compared with flat-reservation policies, it does a better job of preventing overdue treatments for emergency patients and also maintains comparable waiting times for the other patients. We also demonstrate how our proposed approach supports explainability and interpretability in scheduling decisions using Shapley additive explanation values. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: Mitacs Accélération IT26995 and Canada Research Chair in Analytics and Logistics in Healthcare (HANALOG). Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.1289 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0342 ) at ( http://dx.doi.org/10.5281/zenodo.7579533 ).

Decision diagrams are an increasingly important tool in cutting-edge solvers for discrete optimization. However, the field of decision diagrams is relatively new, and is still incorporating the library of techniques that conventional solvers have had decades to build. We drew inspiration from the warm-start technique used in conventional solvers to address one of the major challenges faced by decision diagram based methods. Decision diagrams become more useful the wider they are allowed to be, but also become more costly to generate, especially with large numbers of variables. In the original version of this paper, we presented a method of peeling off a sub-graph of previously constructed diagrams and using it as the initial diagram for subsequent iterations that we call peel-and-bound. We tested the method on the sequence ordering problem, and our results indicate that our peel-and-bound scheme generates stronger bounds than a branch-and-bound scheme using the same propagators, and at significantly less computational cost. In this extended version of the paper, we also propose new methods for using relaxed decision diagrams to improve the solutions found using restricted decision diagrams, discuss the heuristic decisions involved with the parallelization of peel-and-bound, and discuss how peel-and-bound can be hyper-optimized for sequencing problems. Furthermore, we test the new methods on the sequence ordering problem and the traveling salesman problem with time-windows (TSPTW), and include an updated and generalized implementation of the algorithm capable of handling any discrete optimization problem. The new results show that peel-and-bound outperforms ddo (a decision diagram based branch-and-bound solver) on the TSPTW. We also close 15 open benchmark instances of the TSPTW.

Decision diagrams are an increasingly important tool in cutting-edge solvers for discrete optimization. However, the field of decision diagrams is relatively new, and is still incorporating the library of techniques that conventional solvers have had decades to build. We drew inspiration from the warm-start technique used in conventional solvers to address one of the major challenges faced by decision diagram based methods. Decision diagrams become more useful the wider they are allowed to be, but also become more costly to generate, especially with large numbers of variables. We present a method of peeling off a sub-graph of previously constructed diagrams and using it as the initial diagram for subsequent iterations that we call peel-and-bound. We test the method on the sequence ordering problem, and our results indicate that our peel-and-bound scheme generates stronger bounds than a branch-and-bound scheme using the same propagators, and at significantly less computational cost.

Prescriptive analytics provides organizations with scalable solutions for large-scale, automated decision making. At the core of prescriptive analytics methodology is optimization, a field devoted to the study of algorithms that solve complex decision-making problems. Optimization algorithms rely heavily on generic methods for identifying tight bounds, which provide both solutions to problems and optimality guarantees. In the last decade, decision diagrams (DDs) have demonstrated significant advantages in obtaining bounds compared with the standard linear relaxation commonly used by commercial solvers. However, the quality of the bounds computed by DDs depends heavily on the variable ordering chosen for the construction. Besides, the problem of finding an ordering that optimizes a given metric is generally NP-hard. This paper studies how machine learning, specifically deep reinforcement learning (DRL), can be used to improve bounds provided by DDs, in particular through learning a good variable ordering. The introduced DRL models improve primal and dual bounds, even over standard linear programming relaxations, and are integrated in a full-fledged branch-and-bound algorithm. This paper, therefore, provides a novel mechanism for utilizing machine learning to tighten bounds, adding to recent research on using machine learning to obtain high-quality heuristic solutions and, for the first time, using machine learning to improve relaxation bounds through a generic bounding method. We apply the methods on a classic optimization problem, the maximum independent set, and demonstrate through computational testing that optimization bounds can be significantly improved through DRL. We provide the code to replicate the results obtained on the maximum independent set. Summary of Contribution: This paper studies the use of reinforcement learning to compute a variable ordering of decision diagram-based approximations for discrete optimization problems. This is among the first works to propose the use of machine learning to improve upon generic bounding methods for discrete optimization problems, thereby establishing a critical bridge between optimization and learning.

This paper studies the team orienteering problem, where the arrival time and service time affect the collection of profits. Such interactions result in a nonconcave profit function. This problem integrates the aspect of time scheduling into the routing decision, which can be applied in humanitarian search and rescue operations where the survival rate declines rapidly. Rescue teams are needed to help trapped people in multiple affected sites, whereas the number of people who could be saved depends as well on how long a rescue team spends at each site. Efficient allocation and scheduling of rescue teams is critical to ensure a high survival rate. To solve the problem, we formulate a mixed-integer nonconcave programming model and propose a Benders branch-and-cut algorithm, along with valid inequalities for tightening the upper bound. To solve it more effectively, we introduce a hybrid heuristic that integrates a modified coordinate search (MCS) into an iterated local search. Computational results show that valid inequalities significantly reduce the optimality gap, and the proposed exact method is capable of solving instances where the mixed-integer nonlinear programming solver SCIP fails in finding an optimal solution. In addition, the proposed MCS algorithm is highly efficient compared with other benchmark approaches, whereas the hybrid heuristic is proven to be effective in finding high-quality solutions within short computing times. We also demonstrate the performance of the heuristic with the MCS using instances with up to 100 customers. Summary of Contribution: Motivated by search and rescue (SAR) operations, we consider a generalization of the well-known team orienteering problem (TOP) to incorporate a nonlinear time-varying profit function in conjunction with routing and scheduling decisions. This paper expands the envelope of operations research and computing in several ways. To address the scalability issue of this highly complex combinatorial problem in an exact manner, we propose a Benders branch-and-cut (BBC) algorithm, which allows us to efficiently deal with the nonconcave component. This BBC algorithm is computationally enhanced through valid inequalities used to strengthen the bounds of the BBC. In addition, we propose a highly efficient hybrid heuristic that integrates a modified coordinate search into an iterated local search. It can quickly produce high-quality solutions to this complex problem. The performance of our solution algorithms is demonstrated through a series of computational experiments.

Combinatorial optimization has found applications in numerous fields, from aerospace to transportation planning and economics. The goal is to find an optimal solution among a finite set of possibilities. The well-known challenge one faces with combinatorial optimization is the state-space explosion problem: the number of possibilities grows exponentially with the problem size, which makes solving intractable for large problems. In the last years, deep reinforcement learning (DRL) has shown its promise for designing good heuristics dedicated to solve NP-hard combinatorial optimization problems. However, current approaches have an important shortcoming: they only provide an approximate solution with no systematic ways to improve it or to prove optimality. In another context, constraint programming (CP) is a generic tool to solve combinatorial optimization problems. Based on a complete search procedure, it will always find the optimal solution if we allow an execution time large enough. A critical design choice, that makes CP non-trivial to use in practice, is the branching decision, directing how the search space is explored. In this work, we propose a general and hybrid approach, based on DRL and CP, for solving combinatorial optimization problems. The core of our approach is based on a dynamic programming formulation, that acts as a bridge between both techniques. We experimentally show that our solver is efficient to solve three challenging problems: the traveling salesman problem with time windows, the 4-moments portfolio optimization problem, and the 0-1 knapsack problem. Results obtained show that the framework introduced outperforms the stand-alone RL and CP solutions, while being competitive with industrial solvers.

End-to-end training of neural network solvers for combinatorial optimization problems such as the Travelling Salesman Problem is intractable and inefficient beyond a few hundreds of nodes. While state-of-the-art Machine Learning approaches perform closely to classical solvers when trained on trivially small sizes, they are unable to generalize the learnt policy to larger instances of practical scales. Towards leveraging transfer learning to solve large-scale TSPs, this paper identifies inductive biases, model architectures and learning algorithms that promote generalization to instances larger than those seen in training. Our controlled experiments provide the first principled investigation into such zero-shot generalization, revealing that extrapolating beyond training data requires rethinking the neural combinatorial optimization pipeline, from network layers and learning paradigms to evaluation protocols.

This paper addresses a class of two-stage robust optimization models with an exponential number of scenarios given implicitly. We apply Dantzig–Wolfe decomposition to exploit the structure of these models and show that the original problem reduces to a single-stage robust problem. We propose a Benders algorithm for the reformulated single-stage problem. We also develop a heuristic algorithm that dualizes the linear programming relaxation of the inner maximization problem in the reformulated model and iteratively generates cuts to shape the convex hull of the uncertainty set. We combine this heuristic with the Benders algorithm to create a more effective hybrid Benders algorithm. Because the master problem and subproblem in the Benders algorithm are mixed-integer programs, it is computationally demanding to solve them optimally at each iteration of the algorithm. Therefore, we develop novel stopping conditions for these mixed-integer programs and provide the relevant convergence proofs. Extensive computational experiments on a nurse planning problem and a two-echelon supply chain problem are performed to evaluate the efficiency of the proposed algorithms.

Optimal cost partitioning of classical planning heuristics has been shown to lead to excellent heuristic values but is often prohibitively expensive to compute. We analyze the application of Lagrangian decomposition, a classical tool in mathematical programming, to cost partitioning of operator-counting heuristics. This allows us to view the computation as an iterative process that can be seeded with any cost partitioning and that improves over time. In the case of non-negative cost partitioning of abstraction heuristics the computation reduces to independent shortest path problems and does not require an LP solver.

Finding tight bounds on the optimal solution is a critical element of practical solution methods for discrete optimization problems. In the last decade, decision diagrams (DDs) have brought a new perspective on obtaining upper and lower bounds that can be significantly better than classical bounding mechanisms, such as linear relaxations. It is well known that the quality of the bounds achieved through this flexible bounding method is highly reliant on the ordering of variables chosen for building the diagram, and finding an ordering that optimizes standard metrics is an NP-hard problem. In this paper, we propose an innovative and generic approach based on deep reinforcement learning for obtaining an ordering for tightening the bounds obtained with relaxed and restricted DDs. We apply the approach to both the Maximum Independent Set Problem and the Maximum Cut Problem. Experimental results on synthetic instances show that the deep reinforcement learning approach, by achieving tighter objective function bounds, generally outperforms ordering methods commonly used in the literature when the distribution of instances is known. To the best knowledge of the authors, this is the first paper to apply machine learning to directly improve relaxation bounds obtained by general-purpose bounding mechanisms for combinatorial optimization problems.

This paper presents an efficient algorithm for an integrated operating room planning and scheduling problem. It combines the assignment of surgeries to operating rooms and scheduling over a short-term planning horizon. This integration results in more stable planning through consideration of the operational details at the scheduling level, and this increases the chance of successful implementation. We take into account the maximum daily working hours of surgeons, prevent the overlapping of surgeries performed by the same surgeon, allow time for the obligatory cleaning when switching from infectious to noninfectious cases, and respect the surgery deadlines. We formulate the problem using a mathematical programming model and develop a branch-and-price-and-cut algorithm based on a constraint programming model for the subproblem. We also develop dominance rules and a fast infeasibility-detection algorithm based on a multidimensional knapsack problem to improve the efficiency of the constraint programming model. The computational results show that our method has an average optimality gap of 2.81% and significantly outperforms a compact mathematical formulation in the literature.

This paper presents a branch-and-price approach to solve personalized tour-scheduling problems in a multiactivity context. Two formulations are considered. In the first, columns correspond to daily shifts that are modeled with context-free grammars, and tours are assembled in the master problem by means of extra constraints. In the second formulation, columns correspond to tours that are built in a two-phase procedure. The first phase involves the composition of daily shifts; the second assembles those shifts to generate tours using a shortest path problem with resource constraints. Both formulations are flexible enough to allow different start times, lengths, and days-off patterns, as well as multiple breaks and continuity and discontinuity in labor requirements. We present computational experiments on problems dealing with up to five work activities and a one-week planning horizon. The results show that the second formulation is stronger in terms of its lower bound and that it is able to find high-quality solutions for all instances with an optimality gap lower than 1%.

Abstract The close‐enough arc routing problem has an interesting real‐life application to routing for meter reading. In this article, we propose a new mathematical formulation for this problem. We analyze our formulation and compare it with two formulations in the literature. We also develop branch‐and‐cut algorithms to solve the problem to optimality. We present computational results for instances based on three types of graphs: directed, undirected, and mixed. Copyright © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(1), 107–118 2014

We present a branch-and-price algorithm to solve personalized multi-activity shift scheduling problems. The subproblems in the column generation method are formulated using grammars and solved with dynamic programming. The expressiveness of context-free grammars is exploited to easily model restrictions over shifts, allowing the branch-and-price algorithm to solve large-scale problem instances. We present computational experiments on two types of multi-activity shift scheduling problems and compare our approach with existing methods in the literature. These experiments show that our approach can efficiently solve large-scale instances and is flexible enough to model different classes of problems.

This paper presents an optimal constraint programming approach for the open-shop scheduling problem, which integrates recent constraint propagation and branching techniques with new upper bound heuristics. Randomized restart policies combined with nogood recording allow us to search diversification and learning from restarts. This approach is compared with the best-known metaheuristics and exact algorithms, and it shows better results on a wide range of benchmark instances.

Abstract Given a fleet of vehicles assigned to a single depot, the vehicle routing problem with time windows (VRPTW) consists of determining a set of feasible vehicle routes to deliver goods to a set of customers while minimizing, first, the number of vehicles used and, second, total distance traveled. A large number of heuristic approaches for the VRPTW have been proposed in the literature. In this article, we present a large neighborhood search algorithm that takes advantage of the power of branch‐and‐price which is the leading methodology for the exact solution of the VRPTW. To ensure diversification during the search, this approach uses different procedures for defining the neighborhood explored at each iteration. Computational results on the Solomo's and the Gehring and Homberge's benchmark instances are reported. Compared to the best known methods, the proposed algorithm produces better solutions, especially on the largest instances where the number of vehicles used is significantly reduced. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

We model portions of the search tree via so-called search constraints. We focus on a particular kind of search constraint, the k-discrepancy constraint appearing in discrepancy-based search. The property that a node has an associated discrepancy k can be modeled (and enforced) through a linear constraint. Our key result is the exploitation of the k-discrepancy constraint to improve the bound given by any relaxation of a combinatorial optimization problem through the additive bounding technique (Fischetti and Toth 1989). We show how this simple idea can be effectively exploited to tighten relaxations in CP solvers and speed up the proof of optimality by performing a large variety of computational experiments on test problems involving the AllDifferent constraint. In this view, the additive bounding technique represents a non-trivial link between search and bound. Moreover, such a technique is general because it does not depend on either the AllDifferent constraint or the discrepancy search technique.