We propose a methodology at the nexus of operations research and machine learning (ML) leveraging generic approximators available from ML to accelerate the solution of mixed-integer linear two-stage stochastic programs. We aim at solving problems where the second stage is demanding. Our core idea is to gain large reductions in online solution time, while incurring small reductions in first-stage solution accuracy by substituting the exact second-stage solutions with fast, yet accurate, supervised ML predictions. This upfront investment in ML would be justified when similar problems are solved repeatedly over time—for example, in transport planning related to fleet management, routing, and container yard management. Our numerical results focus on the problem class seminally addressed with the integer and continuous L-shaped cuts. Our extensive empirical analysis is grounded in standardized families of problems derived from stochastic server location (SSLP) and stochastic multi-knapsack (SMKP) problems available in the literature. The proposed method can solve the hardest instances of SSLP in less than 9% of the time it takes the state-of-the-art exact method, and in the case of SMKP, the same figure is 20%. Average optimality gaps are, in most cases, less than 0.1%. History: Accepted by Alice Smith, Area Editor (for this paper) for Design and Analysis of Algorithms–Discrete. Funding: Financial support from the Institut de Valorisation des Données (IVADO) Fundamental Research Project Grants [project entitled “Machine Learning for (Discrete) Optimization”]; Canada Research Chairs; the Natural Sciences and Engineering Research Council of Canada [Collaborative Research and Development Grant CRD-477938-14]; and the Canadian National Railway Company Chair in Optimization of Railway Operations at Université de Montréal is gratefully acknowledged. E. Frejinger holds a Canada Research Chair. Computations were made on the supercomputer Béluga, managed by Calcul Québec and Digital Research Alliance of Canada. The operation of this supercomputer is funded by the Canada Foundation for Innovation; the Ministère de l’Économie, de la Science et de l’Innovation du Québec; and the Fonds de Recherche du Québec – Nature et Technologies.

We present a new model for finding the optimal placement of electric vehicle charging stations across a multiperiod time frame so as to maximise electric vehicle adoption. Via the use of stochastic discrete choice models and user classes, this work allows for a granular modelling of user attributes and their preferences in regard to charging station characteristics. We adopt a simulation approach and precompute error terms for each option available to users for a given number of scenarios. This results in a bilevel optimisation model that is, however, intractable for all but the simplest instances. Our major contribution is a reformulation into a maximum covering model, which uses the precomputed error terms to calculate the users covered by each charging station. This allows solutions to be found more efficiently than for the bilevel formulation. The maximum covering formulation remains intractable in some instances, so we propose rolling horizon, greedy, and greedy randomised adaptive search procedure heuristics to obtain good-quality solutions more efficiently. Extensive computational results are provided, and they compare the maximum covering formulation with the current state of the art for both exact solutions and the heuristic methods. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by Hydro-Québec and the Natural Sciences and Engineering Research Council of Canada [Discovery Grant 2017-06054; Collaborative Research and Development Grant CRDPJ 536757–19]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0185 .

Abstract We introduce a modeling framework for stochastic rider‐driver matching in many‐to‐one ridesharing systems, in which drivers have to be selected before the exact rider demand is known. The modeling framework allows for the use of driver booking fees and penalties for unmatched drivers, therefore supporting different system operating modes. We model this problem as a two‐stage stochastic set packing problem. To tackle the intractability of the stochastic problem, we introduce three model approximations and evaluate them on a large set of benchmark instances for three different system operating modes. Our computational experiments show the superiority of some model approximations over others and provide valuable insights on the impact of penalties and booking fees on the system's profitability and user satisfaction.

We study the network pricing problem where the leader maximizes revenue by determining the optimal amounts of tolls to charge on a set of arcs, under the assumption that the followers will react rationally and choose the shortest paths to travel. Many distinct single-level reformulations of this bilevel optimization program have been proposed; however, their relationship has not been established. In this paper, we aim to build a connection between those reformulations and explore the combination of the path representation with various modeling options, allowing us to generate 12 different reformulations of the problem. Moreover, we propose a new path enumeration scheme, path-based preprocessing, and hybrid framework to further improve performance and robustness when solving the final model. We provide numerical results, comparing all the derived reformulations and confirming the efficiency of the novel dimensionality reduction procedures.

The multiple knapsack problem is a well-studied combinatorial optimization problem with several practical and theoretical applications. It consists of packing some subset of n items into m knapsacks such that the total profit of the chosen items is maximum. A new formulation of the problem is presented, where a Lagrangian relaxation is derived, and we prove that it dominates the commonly used relaxations for this problem. We also present a Dantzig-Wolfe decomposition of the new formulation that we solve to optimality using a branch-and-price algorithm, where its main advantage comes from the fact that it is possible to control whether an item is included in some knapsack or not. An improved algorithm for solving the resulting packing subproblems is also introduced. Computational experiments then show that the new approach achieves state-of-the-art results. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the Canadian Natural Sciences and Engineering Research Council (NSERC) [Grants 2017-06054 and 2021-04037]. This support is gratefully acknowledged.

