Constructing Representative Scenarios to Approximate Robust Combinatorial Optimization Problems
Marc Goerigk





Department of Management Science, Lancaster University, United Kingdom




Constructing Representative Scenarios to Approximate Robust Combinatorial Optimization Problems
    Marc GoerigkEmail: m.goerigk@lancaster.ac.uk
    
===============================================================================================



In robust combinatorial optimization with discrete uncertainty, two general approximation algorithms are frequently used, which are both based on constructing a single scenario representing the whole uncertainty set. In the midpoint method, one optimizes for the average case scenario. In the element-wise worst-case approach, one constructs a scenario by taking the worst case in each component over all scenarios. Both methods are known to be N-approximations, where N is the number of scenarios.

In this paper, these results are refined by reconsidering their respective proofs as optimization problems. We present a linear program to construct a representative scenario for the uncertainty set, which guarantees an approximation guarantee that is at least as good as for the previous methods. Incidentally, we show that the element-wise worst-case approach can have an advantage over the midpoint approach if the number of scenarios is large. In numerical experiments on the selection problem we demonstrate that our approach can improve the approximation guarantee of the midpoint approach by around 20%.

Keywords:  robust optimization; combinatorial optimization; approximation algorithms




§ INTRODUCTION


We consider combinatorial optimization problems of the general form

    min_x∈cx

where c≥0 is a cost vector, and ⊆{0,1}^n is a set of feasible solutions. As real-world problems may suffer from uncertainty, robust counterparts to combinatorial problems have been considered in the literature, see <cit.> for surveys on the topic. The resulting robust (or min-max) optimization problem is then of the form

    min_x∈max_c∈cxMinMax

where  contains all possible cost vectors c^1, …, c^N against we wish to protect.

As robust combinatorial problems are usually NP-hard, approximation methods have been considered <cit.>. Two such heuristics stand out in the literature, as they are easy to use and implement, and have been providing the best-known approximation guarantee for a wide range of problems. While this guarantee has been improved for specific problems, they are still the best-known general methods (see <cit.>).
Both algorithms are based on constructing a single scenario that represents the whole uncertainty . For the midpoint algorithm, we use ĉ with ĉ_i = 1/N ∑_j∈[N] c^j_i for all i∈[n]. For the element-wise worst-case algorithm, we set c by using c_i = max_j∈[N] c^j_i. Let us denote by x(c) a minimizer for the nominal problem with costs c, and set x̂:=x(ĉ) (the midpoint solution) and x:=x(c) (the element-wise worst-case solution). The following results can be found in <cit.>.


The midpoint solution x̂ is an N-approximation for MinMax.



The element-wise worst-case solution x is an N-approximation for MinMax.


Frequently, problems with ”nice” structure (such as shortest path, spanning tree, selection, or assignment) have been considered in the literature, where it is possible to solve the nominal problem in polynomial time. In particular, this setting makes it possible to solve both of the above approaches in polynomial time by solving one specific scenario (i.e., finding x(ĉ) or x(c)). This can then be used, e.g., as part of a branch and bound procedure for the (hard) robust problem.

Recently, data-driven robust optimization approaches have been investigated in the literature (see, e.g., <cit.>). This paper has a similar research outlook by using the available data for better approximation guarantees, instead of ignoring structure that may be present. In a similar spirit, by analyzing the symmetry of an uncertainty set, <cit.> is able to derive improved approximation bounds for the related MinMax Regret problem with compact uncertainty sets.

The contributions of this paper are as follows. By re-examining the proofs for Theorems <ref> and <ref>, we present a linear program (LP) to construct a scenario c' that is ”representative” for the uncertainty set . We show that the resulting solution x(c') has an approximation guarantee that is at least as good as the guarantee for x̂ and x. We also compare the midpoint and element-wise worst-case approach in more detail and find that the latter can outperform the former if the number of scenarios is large. In numerical experiments, we compare the quality of upper and lower bounds of our approach with the midpoint method, and demonstrate that it is possible to find considerably smaller a-priori and a-posteriori gaps by solving a simple linear program.




§ SCENARIO CONSTRUCTION BASED ON THE MIDPOINT APPROACH


Let OPT be the optimal objective value of problem MinMax, and let x^* be any optimal solution. We make the following distinctions.


Let some scenario c (not necessarily in ) be given. Then

    UB(c) = max_i∈[N]c^ix(c)

is an upper bound on OPT.
If it is possible to compute a lower bound from c, we denote this as LB(c), and a bound on the ratio as

    r(c) ≥ UB(c) / LB(c)

We call r(c) an a-priori bound, if it does not require the computation of x(c) to find. Otherwise, we call it an a-posteriori bound.

The reason for this distinction is that calculation of x can be costly, if the nominal problem is not solvable in polynomial time.

