Search

In this paper, we consider the problem of finding bounds on the prices of options depending on multiple assets without assuming any underlying model on the price dynamics but only the absence of arbitrage opportunities. We formulate this as a generalized moment problem and utilize the well-known moment-sum-of-squares hierarchy of Lasserre to obtain bounds on the range of the possible prices. A complementary approach (also from Lasserre) is employed for comparison. We present several numerical examples to demonstrate the viability of our approach. The framework we consider makes it possible to incorporate different kinds of observable data, such as moment information, as well as observable prices of options on the assets of interest. History: Accepted by Antonio Frangioni, area editor for Design & Analysis of Algorithms–Continuous. Funding: This work was supported by the European Union's Horizon 2020 research and innovation program under the Marie Skłodowska-Curie grant agreement [Grant 813211 (POEMA)]. 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.1220] or is available from the IJOC GitHub software repository (https://github.com/INFORMSJoC) at [http://dx.doi.org/10.5281/zenodo.6602361]. [ABSTRACT FROM AUTHOR]

Introduces articles related to mining of web-based data for electronic-business applications published in May 2003 issue of the journal 'Informs Journal on Computing.' Advantages of web information; Problem of data preprocessing of weblog files; Challenge for the data-mining community; Concept of web business intelligence.

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. [ABSTRACT FROM AUTHOR]

In the biobjective branch-and-bound literature, a key ingredient is objective branching, that is, to create smaller and disjoint subproblems in the objective space, obtained from the partial dominance of the lower bound set by the upper bound set. When considering three or more objective functions, however, applying objective branching becomes more complex, and its benefit has so far been unclear. In this paper, we investigate several ingredients that allow us to better exploit objective branching in a multiobjective setting. We extend the idea of probing to multiple objectives for the 0-1 case, enhance it in several ways, and show that, when coupled with objective branching, it results in significant speedups in terms of CPU times. We also show how to adapt it to the general integer case. Furthermore, we investigate cut generation based on the objective branching constraints. Besides, we generalize the best bound idea for node selection to multiple objectives, and we show that the proposed rules outperform, in the multiobjective literature, the commonly employed depth-first and breadth-first strategies. We also analyze problem-specific branching rules. We test the proposed ideas on available benchmark instances for three problem classes with three and four objectives, namely, the capacitated facility location problem, the uncapacitated facility location problem, and the knapsack problem. Our enhanced multiobjective branch-and-bound algorithm outperforms the best existing branch-and-bound–based approach and is the first to obtain competitive and even slightly better results than a state-of-the-art objective space search method on a subset of the problem classes. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This work was supported in whole, or in part, by the Austrian Science Fund [Grant P 31366]. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.0299. [ABSTRACT FROM AUTHOR]

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

Program coverage customization selectively adds instrumentation to a compiled computer program so that a limited amount of directly observed data can be used to infer other program coverage information after a run. A good instrumentation plan can reduce run-time overheads while still giving software developers the information they need. Unfortunately, optimal coverage planning is NP-hard, limiting either the quality of heuristic plans or the sizes of programs that can be instrumented optimally. We exploit the monotonicity property of feasible instrumentations to formulate this problem as an intraprocedural set covering problem. Our formulation has an exponential number of constraints, and we design a polynomial-time separation algorithm to incrementally add the necessary subset of these inequalities. Our approach reduces expected run-time probing costs compared with existing methods, offers a guarantee of the optimality of the instrumentation, and has compilation-time overhead suitable for wide practical use. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: This work was supported by the National Science Foundation [Grants CCF-1318489, CCF-1420866, and CCF-1423237] and the Air Force Research Laboratory [Grant FA8750-14-2-0270]. 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.2021.0349) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0349). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

This study considers a well-known critical node detection problem that aims to minimize a pairwise connectivity measure of an undirected graph via the removal of a subset of nodes (referred to as critical nodes) subject to a cardinality constraint. Potential applications include epidemic control, emergency response, vulnerability assessment, carbon emission monitoring, network security, and drug design. To solve the problem, we present a "reduce-solve-combine" memetic search approach that integrates a problem reduction mechanism into the popular population-based memetic algorithm framework. At each generation, a common pattern mined from two parent solutions is first used to reduce the given problem instance, then the reduced instance is solved by a component-based hybrid neighborhood search that effectively combines an articulation point impact strategy and a node weighting strategy, and finally an offspring solution is produced by combining the mined common pattern and the solution of the reduced instance. Extensive evaluations on 42 real-world and synthetic benchmark instances show the efficacy of the proposed method, which discovers nine new upper bounds and significantly outperforms the current state-of-the-art algorithms. Investigation of key algorithmic modules additionally discloses the importance of the proposed ideas and strategies. Finally, we demonstrate the generality of the proposed method via its adaptation to solve the node-weighted critical node problem. 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 72371157, 61903144, 72031007]. 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.0130) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0130). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Model calibration is challenging for large-scale system models with a great number of variables. Existing approaches to partitioning system models and prioritizing data acquisition rely on heuristics rather than formal treatments. The sensor placement problem in physical dynamic systems points to a promising avenue for formalizing data acquisition priorities, which addresses the following question for system models: With the model at hand and pre-existing data availability on a subset of model variables, what are the (next) k model variables that would bring the largest utility to model calibration, once their data are acquired? In this study, we formalize this problem as a combinatorial optimization and adapt two solutions, the information-entropy approach and the miss-probability approach, from physical dynamic systems to system models in management sciences. Next, based on the idea of the data availability partition, we develop a third solution. The new approach can be understood from the entropy perspective and is embedded in the theoretical framework for the evaluation of side information. Our solution applies to system models of all topologies: analytical results of the optimal placement are derived for binary/multinary trees; for general (directed) tree structures, an algorithm to determine the optimal placement is devised, whose complexity is upper-bounded by O(nlog2(n)) for an n-variable system; for arbitrary model topologies with the presence of loops, sequential-optimal and simulated-annealing schemes are formulated. Three approaches are compared on a validating example; our solution outperforms the two alternatives. Application on a multicompartment system demonstrates the toolkit's practical use. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. 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.0128) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0128). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

