(280c) Deep Lifted Decision Rules for Two-stage Adaptive Optimization

Adaptive optimization is a framework to handle dynamic decision-making problems, which are widely seen in many process system engineering problems. The key idea is to categorize the decisions into non-adaptive and adaptive decisions. The former, also known as “here and now” decisions, are made at the outset of the problem while the latter, also known as “wait and see” decisions, are made gradually in recourse to the newly revealed information of uncertain parameters.

Due to the problem nature, it is in general very hard to obtain the exact optimal adaptive decision policy. Existing solution methods are based on approximation techniques. The seminal paper of Ben-Tal, et al. (2004) introduced the linear decision rule-based approximation method to derive a linear deterministic counterpart, under a polyhedral uncertainty set, of the original adaptive optimization problem. Ben-Tal & Den Hertog (2011) proposed an alternative method by defining the adaptive decisions as quadratic functions of the uncertain parameters. The obtained counterpart, under an ellipsoidal uncertainty set, is a second-order cone programming problem. Bertsimas, et al. (2011) proposed polynomial decision rules in multistage robust dynamic problems. The derived counterpart, under an intersection of convex uncertainty sets, is a semidefinite programming problem. The increase in the complexity of the decision rule functions does indeed improve the solution quality of decision-making problems. However, this comes at the expense of more complex counterparts which are computationally prohibitive. Alternatively, the solution quality may be improved using a set of piecewise linear “transformed” parameters. Georghiou, et al. (2015) introduced lifted decision rule constructed via uncertainty lifting. The main property is the one-to-one correspondence between a set of linear functions in the lifted uncertainty space and a family of piecewise linear functions in the original uncertainty space. Hence, the attractive modelling in the lifted problem are exploited, while exhibiting a better solution quality for the original problem.

Building on ideas from deep neural networks and lifted decision rules, this paper presents a novel method to generate flexible piecewise linear decision rules for two-stage stochastic adaptive optimization problems using a ``deep lifting" network. Taking the original uncertain parameters as input, the network consists of multiple processing layers that enable the construction of decision rules whose quality and flexibility is superior to linear decision rules and axially-lifted ones. In the proposed network, each layer consists of two simple operations: an affine transformation through a weight matrix and a lifting operation. The approximation function used to define an adaptive policy is a linear function of the primitive uncertain parameters and the lifted uncertain parameters in all layers. Finding optimal decision rules in the presence of the successive operations, however, is a challenging global optimization problem. We propose two solution methods to optimize the weights and the decision rule approximation quality. A derivative-free method via an evolutionary algorithm and a derivative-based method using approximate first- and second-order derivative information. For the latter method, we suggest local-search heuristics that scale well and reduce the computational time by several folds while offering similar solution quality. We illustrate the flexibility of the generated piecewise linear decision rules using deep lifting in comparison to linear and axial piecewise linear decision rules via a transportation and an airlift operations scheduling problem.

References

Ben-Tal, A. & Den Hertog, D., 2011. Immunizing Conic Quadratic Optimization Problems Against Implementation Errors, Tilburg: Tilburg University.

Ben-Tal, A., Goryashko, A., Guslitzer, E. & Nemirovski, A., 2004. Adjustable robust solutions of uncertain linear programs. Mathematical Programming, 99(2), pp. 351-376.

Bertsimas, D., Iancu, D. & Parrilo, P., 2011. A hierarchy of near-optimal policies for multistage adaptive optimization. Volume 56, pp. 2809-2824.

Georghiou, A., Wiesemann, W. & Kuhn, D., 2015. Generalized decision rule approximations for stochastic programming via liftings. Mathematical Programming, 152(1-2), pp. 301-338.