The alternating current optimal transmission switching (ACOTS) problem incorporates line switching decisions into the alternating current optimal power flow framework, offering well-known benefits in reducing operational costs and enhancing system reliability. ACOTS optimization models contain discrete variables and nonlinear, nonconvex constraints, which make them difficult to solve. In this work, we develop strengthened quadratic convex (QC) relaxations for ACOTS, in which we tighten the relaxation with several new valid inequalities, including a novel kind of on/off cycle–based polynomial constraints by taking advantage of the network structure. We linearize the sum of on/off trilinear terms in the relaxation using extreme-point representation, demonstrating theoretical tightness, and efficiently incorporate on/off cycle–based polynomial constraints through disjunctive programming–based cutting planes. Combined with an optimization-based bound-tightening algorithm, this results in the tightest QC-based ACOTS relaxation to date. We additionally propose a novel maximum spanning tree–based heuristic to improve the computational performance by fixing certain lines to be switched on. Our extensive numerical experiments on medium-scale power grid library instances show significant improvements on relaxation bounds, whereas tests on large-scale instances with up to 2,312 buses demonstrate substantial performance gains. To our knowledge, this is the first ACOTS relaxation-based approach to demonstrate near-optimal switching solutions on realistic large-scale power grid instances. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: The authors gratefully acknowledge support from the U.S. Department of Energy through Los Alamos National Laboratory’s directed research and development program [Grant 20230091ER: Learning to Accelerate Global Solutions for Non-Convex Optimization]. 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.0236 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0236 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

This article explores the integration of Automated Guided Vehicles (AGVs) in warehouse order picking, a crucial and cost-intensive aspect of warehouse operations. The booming AGV industry, accelerated by the COVID-19 pandemic, is witnessing widespread adoption due to its efficiency, reliability, and cost-effectiveness in automating warehouse tasks. Through the strategic use of AGVs, this article focuses on enhancing the picker-to-parts system, which involves workers travelling to item locations, collecting them, and moving to the next location. We propose a novel MDP model for coordinating a hybrid team of human and AGV workers, aiming to maximize order throughput and operational efficiency, and employ a Neural Approximate Dynamic Programming (NeurADP) approach as the solution method. Specifically, our solution framework involves innovative solutions for non-myopic decision making, order batching, and battery management. The numerical results demonstrate that the NeurADP policy outperforms all benchmark policies, including both myopic and non-myopic ones, with a 3.32% and 5.44% improvement in order fulfillment over the alternatives. Comprehensive empirical analysis offers valuable insights for managing a heterogeneous workforce in a hybrid warehouse setting, highlighting the contributions of our work to the field of warehouse automation and logistics.

