\(\)
We consider two-stage robust linear programs with a budget of uncertainty for the righthand side. In this scenario set, which is frequently used in robust optimization, the uncertain righthand side for each row lies in an interval and the relative increases summed over all rows are less than a budget \(\Gamma\). We develop a General Polyhedral Approximation (GPA) method, in which the uncertainty set \(\mathcal{U}\) is substituted by a finite set of polytopes derived from the vertex set of an arbitrary polytope that dominates \(\mathcal{U}\). The method combines the solutions for the individual polytopes and thereby achieves an approximation factor of \(\beta \sum_{i=1}^N \sigma_i\) significantly improving on the literature. Moreover, the method allows for even stronger results on specific problems as we exemplify for the Transportation Location Problem.
Previous methods reach a threshold at \(\Gamma > \sqrt{m}\) after which they are not better than a quasi nominal solution, i.e., the power of second stage decisions cannot be used. The GPA method significantly improves the approximation factor \emph{before} this threshold. After the threshold, as the GPA allows to use scaled budget polytopes, it provides a scheme to trade-off the number of vertices against the approximation factor. This way the GPA breaks the threshold and finds solutions that are better than the quasi nominal solution even for cases with \(\Gamma > \sqrt{m}\).
Article
View General Polyhedral Approximation of Two-Stage Robust Linear Programming