As an example, the midpoint method uses ĉ := 1/N∑_i∈[N]c^i. It comes with an a-priori bound that is N, but by using LB(ĉ) = ĉx(ĉ), we can calculate a stronger a-posteriori bound.

We now consider the problem of finding a better a-priori bound than N. To this end, note that Theorem <ref>  can be proven in the following way.


    UB(ĉ) = max_i∈[N]c^i x̂(i)≤ N ĉx̂≤ N ĉx^* (ii)≤ N max_i∈[N]c^i x^* = N· OPT


To mirror the steps of this proof, let us consider the following optimization problem:

    min_t,c    t 
    s.t.    max_i∈[N]c^ix(c) ≤ t·cx(c) 
       cx^* ≤max_i∈[N]c^i x^*


Let (t,c) be a feasible solution to problem (<ref>–<ref>). Then, x(c) is a t-approximation for MinMax.


Analogous to the proof of Theorem <ref>.

Note that Problem (<ref>–<ref>) cannot be solved directly, as both the optimal solution x^* and x(c) are unknown. To circumvent these two issues, we use different, sufficient constraints instead.


Let c fulfil

    ∑_j∈ S c^i_j ≤ t ∑_j∈ S c_j   ∀ i∈[N], S⊆[n] : |S| = k

for some value of t, and constant k such that k≤∑_j∈[n] x_j for all x∈. Then, (t,c) also fulfils (<ref>).


Let X = {j∈[n]: x_j(c) = 1} and 𝒮 = {S⊆[n] : |S| = k, S⊆ X}. Then, the number of sets S in 𝒮 containing a specific item j∈ X is the same for all j. Let ℓ be this number. By summing (<ref>) over all S∈𝒮, we find that

    ℓ∑_j∈ X c^i_j ≤ t ℓ∑_j∈ X c_j     ∀ i∈[N]

and the claim follows.

Note that for constant k, it is possible in polynomial time to check if k≤∑_j∈[n] x_j for all x∈. Also, the set 𝒮 contains polynomially many elements. As an example, for k=1, Constraint (<ref>) becomes

    c^i_j ≤ tc_j     ∀ i∈[N], j∈[n]

and for k=2, it becomes

    c^i_j + c^i_l ≤ t(c_j+c_l)     ∀ i∈[N], j,l∈[n], j≠ l

In general, the constraints for some fixed k also imply the constraints for any larger k. This means that the larger the value of k, the larger is the set of feasible solutions to our optimization problem, and the better approximation guarantees we can get.


Let c be in conv() = conv{c^1,…,c^N}. Then, c fulfils (<ref>).


Let c = ∑_i∈[N]λ_i c^i with ∑_i∈[N]λ_i = 1 and λ_i ≥ 0 for all i∈[N]. Then, for any x∈,

    cx = ∑_i∈[N]λ_i c^ix≤∑_i∈[N]λ_i max_j∈[N]c^jx = max_i∈[N]c^ix


We now consider the following linear program:

    max     t 
    s.t.     t ∑_j∈ S c^i_j ≤∑_j∈ S c_j    ∀ i∈[N], S⊆[n] : |S| = k 
       c = ∑_i∈[N]λ_i c^i 
       ∑_i∈[N]λ_i = 1 
       λ_i ≥ 0    ∀ i∈[N]

Note that we replaced variable t in Problem (<ref>–<ref>) with 1/t to linearize terms.


Let (t^*,c^*) be an optimal solution to Problem (<ref>–<ref>). Then, x(c^*) is a 1/t^*-approximation for MinMax, and 1/t^* ≤ N.


By Lemmas <ref> and <ref>, (1/t^*,c^*) is feasible for Problem (<ref>–<ref>). Using Lemma <ref>, we therefore find that x(c^*) is a 1/t^*-approximation for MinMax.

To see that 1/t^* ≤ N, note that (1/N,ĉ) is a feasible solution to Problem (<ref>–<ref>).


Once a solution (t^*,c^*) has been computed, we have found an a-priori approximation guarantee. If we then compute x(c^*), we can derive a lower bound c^*x(c^*), as c^*∈ conv(), and an upper bound by calculating the objective value of x(c^*) for MinMax. This way, a stronger a-posteriori guarantee is found.



We illustrate our approach using a small selection problem as an example. Given four items, the task is to choose two of them that minimize the worst-case costs over three scenarios. The upper part of Table <ref> shows the item costs in each scenario.



The midpoint scenario (i.e., the average in each item) is shown in the row below (ĉ). An optimal solution for this scenario is to pack items 1 and 3. This means that we have an a-priori approximation ratio of N=3, and can calcluate a lower bound LB(ĉ) = ĉx̂ = 8 and an upper bound UB(ĉ) = max_i∈[N]c^ix̂ = 12. Combining lower and upper bound, we find the stronger a-posteriori bound of 1.50.