We consider the dynamic facility location problem with generalized modular capacities, a multiperiod facility location problem in which the costs for capacity changes may differ for all pairs of capacity levels. The problem embeds a complex cost structure and generalizes several existing facility location problems, such as those that allow temporary facility closing or capacity expansion and reduction. As the model may become very large, general-purpose mixed-integer programming (MIP) solvers are limited to solving instances of small to medium size. In this paper, we extend the generalized model to the case of multiple commodities. We propose Lagrangian heuristics, based on subgradient and bundle methods, to find good quality solutions for large-scale instances with up to 250 facility locations and 1,000 customers. To improve the final solution quality, a restricted MIP model is solved based on the information collected through the solution of the Lagrangian dual. Computational results show that the Lagrangian-based heuristics provide highly reliable results for all problem variants considered. They produce good quality solutions in short computing times even for instances where state-of-the-art MIP solvers do not find feasible solutions. The strength of the formulation also allows the method to provide tight bounds on the optimal value. Data and the online appendix are available at https://doi.org/10.1287/ijoc.2016.0738 .

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%.

Given a connected and undirected graph G, the degree preserving spanning tree problem (DPSTP) asks for a spanning tree of G with the maximum number of vertices having the same degree in the tree and in G. These are called full degree vertices. We introduce integer programming formulations, valid inequalities and four exact solution approaches based on different formulations. Two branch‐and‐bound procedures, a branch‐and‐cut (BC) algorithm and an iterative probing combinatorial Benders decomposition method are introduced here. The problem of optimally lifting one of the classes of valid inequalities proposed here is equivalent to solving a DPSTP instance, for a conveniently defined subgraph of G. We thus apply one of the proposed methods to optimally lift these cuts, within the other solution methods. In doing so, two additional algorithms, a hybrid Benders decomposition and a hybrid BC are proposed. Extensive computational experiments are conducted with the solution algorithms introduced in this study. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(4), 329–343 2015

We develop a variant of the variable neighborhood search (VNS) metaheuristic called the multilayer VNS (MLVNS). It consists in partitioning the neighborhood structures into multiple layers. For each layer , a VNS defined on the associated neighborhood structures is invoked, each move being evaluated and completed by a recursive call to the MLVNS at layer . A specific MLVNS is developed to solve approximately a class of two‐level uncapacitated facility location problems with single assignment (TUFLPS), when only mild assumptions are imposed on the cost functions. Two special cases are used to illustrate the efficiency of the MLVNS: the classical TUFLPS and a problem with modular costs derived from a real‐life case. To assess the efficiency of the MLVNS, computational results on a large set of instances are compared with those obtained by slope scaling heuristic methods and by solving integer programming models using a state‐of‐the‐art commercial solver. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(3), 214–234 2015

In this paper we present an exact algorithm for the capacitated location-routing problem (CLRP) based on cut-and-column generation. The CLRP is formulated as a set-partitioning problem that also inherits all of the known valid inequalities for the flow formulations of the CLRP. We introduce five new families of inequalities that are shown to dominate some of the cuts from the two-index formulation. The problem is solved by column generation, where the subproblem consists in finding a shortest path of minimum reduced cost under capacity constraints. We first use the two-index formulation for enumerating all of the possible subsets of depot locations that could lead to an optimal solution of cost less than or equal to a given upper bound. For each of these subsets, the corresponding multiple depot vehicle routing problem is then solved by means of column generation. The results show that we can improve the bounds found in the literature, solve to optimality some previously open instances, and improve the upper bounds on some other instances.

We present exact algorithms for solving the minimum connected dominating set problem in an undirected graph. The algorithms are based on two approaches: a Benders decomposition algorithm and a branch-and-cut method. We also develop a hybrid algorithm that combines these two approaches. Two variants of each of the three resulting algorithms are considered: a stand-alone version and an iterative probing variant. The latter variant is based on a simple property of the problem, which states that if no connected dominating set of a given cardinality exists, then there are no connected dominating sets of lower cardinality. We present computational results on a large set of instances from the literature.

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.

Abstract We present cycle‐based algorithmic approaches to find local minima of a nonconvex and nonsmooth model for capacity expansion of a network supporting multicommodity flows. By exploiting complete optimality conditions for local minima, we give the convergence analysis of the negative‐cost cycle canceling method. The cycle canceling method is embedded in a tabu search strategy to explore the solution space beyond the first local optimum. Reaching a local optimum, the idea is to accept a cost‐increasing solution by pushing flow around a positive‐cost cycle, and then to make use of the cycle cancelling method incorporating tabu search memory structures to find high quality local optima. Computational experiments on instances of the literature show that the tabu search algorithm can significantly improve feasible solutions obtained by the local optimization procedure, and it outperforms the capacity and flow assignment heuristic in terms of solution quality. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008