In this paper, we study adjustable robust optimization (ARO) problems with discrete uncertainty. Under a very general modeling framework, we show that such two-stage robust problems can be exactly reformulated as ARO problems with objective uncertainty only. This reformulation is valid with and without the fixed recourse assumption and is not limited to continuous wait-and-see decision variables unlike most of the existing literature. Additionally, we extend an enumerative algorithm akin to a branch-and-cut scheme for which we study the asymptotic convergence. We discuss how to apply the reformulation on two variants of well-known optimization problems, a facility location problem in which uncertainty may affect the capacity values and a multiple knapsack problem with uncertain weights, and we report extensive computational results demonstrating the effectiveness of the approach. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This work was supported by the Air Force Office of Scientific Research [Grants FA8655-20-1-7012, FA8655-20-1-7019]. [ABSTRACT FROM AUTHOR]

Although most methods for solving mixed-integer optimization problems compute a single optimal solution, a diverse set of near-optimal solutions can often lead to improved outcomes. We present a new method for finding a set of diverse solutions by emphasizing diversity within the search for near-optimal solutions. Specifically, within a branch-and-bound framework, we investigated parameterized node selection rules that explicitly consider diversity. Our results indicate that our approach significantly increases the diversity of the final solution set. When compared with two existing methods, our method runs with similar runtime as regular node selection methods and gives a diversity improvement between 12% and 190%. In contrast, popular node selection rules, such as best-first search, in some instances performed worse than state-of-the-art methods by more than 35% and gave an improvement of no more than 130%. Furthermore, we find that our method is most effective when diversity in node selection is continuously emphasized after reaching a minimal depth in the tree and when the solution set has grown sufficiently large. Our method can be easily incorporated into integer programming solvers and has the potential to significantly increase the diversity of solution sets. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: This work was supported by the Army Research Office [Grant W911NF-21-1-0079]. The views expressed in this study do not represent those of the U.S. Government, the U.S. Department of Defense, or the U.S. Army. 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.0164) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0164). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Federated learning is a new distributed machine learning framework, where numerous heterogeneous clients collaboratively train a model without sharing training data. In this work, we consider a practical and ubiquitous issue when deploying federated learning in mobile environments: intermittent client availability, where the set of eligible clients may change during the training process. Such intermittent client availability would seriously deteriorate the performance of the classical federated averaging algorithm (FedAvg). Thus, we propose a simple distributed nonconvex optimization algorithm, called federated latest averaging (FedLaAvg), which leverages the latest gradients of all clients, even when the clients are not available, to jointly update the global model in each iteration. Our theoretical analysis shows that FedLaAvg achieves guaranteed convergence and a sublinear speedup with respect to the total number of clients. We implement FedLaAvg along with several baselines and evaluate them over the benchmarking MNIST and Sentiment140 data sets. The evaluation results demonstrate that FedLaAvg achieves more stable training than FedAvg in both convex and nonconvex settings and reaches a sublinear speedup. Source code and online supplement are available at the IJOC GitHub site (http://dx.doi.org/10.1287/ijoc.2022.0057.cd, https://github.com/INFORMSJoC/2022.0057). History: Accepted by Ram Ramesh, Area Editor for Data Science & Machine Leaning. Funding: This work was supported by the National Key R&D Program of China [Grant 2022ZD0119100], the National Natural Science Foundation of China (NSFC) [Grants 61972252, 61972254, 62072303, 62025204, 62132018, 62202296, and 62202297], the Alibaba Innovation Research (AIR) Program, and the Tencent Rhino Bird Key Research Project. 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.0057) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0057). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Economic capital (EC) is a risk measure used by financial firms to specify capital levels to protect (with high probability) against large unforeseen losses. Defined as the difference between an (extreme) quantile and the mean of the loss distribution, the EC is often estimated via Monte Carlo methods. Although simple random sampling (SRS) may be effective in estimating the mean, it can be inefficient for the extreme quantile in the EC. Applying importance sampling (IS) may lead to an efficient quantile estimator but can do poorly for the mean. Measure-specific IS (MSIS) instead uses IS to estimate only the quantile, and the mean is independently handled via SRS. We analyze large-sample properties of EC estimators obtained via SRS only, IS only, MSIS, IS using a defensive mixture, and a double estimator using both SRS and IS to estimate both the quantile and the mean, establishing Bahadur-type representations for the EC estimators and proving they obey central limit theorems. We provide asymptotic theory comparing the estimators when the loss is the sum of a large number of independent and identically distributed random variables. Numerical and simulation results, including for a large portfolio credit risk model with dependent obligors, complement the theory. History: Accepted by Bruno Tuffin, Area Editor for Simulation. Funding: This work was supported by the National Science Foundation [Grant CMMI-1537322]. 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.2021.0261) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0261). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Research on software reliability growth models (SRGMs) has been extensively conducted for decades, and the models were often developed based on two assumptions: (1) once the errors are detected, they can be completely removed instantly, and (2) errors can be removed eternally, and the debugging tasks will not produce any new errors. However, both assumptions are unrealistic. This study proposes an SRGM that ignores these restricted assumptions by introducing a detection process that may remove an error after a period of time once it has been detected and by considering imperfect debugging, which indicates that new errors may emerge through corresponding debugging tasks. In addition, because software can be upgraded to respond on a timely basis to constantly changing consumer expectations and thus extend product life in the market, the proposed SRGM also considers software upgrades for the multiversion software, and a dynamic programming approach is used to effectively obtain the optimal release schedule with consideration of the constraint of budget. Real data sets are used to examine the effectiveness of the proposed model, and the fitting results show that the proposed model outperforms other existing models. The results of numerical validation indicate that the proposed dynamic programming method with information updating outperforms the sequential solution method in determining the optimal release time for each version. Moreover, decision makers should carefully evaluate the parameters because overestimating the parameters of the mean value functions will cause serious software risk due to excessively shortening the testing time. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. 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.2021.0141) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0141). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

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]. [ABSTRACT FROM AUTHOR]

