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
Adjustable robust optimization through multi-parametric programming
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
- PAR ID:
- 10096666
- Date Published:
- Journal Name:
- Optimization Letters
- ISSN:
- 1862-4472
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study robust convex quadratic programs where the uncertain problem parameters can contain both continuous and integer components. Under the natural boundedness assumption on the uncertainty set, we show that the generic problems are amenable to exact copositive programming reformulations of polynomial size. These convex optimization problems are NP-hard but admit a conservative semidefinite programming (SDP) approximation that can be solved efficiently. We prove that the popular approximate S-lemma method—which is valid only in the case of continuous uncertainty—is weaker than our approximation. We also show that all results can be extended to the two-stage robust quadratic optimization setting if the problem has complete recourse. We assess the effectiveness of our proposed SDP reformulations and demonstrate their superiority over the state-of-the-art solution schemes on instances of least squares, project management, and multi-item newsvendor problems.more » « less
-
We study two-stage stochastic optimization problems with random recourse, where the coefficients of the adaptive decisions involve uncertain parameters. To deal with the infinite-dimensional recourse decisions, we propose a scalable approximation scheme via piecewise linear and piecewise quadratic decision rules. We develop a data-driven distributionally robust framework with two layers of robustness to address distributional uncertainty. We also establish out-of-sample performance guarantees for the proposed scheme. Applying known ideas, the resulting optimization problem can be reformulated as an exact copositive program that admits semidefinite programming approximations. We design an iterative decomposition algorithm, which converges under some regularity conditions, to reduce the runtime needed to solve this program. Through numerical examples for various known operations management applications, we demonstrate that our method produces significantly better solutions than the traditional sample-average approximation scheme especially when the data are limited. For the problem instances for which only the recourse cost coefficients are random, our method exhibits slightly inferior out-of-sample performance but shorter runtimes compared with a competing approach.more » « less
-
null (Ed.)This paper presents a multi-objective (MO) optimization for economic/emission dispatch (EED) problem incorporating hydrothermal plants, wind power generation, energy storage systems (ESSs) and responsive loads. The uncertain behavior of wind turbines and electric loads is modeled by scenarios. Stochastic programming is proposed to achieve the expected cost and emission production. Moreover, the carbon capture systems are considered to lower the level of carbon emission produced by conventional thermal units. The proposed optimization problem is tested on the IEEE 24-bus case study using DC power flow calculation. The optimal Pareto frontier is obtained, and a fuzzy decision-making tool determined the best solution among obtained Pareto points. The problem is modeled as mixed-integer non-linear programming in the General Algebraic Modelling System (GAMS) and solved using DICOPT solver.more » « less
-
Space mission planning and spacecraft design are tightly coupled and need to be considered together for optimal performance; however, this integrated optimization problem results in a large-scale Mixed-Integer Nonlinear Programming (MINLP) problem, which is challenging to solve. In response to this challenge, this paper proposes a new solution approach to this MINLP problem by iterative solving a set of coupled subproblems via the augmented Lagrangian coordination approach following the philosophy of Multi-disciplinary Design Optimization (MDO). The proposed approach leverages the unique structure of the problem that enables its decomposition into a set of coupled subproblems of different types: a Mixed-Integer Quadratic Programming (MIQP) subproblem for mission planning and one or more Nonlinear Programming (NLP) subproblem(s) for spacecraft design. Since specialized MIQP or NLP solvers can be applied to each subproblem, the proposed approach can efficiently solve the otherwise intractable integrated MINLP problem. An automatic and effective method to find an initial solution for this iterative approach is also proposed so that the optimization can be performed without the need for a user-defined initial guess. In the demonstration case study, a human lunar exploration mission sequence is optimized with a subsystem-level parametric spacecraft design model. Compared to the state-of-the-art method, the proposed formulation can obtain a better solution with a shorter computational time even without parallelization. For larger problems, the proposed solution approach can also be easily parallelizable and thus is expected to be further advantageous and scalable.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/s11590-019-01438-5
