We present a non-anticipative learning- and scenario-based prediction-optimization (ScenPredOpt) framework that combines deep learning, heuristics, and mathematical solvers for solving combinatorial problems under uncertainty. Specifically, we transform neural machine translation frameworks to predict the optimal solutions of scenario-based multi-stage stochastic programs. The learning models are trained efficiently using the input and solution data of the multi-stage single-scenario deterministic problems. Then our ScenPredOpt framework creates a mapping from the inputs used in training into an output of predictions that are close to optimal solutions. We present a Non-anticipative Encoder-Decoder with Attention (NEDA) approach, which ensures the non-anticipativity property of multi-stage stochastic programs and, thus, time consistency by calibrating the learned information based on the problem’s scenario tree and adjusting the hidden states of the neural network. In our ScenPredOpt framework, the percent predicted variables used for the solution are iteratively reduced through a relaxation of the problem to eliminate infeasibility. Then, a linear relaxation-based heuristic is performed to further reduce the solution time. Finally, a mathematical solver is used to generate the complete solution. We present the results on two NP-Hard sequential optimization problems under uncertainty: stochastic multi-item capacitated lot-sizing and stochastic multistage multidimensional knapsack. The results show that the solution time can be reduced by a factor of 599 with an optimality gap of only 0.08%. We compare the results of the ScenPredOpt framework with cutting-edge exact and heuristic solution algorithms for the problems studied and find that our framework is more effective. Additionally, the computational results demonstrate that ScenPredOpt can solve instances with a larger number of items and scenarios than the trained ones. Our non-anticipative learning-optimization approach can be beneficial for stochastic programming problems involving binary variables that are solved repeatedly with various types of dimensions and similar decisions at each period.
more » « less- PAR ID:
- 10520679
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Annals of Operations Research
- ISSN:
- 0254-5330
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
A stochastic optimization model for patient evacuation from health care facilities during hurricanesWe propose a rigorous modeling and methodological effort that integrates statistical implementation of hydrology models in predicting inland and coastal flood scenarios due to hurricanes and a scenario-based stochastic integer programming model which suggests resource and staging area decisions in the first stage and the evacuation decisions in the second stage. This novel study combines physics-based flood prediction models and stochastic optimization for large- scale multi-facility coordination of hospital and nursing home evacuations before impending hurricanes. The optimization model considers scenario-dependent evacuation demand, transport vehicles with varying capacities, and both critical and non-critical patients. Utilizing Hurricane Harvey of 2017 as a case study and actual healthcare facility locations in southeast Texas, we explore various evacuation policies, demonstrating the impact of routing strategies, staging area decisions, flood thresholds, and receiving facility capacities on evacuation outcomes. One of the findings is that choosing staging area(s) and deploying evacuation vehicles optimally considering the uncertainty of the hurricane’s path at the time of decision making could have significant effect on the total cost of the operation and evacuation time experienced by the evacuees. We also show the non-negligible value of the scenario-based staging and routing solution conservatively calculated in relation to a single scenario solution using the concept of value of stochastic solution.more » « less
-
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 ).more » « less
-
null (Ed.)Bayesian optimization is a sequential decision making framework for optimizing expensive-to-evaluate black-box functions. Computing a full lookahead policy amounts to solving a highly intractable stochastic dynamic program. Myopic approaches, such as expected improvement, are often adopted in practice, but they ignore the long-term impact of the immediate decision. Existing nonmyopic approaches are mostly heuristic and/or computationally expensive. In this paper, we provide the first efficient implementation of general multi-step lookahead Bayesian optimization, formulated as a sequence of nested optimization problems within a multi-step scenario tree. Instead of solving these problems in a nested way, we equivalently optimize all decision variables in the full tree jointly, in a "one-shot" fashion. Combining this with an efficient method for implementing multi-step Gaussian process "fantasization," we demonstrate that multi-step expected improvement is computationally tractable and exhibits performance superior to existing methods on a wide range of benchmarks.more » « less
-
Adjustable robust optimization (ARO) involves recourse decisions (i.e. reactive actions after the realization of the uncertainty, ‘wait-and-see’) as functions of the uncertainty, typically posed in a two-stage stochastic setting. Solving the general ARO problems is challenging, therefore ways to reduce the computational effort have been proposed, with the most popular being the affine decision rules, where ‘wait-and-see’ decisions are approximated as affine adjustments of the uncertainty. In this work we propose a novel method for the derivation of generalized affine decision rules for linear mixed-integer ARO problems through multi-parametric programming, that lead to the exact and global solution of the ARO problem. The problem is treated as a multi-level programming problem and it is then solved using a novel algorithm for the exact and global solution of multi-level mixed-integer linear programming problems. The main idea behind the proposed approach is to solve the lower optimization level of the ARO problem parametrically, by considering ‘here-and-now’ variables and uncertainties as parameters. This will result in a set of affine decision rules for the ‘wait-and-see’ variables as a function of ‘here-and-now’ variables and uncertainties for their entire feasible space. A set of illustrative numerical examples are provided to demonstrate the potential of the proposed novel approach.more » « less
-
Abstract This article proposes a novel distributionally robust optimization (DRO)‐based soft‐constrained model predictive control (MPC) framework to explicitly hedge against unknown external input terms in a linear state‐space system. Without a priori knowledge of the exact uncertainty distribution, this framework works with a lifted ambiguity set constructed using machine learning to incorporate the first‐order moment information. By adopting a linear performance measure and considering input and state constraints robustly with respect to a lifted support set, the DRO‐based MPC is reformulated as a robust optimization problem. The constraints are softened to ensure recursive feasibility. Theoretical results on optimality, feasibility, and stability are further discussed. Performance and computational efficiency of the proposed method are illustrated through motion control and building energy control systems, showing 18.3% less cost and 78.8% less constraint violations, respectively, while requiring one third of the CPU time compared to multi‐stage scenario based stochastic MPC.