An official website of the United States government
As we strive to establish a long-term presence in space, it is crucial to plan large-scale space missions and campaigns with future uncertainties in mind. However, integrated space mission planning, which simultaneously considers mission planning and spacecraft design, faces significant challenges when dealing with uncertainties; this problem is formulated as a stochastic mixed integer nonlinear program (MINLP), and solving it using the conventional method would be computationally prohibitive for realistic applications. Extending a deterministic decomposition method from our previous work, we propose a novel and computationally efficient approach for integrated space mission planning under uncertainty. The proposed method effectively combines the Alternating Direction Method of Multipliers (ADMM)-based decomposition framework from our previous work, robust optimization, and two-stage stochastic programming (TSSP).This hybrid approach first solves the integrated problem deterministically, assuming the worst scenario, to precompute the robust spacecraft design. Subsequently, the two-stage stochastic program is solved for mission planning, effectively transforming the problem into a more manageable mixed-integer linear program (MILP). This approach significantly reduces computational costs compared to the exact method, but may potentially miss solutions that the exact method might find. We examine this balance through a case study of staged infrastructure deployment on the lunar surface under future demand uncertainty. When comparing the proposed method with a fully coupled benchmark, the results indicate that our approach can achieve nearly identical objective values (no worse than 1% in solved problems) while drastically reducing computational costs.
more »
« less
On Robust Fractional 0-1 Programming
We study single- and multiple-ratio robust fractional 0-1 programming problems (RFPs). In particular, this work considers RFPs under a wide range of disjoint and joint uncertainty sets, where the former implies separate uncertainty sets for each numerator and denominator and the latter accounts for different forms of interrelatedness between them. We first demonstrate that unlike the deterministic case, a single-ratio RFP is nondeterministic polynomial-time hard under general polyhedral uncertainty sets. However, if the uncertainty sets are imbued with a certain structure, variants of the well-known budgeted uncertainty, the disjoint and joint single-ratio RFPs are polynomially solvable when the deterministic counterpart is. We also propose mixed-integer linear programming (MILP) formulations for multiple-ratio RFPs. We conduct extensive computational experiments using test instances based on real and synthetic data sets to evaluate the performance of our MILP reformulations as well as to compare the disjoint and joint uncertainty sets. Finally, we demonstrate the value of the robust approach by examining the robust solution in a deterministic setting and vice versa.
more »
« less
- Award ID(s):
- 1818700
- PAR ID:
- 10188592
- Date Published:
- Journal Name:
- INFORMS Journal on Optimization
- Volume:
- 2
- Issue:
- 2
- ISSN:
- 2575-1484
- Page Range / eLocation ID:
- 96 to 133
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Problem definition: Infectious disease screening can be expensive and capacity constrained. We develop cost- and capacity-efficient testing designs for multidisease screening, considering (1) multiplexing (disease bundling), where one assay detects multiple diseases using the same specimen (e.g., nasal swabs, blood), and (2) pooling (specimen bundling), where one assay is used on specimens from multiple subjects bundled in a testing pool. A testing design specifies an assay portfolio (mix of single-disease/multiplex assays) and a testing method (pooling/individual testing per assay). Methodology/results: We develop novel models for the nonlinear, combinatorial multidisease testing design problem: a deterministic model and a distribution-free, robust variation, which both generate Pareto frontiers for cost- and capacity-efficient designs. We characterize structural properties of optimal designs, formulate the deterministic counterpart of the robust model, and conduct a case study of respiratory diseases (including coronavirus disease 2019) with overlapping clinical presentation. Managerial implications: Key drivers of optimal designs include the assay cost function, the tester’s preference toward cost versus capacity efficiency, prevalence/coinfection rates, and for the robust model, prevalence uncertainty. When an optimal design uses multiple assays, it does so in conjunction with pooling, and it uses individual testing for at most one assay. Although prevalence uncertainty can be a design hurdle, especially for emerging or seasonal diseases, the integration of multiplexing and pooling, and the ordered partition property of optimal designs (under certain coinfection structures) serve to make the design more structurally robust to uncertainty. The robust model further increases robustness, and it is also practical as it needs only an uncertainty set around each disease prevalence. Our Pareto designs demonstrate the cost versus capacity trade-off and show that multiplexing-only or pooling-only designs need not be on the Pareto frontier. Our case study illustrates the benefits of optimally integrated designs over current practices and indicates a low price of robustness. Funding: This work was supported by the National Science Foundation [Grant 1761842]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2022.0296 .more » « less
-
This paper studies the distributionally robust fair transit resource allocation model (DrFRAM) under the Wasserstein ambiguity set to optimize the public transit resource allocation during a pandemic. We show that the proposed DrFRAM is highly nonconvex and nonlinear, and it is NP-hard in general. Fortunately, we show that DrFRAM can be reformulated as a mixed integer linear programming (MILP) by leveraging the equivalent representation of distributionally robust optimization and monotonicity properties, binarizing integer variables, and linearizing nonconvex terms. To improve the proposed MILP formulation, we derive stronger ones and develop valid inequalities by exploiting the model structures. Additionally, we develop scenario decomposition methods using different MILP formulations to solve the scenario subproblems and introduce a simple yet effective no one left-based approximation algorithm with a provable approximation guarantee to solve the model to near optimality. Finally, we numerically demonstrate the effectiveness of the proposed approaches and apply them to real-world data provided by the Blacksburg Transit. History: This paper has been accepted for the Transportation Science Special Issue on Emerging Topics in Transportation Science and Logistics. Funding: This work was supported by the Division of Computing and Communication Foundations [Grant 2153607] and the Division of Civil, Mechanical and Manufacturing Innovation [Grant 2046426]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.1159 .more » « less
-
The Robust Markov Decision Process (RMDP) framework focuses on designing control policies that are robust against the parameter uncertainties due to the mis- matches between the simulator model and real-world settings. An RMDP problem is typically formulated as a max-min problem, where the objective is to find the policy that maximizes the value function for the worst possible model that lies in an uncertainty set around a nominal model. The standard robust dynamic programming approach requires the knowledge of the nominal model for computing the optimal robust policy. In this work, we propose a model-based reinforcement learning (RL) algorithm for learning an ε-optimal robust policy when the nominal model is unknown. We consider three different forms of uncertainty sets, characterized by the total variation distance, chi-square divergence, and KL divergence. For each of these uncertainty sets, we give a precise characterization of the sample complexity of our proposed algorithm. In addition to the sample complexity results, we also present a formal analytical argument on the benefit of using robust policies. Finally, we demonstrate the performance of our algorithm on two benchmark problems.more » « less
-
null (Ed.)We investigate a data-driven approach to constructing uncertainty sets for robust optimization problems, where the uncertain problem parameters are modeled as random variables whose joint probability distribution is not known. Relying only on independent samples drawn from this distribution, we provide a nonparametric method to estimate uncertainty sets whose probability mass is guaranteed to approximate a given target mass within a given tolerance with high confidence. The nonparametric estimators that we consider are also shown to obey distribution-free finite-sample performance bounds that imply their convergence in probability to the given target mass. In addition to being efficient to compute, the proposed estimators result in uncertainty sets that yield computationally tractable robust optimization problems for a large family of constraint functions.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1287/ijoo.2019.0025
