Mixed uncertainty sets for robust combinatorial optimization

Abstract

In robust optimization, the uncertainty set is used to model all possible outcomes of uncertain parameters. In the classic setting, one assumes that this set is provided by the decision maker based on the data available to her. Only recently it has been recognized that the process of building useful uncertainty sets is in itself a challenging task that requires mathematical support. In this paper, we propose an approach to go beyond the classic setting, by assuming multiple uncertainty sets to be prepared, each with a weight showing the degree of belief that the set is a “true” model of uncertainty. We consider theoretical aspects of this approach and show that it is as easy to model as the classic setting. In an extensive computational study using a shortest path problem based on real-world data, we auto-tune uncertainty sets to the available data, and show that with regard to out-of-sample performance, the combination of multiple sets can give better results than each set on its own.

Appendix: Additional experimental results

To understand how each uncertainty set performs for each s-t pair, we choose a representative configuration for each uncertainty set to compare the performance. The description of the configurations which are compared can be found below.

• Mixed Uncertainty Set: We use a mix of convex hull and ellipsoidal uncertainty. The scaling parameter, $\lambda$, and the weight parameter, $w_j$, of convex hull are 0.2234 and 0.7502 respectively. For the ellipsoidal set, the scaling and weight parameters take the values 5.4609 and 0.9796 respectively.

• Convex Hull: The scaling parameter is 0.2.

• Ellipsoidal: The scaling parameter is 6.0.

• Interval: The scaling parameter is 0.075.

Figure 4 shows the comparison in performance for each measure (Avg, Max and CVaR), both in-sample and out-of-sample, for every pair of mixed set and parent set, i.e., we compare performance for mixed and convex hull sets, for mixed and ellipsoidal sets and for mixed and interval sets. This is achieved by taking the relative difference in the solutions delivered by the mixed set and the comparing parent set for each s-t pair, i.e., we calculate the difference between the value of parent and mixed solution, and divide by the value of the mixed solution. While a negative value indicates that the solution delivered by the mixed set is better than the parent set, a positive value indicates the opposite. For the sake of clarity in the plots, we filter out the sample containing only zero values as they indicate that both the sets deliver exactly the same solution. In our case, for each pair of mixed and parent set, the number of s-t pairs for which the solutions differed are as follows: 131 (21.8%) for mixed and convex hull sets; 91 (15.2%) for mixed and ellipsoidal sets; and 129 (21.5%) for mixed and interval sets.

Fig. 4

Relative differences with respect to average, worst-case (max), and average of worst 5% (CVaR) performance measures

Figure 4a, d, and 4b, e respectively compare the Avg and Max performance measures (both in-sample and out-of-sample) for each pair of mixed and parent set. For the majority of the s-t pairs, mixed set performs better than both ellipsoidal and interval sets for both in-sample and out-of-sample data. Moreover, while in-sample performance given by convex hull is better than that of mixed set, the out-of-sample performance of convex hull is similar to that of mixed set. Similarly, for the CVaR performance measure, Fig. 4c, f lead us to conclude that for majority of the s-t pairs, for both in-sample and out-of-sample performances, while mixed set performs worse than ellipsoidal set, it performs better than the other two parent sets.