Robust combinatorial optimization problems under budgeted interdiction uncertainty

Goerigk, Marc; Khosravi, Mohammad Article — Published Version Robust combinatorial optimization problems under budgeted interdiction uncertainty OR Spectrum Provided in Cooperation with: Springer Nature Suggested Citation: Goerigk, Marc; Khosravi, Mohammad (2024) : Robust combinatorial optimization problems under budgeted interdiction uncertainty, OR Spectrum, ISSN 1436-6304, Springer, Berlin, Heidelberg, Vol. 47, Iss. 1, pp. 255-285, https://doi.org/10.1007/s00291-024-00772-0 This Version is available at: https://hdl.handle.net/10419/323262 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Vol.:(0123456789) OR Spectrum (2025) 47:255–285 https://doi.org/10.1007/s00291-024-00772-0 ORIGINAL ARTICLE Robust combinatorial optimization problems underbudgeted interdiction uncertainty MarcGoerigk1 · MohammadKhosravi1 Received: 8 July 2023 / Accepted: 27 May 2024 / Published online: 5 June 2024 © The Author(s) 2024 Abstract In robust combinatorial optimization, we would like to find a solution that performs well under all realizations of an uncertainty set of possible parameter values. How we model this uncertainty set has a decisive influence on the complexity of the corresponding robust problem. For this reason, budgeted uncertainty sets are often studied, as they enable us to decompose the robust problem into easier subproblems. We propose a variant of discrete budgeted uncertainty for cardinality-based constraints or objectives, where a weight vector is applied to the budget constraint. We show that while the adversarial problem can be solved in linear time, the robust problem becomes NP-hard and not approximable. We discuss different possibilities to model the robust problem and show experimentally that despite the hardness result, some models scale relatively well in the problem size. Keywords Robust optimization· Combinatorial optimization· Budgeted uncertainty· Knapsack uncertainty 1 Introduction Uncertainty can manifest in various forms, such as imprecise data or the inherent unpredictability of the future. A notable case study utilizing linear programs (BenTal and Nemirovski 2000) demonstrated that even slight changes in problem data can significantly shift an optimal solution towards infeasibility, rendering it practically useless. Consequently, a range of decision-making approaches under uncertainty have been developed, including stochastic programming (Kail and Mayer 2005), fuzzy optimization (Lodwick and Kacprzyk 2010), and robust optimization (BenTal Aharon etal. 2009). Often, such approaches make the resulting decision-making problems more challenging to solve than their nominal counterparts. The focus of * Mohammad Khosravi mohammad.khosra[email protected] 1 Business Decisions andData Science, University ofPassau, Dr.-Hans-Kapfinger-Straße 30, 94032Passau, Germany 256 M.Goerigk, M.Khosravi this paper is on robust combinatorial decision problems, which have the distinct advantage that a probability distribution on the uncertain data does not need to be known. More formally, consider some nominal combinatorial problem where we write vectors in bold and use the notation [n] to denote sets {1, …,n} . In addition, assume that the data c c c in the objective function is not known exactly. Given a set of possible data values U , the classic min-max approach to robust optimization is to solve the problem Many more variants of robust optimization problems exist, see e.g. Goerigk and Schöbel (2016), Kasperski and Zieliński (2016) and Buchheim and Kurtz (2018) for an overview. What they have in common is that a set U containing all scenarios can be formulated by the decision maker, and is made available to the optimization problem. Data-driven robust optimization (Bertsimas etal. 2018) aims at automating this step by formulating suitable uncertainty sets based on available data (e.g., by using on the risk preference of the decision maker). There is typically a trade-off between the modeling capabilities of the uncertainty set U and the complexity of the resulting problem. A discrete scenario set U offers broad flexibility as it allows direct utilization of any amount of historical data observations in the model. However, it comes with a drawback that the robust versions of relevant combinatorial problems are already computationally difficult (NP-hard) even when considering only two scenarios (Kasperski and Zieliński 2016). Representing U using a general polyhedron, defined by its inner or outer description, suffers from the same limitation (Goerigk etal. 2022). A significant breakthrough was made with the introduction of budgeted uncertainty sets, also known as the Bertsimas–Sim approach (2003, 2004). This approach addresses an uncertain linear objective c c c⊺x x x , where each coefficient i∈[n] is bounded by a lower bound ci and an upper bound ci . Moreover, only a fixed integer Γ of coefficients are allowed to deviate simultaneously from their lower to upper bounds. In other words, U incorporates a cardinality constraint of the following form: The introduction of this simple idea has had a profound impact on the field of robust optimization. The two papers that presented this idea continue to be widely cited, highlighting their significance. The appeal of uncertainty sets of this nature lies in their simplicity and intuitive nature. Furthermore, it has been demonstrated that the robust min–max problem can be decomposed into a manageable number min ∑ i∈[n] cixi (Nom) s.t. x x x∈ X ⊆{0, 1} n min x x x∈Xmax c c c∈U ∑ i∈[n] cixi (RO) UΓ= { c c c∈ℝn∶∃𝛿 𝛿 𝛿∈{0, 1}ns.t. ci=ci+( ci−ci)𝛿i, ∑ i∈[n] 𝛿i≤Γ } 257 Robust combinatorial optimization problems underbudgeted… (specifically, O(n)) of nominal-type problems (Nom). This decomposition allows for increased modeling flexibility without incurring significant computational complexity. If the nominal problem can be solved in polynomial time, the corresponding robust problems can be solved in polynomial time as well. The advantages offered by budgeted uncertainty sets have resulted in their widespread and varied applications to real-world problems. These applications encompass a range of domains, including portfolio management (Bertsimas and Pachamanova 2008), wine grape harvesting (Bohle et al. 2010), supply chain control (Bertsimas and Thiele 2006), furniture production planning (Douglas and Morabito 2012), train load planning (Bruns etal. 2014), and many others. The versatility of budgeted uncertainty sets has made them a valuable tool in addressing uncertainty and optimizing decision-making in numerous practical scenarios. A noteworthy characteristic of UΓ is that if Γ is an integer, we can utilize continuous deviations 𝛿 𝛿 𝛿∈[0, 1]n without altering the problem. This is due to the fact that when finding an optimal strategy for the adversary in the problem maxc c c∈Uc c c⊺x x x given a fixed solution x x x , it is sufficient to sort the items chosen by x x x based on the potential cost deviation ci −ci , and select the Γ largest values. Consequently, the equivalence between “discrete” and “continuous” budgeted uncertainty holds. However, this equivalence does not generally hold in the case of multi-stage robust problems, where recourse actions can be taken after the cost scenario has been revealed (see, e.g., the discussion in Goerigk etal. (2022)). The effectiveness of budgeted uncertainty sets has led to the emergence of various variants and generalizations of this approach. In the paper by Bertsimas etal. (2004), norm-based uncertainty sets were introduced. It was demonstrated that the traditional budgeted uncertainty set can be constructed using a specific norm known as the D-norm. Another variant is multi-band uncertainty (Büsing and D’andreagiovanni 2012), which involves a system of deviation values d1 ij <d 2 ij <…<d K ij with both lower and upper bounds on the number of possible deviations from each band k∈[K] . In variable budgeted uncertainty (Poss 2013), the number of deviations 𝛾 taken into account may depend on the size ‖x x x‖1 of the solution x x x for which the adversarial problem is being solved. Additionally, there is knapsack uncertainty (Poss 2018), which can be represented as follows: Here, the set of possible scenarios is bounded by m linear knapsack constraints. When the value of m is fixed, similar results to those obtained for the original set UΓ can be derived. A special case of this type of set is locally budgeted uncertainty, see Goerigk and Lendl (2021) and Yaman (2023), where each of the knapsack constraints affects a subset of variables, and these subsets are disjoint between constraints. These variants and generalizations of budgeted uncertainty sets provide U knap = { c c c∈ℝn∶∃𝛿 𝛿 𝛿∈[0, 1]ns.t. ci=ci+( ci−ci)𝛿i, ∑ i∈[n] aji𝛿i≤bj,j∈[m] } 258 M.Goerigk, M.Khosravi additional flexibility and adaptability to various problem settings, enhancing the robustness of decision-making under uncertainty. In this paper we consider a new type of uncertainty set, applicable to an objective or constraints that involve the cardinality1 ‖x x x‖1 , e.g., to problems where the task is to maximize the size of a set, or where this cardinality is not allowed to fall below a certain threshold. The motivation to consider such sets comes from a real-world problem involving the composition of teams to take on a set of jobs under uncertain skill requirements (see Anoshkina and Meisel 2019; Anoshkina etal. 2020). In such problems, one would like to compose teams that can take on the maximum possible number of jobs. From an adversarial perspective, the task is to change the job skill requirements in a way that minimizes the number of jobs that can be carried out successfully. From a more theoretical perspective, the study of robust combinatorial problems often makes use of selection-type problems (see, e.g., Averbakh 2001; Dolgui and Kovalev 2012; Deineko and Woeginger 2013; Kasperski etal. 2015). In the most basic form, the selection problem requires us to select p out of n possible items, i.e., to solve with known costs d d d∈ℝn + . While this nominal problem is trivial to solve, treating robust variants becomes more complex. A new perspective on problems of this type is to locate the uncertainty not (only) on the item costs; instead, items have different degrees of reliability, and an adversary tries to violate the constraint ∑i∈[n] x i ≥ p . Motivated by these two problems, but being applicable to a wider range of problems as well, the “budgeted interdiction” approach that we thus propose is to consider uncertainty sets of the form with w w w∈ℕn and B∈ℕ . The adversary can therefore interdict a solution (i.e., let items fail), but has a specified budget for this purpose. Throughout the paper, we assume that each wi is not larger than B; otherwise, its coefficient cannot be attacked and is therefore not uncertain. The uncertainty can affect a cardinality objective function (1 1 1−c c c)⊺x x x that should be maximized, or a cardinality constraint (1 1 1−c c c)⊺x x x ≥ p . Note that in the corresponding nominal problems, vector c c c is not present, but is introduced in the robust problem to model the uncertainty of the vector 1 1 1 . Cardinality constraints also play a role in many optimization problems that allow a cut-based formulation. For example, the shortest path problem can be written as min { d d d⊺x x x∶ ∑ i∈[n] xi≥p,x x x∈{0, 1}n } U = { c c c∈{0, 1}n∶ ∑ i∈[n] wici≤B } 1 As x x x is binary, it corresponds to a subset X of [n], where X={i∈[n]∶xi=1} . The notion of cardinality refers to �X�=‖x x x‖1 . 259 Robust combinatorial optimization problems underbudgeted… with S={S⊆V∶s∈S,t∉S} . Cut-based problem formulations are also used for the generalized Steiner tree, spanning tree, feedback vertex set, or traveling salesperson problems (Korte and Vygen 2018). Observe that this definition of uncertainty set is essentially the budgeted uncertainty set UΓ “upside down”: while UΓ has a bound on the number of coefficients that can deviate and the effect of deviation is given by some parameter ci −ci , here we want to maximize the number of deviations and each deviation has a cost parameter wi . Note that different to Uknap , there is a single budget constraint, we consider a discrete instead of continuous deviation, and in particular, the vector c c c is binary. As an example, consider the selection problem where the cardinality constraint ∑i∈[4] x i ≥ 1 is uncertain and thus can be attacked by an adversary. The cardinality constraint of the robust counterpart of this example becomes where the function 𝜙(x x x) represents the number of items that can fail. To further illustrate this setting, let us assume that that is, in the definition of U , we use B=10 and w=(3, 7, 4, 10)⊺ . A possible solution to the robust problem is to pick items 1, 2 and 3 at cost 2+3+4=9 . The adversary can attack items 1 and 3, but does not have sufficient budget to let all three items fail. An even better solution is to pick items 1 and 4 at cost 2+5=7 . In this case, the adversary can only attack one of the two items. The remainder of this paper is structured as follows. In Sect.2, we discuss the complexity of the robust problem with budgeted interdiction uncertainty, and prove that the problem is not approximable. Furthermore, we provide five compact formulations to solve problems with cardinality constraints under interdiction uncertainty set in Sect. 3. Experimental results illustrating the performance of the models for the selection, job assignment and 2-edge-connected subgraph problems are collected in Sect. 4. We summarize our findings and pointing out min ∑ i∈E dexe s.t. ∑ e∈𝛿(S) xe≥1∀S∈ S xe∈{ 0, 1 } min { 2x1+3x2+4x3+5x4∶ ∑ i∈[4] xi≥1,x x x∈{0, 1}4 } min c c c∈U(1 1 1−c c c)⊺x x x= ∑ i∈[n] xi−max c c c∈U c c c⊺x x x= ∑ i∈[n] xi−𝜙(x x x)≥ 1 𝜙 (x x x)=max {∑ i∈[n] xici∶3c1+7c2+4c3+10c4≤10, c c c∈{0, 1}4 } 260 M.Goerigk, M.Khosravi further research questions in Sect.5. The detailed information on how to model the compact formulation of both job assignment and cut-based problems are provided in AppendixA and B, respectively. 2 Complexity analysis In order to check the complexity level of the robust selection problem under interdiction budgeted uncertainty, we first need to introduce the compact formulation of it, thus we have where the adversary problem is for a given x x x∈{0, 1}n . There is a trivial algorithm to solve this problem; namely, we sort items i with xi=1 by non-decreasing weight wi , and pack items in this order until the budget B cannot accommodate any further items. Hence, the adversarial problem can be solved in O(n) time (as it is not necessary to sort the complete vector, see, e.g. (Korte and Vygen 2018, Chapter 17.1). Now we show that the decision version of the robust selection problem with interdiction uncertainty affecting the constraints (ROSel) is hard. Theorem1 The following decision problem is NP-complete: Given d d d∈ℕn , w w w∈ℕn , B∈ℕ , and V∈ℕ , is there a vector x x x∈{0, 1}n with ∑i∈[n] x i −𝜙(x x x)≥ 1 and ∑i∈[n] d i x i ≤V? Proof Observe that it is trivial to check if ∑i∈[n] x i− 𝜙 ( x x x ) ≥ 1 and ∑i∈[n] d i x i ≤V for a given x x x , which means that the decision problem is indeed in NP. To show NP-completeness, we make use of the partition problem: Given positive integers v1,…,vn , is there a set S⊆[n] such that ∑i∈S v i= V with V=∑i∈[n] v i∕2 ? Given such an instance of the partition problem, we construct a robust problem with budgeted interdiction in the following way. Set di=wi=vi and B=V−1 . Then the constraint with min ∑ i∈[n] dixi s.t. ∑ i∈[n] xi−𝜙(x)≥p∀c∈U x∈{ 0, 1 } n 𝜙 (x x x)=max {∑ i∈[n] xici∶ ∑ i∈[n] wici≤B,ci∈{0, 1}∀i∈[n] } ∑ i∈[n] xi−𝜙(x x x)≥ 1 261 Robust combinatorial optimization problems underbudgeted… requires us to pack items of total weight strictly greater than V−1 to avoid having all items interdicted. This means that the partition problem is a Yes-instance if and only if there is a feasible solution x x x∈{0, 1}n with objective value less or equal to V. As the partition problem is well-known to be NP-complete (Garey and Johnson 1979), the claim follows. ◻ This brief analysis shows that we lose a main advantage of classic budgeted uncertainty, where the robust problem can be decomposed into a set of nominal problems. Note that Theorem1 applies to optimization problems with an uncertain cardinality constraint and an objective ∑i∈[n] d i x i that should be minimized, but it also applies to the case of having one linear constraint ∑i∈[n] d i x i ≤ V and an uncertain cardinality objective that should be maximized. In particular, in the latter case this means that it is NP-complete to find a solution with a non-zero objective value; in other words, it is not possible to find a polynomial-time approximation algorithm for this setting, unless P = NP. Hence we conclude the following result. Corollary 2 The optimization problem maxx x x∈ Xmin c c c∈ U ∑i∈[n] (1−c i )x i is not approximable, even if maxx x x∈ X ∑i∈[n] x i can be solved in polynomial time. Proof Given a partition problem as in the proof of Theorem 1, set X={ x x x ∈{0, 1}n∶∑i∈[n] v i x i ≤V } . Then there is a solution with objective value greater or equal to one if and only if the partition problem is a Yes-instance. Hence, there cannot be an 𝛼 -approximation for any 𝛼>0 , unless P = NP. ◻ 3 Model formulations In this section, we introduce five compact formulations of the robust problem, where we focus on an uncertain cardinality constraint ∑i∈[n] x i ≥ p for ease of presentation. Additional constraints on x x x may be considered, which are assumed to be modeled indirectly in the set X⊆{0, 1}n . That is, we consider reformulations of the following type of robust problem with cardinality constraints: where the nominal problem corresponds to the case c c c=0 0 0 . In addition, without loss of generality, we assume that the items are sorted based on their weights ( wi ), non-decreasingly. 𝜙 (x x x)=max {∑ i∈[n] xici∶ ∑ i∈[n] vici≤V−1 } min ∑ i∈[n] dixi s.t. ∑ i∈[n] (1−ci)xi≥p∀c c c∈U x x x∈X 262 M.Goerigk, M.Khosravi 3.1 IP‑1 The first idea to find a compact formulation of the problem is only applicable to the case p=1 with integer weights w w w . This means we only need to have one item after the adversary attacks, a case that remains hard, as Theorem1 shows. Therefore, it suffices to pack items with minimum cost whose total weight strictly exceeds the adversarial budget B. This idea can be formulated as follows: 3.2 IP‑2 We now consider the general case of arbitrary values for p. As noted, the adversarial problem 𝜙(x x x) can be solved in polynomial time by packing items with smallest weight first. Therefore, we introduce variables 𝜆k∈{0, 1} for all k∈[n] , where 𝜆k is active if and only if we attack the first k items (note that the case k=0 can be ignored, as we can always attack at least one item, due to each wi being not larger than B). An attack only incurs costs on the interdiction budget if xi=1 . Hence, we obtain the following integer program: By Constraint(3), we can only choose one of the candidate attacks represented by 𝜆k . Due to Constraint(2), we cannot use attack 𝜆k if ∑i∈[k] w i x i > B . It is easy to see that we can relax the integrality constraints of 𝜆k , which gives an LP formulation for 𝜙(x x x) . By using linear programming duality, we thus can obtain the formulation for the robust problem under budgeted interdiction uncertainty: min ∑ i∈[n] dixi (IP-1) s.t. ∑ i∈[n] wixi≥B+1 x x x∈X (1) 𝜙 (x x x)=max ∑ k∈[n] ( ∑ i∈[k] xi)𝜆 k (2) s.t.(∑ i∈[k] wixi−B ) 𝜆k≤0∀k∈[n ] (3) ∑ k∈[n] 𝜆k≤ 1 (4) 𝜆k∈{0, 1}∀k∈[n] 269 Robust combinatorial optimization problems underbudgeted… We use two techniques to generate instances for the selection problem under budgeted interdiction uncertainty, called Gen-1 and Gen-2. In Gen-1, the weights are chosen independently from the corresponding costs, which meanst that there may be both particularly good items (with low ci and high wi ) and bad items. In Gen-2, the weight of items depend on their costs, which intuitively may lead to harder instances compared to Gen-1. The generation methods are considered as follows: • Gen-1: for each i∈[n] we choose di,wi from {1, …, 100} independently random uniform • Gen-2: for each i∈[n] the value of wi depends on the value of di , thus we choose di from {1, …, 100} and wi from {max(1, di−5),…, min(100, di+5)} randomly uniform In both cases, we set 4.1.2 Experiment 1 Here we focus on the LP-relaxation of all models and compare the lower bounds obtained by each of them. In this experiment we fix n=10 and p=1 to include all models. We solve the LP relaxations of 1000 instances for each combination of generation and solution methods using CPLEX. We then perform a pairwise comparison of the resulting lower bounds. B = �∑ i∈[n]wi 4 � Table 2 LB comparison (Gen1)IP-1 IP-2 IP-3 IP-4 IP-5 % IP-1 – 979 967 993 983 98.05 IP-2 21 – 5 368 92 12.15 IP-3 33 982 – 878 412 57.63 IP-4 7 628 118 – 9 19.05 IP-5 17 898 575 987 – 61.93 Table 3 LB comparison (Gen2)IP-1 IP-2 IP-3 IP-4 IP-5 % IP-1 – 1000 999 1000 1000 99.98 IP-2 0 – 0 999 586 39.63 IP-3 1 1000 – 1000 1000 75.03 IP-4 0 1 0 – 0 0.03 IP-5 0 414 0 1000 – 35.35 270 M.Goerigk, M.Khosravi The results of this experiment is presented in Tables 2 and 3 for Gen-1 and Gen-2, respectively. Each number shows how many times the method in the respective row provided a strictly better (in this case higher) lower bound than the model in the correspondence column. The last column shows the average of cases per row where the model has been better then the comparison model in percent. Based on the information provided in Table 2 for Gen-1, we note that IP-1 dominates all other models in over 98% of cases (which is not surprising, as it is the most specialized model). The next best model is IP-5, followed by IP-3. With some gap behind these two models follow IP-4 and IP-2. The weakest model, IP-2, is stronger than another model in only around 12% of cases. Interestingly, this ordering changes when using instances of type Gen-2, see Table3. While IP-1 still outperforms other models other models in nearly all cases (over 99%), the second best model is IP-3, which performs relatively better than before. Similarly, IP-2 has improved in the ranking, while IP-5 (which was the second best choice in Table2 is now relegated to fourth place. IP-4 can provide a better bound than another model in only one single instance. 4.1.3 Experiment 2 In this experiment, we vary the problem size in n∈{20, 25, …, 100} . The experiment is divided into two parts. In the first part, we fix p to 1 so that all solution methods could be included, and also consider p=5 to compare the performance of solution methods which can be applied to cases where p>1 . In the second part, we use p =n 5 so that p grows linearly in n. For each combination of generation and solution methods we solved 50 instances using CPLEX and with a 600s time limit. We always present a plot of average solution times and a performance profile. Figure1 shows the solution times for p=1 . Clearly, IP-1 is the fastest model to solve instances for both Gen-1 and Gen-2, followed by IP-3. Other models also show similar behavior for both generation methods. Interestingly, IP-2 may even become faster as n increases, which seems counterintuitive, but can be explained by 0.001 0.01 0.1 1 10 100 1000 20 30 40 50 60 70 80 90 100 Solution Time Size of (n) IP1 IP2 IP3 IP4 IP5 (a) Gen-1 0.001 0.01 0.1 1 10 100 1000 20 30 40 50 60 70 80 90 100 Solution Time Size of (n) IP1 IP2 IP3 IP4 IP5 (b) Gen-2 Fig. 1 Selection—Exp2—solution times ( p=1 ) 271 Robust combinatorial optimization problems underbudgeted… the fact that p remains constant. The performance profiles (see Fig.2) reflect a similar relative performance of the five models. In Figs.3 and 4, we show the average solution times and performance profiles for the case p=5 , where IP-1 is not included. A similar behavior to the cases when p=1 can be seen. As IP-1 is excluded, here IP-3 has the best average solution time. 0 0.2 0.4 0.6 0.8 1 1.2 1 4 16 64 256 1024 Time Performance Ratio IP1 IP2 IP3 IP4 IP5 (a) Gen-1 0 0.2 0.4 0.6 0.8 1 1.2 1 4 16 64 256 1024 Time Performance Ratio IP1 IP2 IP3 IP4 IP5 (b) Gen-2 Fig. 2 Selection—Exp2—performance profiles ( p=1 ) 0.001 0.01 0.1 1 10 100 1000 20 30 40 50 60 70 80 90 100 Solution Time Size of (n) IP2 IP3 IP4 IP5 (a) Gen-1 0.001 0.01 0.1 1 10 100 1000 20 30 40 50 60 70 80 90 100 Solution Time Size of (n) IP2 IP3 IP4 IP5 (b) Gen-2 Fig. 3 Selection—Exp2—solution times ( p=5 ) 0 0.2 0.4 0.6 0.8 1 1.2 1 4 16 64 256 1024 Time Performance Ratio IP2 IP3 IP4 IP5 (a) Gen-1 0 0.2 0.4 0.6 0.8 1 1.2 1 4 16 64 256 1024 Time Performance Ratio IP2 IP3 IP4 IP5 (b) Gen-2 Fig. 4 Selection—Exp2—performance profiles ( p=5 ) 272 M.Goerigk, M.Khosravi The difference is that IP-3 fails to be faster than IP-5 for instances with smaller size of n. Similarly, in the performance profile, IP-3 dominates other models. The main difference compared to the case with p=1 is that none of the models is always superior to others. We now consider the case p= n 5 , i.e., p grows linearly with n. The average solution times and performance profiless of this experiment are presented in Figs.5 and 6, respectively. The results of the second part is closely similar to the first part results when p=5 . That is, IP-3 beats all formulations except IP-5 with n=20, 30, 40 for Gen1 and n=20, 30 for Gen-2. In addition, the behavior of IP-2 and IP-4 is similar, however their comparison is difficult because of the time limit. In this experiment, IP-4 has better solution time than IP-2 for Gen-1, but for Gen-2, IP-2 is slightly faster than IP-4. 4.1.4 Experiment 3 In this experiment, we fix the number of items n and change the number of items we want to select p. We consider the cases n=20 and n=40 . In both cases, p is chosen 0.01 0.1 1 10 100 1000 20 30 40 50 60 70 80 90 100 Solution Time Size of (n) IP2 IP3 IP4 IP5 (a) Gen-1 0.01 0.1 1 10 100 1000 20 30 40 50 60 70 80 90 100 Solution Time Size of (n) IP2 IP3 IP4 IP5 (b) Gen-2 Fig. 5 Selection—Exp2—solution times ( p = n ∕5 ) 0 0.2 0.4 0.6 0.8 1 1.2 1 4 16 64 256 1024 Time Performance Ratio IP2 IP3 IP4 IP5 (a) Gen-1 0 0.2 0.4 0.6 0.8 1 1.2 1 4 16 64 256 1024 Time Performance Ratio IP2 IP3 IP4 IP5 (b) Gen-2 Fig. 6 Selection—Exp2—performance profiles ( p=n∕5 ) 273 Robust combinatorial optimization problems underbudgeted… from {1, 2, …, 10} . As before, we solved 50 instances using CPLEX with a 600-second time limit for each combination of generation and solution methods. The results of this experiment is provided in Figs.7, 8, 9 and 10. 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 Solution Time Size of (p) IP2 IP3 IP4 IP5 (a) Gen-1 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 Solution Time Size of (p) IP2 IP3 IP4 IP5 (b) Gen-2 Fig. 7 Selection—Exp3—solution times ( n=20 ) 0 0.2 0.4 0.6 0.8 1 1.2 1 4 16 64 256 1024 Time Performance Ratio IP2 IP3 IP4 IP5 (a) Gen-1 0 0.2 0.4 0.6 0.8 1 1.2 1 4 16 64 256 1024 Time Performance Ratio IP2 IP3 IP4 IP5 (b) Gen-2 Fig. 8 Selection—Exp3—performance profiles ( n=20 ) 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 Solution Time Size of (p) IP2 IP3 IP4 IP5 (a) Gen-1 0.01 0.1 1 10 100 1000 1 2 3 4 5 6 7 8 9 10 Solution Time Size of (p) IP2 IP3 IP4 IP5 (b) Gen-2 Fig. 9 Exp3, solution times for n=40 274 M.Goerigk, M.Khosravi Interestingly, the experiment for instances with n=20 shows that IP-2, IP-3 and IP-4 are dominated by IP-5 except for p=1 for both Gen-1 and Gen-2. In this single case, IP-5 is outperformed by IP-3. This experiment shows that the problem solved faster for larger value of p. This can be explained by the observation that for larger values of p, nearly all items need to be selected (recall that we need to pack more than p items to respect the uncertainty). Similar to other experiments, the performance profile (see Fig.8) represents the obtained results for the average solution times also holds for the instance-wise comparisons of the given models. The results depicted in Figs.9 and 10 show that the problems first tend to become harder to solve and then the solution time falls. Notably, unlike the case with n=20 , IP-3 has the best performance with regard to the solution time. Another difference is that IP-3 is always superior in comparison to the other mathematical formulations. In this case the problem in considerably harder to solve than cases with n=20 . In this sense, the problem hits the time limit even for p=1 , while IP-3 never reaches even close to the time limit. The performance profile shows that IP-3 is almost always faster than other IPs. 4.2 Job assignment 4.2.1 Setup We now consider a job assignment problem with m jobs and n workers. Each job has a profit pj and workers demand of dj for all j∈[m] . Here, instead of weights for each item in the selection problem, we have a failure probability for each worker wi for all i∈[n] . Therefore, the robust job assignment problem under the budgeted interdiction uncertainty can be formulated as follows 0 0.2 0.4 0.6 0.8 1 1.2 1 4 16 64 256 1024 Time Performance Ratio IP2 IP3 IP4 IP5 (a) Gen-1 0 0.2 0.4 0.6 0.8 1 1.2 1 4 16 64 256 1024 Time Performance Ratio IP2 IP3 IP4 IP5 (b) Gen-2 Fig. 10 Selection—Exp3—performance profiles ( n=40 ) 275 Robust combinatorial optimization problems underbudgeted… In this case and in order to see the performance of our IPs over the job assignment problem, we only consider IP-2, IP-3, IP-4 and IP-5. The compact formulations of these four IPs are collected in “Appendix A”. Furthermore, we introduce two experiments, where in experiment 1 we fix the number of jobs and change the number of workers; while in experiment2 we fix the number of workers and vary the number of jobs. Similar to the experiments on the selection problem, we use two types of instance generation methods for the job assignment problem under budgeted interdiction uncertainty, called Gen-1 and Gen-2. In Gen-1, the job demands are chosen independently from the corresponding profits. In Gen-2, however, the profits of jobs depend on their demands. The generation methods are considered as follows: Gen-1 • for each i∈[m] we choose di from { 1, …, 2n m} independently random uniform. • for each i∈[m] we choose pi from {1, …, 25} independently random uniform. Gen-2 • for each i∈[m] we choose di from { 1, …, 2n m} independently random uniform. • for each i∈[m] the value of pi depends on the value of di . If d i≤ n m then pi is chosen from {1, …, 25} , otherwise we choose pi from {10, …, 34} randomly uniform. In both cases, we choose wi from {101, …, 150} randomly uniform for all i∈[n] . Then we set 4.2.2 Experiment 1 In this experiment, we fix the number of jobs (m) and change the number of workers (n). To this end, we consider the case when m=5 and n={5, 10, …, 40} . For each combination we solve 50 instances with a time limit of 600s and show the average solution times. The results of this experiment is provided in Figs.11 and 12. max ∑ j∈[m] pj zj s.t. ∑ i∈[n] (1−ci)xij ≥dj zj∀j∈[m],c c c∈U ∑ j∈[m] xij ≤1∀i∈[n] x ij ,z j ∈{0, 1} B = �∑ i∈[n] 2w i n � 276 M.Goerigk, M.Khosravi The solution times presented in Fig. 11 show that all introduced IPs perform similarly over the given generation methods. It can be seen that the problem constantly tends to be harder to solve from n=5 to n=30 and then solution times for all IPs decrease slightly. Here, IP-4 and IP-5 (which is one of the best also for the selection problem) are the fastest IPs. The reason is they have fewer number of constraints. Like the solution times, Fig.12 illustrates that IP-5 leads to the best performance profile, meaning that for most of instances it is the fastest IP following by IP-4. In this setting IP-2 is the worst IP in terms of solution times. 4.2.3 Experiment 2 In the second experiment of the job assignment problem, we fix the number of workers ( n=20 ) and change the number of jobs ( n={2, 3, …,9} ). Similarly, for each given combination we solve 50 instances with a time limit of 600s and show 0.001 0.01 0.1 1 10 100 1000 5 10 15 20 25 30 35 40 Solution Time Number of workers (n) IP-2 IP-3 IP-4 IP-5 (a) Gen-1 0.001 0.01 0.1 1 10 100 1000 5 10 15 20 25 30 35 40 Solution Time Number of workers (n) IP-2 IP-3 IP-4 IP-5 (b) Gen-2 Fig. 11 Job assignment—Exp1—solution times ( m=5 ) 0 0.2 0.4 0.6 0.8 1 1.2 1 4 16 64 256 1024 Time Performance Ratio IP-2 IP-3 IP-4 IP-5 (a) Gen-1 0 0.2 0.4 0.6 0.8 1 1.2 1 4 16 64 256 1024 Time Performance Ratio IP-2 IP-3 IP-4 IP-5 (b) Gen-2 Fig. 12 Job assignment—Exp1—performance profiles m=5 277 Robust combinatorial optimization problems underbudgeted… the average solution times. The time performance of this experimental setting is shown in Figs.13 and 14. Here, again the same trend as experiment 1 (4.2.2) can be observed in terms of both solution times and the corresponding performance profile. The results of the introduced generation methods are equivalent. However, the drop of the solution times for the larger case of instances are less noticeable. Likewise, IP-5 has both the best average and instance-wise solution times and the slowest IP is again IP-2. 4.3 2‑Edge‑connected spanning subgraph 4.3.1 Setup In the NP-hard 2-edge-connected spanning subgraph problem, an undirected graph G=(V,E) is given with edge weights d d d ∈ℝ |E| + . The objective is to find a subset of edges E′ with minimum weight such that G[E�] is 2-edge-connceted, i.e., there are two edge-disjoint paths between any pair of nodes (see, e.g., Woonghee 2004). We 0.001 0.01 0.1 1 10 100 1000 2 3 4 5 6 7 8 9 Solution Time Number of jobs (m) IP-2 IP-3 IP-4 IP-5 (a) Gen-1 0.001 0.01 0.1 1 10 100 1000 2 3 4 5 6 7 8 9 Solution Time Number of jobs (m) IP-2 IP-3 IP-4 IP-5 (b) Gen-2 Fig. 13 Job assignment—Exp2—solution times n=20 0 0.2 0.4 0.6 0.8 1 1.2 1 4 16 64 256 1024 Time Performance Ratio IP-2 IP-3 IP-4 IP-5 (a) Gen-1 0 0.2 0.4 0.6 0.8 1 1.2 1 4 16 64 256 1024 Time Performance Ratio IP-2 IP-3 IP-4 IP-5 (b) Gen-2 Fig. 14 Job assignment—Exp2—performance profiles n=20 278 M.Goerigk, M.Khosravi consider a robust version where edges can fail, but the subgraph is still required to remain 2-edge-connected. The nominal problem can be formulated as follows: where C denotes the set of all cuts in the graph G. As there are exponentially many constraints, we use an iterative procedure. In “Appendix B”, we describe models IP-2, IP-3, IP-4 and IP-5 for a subset C′⊆C of cuts. We begine with C�=� , solve the corresponding formulation, and check if the resulting solution x x x is feasible with respect to all cuts C . To check if a cut is violated, we solve the following IP: If a violated cut can be found, it is added to C′ , and the robust problem is solved again, until convergence is reached. We introduce one experiment where the number of nodes of the given graph vary. We also set the density (D) of the graph equal to 0.8. Unlike the experiments on both the selection and job assignment problem, we just introduce on approach of instance generation for the cut based problem under budgeted interdiction uncertainty. In this case our graph has n nodes and m edges, where m =D× n(n−1) 2 . Here, for each e∈E we choose de from {1, …, 10} and we from {5, …, 10} randomly uniform. Moreover, we set B=15 . 4.3.2 Experiment In the only experiment of the cut based problem, we change the number of nodes and thus choose n from {10, 12, …, 30} . Similarly, for each instance size we solve 50 instances with a time limit of 600s and show the average solution times. The time performance of this experimental setting is shown in Fig.15. min ∑ {i,j}∈E dijxij s.t. ∑ {i,j}∈C xij ≥2∀C∈C x ij ∈{0, 1} ∀{i,j}∈E min ∑ e∈E ye+𝜖ze s.t. zij ≥ui−uj∀{i,j}∈ E zij ≥uj−ui∀{i,j}∈ E 1≤∑ i∈[n] ui≤n−1 ye≥xe+ze−ce−1∀e∈ E ∑ e∈E wece≤B yi,ci,zi∈{0, 1 }∀ i∈[m ] ui∈{ 0, 1 }∀i∈[n] 285 Robust combinatorial optimization problems underbudgeted… Bruns F, Goerigk M, Knust S, Schöbel A (2014) Robust load planning of trains in intermodal transportation. OR Spectrum 36(3):631–668 Buchheim C, Kurtz J (2018) Robust combinatorial optimization under convex and discrete cost uncertainty. EURO J Comput Optim 6(3):211–238 Büsing C, D’andreagiovanni F (2012) New results about multi-band uncertainty in robust optimization. In: International symposium on experimental algorithms, pp 63–74. Springer Deineko VG, Woeginger GJ (2013) Complexity and in-approximability of a selection problem in robust optimization. 4OR 11(3):249–252 Dolan Elizabeth D, Moré Jorge J (2022) Benchmarking optimization software with performance profiles. Math Program 91:201–213 Dolgui A, Kovalev S (2012) Min–max and min–max (relative) regret approaches to representatives selection problem. 4OR 10(2):181–192 Garey MR, Johnson DS (1979) Computers and intractability. W. H. Freeman and Company, New York Goerigk M, Kasperski A, Zieliński P (2022) Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty. J Comb Optim 43(3):497–527 Goerigk M, Lendl S (2021) Robust combinatorial optimization with locally budgeted uncertainty. Open J Math Optim 2:1–18 Goerigk M, Lendl S, Wulf L (2022) On the complexity of robust multi-stage problems in the polynomial hierarchy. arXiv preprint arXiv: 2209. 01011 Goerigk M, Schöbel A (2016) Algorithm engineering in robust optimization. In: Algorithm engineering, pp 245–279. Springer Kail P, Mayer J (2005) Stochastic linear programming, models, theory, and computation. Springer, New York Kasperski A, Kurpisz A, Zieliński P (2015) Approximability of the robust representatives selection problem. Oper Res Lett 43(1):16–19 Kasperski A, Zieliński P (2016) Robust discrete optimization under discrete and interval uncertainty: a survey. In: Robustness analysis in decision aiding, optimization, and analytics, pp 113–143. Springer Korte B, Vygen J (2018) Combinatorial optimization. Algorithms and combinatorics. Springer, Berlin Lodwick WA, Kacprzyk J (2010) Fuzzy optimization: recent advances and applications, vol 254. Springer, Berlin Poss M (2013) Robust combinatorial optimization with variable budgeted uncertainty. 4OR 11(1):75–92 Poss M (2018) Robust combinatorial optimization with knapsack uncertainty. Discret Optim 27:88–102 Tim Huh W (2004) Finding 2-edge connected spanning subgraphs. Oper Res Lett 32(3):212–216 Yaman H (2023) Short paper-a note on robust combinatorial optimization with generalized interval uncertainty. Open J Math Optim 4:1–7 Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.