The time-dependent traveling salesman problem with time windows (TDTSPTW) is a variant of the well-known traveling salesman problem with time windows, in which travel times are not assumed to be constant. The TDTSPTW accounts for the effects of congestion at the planning level, being particularly suited for distribution problems in large cities. In this paper we develop a labeling-based algorithm for the TDTSPTW that incorporates partial dominance and generalizes several state-of-the-art components from the time-independent related literature. We propose a framework general enough to be applied to the TDTSPTW and its variant without time windows, with the objective of minimizing the duration or the makespan. As part of the framework, we introduce a new state-space relaxation specifically designed for the time-dependent context. Extensive computational experiments show the effectiveness of the overall approach and the impact of the new relaxation, outperforming several recent algorithms proposed for these variants on more than 9,000 benchmark instances. In addition, we frame the minimum tour duration problem within the time-dependent literature and include it as a benchmark for our algorithm, obtaining improved computation times and 31 new optimal solutions. Summary of Contribution: In this paper, we study the time-dependent traveling salesman problem with time windows (TDTSPTW), a difficult single-vehicle routing problem that incorporates more realistic travel time functions than its classic time-independent counterpart. As a result, the TDTSPTW is harder to solve, as it requires more complex models and algorithms. Using state-of-the-art optimization techniques, we propose an efficient solution approach for the TDTSPTW and some related variants that outperforms the previous approaches in the literature. Our paper emphasizes the importance of algorithmic design and efficient implementations to tackle relevant practical combinatorial optimization problems—in particular, for time-dependent problems. Moreover, the resulting algorithm fosters a new research direction regarding exact algorithms for time-dependent problems using dynamic programming and relaxation techniques. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This research has been funded by Fondo para la Investigación Científica y Tecnológica (FONCyT) [Grants PICT-2016-2677 and PICT-2018-2961] from the Ministry of Science, Argentina, and by the Google Latin America Research Award (LARA) 2019. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.1236. [ABSTRACT FROM AUTHOR]

