(419b) Efficient Solution of Mixed-Integer Multistage Stochastic Programs for the Optimal Design of Smart Manufacturing Systems Using “Smooth-in-Expectation” Decision Rules

Authors: 
Scott, J., Georgia Institute of Technology
Hakizimana, A., Clemson University
The ability to operate manufacturing plants in a flexible manner has long been motivated by the need to accommodate long-term market fluctuations and equipment failures. However, two contemporary trends have greatly heightened the significance of flexibility. First, increasingly volatile markets and the growing utilization of renewable resources (both energy and chemicals) are introducing unprecedented levels of variability and uncertainty into process operations. Second, advances in automation and process intensification are making it possible to envision systems that are much more responsive and adaptable than ever before. Together, these factors are creating an environment in which flexible operating policies have the potential to achieve dramatic increases in efficiency and reliability in many critical applications, including distributed power generation, (bio)refining, and chemical manufacturing in multi-product plants. Indeed, this potential has placed flexibility astride information technology as a central theme of the smart manufacturing paradigm.

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.