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.

This paper offers a methodological contribution at the intersection of machine learning and operations research. Namely, we propose a methodology to quickly predict expected tactical descriptions of operational solutions (TDOSs). The problem we address occurs in the context of two-stage stochastic programming, where the second stage is demanding computationally. We aim to predict at a high speed the expected TDOS associated with the second-stage problem, conditionally on the first-stage variables. This may be used in support of the solution to the overall two-stage problem by avoiding the online generation of multiple second-stage scenarios and solutions. We formulate the tactical prediction problem as a stochastic optimal prediction program, whose solution we approximate with supervised machine learning. The training data set consists of a large number of deterministic operational problems generated by controlled probabilistic sampling. The labels are computed based on solutions to these problems (solved independently and offline), employing appropriate aggregation and subselection methods to address uncertainty. Results on our motivating application on load planning for rail transportation show that deep learning models produce accurate predictions in very short computing time (milliseconds or less). The predictive accuracy is close to the lower bounds calculated based on sample average approximation of the stochastic prediction programs.

We present new distance computation algorithms using hierarchies of rectangular swept spheres. Each bounding volume of the tree is described as the Minkowski sum of a rectangle and a sphere, and fits tightly to the underlying geometry. We present accurate and efficient algorithms to build the hierarchies and perform distance queries between the bounding volumes. We also present traversal techniques for accelerating distance queries using coherence and priority directed search. These algorithms have been used to perform proximity queries for applications including virtual prototyping, dynamic simulation, and motion planning on complex models. As compared to earlier algorithms based on bounding volume hierarchies for separation distance and approximate distance computation, our algorithms have achieved significant speedups on many benchmarks.

No abstract available.

We describe an approach for interactive collision detection and proximity computations on massive models composed of millions of geometric primitives. We address issues related to interactive data access and processing in a large geometric database, which may not fit into main memory of typical desktop workstations or computers. We present a new algorithm using overlap graphs for localizing the “regions of interest” within a massive model, thereby reducing runtime memory requirements. The overlap graph is computed off‐line, pre‐processed using graph partitioning algorithms, and modified on the fly as needed. At run time, we traverse localized sub‐graphs to check the corresponding geometry for proximity and pre‐fetch geometry and auxiliary data structures. To perform interactive proximity queries, we use bounding‐volume hierarchies and take advantage of spatial and temporal coherence. Based on the proposed algorithms, we have developed a system called IMMPACT and used it for interaction with a CAD model of a power plant consisting of over 15 million triangles. We are able to perform a number of proximity queries in real‐time on such a model. In terms of model complexity and application to large models, we have improved the performance of interactive collision detection and proximity computation algorithms by an order of magnitude.