Over the last two decades, robust optimization has emerged as a popular means to address decision-making problems affected by uncertainty. This includes single-stage and multi-stage problems involving real-valued and/or binary decisions and affected by exogenous (decision-independent) and/or endogenous (decision-dependent) uncertain parameters. Robust optimization techniques rely on duality theory potentially augmented with approximations to transform a (semi-)infinite optimization problem to a finite program, the robust counterpart. Whereas writing down the model for a robust optimization problem is usually a simple task, obtaining the robust counterpart requires expertise. To date, very few solutions are available that can facilitate the modeling and solution of such problems. This has been a major impediment to their being put to practical use. In this paper, we propose ROC++, an open-source C++ based platform for automatic robust optimization, applicable to a wide array of single-stage and multi-stage robust problems with both exogenous and endogenous uncertain parameters, that is easy to both use and extend. It also applies to certain classes of stochastic programs involving continuously distributed uncertain parameters and endogenous uncertainty. Our platform naturally extends existing off-the-shelf deterministic optimization platforms and offers ROPy, a Python interface in the form of a callable library, and the ROB file format for storing and sharing robust problems. We showcase the modeling power of ROC++ on several decision-making problems of practical interest. Our platform can help streamline the modeling and solution of stochastic and robust optimization problems for both researchers and practitioners. It comes with detailed documentation to facilitate its use and expansion. The latest version of ROC++ can be downloaded from https://sites.google.com/usc.edu/robust-opt-cpp/. Summary of Contribution: The paper "ROC++: Robust Optimization in C++" proposes a new open-source C++ based platform for modeling, automatically reformulating, and solving robust optimization problems. ROC++ can address both single-stage and multi-stage problems involving exogenous and/or endogenous uncertain parameters and real- and/or binary-valued adaptive variables. The ROC++ modeling language is similar to the one provided for the deterministic case by state-of-the-art deterministic optimization solvers. ROC++ comes with detailed documentation to facilitate its use and expansion. It also offers ROPy, a Python interface in the form of a callable library. The latest version of ROC++ can be downloaded from https://sites.google.com/usc.edu/robust-opt-cpp/. History: Accepted by Ted Ralphs, Area Editor for Software Tools. Funding: This material is based upon work supported by the National Science Foundation under Grant No. 1763108. This support is gratefully acknowledged. 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.1209) or is available from the IJOC GitHub software repository (https://github.com/INFORMSJoC) at (https://dx.doi.org/10.5281/zenodo.6360996). [ABSTRACT FROM AUTHOR]

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 O (K − 1 / 2) 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 O (log (K) K − 1 / 2) constraint violation bound and O (log 3 / 2 (K) K − 1 / 2) 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The appointment scheduling problem (ASP) studies how to manage patient arrivals to a healthcare system to improve system performance. An important challenge occurs when some patients may not show up for an appointment. Although the ASP is well studied in the literature, the vast majority of the existing work does not consider the well-observed phenomenon that patient no-show is influenced by the appointment time, the usual decision variable in the ASP. This paper studies the ASP with random service time (exogenous uncertainty) with known distribution and patient decision-dependent no-show behavior (endogenous uncertainty). This problem belongs to the class of stochastic optimization with decision-dependent uncertainties. Such problems are notoriously difficult as they are typically nonconvex. We propose a stochastic projected gradient path (SPGP) method to solve the problem, which requires the development of a gradient estimator of the objective function—a nontrivial task, as the literature on gradient-based optimization algorithms for problems with decision-dependent uncertainty is very scarce and unsuitable for our model. Our method can solve the ASP problem under arbitrarily smooth show-up probability functions. We present solutions under different patterns of no-show behavior and demonstrate that breaking the assumption of constant show-up probability substantially changes the scheduling solutions. We conduct numerical experiments in a variety of settings to compare our results with those obtained with a distributionally robust optimization method developed in the literature. The cost reduction obtained with our method, which we call the value of distribution information, can be interpreted as how much the system performance can be improved by knowing the distribution of the service times, compared to not knowing it. We observe that the value of distribution information is up to 31% of the baseline cost, and that such value is higher when the system is crowded or/and the waiting time cost is relatively high. Summary of Contribution: This paper studies an appointment scheduling problem under time-dependent patient no-show behavior, a situation commonly observed in practice. The problem belongs to the class of stochastic optimization problems with decision-dependent uncertainties in the operations research literature. Such problems are notoriously difficult to solve as a result of the lack of convexity, and the present case requires different techniques because of the presence of continuous distributions for the service times. A stochastic projected gradient path method, which includes the development of specialized techniques to estimate the gradient of the objective function, is proposed to solve the problem. For problems with a similar structure, the algorithm can be applied once the gradient estimator of the objective function is obtained. Extensive numerical studies are presented to demonstrate the quality of the solutions, the importance of modeling time-dependent no-shows in appointment scheduling, and the value of using distribution information about the service times. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We explore the Projective Cutting-Planes algorithm proposed in Porumbel (2020) from new angles by applying it to two new problems, that is, to robust linear programming and to a cutting-stock problem with multiple lengths. Projective Cutting-Planes is a generalization of the widely used Cutting-Planes, and it aims at optimizing a linear function over a polytope P with prohibitively many constraints. The main new idea is to replace the well-known separation subproblem with the following projection subproblem: given an interior point x ∈ P and a direction d , find the maximum steplength t such that x + t d ∈ P. This enables one to generate a feasible solution at each iteration, a feature that does not exist built-in in a standard Cutting-Planes algorithm. The practical success of this new algorithm does not mainly come from the higher level ideas already presented in Porumbel (2020). Its success is significantly more dependent on the computation time needed to solve the projection subproblem in practice. Thus, the main challenge addressed by the current paper is the design of new techniques for solving this subproblem very efficiently for different polytopes P. We first address a well-known robust linear programming problem in which P is defined as a primal polytope. We then solve a multiple-length cutting stock problem in which P is a dual polytope defined in a column generation model. Numerical experiments on both these new problems confirm the potential of the proposed ideas. This enables us to draw conclusions supported by numerical results from both the current paper and Porumbel (2020) while also gaining more insight into the dynamics of the algorithm. Summary of Contribution: The well-known Cutting-Planes algorithm relies on the separation subproblem to cut off the current optimal solution. This paper belongs to a line of work whose goal is to "upgrade" the widely used separation subproblem to the following projection subproblem: given a feasible solution x inside some polytope P and a direction d, what is the maximum t value such that x + td ∈ P. In simple terms, one has to "shoot" from x along direction d up to the point where the boundary of the polytope is hit. The greatest challenge is to solve this projection subproblem rapidly enough to compete well in terms of computational speed with the separation subproblem algorithm. This paper shows how to achieve this on two new problems: robust linear programming and multiple length cutting stock. The numerical results confirm one important advantage offered by the projection logic: it enables one to generate a new feasible interior solution (i.e., x + td) at each iteration. The interior points thus generated actually guide the evolution of the overall algorithm, which is a feature that does not exist (built-in) in a traditional Cutting-Planes algorithm. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In designing ideal multiple recursive random number (RN) generators (MRGs), the best set of multipliers, in terms of the lattice structure of the RNs produced, is sought. As the order of the MRG increases, the number of possible sets of multipliers to be examined grows exponentially This paper proposes a genetic algorithm for designing good MRGs. The set of multipliers associated with the MRG is encoded as a binary string. Via the operations of reproduction, crossover, and mutation, new sets of multipliers are generated. The spectral values of the MRGs are calculated to guide the search process. As an illustration, the proposed algorithm is employed to find good sets of multipliers for MRGs of orders three and four. The results are better than those derived from other studies. To conclude, this paper not only finds better MRGs of orders three and four, but also develops an algorithm for designing MRGs of higher orders. [ABSTRACT FROM AUTHOR]

