An official website of the United States government
In this paper, we consider the problem of dynamic programming when supremum terms appear in the objective function. Such terms can represent overhead costs associated with the underlying state variables. Specifically, this form of optimization problem can be used to represent optimal scheduling of batteries such as the Tesla Powerwall for electrical consumers subject to demand charges - a charge based on the maximum rate of electricity consumption. These demand charges reflect the cost to the utility of building and maintaining generating capacity. Unfortunately, we show that dynamic programming problems with supremum terms do not satisfy the principle of optimality. However, we also show that the supremum is a special case of the class of forward separable objective functions. To solve the dynamic programming problem, we propose a general class of optimization problems with forward separable objectives. We then show that for any problem in this class, there exists an augmented-state dynamic programming problem which satisfies the principle of optimality and the solutions to which yield solutions to the original forward separable problem. We further generalize this approach to stochastic dynamic programming problems and apply the results to the problem of optimal battery scheduling with demand charges using a data-based stochastic model for electricity usage and solar generation by the consumer.
more »
« less
This content will become publicly available on January 2, 2027
Multi-Objective Optimization of Space Exploration Campaign Schedules with Stochastic Launch Delay
Complex, multimission space exploration campaigns are particularly vulnerable to payload development and launch delays due to program-level schedule constraints and interactions between the payloads. While deterministic space logistics problems seek strongly performing (e.g., minimized cost) solutions, stochastic models must balance performance with robustness. The introduction of stochastic delays to the otherwise deterministic problem produces large and computationally intractable optimization problems. This paper presents and compares two multi-objective (minimized cost vs robustness) formulations for the stochastic campaign scheduling problem. First, a multi-objective mixed-integer quadratically constrained program (MOMIQCP) formulation is presented. Secondly, due to the computational intractability of the MOMIQCP for large problems, a method for constructing restricted, deterministic scheduling subproblems is defined. These subproblems are input to a noisy multi-objective evolutionary algorithm (NMOEA), which is used for the purpose of stochastically applying delays to the deterministic subproblem and building approximations of the objectives of the stochastic problems. Both methods are demonstrated through case studies, and the results demonstrate that the NMOEA can successfully find strongly performing solutions to larger stochastic scheduling problems.
more »
« less
- Award ID(s):
- 1942559
- PAR ID:
- 10657548
- Publisher / Repository:
- American Institute of Aeronautics and Astronautics
- Date Published:
- Journal Name:
- Journal of Spacecraft and Rockets
- ISSN:
- 0022-4650
- Page Range / eLocation ID:
- 1 to 19
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
This work proposes a new algorithm – the Single-timescale Double-momentum Stochastic Approximation (SUSTAIN) –for tackling stochastic unconstrained bilevel optimization problems. We focus on bilevel problems where the lower level subproblem is strongly-convex and the upper level objective function is smooth. Unlike prior works which rely on two-timescale or double loop techniques, we design a stochastic momentum-assisted gradient estimator for both the upper and lower level updates. The latter allows us to control the error in the stochastic gradient updates due to inaccurate solution to both subproblems. If the upper objective function is smooth but possibly non-convex, we show that SUSTAIN requires $${O}(\epsilon^{-3/2})$$ iterations (each using $O(1)$ samples) to find an $$\epsilon$$-stationary solution. The $$\epsilon$$-stationary solution is defined as the point whose squared norm of the gradient of the outer function is less than or equal to $$\epsilon$$. The total number of stochastic gradient samples required for the upper and lower level objective functions match the best-known complexity for single-level stochastic gradient algorithms. We also analyze the case when the upper level objective function is strongly-convex.more » « less
-
A stochastic algorithm is proposed, analyzed, and tested experimentally for solving continuous optimization problems with nonlinear equality constraints. It is assumed that constraint function and derivative values can be computed but that only stochastic approximations are available for the objective function and its derivatives. The algorithm is of the sequential quadratic optimization variety. Distinguishing features of the algorithm are that it only employs stochastic objective gradient estimates that satisfy a relatively weak set of assumptions (while using neither objective function values nor estimates of them) and that it allows inexact subproblem solutions to be employed, the latter of which is particularly useful in large-scale settings when the matrices defining the subproblems are too large to form and/or factorize. Conditions are imposed on the inexact subproblem solutions that account for the fact that only stochastic objective gradient estimates are employed. Convergence results are established for the method. Numerical experiments show that the proposed method vastly outperforms a stochastic subgradient method and can outperform an alternative sequential quadratic programming algorithm that employs highly accurate subproblem solutions in every iteration. Funding: This material is based upon work supported by the National Science Foundation [Awards CCF-1740796 and CCF-2139735] and the Office of Naval Research [Award N00014-21-1-2532].more » « less
-
Autonomous Mobile Robots (AMRs) rely on rechargeable batteries to execute several objective tasks during navigation. Previous research has focused on minimizing task downtime by coordinating task allocation and/or charge scheduling across multiple AMRs. However, they do not jointly ensure low task downtime and high-quality battery life.In this paper, we present TCM, a Task allocation and Charging Manager for AMR fleets. TCM allocates objective tasks to AMRs and schedules their charging times at the available charging stations for minimized task downtime and maximized AMR batteries’ quality of life. We formulate the TCM problem as an MINLP problem and propose a polynomial-time multi-period TCM greedy algorithm that periodically adapts its decisions for high robustness to energy modeling errors. We experimentally show that, compared to the MINLP implementation in Gurobi solver, the designed algorithm provides solutions with a performance ratio of 1.15 at a fraction of the execution time. Furthermore, compared to representative baselines that only focus on task downtime, TCM achieves similar task allocation results while providing much higher battery quality of life.more » « less