Using our linear program (<ref>–<ref>) with k=1, we construct the scenario given in the next row (c') and find an a-priori guarantee of 1.33. For this scenario, an optimal solution is to take items 1 and 4. Accordingly, we find a lower bound of 9.25, an upper bound of 10, and an a-posteriori ratio of 1.08.

Finally, we also use our LP with k=2 to find the scenario c” and an a-priori guarantee of 1. This means that even before we have solved the problem, we already know that the resulting solution will be optimal. Indeed, we find that packing items 1 and 4 gives the optimal solution with objective value 10.



Note that we can also use the linear program (<ref>–<ref>) to strengthen the approximation guarantee of the midpoint scenario ĉ without calculating x̂, by only keeping t variable.

We conclude this section by introducing an alternative approach to calculate a-posteriori bounds, which cannot be used for a-priori bounds. To this end, note that

    max_c∈ conv()min_x∈cx≤min_x∈max_i∈[n]c^ix

If the nominal problem can be written as a linear program, it can be dualized to find a compact formulation for the max-min problem. As both ĉ and the optimal solution to problem (<ref>–<ref>) are in conv(), this approach will result in a lower bound which will be at least as good as the lower bounds of the other two approaches. This may not result in a better ratio beteen upper and lower bound, however. We will test this approach in the experimental section.






§ ON THE ELEMENT-WISE WORST-CASE


We now focus on the element-wise worst-case scenario c with c_i = max_j∈[N] c^j_i. A proof for Theorem <ref> is the following.


    UB(c) = max_i∈[N]c^i x(i)≤cx≤cx^* (ii)≤ N max_i∈[N]c^ix^* = N · OPT


Accordingly, we can generalize this proof to an optimization problem by writing

    min_t,c    t 
    s.t.    max_i∈[N]c^i x(c) ≤cx(c) 
       cx^* ≤ t max_i∈[N]c^i x^*

By substituting c' := c/t, Problem (<ref>–<ref>) becomes equivalent to Problem (<ref>–<ref>). Hence, we can apply the same techniques to transform this into a conservative linear program (<ref>–<ref>) as in the previous section. Note, however, that while ĉ is a feasible solution for this problem, this may not be the case for c.

Related to the MinMax approach is MinMax Regret, where objective values are normalized by the optimal objective value in each scenario, i.e., 

    min_x∈max_i∈[N]( c^ix - c^ix(c^i) )  MinMax Regret

The following result is also from <cit.>.


The midpoint algorithm is an N-approximation for MinMax Regret; this does not hold for the element-wise worst-case algorithm.


In combination with Theorems <ref> and <ref>, this means that there are no known problem classes where the element-wise worst-case solution gives a better performance guarantee than the midpoint solution. The midpoint solution has also been found to be the best-known general approximation algorithm for interval uncertainty problems <cit.>. For these reasons, the midpoint solution has seen more attention in the research literature than the element-wise worst-case approach. However, in the following we show that if the number of scenarios is large, we element-wise worst-case approach can perform better than the midpoint approach, i.e., not only the size of the uncertainty set plays a role for approximability, but also the problem dimension.


The element-wise worst-case algorithm is a |X|-approximation for MinMax, where 
|X|=max_x∈∑_j∈[n] x_j. 


It holds that

    max_i∈[N]∑_j∈[n] c^i_j x_j 
    ≤∑_j∈[n]c_j x_j 
    ≤∑_j∈[n]c_j x^*_j 
    = ∑_j∈[n]max_i∈[N] c^i_j x^*_j 
       ≤ |X| ·max_j∈[n]max_i∈[N] c^i_j x^*_j
    = |X|·max_i∈[N]max_j∈[n] c^i_j x^*_j 
    ≤ |X| ·max_i∈[N]∑_j∈[n] c^i_j x^*_j = |X| · OPT



Note that |X| ≤ n. The approximation guarantees from Theorems <ref> and <ref> are tight, as the following two examples for robust shortest path problems demonstrate (see also <cit.>).



In Figure <ref>, the midpoint solution cannot distinguish between the upper edge and the lower edge. Hence, in this case, the N-approximation guarantee is tight with N=2. In Figure <ref>, the element-wise worst-case solution cannot differentiate between the upper and the lower path. This instance is an example where the N-approximation guarantee is tight for this approach.

Note that the instance from Figure <ref> can be extended by using more scenarios, preserving that the midpoint solution is an N-approximation, without additional edges. This is not the case for the element-wise worst-case scenario in Figure <ref>: To extend this instance to more scenarios, additional edges are required. This demonstrates that the midpoint solution is not a |X|-approximation, as shown for the element-wise worst-case approach.




§ EXPERIMENTS


To test the quality of our LP-based scenario construction approach, we consider instances of the selection problem (see, e.g., <cit.>). Here, = {x∈{0,1}^n : ∑_j∈[n] x_j = p} for some integer parameter p. We generate item costs c^i_j by sampling uniformly i.i.d. from {0,1,…,100}. We use instances sizing from n=10, p=3 to n=30, p=9 and use N∈{2,5,10,50,100}. For each parameter combination, we generate 1000 instances and average results.

Table <ref> shows the a-priori bounds for the midpoint approach when using our linear program (<ref>–<ref>) for evaluation with k=1, k=2 and k=3 (Mid-1-Pre, Mid-2-Pre, and Mid-3-Pre, respectively). We compare this to the a-priori bounds that are found when also optimizing over the scenario c for k=1, k=2 and k=3 (LP-1-Pre, LP-2-Pre, and LP-3-Pre, respectively). Note that overall, all guarantees are considerably smaller than N. Furthermore, our approach is able to improve the bound of the midpoint algorithm. On average, the guarantee that the midpoint approach gives is more than 20% larger than our guarantee.



We contrast the a-priori bounds with a-posteriori bounds in Table <ref>, i.e., we calculate the solutions x(c) for the respective scenarios c and the resulting ratio of upper and lower bound. On average, the bound provided by the midpoint solution is around 17% larger than the bound provided by our approach with k=2 or k=3. The max-min approach (denoted by MM) performs slightly better than our approach (Mid-Post is on average 19% larger than MM-Post), but this comes without an a-priori guarantee, at the cost of higher computational effort, and it is not always possible to compute as explained in Section <ref>.



Finally, we show more details on the a-posteriori bounds by providing both the upper and lower bounds in Tables <ref> and <ref>. We find that our approach gives both better upper, and better lower bounds than the midpoint approach. While the MaxMin approach provides the best lower bounds, its upper bounds are often worse than for the midpoint solution.








§ CONCLUSION

Most robust combinatorial optimization problems are hard, which has lead to the development of general approximation algorithms. The two best-known such approaches are the midpoint method and the element-wise worst-case approach. Both rely on creating a single scenario that is representative for the whole uncertainty set. By reconsidering the respective proofs that both are N-approximation algorithms, we find an optimization problem to construct a representative scenario that results in an approximation which is at least as good as for the previous two scenarios.

In computational experiments using the selection problem, we test this approach numerically. We find that the midpoint method gives a guarantee that is about 20% larger than ours, while we only need to solve a simple linear program to construct the representative scenario. The improved a-priori guarantee is also reflected in an improved a-posteriori guarantee, with our approach providing both better upper and lower bounds than before. This smaller gap could potentially be used within branch-and-bound algorithms for a more efficient search for an optimal solution.


BGK18

[ABV07]Aissi2007281
H. Aissi, C. Bazgan, and D. Vanderpooten.
Approximation of min–max and min–max regret versions of some
  combinatorial optimization problems.
European Journal of Operational Research, 179(2):281 – 290,
  2007.

[ABV09]Aissi2009
H. Aissi, C. Bazgan, and D. Vanderpooten.
Min–max and min–max regret versions of combinatorial optimization
  problems: A survey.
European Journal of Operational Research, 197(2):427 – 438,
  2009.

[BGK18]bertsimas2018data
D. Bertsimas, V. Gupta, and N. Kallus.
Data-driven robust optimization.
Mathematical Programming, 167(2):235–292, 2018.

[CG17]approx
A. Chassein and M. Goerigk.
On scenario aggregation to approximate robust optimization problems.
Optimization Letters,
  https://doi.org/10.1007/s11590-017-1206-x, 2017.
Available online, to appear.

[Con12]conde2012constant
E. Conde.
On a constant factor approximation for minmax regret problems using a
  symmetry point scenario.
European Journal of Operational Research, 219(2):452–457,
  2012.

[DG17]atmos
T. Dokka and M. Goerigk.
An Experimental Comparison of Uncertainty Sets for Robust Shortest
  Path Problems.
In Gianlorenzo D'Angelo and Twan Dollevoet, editors, 17th
  Workshop on Algorithmic Approaches for Transportation Modelling,
  Optimization, and Systems (ATMOS 2017), volume 59 of OpenAccess Series
  in Informatics (OASIcs), pages 16:1–16:13, Dagstuhl, Germany, 2017. Schloss
  Dagstuhl–Leibniz-Zentrum fuer Informatik.

[KZ06]kasperski2006approximation
A. Kasperski and P. Zieliński.
An approximation algorithm for interval data minmax regret
  combinatorial optimization problems.
Information Processing Letters, 97(5):177–180, 2006.

[KZ16]kasperski2016robust
A. Kasperski and P. Zieliński.
Robust discrete optimization under discrete and interval uncertainty:
  A survey.
In Robustness Analysis in Decision Aiding, Optimization, and
  Analytics, pages 113–143. Springer, 2016.