Though empirical testing is broadly used to evaluate heuristics, there are shortcomings with how it is often applied in practice. In a systematic review of Max-Cut and quadratic unconstrained binary optimization (QUBO) heuristics papers,we found only 4% publish source code, only 14% compare heuristics with identical termination criteria, and most experiments are performed with an artificial, homogeneous set of problem instances. To address these limitations, we implement and release as open-source a code-base of 10 Max-Cut and 27 QUBO heuristics. We perform heuristic evaluation using cloud computing on a library of 3,296 instances. This large-scale evaluation provides insight into the types of problem instances for which each heuristic performs well or poorly. Because no single heuristic outperforms all others across all problem instances, we use machine learning to predict which heuristic will work best on a previously unseen problem instance, a key question facing practitioners. [ABSTRACT FROM AUTHOR]

Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a mixed-integer linear programming solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, we present the basic concept of having two parallel extensions, and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator), including an implementation of deterministic parallelization. Second, we discuss the difficulties in achieving a good performance that utilizes all resources on an actual computing environment, and the difficulties of performance evaluation of the parallel solvers. Third, we present a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions. Finally, we demonstrate the current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer nonlinear programs (MINLPs) in parallel. The online appendix is available at . [ABSTRACT FROM AUTHOR]

Intensity-modulated radiation therapy (IMRT) allows for the design of customized, highly conformal treatments for cancer patients. Creating IMRT treatment plans, however, is a mathematically complex process, which is often tackled in multiple, simpler stages. This sequential approach typically separates radiation dose requirements from mechanical deliverability considerations, which may result in suboptimal treatment quality. For patient health to be considered paramount, holistic models must address these plan elements concurrently, eliminating quality loss between stages. This combined direct aperture optimization (DAO) approach is rarely paired with uncertainty mitigation techniques, such as robust optimization, because of the inherent complexity of both parts. This paper outlines a robust DAO (RDAO) model and discusses novel methodologies for efficiently integrating salient constraints. Because the highly complex RDAO model is difficult to solve, an original candidate plan generation (CPG) heuristic is proposed. The CPG produces rapid, high-quality, feasible plans, which are immediately clinically viable and can also be used to generate a feasible incumbent solution for warm-starting the RDAO model. Computational results obtained using clinical patient data sets with motion uncertainty show the benefit of incorporating the CPG, in terms of both the first incumbent solution and final output plan quality. Summary of Contribution: This paper describes the derivation, implementation, and solution of a large-scale robust direct aperture optimization model for the problem of intensity-modulated radiation therapy planning for cancer treatment. The contribution to operations research lies in the design of a novel mixed-integer programming model that describes all salient mechanical and clinical deliverability requirements for modern delivery equipment. Because of the large-scale nature of the resulting model, a novel tractable heuristic for generating high-quality, feasible treatment plans, as well as warm starts for the full model, is proposed and demonstrated on five clinical patient data sets. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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). [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Operations researchers have long drawn insight from the structure of constraint coefficient matrices (CCMs) for mixed integer programs (MIPs). We propose a new question: Can pictorial representations of CCM structure be used to identify similar MIP models and instances? In this paper, CCM structure is visualized using digital images, and computer vision techniques are used to detect latent structural features therein. The resulting feature vectors are used to measure similarity between images and, consequently, MIPs. An introductory analysis examines a subset of the instances from strIPlib and MIPLIB 2017, two online repositories for MIP instances. Results indicate that structure-based comparisons may allow for relationships to be identified between MIPs from disparate application areas. Additionally, image-based comparisons reveal that ostensibly similar variations of an MIP model may yield instances with markedly different mathematical structures. Summary of Contribution: This paper presents a methodology for comparing mixed integer programs (MIPs) from any research domain based on the structure of the constraint coefficient matrices for one or more instances of a model. Specifically, computer vision and deep learning techniques are used to extract structural features and measure the similarity between these images. This process is agnostic to application area and instead focuses solely on mathematical structure. As a result, this methodology offers a fundamentally new way for operations researchers to view MIP similarity and highlights similarities between research problems that may have previously been viewed as unrelated. [ABSTRACT FROM AUTHOR]

We introduce a prescriptive machine learning approach to speed up the process of solving mixed-integer convex optimization (MICO) problems. We solve multiple optimization instances and train a machine learning model in advance, which we use to solve new instances. Previous works have shown that the predictions of classification algorithms enable us to solve optimization problems much faster than commercial solvers. What distinguishes this paper from the previous work is that we use a prescriptive algorithm, Optimal Policy Trees (OPT), instead of classification algorithms. Whereas classification algorithms aim to predict the correct label and consider all other labels equally undesirable, a prescriptive approach takes into account all the available decision options and their counterfactuals. We first introduce an algorithm that is purely based on OPT and also its extension. We compare their performance with Optimal Classification Trees (OCT) on various MICO problems. Test problems include transportation optimization, portfolio optimization, facility location, and hybrid vehicle control. We also experiment on real-world instances taken from the Mixed Integer Programming Library. OPT-based methods have a significant edge on finding feasible solutions, whereas OCT-based methods have a slight edge on the degree of suboptimality. The proposed extension of the pure OPT algorithm improves on the suboptimality of the solutions the algorithm produces. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: The research was funded in part by a grant from OCP to MIT. [ABSTRACT FROM AUTHOR]

We study a pessimistic stochastic bilevel program in the context of sequential two-player games, where the leader makes a binary here-and-now decision, and the follower responds with a continuous wait-and-see decision after observing the leader's action and revelation of uncertainty. We assume that only the information regarding the mean, covariance, and support is known. We formulate the problem as a distributionally robust (DR) two-stage problem. The pessimistic DR bilevel program is shown to be equivalent to a generic two-stage distributionally robust stochastic (nonlinear) program with both a random objective and random constraints under proper conditions of ambiguity sets. Under continuous distributions, using linear decision rule approaches, we construct upper bounds on the pessimistic DR bilevel program based on (1) a 0-1 semidefinite programming (SDP) approximation and (2) an exact 0-1 copositive programming reformulation. When the ambiguity set is restricted to discrete distributions, an exact 0-1 SDP reformulation is developed, and explicit construction of the worst-case distribution is derived. To further improve the computation of the proposed 0-1 SDPs, a cutting-plane framework is developed. Moreover, based on a mixed-integer linear programming approximation, another cutting-plane algorithm is proposed. Extensive numerical studies are conducted to demonstrate the effectiveness of the proposed approaches on a facility location problem. History: Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. 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.0168) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0168). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

In this paper, we tackle the resolution of chance-constrained problems reformulated via sample average approximation. The resulting data-driven deterministic reformulation takes the form of a large-scale mixed-integer program (MIP) cursed with Big-Ms. We introduce an exact resolution method for the MIP that combines the addition of a set of valid inequalities to tighten the linear relaxation bound with coefficient strengthening and constraint screening algorithms to improve its Big-Ms and considerably reduce its size. The proposed valid inequalities are based on the notion of k-envelopes and can be computed off-line using polynomial-time algorithms and added to the MIP program all at once. Furthermore, they are equally useful to boost the strengthening of the Big-Ms and the screening rate of superfluous constraints. We apply our procedures to a probabilistically constrained version of the DC optimal power flow problem with uncertain demand. The chance constraint requires that the probability of violating any of the power system's constraints be lower than some positive threshold. In a series of numerical experiments that involve five power systems of different size, we show the efficiency of the proposed methodology and compare it with some of the best performing convex inner approximations currently available in the literature. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This work was supported in part by the European Research Council under the EU Horizon 2020 research and innovation program [Grant 755705], in part by the Spanish Ministry of Science and Innovation [Grant AEI/10.13039/501100011033] through project PID2020-115460GB-I00, and in part by the Junta de Andalucía and the European Regional Development Fund through the research project P20_00153. Á. Porras is also financially supported by the Spanish Ministry of Science, Innovation and Universities through the University Teacher Training Program with fellowship number FPU19/03053. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.0302. [ABSTRACT FROM AUTHOR]

We describe software for stochastic programming that uses only sampled data to obtain both a consistent sample-average solution and a consistent estimate of confidence intervals for the optimality gap using bootstrap and bagging. The underlying distribution whence the samples come is not required. History: Accepted by Ted Ralphs, Area Editor for Software Tools. 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.0253) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0253). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

