A tractable approach for designing piecewise affine policies in two-stage adjustable robust optimization
- PDF / 882,503 Bytes
- 46 Pages / 439.37 x 666.142 pts Page_size
- 73 Downloads / 221 Views
Series A
A tractable approach for designing piecewise affine policies in two-stage adjustable robust optimization Aharon Ben-Tal1,2 · Omar El Housni3 · Vineet Goyal3 Received: 15 July 2016 / Accepted: 1 March 2019 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2019
Abstract We consider the problem of designing piecewise affine policies for two-stage adjustable robust linear optimization problems under right-hand side uncertainty. It is well known that a piecewise affine policy is optimal although the number of pieces can be exponentially large. A significant challenge in designing a practical piecewise affine policy is constructing good pieces of the uncertainty set. Here we address this challenge by introducing a new framework in which the uncertainty set is “approximated” by a “dominating” simplex. The corresponding policy is then based on a mapping from the uncertainty set to the simplex. Although our piecewise affine policy has exponentially many pieces, it can be computed efficiently by solving a compact linear program given the dominating simplex. Furthermore, we can find the dominating simplex in a closed form if the uncertainty set satisfies some symmetries and can be computed using a MIP in general. We would like to remark that our policy is an approximate piecewise-affine policy and is not necessarily a generalization of the class of affine policies. Nevertheless, the performance of our policy is significantly better than the affine policy for many important uncertainty sets, such as ellipsoids and norm-balls, both theoretically and numerically. For instance, for hypersphere uncertainty set, our piecewise affine policy can be computed by an LP and gives a O(m 1/4 )-approximation whereas the affine policy requires us to √ solve a second order cone program and has a worst-case performance bound of O( m). Mathematics Subject Classification 90C39 · 90C47 · 49K35
B
Vineet Goyal [email protected] Aharon Ben-Tal [email protected] Omar El Housni [email protected]
1
Industrial Engineering and Management, Technion - Israel Institute of Technology, Haifa, Israel
2
CentER, Tilburg University, Tilburg, The Netherlands
3
Industrial Engineering and Operations Research, Columbia University, New York, USA
123
A. Ben-Tal et al.
1 Introduction Addressing uncertainty in problem parameters in an optimization problem is a fundamental challenge in most real world problems where decisions often need to be made in the face of uncertainty. Stochastic and robust optimization are two approaches that have been studied extensively to handle uncertainty. In a stochastic optimization framework, uncertainty is modeled using a probability distribution and the goal is to optimize an expected objective [18]. We refer the reader to Kall and Wallace [25], Prekopa [27], Shapiro [28], Shapiro et al. [29] for a detailed discussion on stochastic optimization. While it is a reasonable approach in certain settings, it is intractable in general and suffers from the “curse of di
Data Loading...
