skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: On the Value of Risk-Averse Multistage Stochastic Programming in Capacity Planning
We consider a risk-averse stochastic capacity planning problem under uncertain demand in each period. Using a scenario tree representation of the uncertainty, we formulate a multistage stochastic integer program to adjust the capacity expansion plan dynamically as more information on the uncertainty is revealed. Specifically, in each stage, a decision maker optimizes capacity acquisition and resource allocation to minimize certain risk measures of maintenance and operational cost. We compare it with a two-stage approach that determines the capacity acquisition for all the periods up front. Using expected conditional risk measures, we derive a tight lower bound and an upper bound for the gaps between the optimal objective values of risk-averse multistage models and their two-stage counterparts. Based on these derived bounds, we present general guidelines on when to solve risk-averse two-stage or multistage models. Furthermore, we propose approximation algorithms to solve the two models more efficiently, which are asymptotically optimal under an expanding market assumption. We conduct numerical studies using randomly generated and real-world instances with diverse sizes, to demonstrate the tightness of the analytical bounds and efficacy of the approximation algorithms. We find that the gaps between risk-averse multistage and two-stage models increase as the variability of the uncertain parameters increases and decrease as the decision maker becomes more risk averse. Moreover, a stagewise-dependent scenario tree attains much higher gaps than a stagewise-independent counterpart, whereas the latter produces tighter analytical bounds. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work of Dr. X. Yu was partially supported by the U.S. National Science Foundation Division of Information and Intelligent Systems [Grant 2331782]. 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.0396 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0396 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .  more » « less
Award ID(s):
2041745
PAR ID:
10579407
Author(s) / Creator(s):
;
Publisher / Repository:
informs
Date Published:
Journal Name:
INFORMS Journal on Computing
ISSN:
1091-9856
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, INFORMS Journal on Computing)
    We consider linear combinatorial optimization problems under uncertain disruptions that increase the cost coefficients of the objective function. A decision maker, or planner, can invest resources to probe the components (i.e., the coefficients) in order to learn their disruption status. In the proposed probing optimization problem, the planner, knowing just the disruptions’ probabilities, selects which components to probe subject to a probing budget in a first decision stage. Then, the uncertainty realizes, and the planner observes the disruption status of the probed components, after which the planner solves the combinatorial problem in the second stage. In contrast to standard two-stage stochastic optimization, the planner does not have access to the full uncertainty realization in the second stage. Consequently, the planner cannot directly optimize the second-stage objective function, which is given by the actual cost after disruptions, and the decisions have to be made based on an estimate of the cost. By assuming that the estimate is given by the conditional expected cost given the information revealed by probing, we reformulate the probing optimization problem as a bilevel problem with multiple followers and propose an exact algorithm based on a value function reformulation and three heuristic algorithms. We derive theoretical results that bound the value of information and the price of not having full information and a bound on the required probing budget that attains the same performance as full information. Our extensive computational experiments suggest that probing a fraction of the components is sufficient to yield large improvements in the optimal value, that our exact algorithm is competitive for small- to medium-scale instances, and that the proposed heuristics find high-quality solutions in large-scale instances. 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 [Grant FA9550-22-1-0236] and the Division of Civil, Mechanical and Manufacturing Innovation [Grant CMMI 2145553]. 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.2024.0629 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0629 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ . 
    more » « less
  2. ; (, INFORMS Journal on Computing)
    Sparse principal component analysis (SPCA) is designed to enhance the interpretability of traditional principal component analysis by optimally selecting a subset of features that comprise the first principal component. Given the NP-hard nature of SPCA, most current approaches resort to approximate solutions, typically achieved through tractable semidefinite programs or heuristic methods. To solve SPCA to optimality, we propose two exact mixed-integer semidefinite programs (MISDPs) and an arbitrarily equivalent mixed-integer linear program. The MISDPs allow us to design an effective branch-and-cut algorithm with closed-form cuts that do not need to solve dual problems. For the proposed mixed-integer formulations, we further derive the theoretical optimality gaps of their continuous relaxations. Besides, we apply the greedy and local search algorithms to solving SPCA and derive their first-known approximation ratios. Our numerical experiments reveal that the exact methods we developed can efficiently find optimal solutions for data sets containing hundreds of features. Furthermore, our approximation algorithms demonstrate both scalability and near-optimal performance when benchmarked on larger data sets, specifically those with thousands of features. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This research was supported in part by the Division of Civil, Mechanical and Manufacturing Innovation [Grant 224614], the Division of Computing and Communication Foundations [Grant 2246417], and the Office of Naval Research [Grant N00014-24-1-2066]. 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.0372 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0372 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ . 
    more » « less
  3. ; (, INFORMS Journal on Computing)
    We present a novel approach aimed at enhancing the efficacy of solving both regular and distributionally robust chance constrained programs using an empirical reference distribution. In general, these programs can be reformulated as mixed-integer programs (MIPs) by introducing binary variables for each scenario, indicating whether a scenario should be satisfied. Whereas existing methods have focused predominantly on either inner or outer approximations, this paper bridges this gap by studying a scheme that effectively combines these approximations via variable fixing. By checking the restricted outer approximations and comparing them with the inner approximations, we derive optimality cuts that can notably reduce the number of binary variables by effectively setting them to either one or zero. We conduct a theoretical analysis of variable fixing techniques, deriving an asymptotic closed-form expression. This expression quantifies the proportion of binary variables that should be optimally fixed to zero. Our empirical results showcase the advantages of our approach in terms of both computational efficiency and solution quality. Notably, we solve all the tested instances from literature to optimality, signifying the robustness and effectiveness of our proposed approach. History: Accepted by Andrea Lodi/Design & Analysis of Algorithms — Discrete. Funding: This work was supported by Office of Naval Research [N00014-24-1-2066]; Division of Civil, Mechanical and Manufacturing Innovation [2246414]. 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.0299 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0299 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ . 
    more » « less
  4. ; (, INFORMS Journal on Computing)
    In the nested simulation literature, a common assumption is that the experimenter can choose the number of outer scenarios to sample. This paper considers the case when the experimenter is given a fixed set of outer scenarios from an external entity. We propose a nested simulation experiment design that pools inner replications from one scenario to estimate another scenario’s conditional mean via the likelihood ratio method. Given the outer scenarios, we decide how many inner replications to run at each outer scenario as well as how to pool the inner replications by solving a bilevel optimization problem that minimizes the total simulation effort. We provide asymptotic analyses on the convergence rates of the performance measure estimators computed from the optimized experiment design. Under some assumptions, the optimized design achieves [Formula: see text] mean squared error of the estimators given simulation budget [Formula: see text]. Numerical experiments demonstrate that our design outperforms a state-of-the-art design that pools replications via regression. History: Accepted by Bruno Tuffin, Area Editor for Simulation. Funding: This work was supported by the National Science Foundation [Grant CMMI-2045400] and the Natural Sciences and Engineering Research Council of Canada [Grant RGPIN-2018-03755]. 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.0392 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0392 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ . 
    more » « less
  5. ; ; ; (, INFORMS Journal on Computing)
    Chemotherapy drug administration is a complex problem that often requires expensive clinical trials to evaluate potential regimens; one way to alleviate this burden and better inform future trials is to build reliable models for drug administration. This paper presents a mixed-integer program for combination chemotherapy (utilization of multiple drugs) optimization that incorporates various important operational constraints and, besides dose and concentration limits, controls treatment toxicity based on its effect on the count of white blood cells. To address the uncertainty of tumor heterogeneity, we also propose chance constraints that guarantee reaching an operable tumor size with a high probability in a neoadjuvant setting. We present analytical results pertinent to the accuracy of the model in representing biological processes of chemotherapy and establish its potential for clinical applications through a numerical study of breast cancer. History: Accepted by Paul Brooks, Area Editor for Applications in Biology, Medicine, & Healthcare. Funding: This work was supported by the National Science Foundation [Grants CMMI-1933369 and CMMI-1933373]. 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.0207 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0207 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ . 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email