A key challenge in inventory management is to identify policies that optimally replenish inventory from multiple suppliers. To solve such optimization problems, inventory managers need to decide what quantities to order from each supplier given the net inventory and outstanding orders so that the expected backlogging, holding, and sourcing costs are jointly minimized. Inventory management problems have been studied extensively for more than 60 years, and yet even basic dual-sourcing problems, in which orders from an expensive supplier arrive faster than orders from a regular supplier, remain intractable in their general form. In addition, there is an emerging need to develop proactive, scalable optimization algorithms that can adjust their recommendations to dynamic demand shifts in a timely fashion. In this work, we approach dual sourcing from a neural network–based optimization lens and incorporate information on inventory dynamics and its replenishment (i.e., control) policies into the design of recurrent neural networks. We show that the proposed neural network controllers (NNCs) are able to learn near-optimal policies of commonly used instances within a few minutes of CPU time on a regular personal computer. To demonstrate the versatility of NNCs, we also show that they can control inventory dynamics with empirical, nonstationary demand distributions that are challenging to tackle effectively using alternative, state-of-the-art approaches. Our work shows that high-quality solutions of complex inventory management problems with nonstationary demand can be obtained with deep neural network optimization approaches that directly account for inventory dynamics in their optimization process. As such, our research opens up new ways of efficiently managing complex, high-dimensional inventory dynamics. History: Accepted by Ram Ramesh, Area Editor for Data Science & Machine Learning. Funding: This work was supported by Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung (NCCR Automation) [Grant P2EZP2 191888] and the Army Research Office [Grant W911NF-23-1-0129]. 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.0136) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0136). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

