Search

Worldwide epidemics, such as corona virus disease 2019 (COVID-19), cause unprecedented challenges for society and its healthcare systems. Governments attempt to mitigate those challenges by either reducing healthcare demand (“flattening the curve” by imposing restrictions, e.g., on travel or social gatherings) or by increasing healthcare capacity, for example, by canceling elective procedures or setting up field hospitals. To implement these mitigation procedures efficiently, accurate and timely forecasts of the epidemic’s progression are necessary. In this paper, we develop an innovative forecasting methodology based on the ideas of long short-term memory (LSTM) recurrent neural networks. LSTM models are shown to outperform traditional forecasting models, especially when the relationship between input and output is complex and not available in closed form. However, whereas LSTM models perform well for data that changes dynamically over time, one shortcoming is that they are not directly applicable when the data also includes static, nontemporal components. In this work, we propose an [Formula: see text] model that overcomes this limitation. Our model leverages a private partnership with a mobile data company in order to capture population mobility (using mobility indices derived from mobile device data), which allows us to anticipate an epidemic’s spread early and accurately. In addition, we also leverage a public partnership with a consortium of hospitals. Using hospital admissions (rather than, say, positive caseload) results in an unbiased measure of the severity of an epidemic because patients seek and are admitted to hospital care only when symptoms worsen beyond a critical point. We illustrate the effectiveness of our method on forecasting COVID-19 for a major U.S. metropolitan area where it has aided decision makers of the emergency policy group. Our model improves the predictive accuracy of hospital admission by a factor of 2.5× as compared with competing models in the same analytical space. History: Accepted by J. Paul Brooks, Area Editor for Applications in Biology, Medicine, & Healthcare. Funding: This research was funded by a monetary gift from Hillsborough County to establish the Pandemic Response Research Fund at University of South Florida. 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.1269 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0027 ) at ( http://dx.doi.org/10.5281/zenodo.7112004 ).

This paper introduces a major redesign of SimOpt, a testbed of simulation-optimization (SO) problems and solvers. The testbed promotes the empirical evaluation and comparison of solvers and aims to accelerate their development. Relative to previous versions of SimOpt, the redesign ports the code to an object-oriented architecture in Python; uses an implementation of the MRG32k3a random number generator that supports streams, substreams, and subsubstreams; supports the automated use of common random numbers for ease and efficiency; includes a powerful suite of plotting tools for visualizing experiment results; uses bootstrapping to obtain error estimates; accommodates the use of data farming to explore simulation models and optimization solvers as their input parameters vary; and provides a graphical user interface. The SimOpt source code is available on a GitHub repository under a permissive open-source license and as a Python package. History: Accepted by Ted Ralphs, Area Editor for Software Tools. Funding: This work was supported by the National Science Foundation [Grant CMMI-2035086]. 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.1273 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0011 ) at ( http://dx.doi.org/10.5281/zenodo.7468744 ).

Power system restoration is an essential activity for grid resilience, where grid operators restart generators, re-establish transmission paths, and restore loads after a blackout event. With a goal of restoring electric service in the shortest time, the core decisions in restoration planning are to partition the grid into sub-networks, each of which has an initial power source for black-start (called sectionalization problem), and then restart all generators in each network (called generator startup sequencing problem or GSS) as soon as possible. Due to the complexity of each problem, the sectionalization and GSS problems are usually solved separately, often resulting in a sub-optimal solution. Our paper develops models and computational methods to solve the two problems simultaneously. We first study the computational complexity of the GSS problem and develop an efficient integer linear programming formulation. We then integrate the GSS problem with the sectionalization problem and develop an integer linear programming formulation for the parallel power system restoration (PPSR) problem to find exact optimal solutions. To solve larger systems, we then develop bounding approaches that find good upper and lower bounds efficiently. Finally, to address computational challenges for very large power grids, we develop a randomized approach to find a high-quality feasible solution quickly. Our computational experiments demonstrate that the proposed approaches are able to find good solutions for PPSR in up to 2000-bus systems., Comment: 30 pages, working paper

Motivated by rising concerns regarding global warming and traffic congestion effects, we study the time-dependent green vehicle routing problem with time windows (TDGVRPTW), aiming to minimize carbon emissions. The TDGVRPTW is a variant of the time-dependent vehicle routing problem (TDVRP) in which, in addition to the time window constraints, the minimization of carbon emissions requires determination of the optimal departure times for vehicles, from both the depot and customer location(s). Accordingly, the first exact method based on a branch-cut-and-price (BCP) algorithm is proposed for solving the TDGVRPTW. We introduce the notation of a time-dependent (TD) arc and describe how to identify the nondominated TD arcs in terms of arc departure times. In this way, we reduce infinitely many TD arcs to a finite set of nondominated TD arcs. We design a state-of-the-art BCP algorithm for the TDGVRPTW with labeling and limited memory subset row cuts, together with effective dominance rules for eliminating dominated TD arcs. The exact method is tested on a set of test instances derived from benchmark instances proposed in the literature. The results show the effectiveness of the proposed exact method in solving TDGVRPTW instances involving up to 100 customers. Summary of Contribution: Due to the environmental situation, green vehicle routing problems (GVRPs) aim to consider greenhouse gas emissions reduction, while routing the vehicles, and play a key role in transportation and logistics. Vehicle greenhouse gas emissions strongly depend on the vehicle speeds and traffic conditions which in real life vary continuously over time. To tackle these challenges, we address the time-dependent green vehicle routing problem with time windows (TDGVRPTW) aimed at reducing total carbon emissions under time-dependent travel times and time window constraints. We design an effective exact method for the TDGVRPTW based on a state-of-the-art branch-cut-and-price algorithm. The paper is both of methodological value for researchers and of interest for practitioners. For researchers, the presented algorithm is amenable for various routing constraints and provides a ground for further studies and research. For practitioners, the paper suggests insights on how the carbon emissions change based on different vehicle speed profiles. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This research is supported by the National Natural Science Foundation of China [Grants 71831003, 71831006, 72171043, and 71901180] and the Fundamental Research Funds for the Central Universities [Grants N170405005 and N180704015]. Supplemental Material: The electronic companion is available at https://doi.org/10.1287/ijoc.2022.1195 .

This work investigates lot sizing with component substitution under demand uncertainty. The integration of component substitution with lot sizing in an uncertain demand context is important because the consolidation of the demand for components naturally allows risk-pooling and reduces operating costs. The considered problem is relevant not only in a production context, but also in the context of distribution planning. We propose a stochastic programming formulation for the static–dynamic type of uncertainty, in which the setup decisions are frozen but the production and consumption quantities are decided dynamically. To tackle the scalability issues commonly encountered in multistage stochastic optimization, this paper investigates the use of stochastic dual dynamic programming (SDDP). In addition, we consider various improvements of SDDP, including the use of strong cuts, the fast generation of cuts by solving the linear relaxation of the problem, and retaining the average demand scenarios. Finally, we propose two heuristics, namely, a hybrid of progressive hedging with SDDP and a heuristic version of SDDP. Computational experiments conducted on well-known instances from the literature show that the heuristic version of SDDP outperforms other methods. The proposed method can plan with up to 10 decision stages and 20 scenarios per stage, which results in 2010 scenario paths in total. Moreover, as the heuristic version of SDDP can replan to account for new information in less than a second, it is convenient in a dynamic context. Summary of Contribution: We believe our paper is suitable for the mission and scope of IJOC because we design efficient algorithms to solve an operations research problem. More precisely, we investigate the use of stochastic dual dynamic programming (SDDP) for lot sizing with component substitution under demand uncertainty. In this work, we consider the static–dynamic decision framework, and a good approximation of the expected costs in this context requires us to solve the problem with a large number of scenarios of future demand. As solving the considered problem is computationally intensive, we investigate the use of SDDP, which decomposes the problem per decision stage. We study several enhancements of SDDP, such as the use of strong cuts, the incorporation of a lower bound computed with the average demand scenario, the multicut version of SDDP, and scenario sampling with randomized quasi–Monte Carlo. Despite these improvements, the convergence of SDDP remains slow. Consequently, we propose a heuristic version of SDDP and a hybrid of progressive hedging and SDDP. We present the results of an extensive computational study performed on well-known instances from the literature. The results show that the heuristic SDDP outperforms the hybrid of progressive hedging with SDDP and state-of-the-art methods from the literature. Besides, our analysis shows that component substitution can pool the risk, and it allows maintaining the same service level with less inventory. The presented methodology can be used by practitioners to size their production lots, and subsequent researchers can build upon our results to consider uncertainty in other parameters, such as lead times, yields, and production capacities. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This work was supported by Mitacs and the Institut de Valorisation des Données (IVADO). Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.1215 .

In this paper, an algorithm for maximizing a convex function over a convex feasible set is proposed. The algorithm, called CoMax, consists of two phases: in phase 1, a feasible starting point is obtained that is used in a gradient ascent algorithm in phase 2. The main contribution of the paper is connected to phase 1; five different methods are used to approximate the original NP-hard problem of maximizing a convex function (MCF) by a tractable convex optimization problem. All the methods use the minimizer of the convex objective function in their construction. In phase 2, the gradient ascent algorithm yields stationary points to the MCF problem. The performance of CoMax is tested on a wide variety of MCF problems, demonstrating its efficiency. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: This work was supported by the Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Grant 406.17.511]. 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.1238 ] or is available from the IJOC GitHub software repository ( https://github.com/INFORMSJoC ) at [ http://dx.doi.org/10.5281/zenodo.6884872 ].

This paper considers the problem of minimizing a convex expectation function with a set of inequality convex expectation constraints. We propose a stochastic augmented Lagrangian-type algorithm—namely, the stochastic linearized proximal method of multipliers—to solve this convex stochastic optimization problem. This algorithm can be roughly viewed as a hybrid of stochastic approximation and the traditional proximal method of multipliers. Under mild conditions, we show that this algorithm exhibits [Formula: see text] expected convergence rates for both objective reduction and constraint violation if parameters in the algorithm are properly chosen, where K denotes the number of iterations. Moreover, we show that, with high probability, the algorithm has a [Formula: see text] constraint violation bound and [Formula: see text] objective bound. Numerical results demonstrate that the proposed algorithm is efficient. History: Accepted byAntonio Frangioni, Area Editor for Design & Analysis ofAlgorithms—Continuous. Funding: This work was supported by the National Natural Science Foundation of China [Grants 11971089, 11731013, 12071055, and 11871135]. 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.1228 ] or is available from the IJOC GitHub software repository ( https://github.com/INFORMSJoC ) at http://dx.doi.org/10.5281/zenodo.6818229 .

Many network/graph structures are continuously monitored by various sensors that are placed at a subset of nodes and edges. The multidimensional data collected from these sensors over time create large-scale graph data in which the data points are highly dependent. Monitoring large-scale attributed networks with thousands of nodes and heterogeneous sensor data to detect anomalies and unusual events is a complex and computationally expensive process. This paper introduces a new generic approach inspired by state-space models for network anomaly detection that can utilize the information from the network topology, the node attributes (sensor data), and the anomaly propagation sets in an integrated manner to analyze the entire network all at once. This article presents how heterogeneous network sensor data can be analyzed to locate the sources of anomalies as well as the anomalous regions in a network, which can be impacted by one or multiple anomalies at any time instance. Experimental results demonstrate the superior performance of our proposed framework in detecting anomalies in attributed graphs. Summary of Contribution: With the increasing availability of large-scale network sensors and rapid advances in artificial intelligence methods, fundamentally new analytical tools are needed that can integrate data collected from sensors across the networks for decision making while taking into account the stochastic and topological dependencies between nodes, sensors, and anomalies. This paper develops a framework to intelligently and efficiently analyze complex and highly dependent data collected from disparate sensors across large-scale network/graph structures to detect anomalies and abnormal behavior in real time. Unlike general purpose (often black-box) machine learning models, this paper proposes a unique framework for network/graph structures that incorporates the complexities of networks and interdependencies between network entities and sensors. Because of the multidisciplinary nature of the paper that involves optimization, machine learning, and system monitoring and control, it can help researchers in both operations research and computer science domains to develop new network-specific computing tools and machine learning frameworks to efficiently manage large-scale network data.

In this paper, we focus on a subclass of quadratic optimization problems, that is, disjoint bilinear optimization problems. We first show that disjoint bilinear optimization problems can be cast as two-stage robust linear optimization problems with fixed-recourse and right-hand-side uncertainty, which enables us to apply robust optimization techniques to solve the resulting problems. To this end, a solution scheme based on a blending of three popular robust optimization techniques is proposed. For disjoint bilinear optimization problems with a polyhedral feasible region and a general convex feasible region, we show that, under mild regularity conditions, the convex relaxations of the original bilinear formulation and its two-stage robust reformulation obtained from a reformulation-linearization-based technique and linear decision rules, respectively, are equivalent. For generic bilinear optimization problems, the convex relaxations from the reformulation-linearization-based technique are generally tighter than the one from linear decision rules. Numerical experiments on bimatrix games, synthetic disjoint bilinear problem instances, and convex maximization problems demonstrate the efficiency and effectiveness of the proposed solution scheme. Summary of Contribution: Computing solutions for disjoint bilinear optimization problems are of much interest in real-life applications, yet they are, in general, computationally intractable. This paper proposes a computationally tractable approximation as well as a convergent algorithm to the optimal values of such problems. Extensive computational experiments on (i) (constrained) bimatrix games, (ii) synthetic disjoint bilinear problems, and (iii) convex maximization problems are conducted to demonstrate the effectiveness and efficiency of the proposed approach.

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.

In this short paper, we argue that the standard approach adopted by modern mixed-integer linear programming solvers of using very little cutting plane generation in the branch-and-bound tree can be too conservative and lead to the loss of significant opportunities. Our observation is motivated by some relatively simple computational investigation on a couple of instances in the MIPlib 2010 collection for which the benefit of generating globally valid cuts in the tree is significant. History: This “Challenge” paper was invited by the Editor-in-Chief and based on the topics raised by the author at his plenary address at the 2022 INFORMS Computing Society Conference in Tampa, Florida.

The integral column generation algorithm (ICG) was recently introduced to solve set partitioning problems involving a very large number of variables. This primal algorithm generates a sequence of integer solutions with decreasing costs, leading to an optimal or near-optimal solution. ICG combines the well-known column generation algorithm and a primal algorithm called the integral simplex using decomposition algorithm (ISUD). In this paper, we develop a generalized version of ICG, denoted I2CG, that can solve efficiently large-scale set partitioning problems with side constraints. This new algorithm can handle the side constraints in the reduced problem of ISUD, in its complementary problem, or in both components. Computational experiments on instances of the airline crew pairing problem (CPP) and the multidepot vehicle routing problem with time windows show that the latter strategy is the most efficient one and I2CG significantly outperforms basic variants of two popular column generation heuristics, namely, a restricted master heuristic and a diving heuristic. For the largest tested CPP instance with 1,761 constraints, I2CG can produce in less than one hour of computational time more than 500 integer solutions leading to an optimal or near-optimal solution. Summary of Contribution: In this paper, we develop a new integral column generation algorithm that can solve efficiently large-scale set partitioning problems with side constraints. The latter alter the quasi-integrality property needed for primal integral algorithms. The paper adds a methodological contribution remedying this issue. This remedy should, in our opinion, boost the use of primal exact methods, especially in the column generation context. The paper also has a computational contribution. Effectively, computational experiments on instances of the airline crew pairing problem and the multidepot vehicle routing problem with time windows are extensively discussed. We compare the proposed algorithm to basic variants of two popular column generation heuristics.

Scenario reduction is an effective method to ease the computational burden of stochastic programming problems, which aims at choosing a subset of scenarios that can better represent a large number of possible scenarios. Higher-order moments are critical in the scenario reduction process, especially for stochastic programming problems that are greatly affected by the moments. From this idea, we construct a mixed integer linear programming model to improve the reduction accuracy of traditional methods by minimizing the moments’ information loss between the original and reduced scenarios. An improved Benders decomposition algorithm is then designed to find an optimal solution for the model. Finally, the resulting scenarios are examined on an international portfolio selection problem. Empirical and comparative studies are also carried out to reveal the superiority of our proposed scenario reduction method over other existing approaches or models, together with the superior performance of the algorithm. Summary of Contribution: To effectively solve stochastic programming problems, the scenario reduction method has become an active research area to strike a balance between the fine representation of random variables and computational complexity. Thus, how to design a reasonable optimal scenario reduction model and effectively solve this complex model is very important and meaningful. On the other hand, for some stochastic programming problems, especially the portfolio selection problems, statistical properties of risky assets returns may play a more important role in the scenario reduction process. However, the traditional scenario reduction methods have ignored this point. Thus, in this paper, we propose a mixed integer linear programming model to improve the reduction accuracy by minimizing the higher-order moments’ information loss between the original and reduced scenarios. Furthermore, an accelerated Benders decomposition algorithm is also designed to solve the proposed model. Hence, the aim of this paper is to extend the existing scenario reduction method in substantial and meaningful ways.

Co-movement among individual firms’ stock prices can reflect complex interfirm relationships. This paper proposes a novel method to leverage such relationships for stock price predictions by adopting inductive graph representation learning on dynamic stock graphs constructed based on historical stock price co-movement. To learn node representations from such dynamic graphs for better stock predictions, we propose the hybrid-attention dynamic graph neural network, an inductive graph representation learning method. We also extended mini-batch gradient descent to inductive representation learning on dynamic stock graphs so that the model can update parameters over mini-batch stock graphs with higher training efficiency. Extensive experiments on stocks from different markets and trading simulations demonstrate that the proposed method significantly improves stock predictions. The proposed method can have important implications for the management of financial portfolios and investment risk. Summary of Contribution: Accurate predictions of stock prices have important implications for financial decisions. In today’s economy, individual firms are increasingly connected via different types of relationships. As a result, firms’ stock prices often feature synchronous co-movement patterns. This paper represents the first effort to leverage such phenomena to construct dynamic stock graphs for stock predictions. We develop hybrid-attention dynamic graph neural network (HAD-GNN), an inductive graph representation learning framework for dynamic stock graphs to incorporate temporal and graph attention mechanisms. To improve the learning efficiency of HAD-GNN, we also extend the mini-batch gradient descent to inductive representation learning on such dynamic graphs and adopt a t-batch training mechanism (t-BTM). We demonstrate the effectiveness of our new approach via experiments based on real-world data and simulations.

VeRoViz is an open-source vehicle routing visualization package consisting of both Python and web-based components. It was developed to streamline the workflow for vehicle routing researchers by simplifying and automating many of the tedious tasks associated with generating realistic test problems. VeRoViz also provides new functionality to produce customizable visualizations of complex vehicle routing problems. These visualization tools—including Gantt charts, static maps, and dynamic 3-D videos—assist researchers in validating models and communicating results. Additionally, a comprehensive collection of utility functions within VeRoViz provides researchers with useful tools to assess features of their problems. This paper provides an overview of VeRoViz and highlights the flexibility and ease-of-use of the toolkit. Summary of Contribution: This paper describes an open-source software package designed to assist vehicle routing researchers. The software package, named VeRoViz (vehicle routing visualization), streamlines the process of collecting and visualizing data relevant to vehicle routing research. This includes capturing road network travel times (and distances) between locations, displaying turn-by-turn vehicle routes, generating Gantt charts of vehicle assignments, and producing 3-D “movies” of vehicle routing solutions. The VeRoViz suite consists of three components. First, a web-based interface allows researchers (and instructors) to quickly “sketch” elements of a vehicle routing problem, providing visual representations of nodes and arcs on a map. Second, the VeRoViz Python package provides an extensive collection of functions that assist operations researchers in collecting data and displaying solutions. Finally, an HTML/JavaScript plugin is available for displaying time-dynamic 3-D visualization of vehicle routes. VeRoViz is not a vehicle routing solver; it is a software suite that complements and supports researchers who are developing solution approaches to increasingly realistic vehicle routing problems (e.g., problems related to drone delivery, electric vehicles, or dynamic delivery requests).

We propose and evaluate branch-and-price approaches for vehicle routing problems with picking, loading, and soft time windows. This general type of vehicle routing problem is of particular relevance in the same-day delivery context, in which fast routing algorithms are required because of the commitment to real-time delivery in the presence of high customer order frequencies. To boost the performance of the branch-and-price algorithms, we introduce the new method of tree-compatible labeling with nondominance trees. This method represents cost functions by a fixed number of breakpoints and uses a specialized tree-based data structure to store Pareto-optimal labels. We prove the theoretical soundness of the new method and evaluate its performance numerically with respect to pricing, column generation, and branch-and-price. Our numerical results show that the method yields substantial performance gains. In particular, we show that, with the new method, branch-and-price is able to reliably generate within a few minutes close to optimal solutions for problem instances with 50 customers. By additional experiments with classic vehicle routing problems with hard time windows, we show that the performance gains of our method result from its ability to handle cost functions in the pricing step. Our approach is the first branch-and-price approach for vehicle routing with picking, loading, and soft time windows. As such, it represents an exact routing algorithm that is able to reliably satisfy the runtime requirements of real-time delivery services. Summary of Contribution: In this paper, we propose the first branch-and-price approaches for a general class of vehicle routing problems with picking, loading, and soft time windows. This problem class is of particular importance for real-time delivery services, for which customers expect to be served within only a few hours after their order has been placed. We provide a problem formulation that takes into account that short runtimes of routing algorithms are required, that the upper bounds of the customers’ time windows may be violated at a certain cost, and that a significant part of the delivery time window is consumed by picking orders from a warehouse and loading orders into vehicles. Solving the problem with branch-and-price requires the use of cost functions as elements of the labels in the pricing step. We propose a method that approximates these cost functions and leverages the computational performance of nondominance tree data structures for solving the pricing problem. We prove the theoretical soundness of this new method for exact branch-and-price, and we show numerically that the method leads to a significant performance increase of branch-and-price. The paper lies at the intersection of computing and operations research, in particular because our algorithms are designed to leverage the computational performance of advanced data structures for solving a combinatorial optimization problem.

Input model bias is the bias found in the output performance measures of a simulation model caused by estimating the input distributions/processes used to drive it. When the simulation response is a nonlinear function of its inputs, as is usually the case when simulating complex systems, input modelling bias is amongst the errors that arise. In this paper, we introduce a method that recalibrates the input parameters of parametric input models to reduce the bias in the simulation output. The proposed method is based on sequential quadratic programming with a closed form analytical solution at each step. An algorithm with guidance on how to practically implement the method is presented. The method is shown to be successful in reducing input modelling bias and the total mean squared error caused by input modelling error. Summary of Contribution: This paper furthers the understanding and treatment of input modelling error in computer simulation. We provide a novel method for reducing input model bias by recalibrating the input parameters used to drive a simulation model. A sequential quadratic programming approach with an explicit solution is provided to recalibrate the input parameters. The method is therefore computationally inexpensive. An algorithm outlining our proposed procedure is provided within the paper. An evaluation of the method shows the method successfully reduces input model bias and may also reduce the mean squared error caused by input modelling in the output of a simulation model.

In this paper, we consider a variant of adaptive robust combinatorial optimization problems where the decision maker can prepare K solutions and choose the best among them upon knowledge of the true data realizations. We suppose that the uncertainty may affect the objective and the constraints through functions that are not necessarily linear. We propose a new exact algorithm for solving these problems when the feasible set of the nominal optimization problem does not contain too many good solutions. Our algorithm enumerates these good solutions, generates dynamically a set of scenarios from the uncertainty set, and assigns the solutions to the generated scenarios using a vertex p-center formulation, solved by a binary search algorithm. Our numerical results on adaptive shortest path and knapsack with conflicts problems show that our algorithm compares favorably with the methods proposed in the literature. We additionally propose a heuristic extension of our method to handle problems where it is prohibitive to enumerate all good solutions. This heuristic is shown to provide good solutions within a reasonable solution time limit on the adaptive knapsack with conflicts problem. Finally, we illustrate how our approach handles nonlinear functions on an all-or-nothing subset problem taken from the literature. Summary of Contribution: Our paper describes a new exact algorithm for solving adaptive robust combinatorial optimization problems when the feasible set of the nominal optimization problems does not contain too many good solutions. Its development relies on a progressive relaxation of the problem augmented with a row-and-column generation technique. Its efficient execution requires a reformulation of this progressive relaxation, coupled with dominance rules and a binary search algorithm. The proposed algorithm is amenable to exploiting the special structures of the problems considered as illustrated with various applications throughout the paper. A practical view is provided by the proposition of a heuristic variant. Our computational experiments show that our proposed exact solution method outperforms the existing methodologies and therefore pushes the computational envelope for the class of problems considered.

In this paper, we propose a decision criterion that characterizes an enveloping bound on monetary risk measures and is computationally friendly. We start by extending the classical value at risk (VaR) measure. Whereas VaR evaluates the threshold loss value such that the loss from the risk position exceeding that threshold is at a given probability level, it fails to indicate a performance guarantee at other probability levels. We define the probabilistic enveloping measure (PEM) to establish the bound information for the tail probability of the loss at all levels. Using a set of normative properties, we then generalize the PEM to the risk enveloping measure (REM) such that the bound on the general monetary risk measures at all levels of risk aversion are captured. The coherent version of the REM (CREM) is also investigated. We demonstrate its applicability by showing how the coherent REM can be incorporated in distributionally robust optimization. Specifically, we apply the CREM criterion in surgery block allocation problems and provide a formulation that can be efficiently solved. Based on this application, we report favorable computational results from optimizing over the CREM criterion. Summary of Contribution: Our paper studies a fundamental problem in operations research: what criteria to optimize when uncertainties are involved. Extending from the classical chance constraint model, we propose a new decision criterion by an axiomatization approach. We then investigate the computing issue in the corresponding distributionally robust optimization problem. In particular, we provide solution methods for continuous and discrete optimization. After that, we apply it to a practical operations problem, surgery allocation decisions in healthcare management. The computational studies demonstrate the appealing performance of our proposed approach on this surgery allocation problem.

Discrete optimal transport problems give rise to very large linear programs (LPs) with a particular structure of the constraint matrix. In this paper, we present a hybrid algorithm that mixes an interior point method (IPM) and column generation, specialized for the LP originating from the Kantorovich optimal transport problem. Knowing that optimal solutions of such problems display a high degree of sparsity, we propose a column generation–like technique to force all intermediate iterates to be as sparse as possible. The algorithm is implemented nearly matrix-free. Indeed, most of the computations avoid forming the huge matrices involved and solve the Newton system using only a much smaller Schur complement of the normal equations. We prove theoretical results about the sparsity pattern of the optimal solution, exploiting the graph structure of the underlying problem. We use these results to mix iterative and direct linear solvers efficiently in a way that avoids producing preconditioners or factorizations with excessive fill-in and at the same time guaranteeing a low number of conjugate gradient iterations. We compare the proposed method with two state-of-the-art solvers and show that it can compete with the best network optimization tools in terms of computational time and memory use. We perform experiments with problems reaching more than four billion variables and demonstrate the robustness of the proposed method. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: F. Zanetti received funding from the University of Edinburgh, in the form of a PhD scholarship. 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.2022.0184 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0184 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

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

The value at risk (VaR) and the conditional value at risk (CVaR) are two popular risk measures to hedge against the uncertainty of data. In this paper, we provide a computational toolbox for solving high-dimensional sparse linear regression problems under either VaR or CVaR measures, the former being nonconvex and the latter convex. Unlike the empirical risk (neutral) minimization models in which the overall losses are decomposable across data, the aforementioned risk-sensitive models have nonseparable objective functions so that typical first order algorithms are not easy to scale. We address this scaling issue by adopting a semismooth Newton-based proximal augmented Lagrangian method of the convex CVaR linear regression problem. The matrix structures of the Newton systems are carefully explored to reduce the computational cost per iteration. The method is further embedded in a majorization–minimization algorithm as a subroutine to tackle the nonconvex VaR-based regression problem. We also discuss an adaptive sieving strategy to iteratively guess and adjust the effective problem dimension, which is particularly useful when a solution path associated with a sequence of tuning parameters is needed. Extensive numerical experiments on both synthetic and real data demonstrate the effectiveness of our proposed methods. In particular, they are about 53 times faster than the commercial package Gurobi for the CVaR-based sparse linear regression with 4,265,669 features and 16,087 observations. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: This work was supported in part by the NSF, the Division of Computing and Communication Foundations [Grant 2153352], the National Natural Science Foundation of China [Grant 12271187], and the Hong Kong Research Grant Council [Grant 15304019]. 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.1282 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0012 ) at ( http://dx.doi.org/10.5281/zenodo.7483279 ).

Imbalanced classification is widely referred in many real-world applications and has been extensively studied. Most existing algorithms consider alleviating the imbalance by sampling or guiding ensemble learners with punishments. The combination of ensemble learning and sampling strategy at class level has achieved great progress. Actually, specific hard examples have little benefit for model learning and even degrade the performance. From the view of identifying classification difficulty of samples, one important motivation is to design algorithms to finely equip different samples with progressive learning. Unfortunately, how to perfectly configure the sampling and learning strategies under ensemble principles at the sample level remains a research gap. In this paper, we propose a new view from the sample level rather than class level in existing studies. We design an ensemble approach in pipe with sample-level gradient resampling, that is, balanced cascade with filters (BCWF). Before that, as a preliminary exploration, we first design a hard examples mining algorithm to explore the gradient distribution of classification difficulty of samples and identify the hard examples. Specifically, BCWF uses an under-sampling strategy and a boosting manner to train T predictive classifiers and reidentify hard examples. In BCWF, moreover, we design two types of filters: the first is assembled with a hard filter (BCWF_h), whereas the second is assembled with a soft filter (BCWF_s). In each round of boosting, BCWF_h strictly removes a gradient/set of the hardest examples from both classes, whereas BCWF_s removes a larger number of harder and easy examples simultaneously for final balanced-class retention. Consequently, the well-trained T predictive classifiers can be used with two ensemble voting strategies: average probability and majority vote. To evaluate the proposed approach, we conduct intensive experiments on 10 benchmark data sets and apply our algorithms to perform default user detection on a real-world peer to peer lending data set. The experimental results fully demonstrate the effectiveness and the managerial implications of our approach when compared with 11 competitive algorithms. History: Accepted by Ram Ramesh, Area Editor for Data Science & Machine Learning. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72101176, 71722005, and 72241432]. The National Key R&D program of China [Grant 2020YFA0908600] and the Natural Science Foundation of Tianjin City [Grant 18JCJQJC45900]. 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.1274 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0104 ) at ( http://dx.doi.org/10.5281/zenodo.6360996 ).

This paper presents an effective perturbation-based thresholding search for two popular and challenging packing problems with minimal containers: packing N identical circles in a square and packing N identical spheres in a cube. Following the penalty function approach, we handle these constrained optimization problems by solving a series of unconstrained optimization subproblems with fixed containers. The proposed algorithm relies on a two-phase search strategy that combines a thresholding search method reinforced by two general-purpose perturbation operators and a container adjustment method. The performance of the algorithm is assessed relative to a large number of benchmark instances widely studied in the literature. Computational results show a high performance of the algorithm on both problems compared with the state-of-the-art results. For circle packing, the algorithm improves 156 best-known results (new upper bounds) in the range of [Formula: see text] and matches 242 other best-known results. For sphere packing, the algorithm improves 66 best-known results in the range of [Formula: see text], whereas matching the best-known results for 124 other instances. Experimental analyses are conducted to shed light on the main search ingredients of the proposed algorithm consisting of the two-phase search strategy, the mixed perturbation and the parameters. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grants 61703213 and 61933005]. 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.1290 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0004 ) at ( http://dx.doi.org/10.5281/zenodo.7579558 ).

Computing Bayesian Nash equilibrium strategies in auction games is a challenging problem that is not well-understood. Such equilibria can be modeled as systems of nonlinear partial differential equations. It was recently shown that neural pseudogradient ascent (NPGA), an implementation of simultaneous gradient ascent via neural networks, converges to a Bayesian Nash equilibrium for a wide variety of symmetric auction games. Whereas symmetric auction models are widespread in the theoretical literature, in most auction markets in the field, one can observe different classes of bidders having different valuation distributions and strategies. Asymmetry of this sort is almost always an issue in real-world multiobject auctions, in which different bidders are interested in different packages of items. Such environments require a different implementation of NPGA with multiple interacting neural networks having multiple outputs for the different allocations in which the bidders are interested. In this paper, we analyze a wide variety of asymmetric auction models. Interestingly, our results show that we closely approximate Bayesian Nash equilibria in all models in which the analytical Bayes–Nash equilibrium is known. Additionally, we analyze new and larger environments for which no analytical solution is known and verify that the solution found approximates equilibrium closely. The results provide a foundation for generic equilibrium solvers that can be used in a wide range of auction games. History: Accepted by Ram Ramesh, Area Editor for Data Science & Machine Learning. Funding: This work was supported by Deutsche Forschungsgemeinschaft [Grant BI-1056/I-9]. 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.1281 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0151 ) at ( http://dx.doi.org/10.5281/zenodo.7407158 ).

The subgame perfect equilibrium in stationary strategies (SSPE) is the most important solution concept in applications of stochastic games, making it imperative to develop efficient methods to compute an SSPE. For this purpose, this paper develops an interior-point differentiable path-following method (IPM), which establishes a connection between an artificial logarithmic barrier game and the stochastic game of interest by adding a homotopy variable. IPM brings several advantages over the existing methods for stochastic games. On the one hand, IPM provides a bridge between differentiable path-following methods and interior-point methods and remedies several issues of an existing homotopy method called the stochastic linear tracing procedure (SLTP). First, the starting stationary strategy profile can be arbitrarily chosen. Second, IPM does not need switching between different systems of equations. Third, the use of a perturbation term makes IPM applicable to all stochastic games rather than generic games only. Moreover, a well-chosen transformation of variables reduces the number of equations and variables by roughly one half. Numerical results show that the proposed method is more than three times as efficient as SLTP. On the other hand, the stochastic game can be reformulated as a mixed complementarity problem and solved by the PATH solver. We employ the proposed IPM and the PATH solver to compute SSPEs. Numerical results evince that for some stochastic games the PATH solver may fail to find an SSPE, whereas IPM is successful in doing so for all stochastic games, which confirms the reliability and stability of the proposed method. Summary of Contribution: This paper incorporates the interior-point methods into a differentiable path-following method for computing stationary equilibria for stochastic games. This novel method brings excellent computational advantages and remedies several issues with the existing methods for stochastic games. We prove the global convergence of the proposed method and employ this method to solve numerous randomly generated stochastic games with different scales. Numerical results further confirm the high efficiency, stability, and universality of this method for stochastic games.

Aggregation of heating, ventilation, and air conditioning (HVAC) loads can provide reserves to absorb volatile renewable energy, especially solar photo-voltaic (PV) generation. In this paper, we decide HVAC control schedules under uncertain PV generation, using a distributionally robust chance-constrained (DRCC) building load control model under two typical ambiguity sets: the moment-based and Wasserstein ambiguity sets. We derive mixed integer linear programming (MILP) reformulations for DRCC problems under both sets. Especially, for the Wasserstein ambiguity set, we use the right-hand side (RHS) uncertainty to derive a more compact MILP reformulation than the commonly known MILP reformulations with big-M constants. All the results also apply to general individual chance constraints with RHS uncertainty. Furthermore, we propose an adjustable chance-constrained variant to achieve tradeoff between the operational risk and costs. We derive MILP reformulations under the Wasserstein ambiguity set and second-order conic programming (SOCP) reformulations under the moment-based set. Using real-world data, we conduct computational studies to demonstrate the efficiency of the solution approaches and the effectiveness of the solutions. Summary of Contribution: The problem studied in this paper is motivated by a building load control problem that uses the aggregation of heating, ventilation, and air conditioning (HVAC) loads as flexible reserves to absorb uncertain solar photovoltaic (PV) generation. The problem is formulated as distributionally robust chance-constrained (DRCC) programs with right-hand side (RHS) uncertainty. In addition, we propose a risk-adjustable variant of the DRCC programs, where the risk level, instead of being predetermined, is treated as a decision variable. The paper aims to provide tractable reformulations and solution algorithms for both the (general) DRCC and the (general) adjustable DRCC models with RHS uncertainty.

A key question in causal inference analyses is how to find subgroups with elevated treatment effects. This paper takes a machine learning approach and introduces a generative model, causal rule sets (CRS), for interpretable subgroup discovery. A CRS model uses a small set of short decision rules to capture a subgroup in which the average treatment effect is elevated. We present a Bayesian framework for learning a causal rule set. The Bayesian model consists of a prior that favors simple models for better interpretability as well as avoiding overfitting and a Bayesian logistic regression that captures the likelihood of data, characterizing the relation between outcomes, attributes, and subgroup membership. The Bayesian model has tunable parameters that can characterize subgroups with various sizes, providing users with more flexible choices of models from the treatment-efficient frontier. We find maximum a posteriori models using iterative discrete Monte Carlo steps in the joint solution space of rules sets and parameters. To improve search efficiency, we provide theoretically grounded heuristics and bounding strategies to prune and confine the search space. Experiments show that the search algorithm can efficiently recover true underlying subgroups. We apply CRS on public and real-world data sets from domains in which interpretability is indispensable. We compare CRS with state-of-the-art rule-based subgroup discovery models. Results show that CRS achieves consistently competitive performance on data sets from various domains, represented by high treatment-efficient frontiers. Summary of Contribution: This paper is motivated by the large heterogeneity of treatment effect in many applications and the need to accurately locate subgroups for enhanced treatment effect. Existing methods either rely on prior hypotheses to discover subgroups or greedy methods, such as tree-based recursive partitioning. Our method adopts a machine learning approach to find an optimal subgroup learned with a carefully global objective. Our model is more flexible in capturing subgroups by using a set of short decision rules compared with tree-based baselines. We evaluate our model using a novel metric, treatment-efficient frontier, that characterizes the trade-off between the subgroup size and achievable treatment effect, and our model demonstrates better performance than baseline models.

In this paper, we propose a general algorithmic framework for rotating workforce scheduling. We develop a graph representation that allows to model a schedule as a Eulerian cycle of stints, which we then use to derive a problem formulation that is compact toward the number of employees. We develop a general branch-and-cut framework that solves rotating workforce scheduling in its basic variant, as well as several additional problem variants that are relevant in practice. These variants comprise, among others, objectives for the maximization of free weekends and the minimization of employees. Our computational studies show that the developed framework constitutes a new state of the art for rotating workforce scheduling. For the first time, we solve all 6,000 instances of the status quo benchmark for rotating workforce scheduling to optimality with an average computational time of 0.07 seconds and a maximum computational time of 2.53 seconds. These results reduce average computational times by more than 99% compared with existing methods. Our algorithmic framework shows consistent computational performance, which is robust across all studied problem variants. Summary of Contribution: This paper proposes a novel exact algorithmic framework for the well-known rotating workforce scheduling problem (RWSP). Although the RWSP has been extensively studied in different problem variants and for different exact and heuristic solution approaches, the presented algorithmic framework constitutes a new state-of-the-art for the RWSP that solves all known benchmark sets to optimality and improves on the current state-of-the-art by orders of magnitude with respect to computational times, especially for large-scale instances. The paper is both of methodological value for researchers and of high interest for practitioners. For researchers, the presented framework is amenable for various problem variants and provides a common ground for further studies and research. For practitioners and software developers, low computational times of a few seconds allows the framework to be to embedded into personnel scheduling software.

Distributionally robust optimization (DRO) is a modeling framework in decision making under uncertainty in which the probability distribution of a random parameter is unknown although its partial information (e.g., statistical properties) is available. In this framework, the unknown probability distribution is assumed to lie in an ambiguity set consisting of all distributions that are compatible with the available partial information. Although DRO bridges the gap between stochastic programming and robust optimization, one of its limitations is that its models for large-scale problems can be significantly difficult to solve, especially when the uncertainty is of high dimension. In this paper, we propose computationally efficient inner and outer approximations for DRO problems under a piecewise linear objective function and with a moment-based ambiguity set and a combined ambiguity set including Wasserstein distance and moment information. In these approximations, we split a random vector into smaller pieces, leading to smaller matrix constraints. In addition, we use principal component analysis to shrink uncertainty space dimensionality. We quantify the quality of the developed approximations by deriving theoretical bounds on their optimality gap. We display the practical applicability of the proposed approximations in a production–transportation problem and a multiproduct newsvendor problem. The results demonstrate that these approximations dramatically reduce the computational time while maintaining high solution quality. The approximations also help construct an interval that is tight for most cases and includes the (unknown) optimal value for a large-scale DRO problem, which usually cannot be solved to optimality (or even feasibility in most cases). Summary of Contribution: This paper studies an important type of optimization problem, that is, distributionally robust optimization problems, by developing computationally efficient inner and outer approximations via operations research tools. Specifically, we consider several variants of such problems that are practically important and that admit tractable yet large-scale reformulation. We accordingly utilize random vector partition and principal component analysis to derive efficient approximations with smaller sizes, which, more importantly, provide a theoretical performance guarantee with respect to low optimality gaps. We verify the significant efficiency (i.e., reducing computational time while maintaining high solution quality) of our proposed approximations in solving both production–transportation and multiproduct newsvendor problems via extensive computing experiments.

The complexity of current electricity wholesale markets and the increased volatility of electricity prices because of the intermittent nature of renewable generation make independent power producers (IPPs) face significant challenges to submit offers. This challenge increases for those owning traditional coal-fired thermal generators and renewable generation. In this paper, an integrated stochastic optimal strategy is proposed for an IPP using the self-scheduling approach through its participation in both day-ahead and real-time markets (i.e., two-settlement electricity markets) as a price taker. In the proposed approach, the IPP submits an offer for all periods to the day-ahead market for which a multistage stochastic programming setting is explored for providing real-time market offers for each period as a recourse. This strategy has the advantage of achieving overall maximum profits for both markets in the given operational time horizon. Such a strategy is theoretically proved to be more profitable than alternative self-scheduling strategies as it takes advantage of the continuously realized scenario information of the renewable energy output and real-time prices over time. To improve computational efficiency, we explore polyhedral structures to derive strong valid inequalities, including convex hull descriptions for certain special cases, thus strengthening the formulation of our proposed model. Polynomial-time separation algorithms are then established for the derived exponential-sized inequalities to speed up the branch-and-cut process. Finally, both numerical and real case studies demonstrate the potential of the proposed strategy. Summary of Contribution: This paper develops innovative models and methods to study a family of practically important problems via the interactions of operations research and computing. Specifically, this paper provides in-depth analyses of innovative stochastic optimization modeling approaches and develops computationally efficient polyhedral results. The paper also verifies the effectiveness of proposed analyses via extensive computing experiments.

In critical node problems, the task is to identify a small subset of so-called critical nodes whose deletion maximally degrades a network’s “connectivity” (however that is measured). Problems of this type have been widely studied, for example, for limiting the spread of infectious diseases. However, existing approaches for solving them have typically been limited to networks having fewer than 1,000 nodes. In this paper, we consider a variant of this problem in which the task is to delete b nodes so as to minimize the number of node pairs that remain connected by a path of length at most k. With the techniques developed in this paper, instances with up to 17,000 nodes can be solved exactly. We introduce two integer programming formulations for this problem (thin and path-like) and compare them with an existing recursive formulation. Although the thin formulation generally has an exponential number of constraints, it admits an efficient separation routine. Also helpful is a new, more general preprocessing procedure that, on average, fixes three times as many variables than before. Summary of Contribution: In this paper, we consider a distance-based variant of the critical node problem in which the task is to delete b nodes so as to minimize the number of node pairs that remain connected by a path of length at most k. This problem is motivated by applications in social networks, telecommunications, and transportation networks. In our paper, we aim to solve large-scale instances of this problem. Standard out-of-the-box approaches are unable to solve such instances, requiring new integer programming models, methodological contributions, and other computational insights. For example, we propose an algorithm for finding a maximum independent set of simplicial nodes that runs in time O(nm) that we use in a preprocessing procedure; we also prove that the separation problem associated with one of our integer programming models is NP-hard. We apply our branch-and-cut implementation to real-life networks from a variety of domains and observe speedups over previous approaches.

This study introduces a branch-and-bound algorithm to solve mixed-integer bilinear maximum multiplicative programs (MIBL-MMPs). This class of optimization problems arises in many applications, such as finding a Nash bargaining solution (Nash social welfare optimization), capacity allocation markets, reliability optimization, etc. The proposed algorithm applies multiobjective optimization principles to solve MIBL-MMPs exploiting a special characteristic in these problems. That is, taking each multiplicative term in the objective function as a dummy objective function, the projection of an optimal solution of MIBL-MMPs is a nondominated point in the space of dummy objectives. Moreover, several enhancements are applied and adjusted to tighten the bounds and improve the performance of the algorithm. The performance of the algorithm is investigated by 400 randomly generated sample instances of MIBL-MMPs. The obtained result is compared against the outputs of the mixed-integer second order cone programming (SOCP) solver in CPLEX and a state-of-the-art algorithm in the literature for this problem. Our analysis on this comparison shows that the proposed algorithm outperforms the fastest existing method, that is, the SOCP solver, by a factor of 6.54 on average. Summary of Contribution: The scope of this paper is defined over a class of mixed-integer programs, the so-called mixed-integer bilinear maximum multiplicative programs (MIBL-MMPs). The importance of MIBL-MMPs is highlighted by the fact that they are encountered in applications, such as Nash bargaining, capacity allocation markets, reliability optimization, etc. The mission of the paper is to introduce a novel and effective criterion space branch-and-cut algorithm to solve MIBL-MMPs by solving a finite number of single-objective mixed-integer linear programs. Starting with an initial set of primal and dual bounds, our proposed approach explores the efficient set of the multiobjective problem counterpart of the MIBL-MMP through a criterion space–based branch-and-cut paradigm and iteratively improves the bounds using a branch-and-bound scheme. The bounds are obtained using novel operations developed based on Chebyshev distance and piecewise McCormick envelopes. An extensive computational study demonstrates the efficacy of the proposed algorithm.

Various digital data sets that encode user-item relationships contain a multilevel overlapping cluster structure. The user-item relation can be encoded in a weighted bipartite graph and uncovering these overlapping coclusters of users and items at multiple levels in the bipartite graph can play an important role in analyzing user-item data in many applications. For example, for effective online marketing, such as placing online ads or deploying smart online marketing strategies, identifying co-occurring clusters of users and items can lead to accurately targeted advertisements and better marketing outcomes. In this paper, we propose fast algorithms inspired by algebraic multigrid methods for finding multilevel overlapping cocluster structures of feature matrices that encode user-item relations. Starting from the weighted bipartite graph structure of the feature matrix, the algorithms use agglomeration procedures to recursively coarsen the bipartite graphs that represent the relations between the coclusters on increasingly coarser levels. New fast coarsening routines are described that circumvent the bottleneck of all-to-all similarity computations by exploiting measures of direct connection strength between row and column variables in the feature matrix. Providing accurate coclusters at multiple levels in a manner that can scale to large data sets is a challenging task. In this paper, we propose heuristic algorithms that approximately and recursively minimize normalized cuts to obtain coclusters in the aggregated bipartite graphs on multiple levels of resolution. Whereas the main novelty and focus of the paper lies in algorithmic aspects of reducing computational complexity to obtain scalable methods specifically for large rectangular user-item matrices, the algorithmic variants also define several new models for determining multilevel coclusters that we justify intuitively by relating them to principles that underlie collaborative filtering methods for user-item relationships. Experimental results show that the proposed algorithms successfully uncover the multilevel overlapping cluster structure for artificial and real data sets. Summary of Contribution: This paper develops new and efficient computational methods for finding the multilevel overlapping cocluster structure of feature matrices that encode user-item relationships. We base our approach on the use of pairwise similarity measures between features, seeking clusters of points that are similar to each other and dissimilar from the points outside the cluster. We approximately solve the problem of finding optimal overlapping coclusters on multiple levels by employing a framework that is based on efficient multilevel methods that have been used previously to solve sparse linear systems and to cluster graphs. Our main contribution is that we extend these methods in efficient manners to find coclusters in the bipartite graphs that encode common and important user-item relationships or social network relations. The novel methods that we propose are inherently scalable to large problem sizes and are naturally able to uncover overlapping coclusters at multiple levels, whereas existing methods generally only find coclusters at the fine level. We illustrate the algorithm and its performance on some standard test problems from the literature and on a proof-of-concept real-world data set that relates LinkedIn users to their skills and expertise.

This paper addresses a single machine total weighted tardiness (TWT) batch-scheduling problem in which jobs have release dates, nonidentical sizes, and are compatible between each other. We propose two integer linear programming models: the first one is a time-indexed formulation (TIF), and the second is an innovative time-size-indexed formulation (TSIF). Although TIF clearly outperforms the existing formulation for the problem, TSIF is capable of producing much stronger bounds in practice. The latter also enables us to develop an efficient column-generation (CG) algorithm. The pricing subproblem corresponds to a resource-constrained shortest path problem that is solved using a bucket graph–based labeling algorithm. The solutions of such a subproblem may contain cycles (reprocessing of jobs), and thus, a memory mechanism called dynamic arc-based ng-sets is employed in the labeling with a view toward avoiding some of them. Moreover, we also implement a preprocessing scheme based on Lagrangian relaxation to perform variable fixing. Extensive computational experiments were carried out in 810 benchmark instances. The proposed CG algorithm is capable of solving instances with up to 100 jobs to optimality. In addition, we believe that this is the first exact approach for a TWT batch-scheduling variant capable of systematically solving instances with up to 50 jobs. High-quality results are also reported for three special cases of the problem—more precisely, when (i) the penalty weights are unitary, (ii) there are no release dates, and (iii) all due dates are set to zero and, hence, the objective becomes equivalent to minimizing the weighted completion time. Summary of Contribution: This paper provides the first exact algorithm for a standard variant of a batch-scheduling total weighted tardiness problem that can solve instances with up to 100 jobs to optimality, a considerable leap with respect to previous works. In particular, we propose a time-indexed formulation that has the advantage of being relatively simple to implement, and yet we show that it is not theoretically dominated by the other innovative formulation proposed in the paper referred to as the time-size-indexed formulation (TSIF). Moreover, we present a Lagrangian approach to quickly fix variables and an iterative column-generation (CG) procedure over a Dantzig–Wolfe decomposition of TSIF that combines an efficient pricing algorithm with a dynamic scheme to adjust the subproblem constraints. The proposed CG approach is capable of producing very strong bounds for the problem as well as for some of its special cases.

Motivated by applications arising on social networks, we study a generalization of the celebrated dominating set problem called the Positive Influence Dominating Set (PIDS). Given a graph G with a set V of nodes and a set E of edges, each node i in V has a weight bi, and a threshold requirement gi. We seek a minimum weight subset T of V, so that every node i not in T is adjacent to at least gi members of T. When gi is one for all nodes, we obtain the weighted dominating set problem. First, we propose a strong and compact extended formulation for the PIDS problem. We then project the extended formulation onto the space of the natural node-selection variables to obtain an equivalent formulation with an exponential number of valid inequalities. Restricting our attention to trees, we show that the extended formulation is the strongest possible formulation, and its projection (onto the space of the node variables) gives a complete description of the PIDS polytope on trees. We derive the necessary and sufficient facet-dening conditions for the valid inequalities in the projection and discuss their polynomial time separation. We embed this (exponential size) formulation in a branch-and-cut framework and conduct computational experiments using real-world graph instances, with up to approximately 2.5 million nodes and 8 million edges. On a test-bed of 100 real-world graph instances, our approach finds solutions that are on average 0.2% from optimality and solves 51 out of the 100 instances to optimality. Summary of Contribution: In influence maximization problems, a decision maker wants to target individuals strategically to cause a cascade at a minimum cost over a social network. These problems have attracted significant attention as their applications can be found in many different domains including epidemiology, healthcare, marketing, and politics. However, computationally solving large-scale influence maximization problems to near optimality remains a substantial challenge for the computing community, which thus represent significant opportunities for the development of operations-research based models, algorithms, and analysis in this interface. This paper studies the positive influence dominating set (PIDS) problem, an influence maximization problem on social networks that generalizes the celebrated dominating set problem. It focuses on developing exact methods for solving large instances to near optimality. In other words, the approach results in strong bounds, which then provide meaningful comparative benchmarks for heuristic approaches. The paper first shows that straightforward generalizations of well-known formulations for the dominating set problem do not yield strong (i.e., computationally viable) formulations for the PIDS problem. It then strengthens these formulations by proposing a compact extended formulation and derives its projection onto the space on the natural node-selection variables, resulting in two equivalent (stronger) formulations for the PIDS problem. The projected formulation on the natural node-variables contains a new class of valid inequalities that are shown to be facet-defining for the PIDS problem. These theoretical results are complemented by in-depth computational experiments using a branch-and-cut framework, on a testbed of 100 real-world graph instances, with up to approximately 2.5 million nodes and 8 million edges. They demonstrate the effectiveness of the proposed formulation in solving large scale problems finding solutions that are on average 0.2% from optimality and solving 51 of the 100 instances to optimality.

Column generation (CG) algorithms are well known to suffer from convergence issues due, mainly, to the degenerate structure of their master problem and the instability associated with the dual variables involved in the process. In the literature, several strategies have been proposed to overcome this issue. These techniques rely either on the modification of the standard CG algorithm or on some prior information about the set of dual optimal solutions. In this paper, we propose a new stabilization framework, which relies on the dynamic generation of aggregated rows from the CG master problem. To evaluate the performance of our method and its flexibility, we consider instances of three different problems, namely, vehicle routing with time windows (VRPTW), bin packing with conflicts (BPPC), and multiperson pose estimation (MPPEP). When solving the VRPTW, the proposed stabilized CG method yields significant improvements in terms of CPU time and number of iterations with respect to a standard CG algorithm. Huge reductions in CPU time are also achieved when solving the BPPC and the MPPEP. For the latter, our method has shown to be competitive when compared with a tailored method. Summary of Contribution: Column generation (CG) algorithms are among the most important and studied solution methods in operations research. CG algorithms are suitable to cope with large-scale problems arising from several real-life applications. The present paper proposes a generic stabilization framework to address two of the main issues found in a CG method: degeneracy in the master problem and massive instability of the dual variables. The newly devised method, called dynamic separation of aggregated rows (dyn-SAR), relies on an extended master problem that contains redundant constraints obtained by aggregating constraints from the original master problem formulation. This new formulation is solved in a column/row generation fashion. The efficacy of the proposed method is tested through an extensive experimental campaign, where we solve three different problems that differ considerably in terms of their constraints and objective function. Despite being a generic framework, dyn-SAR requires the embedded CG algorithm to be tailored to the application at hand.

The minimum connected dominating set (MCDS) problem consists of selecting a minimum set of vertices from an undirected graph, such that each vertex not in this set is adjacent to at least one of the vertices in it, and the subgraph induced by this vertex set is connected. This paper presents a fast vertex weighting (FVW) algorithm for solving the MCDS problem, which integrates several distinguishing features, such as a vertex weighting-based local search with tabu and perturbation strategies to help the search to jump out of the local optima, as well as a search space reduction strategy to improve the search efficiency. Computational experiments on four sets of 112 commonly used public benchmark instances, as well as 15 newly introduced sparse instances, show that FVW is highly competitive compared with the state-of-the-art algorithms in the literature despite its simplicity. FVW improves the previous best-known results for 20 large public benchmark instances while matching the best-known results for all but 2 of the remaining ones. Several ingredients of FVW are investigated to demonstrate the importance of the proposed ideas and techniques. Summary of Contribution: As a challenging classical NP-hard problem, the minimum connected dominating set (MCDS) problem has been studied for decades in the areas of both operations research and computer science, although there does not exist an exact polynomial algorithm for solving it. Thus, the new breakthrough on this classical NP-hard problem in terms of the computational results on classical benchmark instances is significant. This paper presents a new fast vertex weighting local search for solving the MCDS problem. Computational experiments on four sets of 112 commonly used public benchmark instances show that fast vertex weighting (FVW) is able to improve the previous best-known results for 20 large instances while matching the best-known results for all but 2 of the remaining instances. Several ingredients of FVW are also investigated to demonstrate the importance of the proposed ideas and techniques.

This paper presents a new bidirectional search algorithm to solve the shortest path problem. The new algorithm uses an iterative deepening technique with a consistent heuristic to improve lower bounds on path costs. The new algorithm contains a novel technique of filtering nodes to significantly reduce the memory requirements. Computational experiments on the pancake problem, sliding tile problem, and Rubik’s cube show that the new algorithm uses significantly less memory and executes faster than A* and other state-of-the-art bidirectional algorithms. Summary of Contribution: Quickly solving single-source shortest path problems on graphs is important for pathfinding applications and is a core problem in both artificial intelligence and operations research. This paper attempts to solve large problems that do not easily fit into the available memory of a desktop computer, such as finding the optimal shortest set of moves to solve a Rubik’s cube, and solve them faster than existing algorithms.

Targeted marketing strategies are of significant interest in the smartapp economy. Typically, one seeks to identify individuals to strategically target in a social network so that the network is influenced at a minimal cost. In many practical settings, the effects of direct influence predominate, leading to the positive influence dominating set with partial payments (PIDS-PP) problem that we discuss in this paper. The PIDS-PP problem is NP-complete because it generalizes the dominating set problem. We discuss several mixed integer programming formulations for the PIDS-PP problem. First, we describe two compact formulations on the payment space. We then develop a stronger compact extended formulation. We show that when the underlying graph is a tree, this compact extended formulation provides integral solutions for the node selection variables. In conjunction, we describe a polynomial-time dynamic programming algorithm for the PIDS-PP problem on trees. We project the compact extended formulation onto the payment space, providing an equivalently strong formulation that has exponentially many constraints. We present a polynomial time algorithm to solve the associated separation problem. Our computational experience on a test bed of 100 real-world graph instances (with up to approximately 465,000 nodes and 835,000 edges) demonstrates the efficacy of our strongest payment space formulation. It finds solutions that are on average 0.4% from optimality and solves 80 of the 100 instances to optimality. Summary of Contribution: The study of influence propagation is important in a number of applications including marketing, epidemiology, and healthcare. Typically, in these problems, one seeks to identify individuals to strategically target in a social network so that the entire network is influenced at a minimal cost. With the ease of tracking consumers in the smartapp economy, the scope and nature of these problems have become larger. Consequently, there is considerable interest across multiple research communities in computationally solving large-scale influence maximization problems, which thus represent significant opportunities for the development of operations research–based methods and analysis in this interface. This paper introduces the positive influence dominating set with partial payments (PIDS-PP) problem, an influence maximization problem where the effects of direct influence predominate, and it is possible to make partial payments to nodes that are not targeted. The paper focuses on model development to solve large-scale PIDS-PP problems. To this end, starting from an initial base optimization model, it uses several operations research model strengthening techniques to develop two equivalent models that have strong computational performance (and can be theoretically shown to be the best model for trees). Computational experiments on a test bed of 100 real-world graph instances (with up to approximately 465,000 nodes and 835,000 edges) attest to the efficacy of the best model, which finds solutions that are on average 0.4% from optimality and solves 80 of the 100 instances to optimality.

This study generalizes the r-interdiction median (RIM) problem with fortification to simultaneously consider two types of risks: probabilistic exogenous disruptions and endogenous disruptions caused by intentional attacks. We develop a bilevel programming model that includes a lower-level interdiction problem and a higher-level fortification problem to hedge against such risks. We then prove that the interdiction problem is supermodular and subsequently adopt the cuts associated with supermodularity to develop an efficient cutting-plane algorithm to achieve exact solutions. For the fortification problem, we adopt the logic-based Benders decomposition (LBBD) framework to take advantage of the two-level structure and the property that a facility should not be fortified if it is not attacked at the lower level. Numerical experiments show that the cutting-plane algorithm is more efficient than benchmark methods in the literature, especially when the problem size grows. Specifically, with regard to the solution quality, LBBD outperforms the greedy algorithm in the literature with an up-to 13.2% improvement in the total cost, and it is as good as or better than the tree-search implicit enumeration method. Summary of Contribution: This paper studies an r-interdiction median problem with fortification (RIMF) in a supply chain network that simultaneously considers two types of disruption risks: random disruptions that occur probabilistically and disruptions caused by intentional attacks. The problem is to determine the allocation of limited facility fortification resources to an existing network. It is modeled as a bilevel programming model combining a defender’s problem and an attacker’s problem, which generalizes the r-interdiction median problem with probabilistic fortification. This paper is suitable for IJOC in mainly two aspects: (1) The lower-level attacker’s interdiction problem is a challenging high-degree nonlinear model. In the literature, only a total enumeration method has been applied to solve a special case of this problem. By exploring the special structural property of the problem, namely, the supermodularity of the transportation cost function, we developed an exact cutting-plane method to solve the problem to its optimality. Extensive numerical studies were conducted. Hence, this paper fits in the intersection of operations research and computing. (2) We developed an efficient logic-based Benders decomposition algorithm to solve the higher-level defender’s fortification problem. Overall, this study generalizes several important problems in the literature, such as RIM, RIMF, and RIMF with probabilistic fortification (RIMF-p).

The problem of fitting continuous piecewise linear (PWL) functions to discrete data has applications in pattern recognition and engineering, amongst many other fields. To find an optimal PWL function, the positioning of the breakpoints connecting adjacent linear segments must not be constrained and should be allowed to be placed freely. Although the univariate PWL fitting problem has often been approached from a global optimisation perspective, recently, two mixed-integer linear programming approaches have been presented that solve for optimal PWL functions. In this paper, we compare the two approaches: the first was presented by Rebennack and Krasko [Rebennack S, Krasko V (2020) Piecewise linear function fitting via mixed-integer linear programming. INFORMS J. Comput. 32(2):507–530] and the second by Kong and Maravelias [Kong L, Maravelias CT (2020) On the derivation of continuous piecewise linear approximating functions. INFORMS J. Comput. 32(3):531–546]. Both formulations are similar in that they use binary variables and logical implications modelled by big-[Formula: see text] constructs to ensure the continuity of the PWL function, yet the former model uses fewer binary variables. We present experimental results comparing the time taken to find optimal PWL functions with differing numbers of breakpoints across 10 data sets for three different objective functions. Although neither of the two formulations is superior on all data sets, the presented computational results suggest that the formulation presented by Rebennack and Krasko is faster. This might be explained by the fact that it contains fewer complicating binary variables and sparser constraints. Summary of Contribution: This paper presents a comparison of the mixed-integer linear programming models presented in two recent studies published in the INFORMS Journal on Computing. Because of the similarity of the formulations of the two models, it is not clear which one is preferable. We present a detailed comparison of the two formulations, including a series of comparative experimental results across 10 data sets that appeared across both papers. We hope that our results will allow readers to take an objective view as to which implementation they should use.

In many statistical learning problems, it is desired that the optimal solution conform to an a priori known sparsity structure represented by a directed acyclic graph. Inducing such structures by means of convex regularizers requires nonsmooth penalty functions that exploit group overlapping. Our study focuses on evaluating the proximal operator of the latent overlapping group lasso developed by Jacob et al. in 2009 . We implemented an alternating direction method of multiplier with a sharing scheme to solve large-scale instances of the underlying optimization problem efficiently. In the absence of strong convexity, global linear convergence of the algorithm is established using the error bound theory. More specifically, the paper contributes to establishing primal and dual error bounds when the nonsmooth component in the objective function does not have a polyhedral epigraph. We also investigate the effect of the graph structure on the speed of convergence of the algorithm. Detailed numerical simulation studies over different graph structures supporting the proposed algorithm and two applications in learning are provided. Summary of Contribution: The paper proposes a computationally efficient optimization algorithm to evaluate the proximal operator of a nonsmooth hierarchical sparsity-inducing regularizer and establishes its convergence properties. The computationally intensive subproblem of the proposed algorithm can be fully parallelized, which allows solving large-scale instances of the underlying problem. Comprehensive numerical simulation studies benchmarking the proposed algorithm against five other methods on the speed of convergence to optimality are provided. Furthermore, performance of the algorithm is demonstrated on two statistical learning applications related to topic modeling and breast cancer classification. The code along with the simulation studies and benchmarks are available on the corresponding author’s GitHub website for evaluation and future use.

This paper is devoted to the management of advance admission requests for obstetric care. Pregnant women in China select one hospital and request admission for both antenatal and postnatal care after nine weeks of pregnancy. Schedulers must make the admission decision instantly based on the availability of the most critical resource, that is, hospital beds for postnatal care. The random delay between admission requests and postnatal care has created a distinct advance admission control problem. To address this issue, we propose a basic model that assumes a unit bed requirement for one day. Each admission generates a unit of revenue and each unit of overcapacity use incurs an overcapacity cost. With the objective of maximizing the expected net revenue, we establish an optimal policy for unlimited requests, that is, an expected arrival time quota (EATQ) policy that accepts a fixed quota of advance admission requests with the same expected date of confinement. We then propose an extended model for general capacity requirements. Using the Poisson approximation, we establish the optimality of the EATQ policy, which is shown to be solvable by a simple linear programming model. We compare the numerical results from the different policies and conduct a sensitivity analysis. The EATQ policy is demonstrated to be the best option in all test instances and notably outperforms the current admission rules used in hospitals, which usually accept admission requests according to some empirical monthly quota of the expected delivery month. The Poisson approximation is shown to be effective for determining the optimal EATQ policy for both stationary and nonstationary arrivals. Summary of Contribution: First, this paper investigates the advance admission control problem for obstetric care. Pregnant women in China choose one hospital and request admission for both antenatal and postnatal care after nine weeks of pregnancy but the most critical resource is hospitalization beds needed for postnatal care. The random delay between admission request and postnatal care makes the problem unique and challenging to solve. It belongs to the scope of computing and operations research. Second, this paper formulates a dynamic programming model, analyzes the structural properties of the optimal control policy, and finally proposes a mathematical programming model to determine the optimal quota. Numerical experiments show the validity of the proposed approach. It covers the research contents of theories on dynamic stochastic control, mathematic programming model, and experiments. Moreover, this paper is motivated by the practical problem (advance admission control) in obstetric units of Shanghai. Using these optimality properties, solution approaches, and numerical results, this paper provides guidance on how to manage advance obstetric admission requests.

The emergence of online retailers has brought new opportunities to the design of their distribution networks. Notably, for online retailers that do not operate offline stores, their target customers are more sensitive to the quality of logistic services, such as delivery speed and reliability. This paper is motivated by a leading online retailer for cosmetic products on Taobao.com that aimed to improve its logistics efficiency by redesigning its centralized distribution network into a multilevel one. The multilevel distribution network consists of a layer of primary facilities to hold stocks from suppliers and transshipment and a layer of secondary facilities to provide last-mile delivery. There are two major challenges of designing such a facility network. First, online customers can respond significantly to the change of logistics efficiency with the redesigned network, thereby rendering the network optimized under the original demand distribution suboptimal. Second, because online retailers have relatively small sales volumes and are very flexible in choosing facility locations, the facility candidate set can be large, causing the facility location optimization challenging to solve. To this end, we propose an iterative prediction-and-optimization strategy for distribution network design. Specifically, we first develop an artificial neural network (ANN) to predict customer demands, factoring in the logistic service quality given the network and the city-level purchasing power based on demographic statistics. Then, a mixed integer linear programming (MILP) model is formulated to choose facility locations with minimum transportation, facility setup, and package processing costs. We further develop an efficient two-stage heuristic for computing high-quality solutions to the MILP model, featuring an agglomerative hierarchical clustering algorithm and an expectation and maximization algorithm. Subsequently, the ANN demand predictor and two-stage heuristic are integrated for iterative network design. Finally, using a real-world data set, we validate the demand prediction accuracy and demonstrate the mutual interdependence between the demand and network design. Summary of Contribution: We propose an iterative prediction-and-optimization algorithm for multilevel distribution network design for e-logistics and evaluate its operational value for online retailers. We address the issue of the interplay between distribution network design and the demand distribution using an iterative framework. Further, combining the idea in operational research and data mining, our paper provides an end-to-end solution that can provide accurate predictions of online sales distribution, subsequently solving large-scale optimization problems for distribution network design problems.

In the context of the maximum stable set problem, rank inequalities impose that the cardinality of any set of vertices contained in a stable set be, at most, as large as the stability number of the subgraph induced by such a set. Rank inequalities are very general, as they subsume many classical inequalities such as clique, hole, antihole, web, and antiweb inequalities. In spite of their generality, the exact separation of rank inequalities has never been addressed without the introduction of topological restrictions on the induced subgraph and the tightness of their closure has never been investigated systematically. In this work, we propose a methodology for optimizing over the closure of all rank inequalities with a right-hand side no larger than a small constant without imposing any restrictions on the topology of the induced subgraph. Our method relies on the exact separation of a relaxation of rank inequalities, which we call relaxed k-rank inequalities, whose closure is as tight. We investigate the corresponding separation problem, a bilevel programming problem asking for a subgraph of maximum weight with a bound on its stability number, whose study could be of independent interest. We first prove that the problem is [Formula: see text]-hard and provide some insights on its polyhedral structure. We then propose two exact methods for its solution: a branch-and-cut algorithm (which relies on a family of faced-defining inequalities which we introduce in this paper) and a purely combinatorial branch-and-bound algorithm. Our computational results show that the closure of rank inequalities with a right-hand side no larger than a small constant can yield a bound that is stronger, in some cases, than Lovász’s Theta function, and substantially stronger than bounds obtained with standard inequalities that are valid for the stable set problem, including odd-cycle inequalities and wheel inequalities. Summary of Contribution: This paper proposes two original methods for solving a challenging cut-separation problem (of bilevel type) for a large class of inequalities valid for one of the key operations research problems, namely, the max stable set problem. An extensive set of experimental results validates the proposed methods. All the source code and data sets are available online on GitHub.

This paper considers a class of two-stage stochastic mixed-integer optimization problems where, for a given first-stage solution, we can determine the optimal values of recourse variables sequentially. This class of problems arises in a wide variety of applications. In the case of multivariate discrete distributions for uncertain parameters, a standard stochastic programming formulation of these problems involves an exponential number of scenarios, therefore an exponential number of variables and constraints. We propose a new mixed-integer programming modeling approach where the number of variables and constraints is independent of the number of scenarios and scales at most pseudopolynomially with the problem size. The proposed modeling approach relies on state variables that track the system’s state as the uncertainty realizes sequentially. We demonstrate the advantages of the proposed approach in two applications arising in project scheduling and operating room allocation. Summary of Contribution: This paper proposes a new modeling approach for a class of two-stage stochastic optimization problems that is computationally more efficient than the traditional scenario-based stochastic integer programming models. The proposed modeling approach relies on state variables that track the system's state as the uncertainty realizes sequentially. We demonstrated the efficiency of the proposed approach by computational results on two applications in project scheduling and operating room allocation.

Randomized decision making refers to the process of making decisions randomly according to the outcome of an independent randomization device, such as a dice roll or a coin flip. The concept is unconventional, and somehow counterintuitive, in the domain of mathematical programming, in which deterministic decisions are usually sought even when the problem parameters are uncertain. However, it has recently been shown that using a randomized, rather than a deterministic, strategy in nonconvex distributionally robust optimization (DRO) problems can lead to improvements in their objective values. It is still unknown, though, what is the magnitude of improvement that can be attained through randomization or how to numerically find the optimal randomized strategy. In this paper, we study the value of randomization in mixed-integer DRO problems and show that it is bounded by the improvement achievable through its continuous relaxation. Furthermore, we identify conditions under which the bound is tight. We then develop algorithmic procedures, based on column generation, for solving both single- and two-stage linear DRO problems with randomization that can be used with both moment-based and Wasserstein ambiguity sets. Finally, we apply the proposed algorithm to solve three classical discrete DRO problems: the assignment problem, the uncapacitated facility location problem, and the capacitated facility location problem and report numerical results that show the quality of our bounds, the computational efficiency of the proposed solution method, and the magnitude of performance improvement achieved by randomized decisions. Summary of Contribution: In this paper, we present both theoretical results and algorithmic tools to identify optimal randomized strategies for discrete distributionally robust optimization (DRO) problems and evaluate the performance improvements that can be achieved when using them rather than classical deterministic strategies. On the theory side, we provide improvement bounds based on continuous relaxation and identify the conditions under which these bound are tight. On the algorithmic side, we propose a finitely convergent, two-layer, column-generation algorithm that iterates between identifying feasible solutions and finding extreme realizations of the uncertain parameter. The proposed algorithm was implemented to solve distributionally robust stochastic versions of three classical optimization problems and extensive numerical results are reported. The paper extends a previous, purely theoretical work of the first author on the idea of randomized strategies in nonconvex DRO problems by providing useful bounds and algorithms to solve this kind of problems.

This paper proposes a cluster-aware supervised learning (CluSL) framework, which integrates the clustering analysis with supervised learning. The objective of CluSL is to simultaneously find the best clusters of the data points and minimize the sum of loss functions within each cluster. This framework has many potential applications in healthcare, operations management, manufacturing, and so on. Because CluSL, in general, is nonconvex, we develop a regularized alternating minimization (RAM) algorithm to solve it, where at each iteration, we penalize the distance between the current clustering solution and the one from the previous iteration. By choosing a proper penalty function, we show that each iteration of the RAM algorithm can be computed efficiently. We further prove that the proposed RAM algorithm will always converge to a stationary point within a finite number of iterations. This is the first known convergence result in cluster-aware learning literature. Furthermore, we extend CluSL to the high-dimensional data sets, termed the F-CluSL framework. In F-CluSL, we cluster features and minimize loss function at the same time. Similarly, to solve F-CluSL, a variant of the RAM algorithm (i.e., F-RAM) is developed and proven to be convergent to an [Formula: see text]-stationary point. Our numerical studies demonstrate that the proposed CluSL and F-CluSL can outperform the existing ones such as random forests and support vector classification, both in the interpretability of learning results and in prediction accuracy. Summary of Contribution: Aligned with the mission and scope of the INFORMS Journal on Computing, this paper proposes a cluster-aware supervised learning (CluSL) framework, which integrates the clustering analysis with supervised learning. Because CluSL is, in general, nonconvex, a regularized alternating projection algorithm is developed to solve it and is proven to always find a stationary solution. We further generalize the framework to the high-dimensional data set, F-CluSL. Our numerical studies demonstrate that the proposed CluSL and F-CluSL can deliver more interpretable learning results and outperform the existing ones such as random forests and support vector classification in computational time and prediction accuracy.

Many stochastic systems face a time-dependent demand. Especially in stochastic service systems, for example, in call centers, customers may leave the queue if their waiting time exceeds their personal patience. As discussed in the extant literature, it can be useful to use general distributions to model such customer patience. This paper analyzes the time-dependent performance of a multiserver queue with a nonhomogeneous Poisson arrival process with a time-dependent arrival rate, exponentially distributed processing times, and generally distributed time to abandon. Fast and accurate performance approximations are essential for decision support in such queueing systems, but the extant literature lacks appropriate methods for the setting we consider. To approximate time-dependent performance measures for small- and medium-sized systems, we develop a new stationary backlog-carryover (SBC) approach that allows for the analysis of underloaded and overloaded systems. Abandonments are considered in two steps of the algorithm: (i) in the approximation of the utilization as a reduced arrival stream and (ii) in the approximation of waiting-based performance measures with a stationary model for general abandonments. To improve the approximation quality, we discuss an adjustment to the interval lengths. We present a limit result that indicates convergence of the method for stationary parameters. The numerical study compares the approximation quality of different adjustments to the interval length. The new SBC approach is effective for instances with small numbers of time-dependent servers and gamma-distributed abandonment times with different coefficients of variation and for an empirical distribution of the abandonment times from real-world data obtained from a call center. A discrete-event simulation benchmark confirms that the SBC algorithm approximates the performance of the queueing system with abandonments very well for different parameter configurations. Summary of Contribution: The paper presents a fast and accurate numerical method to approximate the performance measures of a time‐dependent queueing system with generally distributed abandonments. The presented stationary backlog carryover approach with abandonment combines algorithmic ideas with stationary queueing models for generally distributed abandonment times. The reliability of the method is analyzed for transient systems and numerically studied with real‐world data.