(419b) Efficient Solution of Mixed-Integer Multistage Stochastic Programs for the Optimal Design of Smart Manufacturing Systems Using “Smooth-in-Expectation” Decision Rules
However, the design and optimization of flexible systems poses tremendous challenges because it necessarily integrates design, scheduling, and control problems that are conventionally solved independently. Specifically, insofar as the quality of a design is determined by its ability to adapt, long-term design decisions are strongly dependent on operational details that occur on much shorter time-scales. Thus, design decisions must be optimized simultaneously with a potentially huge number of decisions representing short-term scheduling and control actions over long time horizons, and in multiple future scenarios. In general, this leads to large-scale nonlinear multistage stochastic programs with mixed-integer recourse decisions.
Although the effort to optimally integrate design and operations has a long history, the solution of such multistage problems remains a serious outstanding challenge. Broadly, tractable formulations still require significant limitations on the modeling of either short time-scale effects (e.g., coarse time discretization, static or linearized models), uncertainty (e.g., few scenarios, two-stage rather than multi-stage decisions), or permissible operational strategies (e.g., heuristic scheduling policies, fixed control laws). Critically, these approximations degrade optimization models in exactly the aspects that are most essential for assessing the efficiency and reliability of a smart manufacturing system, and for properly weighing these factors against its cost. Thus, there is a need for new theory and algorithms that can effectively solve multistage stochastic programs with mixed-integer recourse.
In this contribution, we will present recent progress towards a new approach for efficiently solving such programs using âsmooth-in-expectationâ decision rules. In this approach, recourse decisions are no longer formulated as explicit optimization variables, but are rather determined (suboptimally) through decisions rules (i.e., functions of the random variables and system state). Although these rules have fixed functional forms, they are parameterized by additional âfirst-stageâ decisions in order to impart some flexibility. This type of approximation was originally developed for linear stochastic programs with continuous recourse variables, and is now commonly used to solve very large-scale linear problems with many stages, which are intractable by other means. However, in the case of integer recourse variables, which are critical for smart manufacturing systems (e.g., scheduling and unit commitment decisions), the use of decision rules has been much less successful. Specifically, this is because decision rules that make integer decisions are inherently discontinuous. Thus, replacing integer recourse decisions with decision rules results in a highly discontinuous optimization model, which hardly simplifies matters.
To overcome this limitation, a key insight in our approach is that the expected value of the objective function can be a smooth function of the decision variables despite the presence of discontinuous decision rules in the model. This can occur because the integral of a discontinuous function need not be discontinuous, and requires that (i) the random variables are continuously distributed, and (ii) the decision rules satisfy a set of ânon-degeneracyâ conditions that we have characterized theoretically. We call a set of mixed-integer decision rules that satisfy these conditions âsmooth-in-expectation.â Applying smooth-in-expectation mixed-integer decision rules to a multistage stochastic program results in a single-stage program with a continuously differentiable objective function. In particular, the overwhelming discrete character of the original problem (assuming mixed-integer recourse) is dramatically reduced, leaving only first-stage integer decisions from the original formulation. On the other hand, the objective of this reformulation is an expected value that typically cannot be evaluated precisely, but rather must be estimated by Monte Carlo methods. In our approach, this problem is solved using a custom stochastic gradient decent algorithm.
In this talk, we will discuss the construction of general-purpose smooth-in-expectation decision rules and the efficient solution of the resulting smooth stochastic program. Case studies in chemical manufacturing and distributed power generation will be used to demonstrate the advantages of our approach relative to existing nonlinear multistage stochastic programming formulations.