We consider selecting the top-m alternatives from a finite number of alternatives via Monte Carlo simulation. Under a Bayesian framework, we formulate the sampling decision as a stochastic dynamic programming problem and develop a sequential sampling policy that maximizes a value function approximation one-step look ahead. To show the asymptotic optimality of the proposed procedure, the asymptotically optimal sampling ratios that optimize the large deviations rate of the probability of false selection for selecting the top-m alternatives have been rigorously defined. The proposed sampling policy is not only proved to be consistent but also achieve the asymptotically optimal sampling ratios. Numerical experiments demonstrate superiority of the proposed allocation procedure over existing ones. History: Accepted by Bruno Tuffin, Area Editor for Simulation. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72250065, 72293582, 72022001, and 71901003], and the National Science Foundation [Grant DMS-2053489], the major project of the National Natural Science Foundation of China [Grant 72293582], and the China Scholarship Council [Grant CSC202206010152]. 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.2021.0333) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0333). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

The ℓ 0 trend filtering ( ℓ 0 -TF) is a new effective tool for nonparametric regression with the power of automatic knot detection in function values or derivatives. It overcomes the drawback of ℓ 1 -TF that is known to have bias issues. To solve the ℓ 0 -TF problem, we propose an alternating minimization induced active set (AMIAS) search method based on the necessary optimality conditions derived from an augmented Lagrangian framework. The proposed method takes full advantage of the primal and dual variables with complementary supports, and decouples the high-dimensional problem into two subsystems on the active and inactive sets, respectively. A sequential AMIAS algorithm with warm start initialization is developed for efficient determination of the cardinality parameter, along with the output of solution paths. Theoretically, the oracle estimator of ℓ 0 -TF is justified to behave like regression splines under the continuous time setting with mild conditions. Our numerical experiments include simulation studies for comparing ℓ 0 -TF to ℓ 1 -TF and free-knot splines on several synthetic examples, and a real data application of time series segmentation on Hong Kong PM2.5 indexes. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms – Continuous. Funding: This work was supported in part by Hong Kong General Research Fund [No. 17306519]. C. Wen's research is partially supported by National Science Foundation of China [12171449] and Fundamental Research Funds for the Central Universities [WK3470000027, YD2040002019]. X. Wang's research is partially supported by National Natural Science Foundation of China [Grants 72171216, 12231017, 71921001, and 71991474], and the National Key R&D Program of China [No. 2022YFA1003803]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2021.0313. 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.2021.0313) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0313). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

The security of credit card fraud detection (CCFD) models based on machine learning is important but rarely considered in the existing research. To this end, we propose a black-box attack-based security evaluation framework for CCFD models. Under this framework, the semisupervised learning technique and transfer-based black-box attack are combined to construct two versions of a semisupervised transfer black-box attack algorithm. Moreover, we introduce a new nonlinear optimization model to generate the adversarial examples against CCFD models and a security evaluation index to quantitatively evaluate the security of them. Computing experiments on two real data sets demonstrate that, facing the adversarial examples generated by the proposed attack algorithms, all six supervised models considered largely lose their ability to identify the fraudulent transactions, whereas the two unsupervised models are less affected. This indicates that the CCFD models based on supervised machine learning may possess substantial security risks. In addition, the evaluation results for the security of the models generate important managerial implications that help banks reasonably evaluate and enhance the model security. History: Accepted by Ram Ramesh, Area Editor for Data Science & Machine Learning. Funding: This work was supported in part by the National Natural Science Foundation of China [Grants 72171160 and 71988101], Key Program of National Natural Science Foundation of China and Quebec Research Foundation (NSFC-FRQ) Joint Project [Grant 7191101304], Key Program of NSFC-FRQSC Joint Project [Grant 72061127002], Excellent Youth Foundation of Sichuan Province [Grant 2020JDJQ0021], and National Leading Talent Cultivation Project of Sichuan University [Grant SKSYL2021-03]. 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.1297) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0076) at (http://dx.doi.org/10.5281/zenodo.7631457). [ABSTRACT FROM AUTHOR]

Recent studies employ collections of binary decision diagrams (BDDs) to solve combinatorial optimization problems. This paper focuses on the problem of optimally aligning two BDDs, that is, transforming them to enforce a common order of variables while keeping the total size of the diagrams as small as possible. We address this problem, which is known to be NP-hard, by introducing and studying a simplified problem instead of working with the more complex original diagrams. We discuss some basic properties of the simplified problem, design a corresponding heuristic for the original problem, and show empirically that this approach yields good quality alignments while significantly reducing the complexity of intermediate diagram transformations. We highlight the practicality of this approach in the context of a variation of the uncapacitated facility location problem. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete. Funding: This work was supported by the Office of Naval Research [Grant N00014-17-1-2421]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/ijoc.2023.1293. [ABSTRACT FROM AUTHOR]

We extend the notion of globalized robustness to consider distributional information beyond the support of the ambiguous probability distribution. We propose the globalized distributionally robust counterpart that disallows any (respectively, allows limited) constraint violation for distributions residing (respectively, not residing) in the ambiguity set. By varying its inputs, our proposal recovers several existing perceptions of parameter uncertainty. Focusing on the type 1 Wasserstein distance, we show that the globalized distributionally robust counterpart has an insightful interpretation in terms of shadow price of globalized robustness, and it can be seamlessly integrated with many popular optimization models under uncertainty without incurring any extra computational cost. Such computational attractiveness also holds for other ambiguity sets, including the ones based on probability metric, optimal transport, ϕ-divergences, or moment conditions, as well as the event-wise ambiguity set. Numerical studies on an adaptive network lot-sizing problem demonstrate the modeling flexibility of our proposal and its emphases on globalized robustness to constraint violation. History: Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous. Funding: Z. Chen was supported by [General Research Fund Grant 9043424, NSFC/RGC Joint Research Scheme N_CityU105/21] from the Hong Kong Research Grants Council. S. Wang was supported by the National Natural Science Foundation of China [Grants 71922020, 72171221, and 71988101, entitled "Econometric Modeling and Economic Policy Studies"] and the Fundamental Research Funds for the Central Universities [Grant UCAS-E2ET0808X2]. 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.0274) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0274). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