Sector duration optimization (SDO) is a problem arising in treatment planning for stereotactic radiosurgery on Gamma Knife. Given a set of isocenter locations, SDO aims to select collimator size configurations and irradiation times thereof such that target tissues receive prescribed doses in a reasonable amount of treatment time and healthy tissues nearby are spared. We present a multiobjective linear programming model for SDO to generate a diverse collection of solutions so that clinicians can select the most appropriate treatment. We develop a generic two-phase solution strategy based on the ε-constraint method for solving multiobjective optimization models, 2phasε, which aims to systematically increase the number of high-quality solutions obtained, instead of conducting a traditional uniform search. To improve solution quality further and to accelerate the procedure, we incorporate some general and problem-specific enhancements. Moreover, we propose an alternative version of 2phasε, which makes use of machine learning tools to reduce the computational effort. In our computational study on eight previously treated real test cases, a significant portion of 2phasε solutions outperformed clinical results and those from a single-objective model from the literature. In addition to significant benefits of the algorithmic enhancements, our experiments illustrate the usefulness of machine learning strategies to reduce the overall run times nearly by half while maintaining or besting the clinical practice. History: Accepted by Paul Brooks, Area Editor for Applications in Biology, Medicine, and Healthcare. Funding: This work was supported in part by the Natural Sciences and Engineering Research Council of Canada [Discovery Grant RGPIN-2019-05588]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplementary Information [ https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.1252 ] or is available from the IJOC GitHub software repository ( https://github.com/INFORMSJoC ) at [ http://dx.doi.org/10.5281/zenodo.7048848 ].

Stochastic Programming is a powerful modeling framework for decision-making under uncertainty. In this work, we tackle two-stage stochastic programs (2SPs), the most widely used class of stochastic programming models. Solving 2SPs exactly requires optimizing over an expected value function that is computationally intractable. Having a mixed-integer linear program (MIP) or a nonlinear program (NLP) in the second stage further aggravates the intractability, even when specialized algorithms that exploit problem structure are employed.Finding high-quality (first-stage) solutions -- without leveraging problem structure -- can be crucial in such settings. We develop Neur2SP, a new method that approximates the expected value function via a neural network to obtain a surrogate model that can be solved more efficiently than the traditional extensive formulation approach. Neur2SP makes no assumptions about the problem structure, in particular about the second-stage problem, and can be implemented using an off-the-shelf MIP solver. Our extensive computational experiments on four benchmark 2SP problem classes with different structures (containing MIP and NLP second-stage problems) demonstrate the efficiency (time) and efficacy (solution quality) of Neur2SP. In under 1.66 seconds, Neur2SP finds high-quality solutions across all problems even as the number of scenarios increases, an ideal property that is difficult to have for traditional 2SP solution techniques. Namely, the most generic baseline method typically requires minutes to hours to find solutions of comparable quality.

This paper provides a novel framework for solving multiobjective discrete optimization problems with an arbitrary number of objectives. Our framework represents these problems as network models, in that enumerating the Pareto frontier amounts to solving a multicriteria shortest-path problem in an auxiliary network. We design techniques for exploiting network models in order to accelerate the identification of the Pareto frontier, most notably a number of operations to simplify the network by removing nodes and arcs while preserving the set of nondominated solutions. We show that the proposed framework yields orders-of-magnitude performance improvements over existing state-of-the-art algorithms on five problem classes containing both linear and nonlinear objective functions. Summary of Contribution: Multiobjective optimization has a long history of research with applications in several domains. Our paper provides an alternative modeling and solution approach for multiobjective discrete optimization problems by leveraging graphical structures. Specifically, we encode the decision space of a problem as a layered network and propose graph reduction operators to preserve only solutions whose image are part of the Pareto frontier. The nondominated solutions can then be extracted through shortest-path algorithms on such a network. Numerical results comparing our method with state-of-the-art approaches on several problem classes, including the knapsack, set covering, and the traveling salesperson problem (TSP), suggest orders-of-magnitude runtime speed-ups for exactly enumerating the Pareto frontier, especially when the number of objective functions grows.

Inverse optimization—determining parameters of an optimization problem that render a given solution optimal—has received increasing attention in recent years. Although significant inverse optimization literature exists for convex optimization problems, there have been few advances for discrete problems, despite the ubiquity of applications that fundamentally rely on discrete decision making. In this paper, we present a new set of theoretical insights and algorithms for the general class of inverse mixed integer linear optimization problems. Specifically, a general characterization of optimality conditions is established and leveraged to design new cutting plane solution algorithms. Through an extensive set of computational experiments, we show that our methods provide substantial improvements over existing methods in solving the largest and most difficult instances to date.

In a telecommunication network, routing and wavelength assignment (RWA) is the problem of finding lightpaths for incoming connection requests. When facing a dynamic traffic, greedy assignment of lightpaths to incoming requests based on predefined deterministic policies leads to a fragmented network that cannot make use of its full capacity because of stranded bandwidth. At this point, service providers try to recover the capacity via a defragmentation process. We study this setting from two perspectives: (i) while granting the connection requests via the RWA problem and (ii) during the defragmentation process by lightpath rerouting. For both problems, we present the first two-stage stochastic integer programming model incorporating incoming request uncertainty to maximize the expected grade of service. We develop a decomposition-based solution approach, which uses various relaxations of the problem and a newly developed problem-specific cut family. Simulation of two-stage policies for a variety of instances in a rolling-horizon framework of 52 stages shows that our stochastic models provide high-quality solutions when compared with traditionally used deterministic ones. Specifically, the proposed provisioning policies yield improvements of up to 19% in overall grade of service and 20% in spectrum saving, while the stochastic lightpath rerouting policies grant up to 36% more requests, using up to just 4% more bandwidth spectrum. Summary of Contribution: For handling the intrinsic uncertainty of demand in the telecommunications industry, this paper proposes novel stochastic models and solution methodology for two fundamental problems in telecommunications at operational level: (i) routing and wavelength assignment (RWA) and (ii) lightpath rerouting problem. Despite the vast literature on the RWA problem, stochastic optimization has not been considered as a viable solution for resource allocation in optical networks. We propose two-stage stochastic programming models for both problems and design efficient decomposition-based solution methods that use various relaxations of the models and a new family of cutting planes. Our extensive and rigorous numerical experiments show the significant merit of incorporating uncertainty into decision making, as well as the effectiveness of the decomposition framework and our newly designed family of cuts in enhancing the solvability of both models. This work opens new avenues to explore where the powerful stochastic programming literature can be leveraged to make operational decisions in telecommunications problems, a field that currently relies mostly on deterministic and heuristic solution methods.

Given an integer dimension K and a simple, undirected graph G with positive edge weights, the Distance Geometry Problem (DGP) aims to find a realization function mapping each vertex to a coordinate in [Formula: see text] such that the distance between pairs of vertex coordinates is equal to the corresponding edge weights in G. The so-called discretization assumptions reduce the search space of the realization to a finite discrete one, which can be explored via the branch-and-prune (BP) algorithm. Given a discretization vertex order in G, the BP algorithm constructs a binary tree where the nodes at a layer provide all possible coordinates of the vertex corresponding to that layer. The focus of this paper is on finding optimal BP trees for a class of discretizable DGPs. More specifically, we aim to find a discretization vertex order in G that yields a BP tree with the least number of branches. We propose an integer programming formulation and three constraint programming formulations that all significantly outperform the state-of-the-art cutting-plane algorithm for this problem. Moreover, motivated by the difficulty in solving instances with a large and low-density input graph, we develop two hybrid decomposition algorithms, strengthened by a set of valid inequalities, which further improve the solvability of the problem. Summary of Contribution: We present a new model to solve a combinatorial optimization problem on graphs, MIN DOUBLE, which comes from the highly active area of distance geometry and has applications in a wide variety of fields. We use integer programming (IP) and present the first constraint programming (CP) models and hybrid decomposition methods, implemented as a branch-and-cut procedure, for MIN DOUBLE. Through an extensive computational study, we show that our approaches advance the state of the art for MIN DOUBLE. We accomplish this by not only combining generic techniques from IP and CP but also exploring the structure of the problem in developing valid inequalities and variable fixing rules. Our methods significantly improve the solvability of MIN DOUBLE, which we believe can also provide insights for tackling other problem classes and applications.

Abstract The Distance Geometry Problem (DGP) seeks to find positions for a set of points in geometric space when some distances between pairs of these points are known. The so‐called discretization assumptions allow us to discretize the search space of DGP instances. In this paper, we focus on a key subclass of DGP, namely the Discretizable Molecular DGP, and study its associated graph vertex ordering problem, the Contiguous Trilateration Ordering Problem (CTOP), which helps solve DGP. We propose the first constraint programming formulations for CTOP, as well as a set of checks for proving infeasibility, domain reduction techniques, symmetry breaking constraints, and valid inequalities. Our computational results on random and pseudo‐protein instances indicate that our formulations outperform the state‐of‐the‐art integer programming formulations.

The distributed operating room (OR) scheduling problem aims to find an assignment of surgeries to ORs across collaborating hospitals that share their waiting lists and ORs. We propose a stochastic extension of this problem where surgery durations are considered to be uncertain. In order to obtain solutions for the challenging stochastic model, we use sample average approximation and develop two enhanced decomposition frameworks that use logic-based Benders (LBBD) optimality cuts and binary decision diagram based Benders cuts. Specifically, to the best of our knowledge, deriving LBBD optimality cuts in a stochastic programming context is new to the literature. Our computational experiments on a hospital data set illustrate that the stochastic formulation generates robust schedules and that our algorithms improve the computational efficiency. Summary of Contribution: We propose a new model for an important problem in healthcare scheduling, namely, stochastic distributed operating room scheduling, which is inspired by a current practice in Toronto, Ontario, Canada. We develop two decomposition methods that are computationally faster than solving the model directly via a state-of-the-art solver. We present both some theoretical results for our algorithms and numerical results for the evaluation of the model and algorithms. Compared with its deterministic counterpart in the literature, our model shows improvement in relevant evaluation metrics for the underlying scheduling problem. In addition, our algorithms exploit the structure of the model and improve its solvability. Those algorithms also have the potential to be used to tackle other planning and scheduling problems with a similar structure.

A proper edge‐coloring of a given undirected graph with natural numbers identified with colors is aninterval (or consecutive) coloringif the colors of edges incident to each vertex form an interval of consecutive integers. Not all graphs admit such an edge‐coloring and the problem of deciding whether a graph is interval colorable is NP‐complete. For a graph that is not interval colorable, determining a graph invariant called the (minimum)deficiencyis a widely used approach. Deficiency is a measure of how close the graph is to have an interval coloring. The majority of the studies in the literature either derive bounds on the deficiency of general graphs or calculate the deficiency of graphs belonging to some special graph classes. In this work, we derive integer programming formulations of theMinimum Deficiency Problemwhich seeks to find the exact deficiency value of a graph, given a bound on the number of colors that can be used. We further enhance the formulation by introducing a family of valid inequalities. Then, we solve our model via abranch‐and‐cut algorithm. Our computational study on a large set of random graphs illustrates the strength of our formulation and the efficiency of the proposed approach.

With stochastic integer programming as the motivating application, we investigate techniques to use integrality constraints to obtain improved cuts within a Benders decomposition algorithm. We compare the effect of using cuts in two ways: (i) cut-and-project, where integrality constraints are used to derive cuts in the extended variable space, and Benders cuts are then used to project the resulting improved relaxation, and (ii) project-and-cut, where integrality constraints are used to derive cuts directly in the Benders reformulation. For the case of split cuts, we demonstrate that although these approaches yield equivalent relaxations when considering a single split disjunction, cut-and-project yields stronger relaxations in general when using multiple split disjunctions. Computational results illustrate that the difference can be very large, and demonstrate that using split cuts within the cut-and-project framework can significantly improve the performance of Benders decomposition.

Abstract– We investigate the problem of finding a maximal matching that has minimum total weight on a given edge‐weighted graph. Although the minimum weight maximal matching problem is NP‐hard in general, polynomial time exact or approximation algorithms on several restricted graph classes are given in the literature. In this article, we propose an exact algorithm for solving several variants of the problem on general graphs. In particular, we develop integer programming (IP) formulations for the problem and devise a decomposition algorithm, which is based on a combination of IP techniques and combinatorial matching algorithms. Our computational tests on a large suite of randomly generated graphs show that our decomposition approach significantly improves the solvability of the problem compared to the underlying IP formulation. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 62(4), 273–287 2013