This paper introduces the hub location problem under interhub link failures, a hub location problem in which activated interhub links may fail with a given probability. Two different optimization models are studied, which construct hub backbone networks protected under interhub link disruptions by imposing that, for each commodity, an additional routing path exists besides its original routing path. Both models consider the minimization of the fixed costs of the activated hubs and interhub links plus the expected value of the routing costs of the original and alternative paths. The first model builds explicitly the alternative routing paths, whereas the second model guarantees that, for each commodity, at least one alternative path exists using a large set of connectivity constraints although the alternative paths are not built explicitly. The results of extensive computational testing allow us to analyze the performance of the two proposed models and to evaluate the extra cost required to design a robust backbone network under interhub link failures. The obtained results support the validity of the proposal. History: Accepted by David Alderson, Area Editor for Network Optimization: Algorithms & Application. Funding: The authors of this research acknowledge financial support by the Spanish Ministerio de Ciencia y Tecnología, Agencia Estatal de Investigación and Fondos Europeos de Desarrollo Regional (FEDER) via projects PID2020-114594GB-C21 and MTM2019-105824GB-I00. The authors also acknowledge partial support from projects FEDER-US-1256951, Junta de Andalucía P18-FR-422, P18-FR-2369, B-FQM-322-UGR20 (COXMOS), and NetmeetData: Ayudas Fundación BBVA a equipos de investigación científica 2019. The first author was partially supported by the IMAG-Maria de Maeztu grant [CEX2020-001105-M/AEI/10.13039/501100011033] and UE-NextGenerationEU (ayudas de movilidad para la recualificación del profesorado universitario). Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2023.1296. [ABSTRACT FROM AUTHOR]

A multidepot capacitated vehicle routing problem aims to serve customers' demands using a fleet of capacitated vehicles located in multiple depots, such that the total travel cost of the vehicles is minimized. We study a variant of this problem, the k-depot split delivery vehicle routing problem (or k-DSDVRP in short), for the situation where each customer's demand can be served by more than one vehicle, and the total number of depots, denoted by k ≥ 2 , is a fixed constant. This is a challenging problem with broad applications in the logistics industry, for which no constant ratio approximation algorithm is known. We develop a new approximation algorithm for the k-DSDVRP, ensuring an approximation ratio of (6 − 4 / k) and a polynomial running time for any fixed constant k ≥ 2. To achieve this, we propose a novel solution framework based on a new relaxation of the problem, a cycle splitting procedure, and a vehicle assignment procedure. To further enhance its efficiency for practical usage, we adapt the newly developed approximation algorithm to a heuristic, which runs in polynomial time even when k is arbitrarily large. Experimental results show that this heuristic outperforms a commercial optimization solver and a standard vehicle routing heuristic. Moreover, our newly proposed solution framework can be applied to developing new constant ratio approximation algorithms for several other variants of the k-DSDVRP with k ≥ 2 being a fixed constant. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported in part by the National Natural Science Foundation of China [Grants 71971177, 71725001, U1811462], Research Grants Council of Hong Kong SAR, China [Grant 15221619], and Guangdong Basic and Applied Basic Research Foundation [Grant 2023A1515030260]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2021.0193. 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.2021.0193) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0193). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

We propose a new nonconvex regularization scheme to improve the performance of the stochastic dual dynamic programming (SDDP) algorithm for solving large-scale multistage stochastic programs. Specifically, we use a class of nonconvex regularization functions, namely folded concave penalty functions, to improve solution quality and the convergence rate of the SDDP procedure. We develop a strategy based on mixed-integer programming to guarantee global optimality of the nonconvex regularization problem. Moreover, we establish provable convergence guarantees for our customized SDDP algorithm. The benefits of our regularization scheme are demonstrated by solving large-scale instances of two multistage stochastic optimization problems. History: Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. 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.2021.0255) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0255). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

We study adjustable distributionally robust optimization problems, where their ambiguity sets can potentially encompass an infinite number of expectation constraints. Although such ambiguity sets have great modeling flexibility in characterizing uncertain probability distributions, the corresponding adjustable problems remain computationally intractable and challenging. To overcome this issue, we propose a greedy improvement procedure that consists of solving, via the (extended) linear decision rule approximation, a sequence of tractable subproblems—each of which considers a relaxed and finitely constrained ambiguity set that can be iteratively tightened to the infinitely constrained one. Through three numerical studies of adjustable distributionally robust optimization models, we show that our approach can yield improved solutions in a systematic way for both two-stage and multistage problems. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: Financial support by the Early Career Scheme from the Hong Kong Research Grants Council [Project No. CityU 21502820], the CityU Start-Up Grant [Project No. 9610481], the CityU Strategic Research Grant [Project No. 7005688], the National Natural Science Foundation of China [Project No. 72032005], and Chow Sang Sang Group Research Fund sponsored by Chow Sang Sang Holdings International Limited [Project No. 9229076] is gratefully acknowledged. 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.2021.0181), as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0181). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]