title: Robust Combinatorial Optimization with Locally Budgeted Uncertainty
authors: Marc Goerigk Stefan Lendl
text: 
  
  
  Identifying and Tracking Solar Magnetic Flux Elements with Deep Learning
      Haimin Wang
      December 30, 2023
  ========================================================================
  
  
  
  
  
   
  Budgeted uncertainty sets have been established as a major influence on uncertainty modeling for robust optimization problems. A drawback of such sets is that the budget constraint only restricts the global amount of cost increase that can be distributed by an adversary. Local restrictions, while being important for many applications, cannot be modeled this way.
  
  We introduce new variant of budgeted uncertainty sets, called locally budgeted uncertainty. In this setting, the uncertain parameters become partitioned, such that a classic budgeted uncertainty set applies to each partition, called region.
  
  In a theoretical analysis, we show that the robust counterpart of such problems for a constant number of regions remains solvable in polynomial time, if the underlying nominal problem can be solved in polynomial time as well. If the number of regions is unbounded, we show that the robust selection problem remains solvable in polynomial time, while also providing hardness results for other combinatorial problems.
  
  In computational experiments using both random and real-world data, we show that using locally budgeted uncertainty sets can have considerable advantages over classic budgeted uncertainty sets.
  
  
  Keywords: robust optimization; combinatorial optimization; budgeted uncertainty
  
  
  
  
  § INTRODUCTION
  
  
  
  
  We consider nominal combinatorial optimization problems of the form
  
      min    c^t x
      s.t.    x∈
  
  where ⊆{0,1}^n is the set of feasible solutions. For uncertain cost coefficients c∈, robust optimization approaches have been analyzed. To this end, one assumes that a set  of possible cost realizations is given by a decision maker or derived from historical data. The set  is referred to as the uncertainty set. The (min-max) robust counterpart is then to solve
  
      min_x∈ max_c∈ c^t x
  
  Different possibilities to model the set  have been proposed. One straight-forward possibility is to use a discrete set of scenarios = {c^1,…,c^N}, i.e., to list all possible outcomes explicitly. While this approach is flexible, it usually results in NP-hard robust optimization problems, even if the nominal problem can be solved in polynomial time (see <cit.> for overviews). Also, implicit descriptions of the uncertainty set can lead to exponential-sized equivalent discrete uncertainty sets.
  
  A popular alternative are budgeted uncertainty sets of the form
  
      = {c = c + δ : δ_i∈[0,d_i] ∀ i∈[n], ∑_i∈[n]δ_ i ≤Γ}
  
  as first introduced in <cit.>. Here we use the notation [n]={1,…,n}. For every item i∈[n], we are given a lower bound on the costs c_i, as well as a possible maximum cost deviation d_i. Additionally, there is a budget Γ on the total increase of costs over the lower bound. Advantages of this set include its intuitive
  description for a decision maker, and that robust counterparts remain efficiently solvable for nominal problems that can be solved efficiently, even though the budgeted uncertainty set has an exponential number of extreme points. These benefits have lead to a substantial amount of research into robust optimization problems with budgeted uncertainty sets, see, e.g., <cit.> and many more.
  
  But there are also limitations to this approach, which has lead to the development of alternative uncertainty sets. These include multi-band uncertainty <cit.>, variable budgeted uncertainty <cit.>, and knapsack uncertainty <cit.>.
  
  To the best of our knowledge, no previous work has considered avoiding the potential problem that the constraint ∑_i∈[n]δ_ i ≤Γ denotes a global budget over all uncertain parameters. For various applications, multiple local budgets are more desirable. As examples, consider
   multi-period problems, where every period has its own budget limitation,
  routing problems, where separate budgets apply to geographic regions or types of roads,
  and portfolio problems, where uncertainty budgets are restricted to asset classes or sectors.
  
  In this paper we introduce a new type of budgeted uncertainty set, where budgets
  apply locally to their respective regions. These sets are of the form
  
      = {c = c + δ : δ_i ∈ [0,d_i] ∀ i∈[n], ∑_i∈ P_jδ_i ≤Γ_j ∀ j∈[K] }
  
  where P_1∪ P_2 ∪…∪ P_K = [n] denotes a partition of the items. Each set P_j is called a region. In this approach, every region has a separate budget constraint, which models the
  local uncertainty. Note that this definition of uncertainty is a generalization of the classic definition (<ref>), which can be recovered by using K=1.
  
  Our contributions are as follows. For min-max problems with locally budgeted uncertainty, we first derive a compact formulation in Section <ref>. Based on this formulation, we then consider the case of a constant number of regions in Section <ref>. We show that the robust problem remains solvable in polynomial time, if it is possible to solve the nominal problem in polynomial time. For an unbounded number of regions, the selection problem remains solvable in polynomial time, while this is not the case for the representative selection problem (see Section <ref>). We conclude that also the spanning tree problem, the s-t-min-cut problem, and the shortest path problem become NP-hard. Additionally, we can exclude the possibility of parameterized algorithms with running time in O^*(2^o(K)). In Section <ref>, we present three computational experiments using locally budgeted uncertainty sets. In all experiments, we compare locally budgeted uncertainty to the classic budgeted uncertainty approach. While the first two experiments use randomly generated data, the third experiment is based on real-world data for robust shortest path problems. Section <ref> concludes the paper and points out further questions.
  
  
  
  § THEORETICAL RESULTS
  
  
  
  
  
  
   §.§ A Compact Formulation
  
  
  
  Let some solution x∈ be fixed. Its objective value is then determined by solving the adversarial problem
  
      max_c∈ c^tx
  
  that is, by choosing a scenario c that maximizes the costs of x. Using the definition of locally budgeted uncertainty, this is equivalent to solving the following linear program:
  
      max    ∑_i∈[n] (c_i + δ_i) x_i 
      s.t.    ∑_i∈ P_jδ_i ≤Γ_j    ∀ j∈[K] 
         δ_i ≤ d_i    ∀ i∈[n] 
         δ_i ≥ 0     ∀ i∈[n]
  
  By strong duality, we can dualize this linear program to find another linear program with the same optimal objective value. Furthermore, any feasible solution to the dual problem gives an upper bound to the objective value of the primal problem. Using the dual, we hence find the following compact problem formulation for the min-max problem with locally budgeted uncertainty.
  
      min    ∑_j∈[K]( Γ_j π_j + ∑_i∈ P_j d_i ρ_i + ∑_i∈ P_jc_i x_i ) 
      s.t.    π_j + ρ_i ≥ x_i    ∀ j∈[K], i∈ P_j 
         π_j ≥ 0    ∀ j∈ [K] 
         ρ_i ≥ 0    ∀ i∈[n] 
         x∈
  
  Recall that  represents the set of feasible solutions for the underlying combinatorial problem. Variables π_j are the duals of Constraints (<ref>), and variables ρ_i are the duals of Constraints (<ref>).
  
  
  
  
   §.§ Constant Number of Regions
  
  
  
  We first consider the case that the number of regions K is a constant value.
  
  
  Note that, in an optimal solution, we can assume that ρ_i = [x_i - π_j]_+, where [y]_+=max{0,y} denotes the positive part of y. 
  
  
  There is an optimal solution to Problem (<ref>-<ref>), where π_j ∈{0,1} for all j∈[K].
  
  
  Let us assume that x∈ is fixed. Let X = { i∈[n] : x_i = 1} denote the set of items taken by solution x. The problem then decomposes to:
  
      min_π≥0∑_j∈[K]( Γ_j π_j + ∑_i∈ P_j d_i ρ_i + ∑_i∈ P_jc_i x_i ) 
      
      =    ∑_i∈[n]c_i x_i + 
      ∑_j∈[K]min_π_j ≥ 0( Γ_jπ_j + ∑_i∈ P_j d_i[x_i - π_j]_+ ) 
      
      =    ∑_i∈ Xc_i 
      + ∑_j∈[K]min_π_j ∈[0,1]( Γ_jπ_j + ∑_i∈ P_j∩ X d_i(1 - π_j) )
  
  Note that the equivalence (<ref>) follows as increasing any variable π_j beyond 1 can never be optimal for Γ_j > 0. If Γ_j=0, then setting π_j=1 gives the same value as setting π_j > 1.
  We can conclude that there is an optimal solution with π_j ∈{0,1} for all j∈[K]. 
  
  
  
  The robust problem with locally budgeted uncertainty (<ref>-<ref>) can be decomposed into 2^K subproblems of nominal type. In particular, if K is a constant and the nominal problem can be solved in polynomial time, Problem (<ref>-<ref>) can be solved in polynomial time as well.
  
  
  By Lemma <ref>, we can assume every variable π_j to be either 0 or 1. We guess these values. There are K variables π_j, and thus 2^K combinations are possible. For fixed π=(π_1,…,π_K), denote by Π⊆[K] the set of indices j where π_j=1. The problem then becomes
  
      min_x∈∑_j∈[K]( Γ_j π_j + ∑_i∈ P_j d_i [x_i - π_j]_+ + ∑_i∈ P_jc_i x_i ) 
      
      =    ∑_j∈ΠΓ_j 
      + min_x∈( ∑_j∈Π∑_i∈ P_jc_i x_i + ∑_j∈ [K]∖Π∑_i∈ P_j (c_i + d_i) x_i )
  
  This is a problem of nominal type, and the claim follows.
  
  
  
  
  
  
  
  
  
   §.§ Unbounded Number of Regions
  
  
  
  We now consider the case that the number of regions K is not a constant, but part of the problem input.
  
  
  
    §.§.§ Hardness Results
  
  
  We first consider the representative selection problem, where
  
      = {x∈{0,1}^n : ∑_i∈ T_ℓ x_i = p_ℓ ∀ℓ∈ [L] }
  
  for a partition T_1∪ T_2 ∪… T_L = [n] and integers p_ℓ for all ℓ∈[L] (see, e.g., <cit.>).
  
  
  The robust representative selection problem with locally budgeted uncertainty and arbitrary K is APX-hard, 
  even if |T_ℓ| = 2, p_ℓ=1 for all ℓ∈[L], and the for the regions it holds
  that |P_j| ≤ 3 for all j ∈ [K].
  
  
  We reduce from an instance of the vertex cover problem, which is
  APX-hard, even on 3-regular graphs <cit.>.
  
  Given: Graph G=(V,E) 3-regular, k ∈
  
  Question: Does there exist a vertex cover of size less or equal to k, i.e. a set S ⊆ V such that for all
              e={u,v}∈ E it holds that u ∈ S or v ∈ S, and |S| ≤ k?
  
      
  
      Given such an instance, we construct an instance of the robust representative
      selection problem with locally budgeted uncertainty fulfilling the
      restrictions stated in the theorem. In Figure <ref> we illustrate
      the reduction via an
      example for a concrete vertex cover instance.
      Let L = |E| and n=2|E|. 
      For each e = {u, v}∈ E let u_e,
      v_e be the two elements of [n] in T_e, which we associate with the two
      vertices u and v. Note that for every vertex v∈ V there exist degree of v many
      elements that are associated with this vertex, one corresponding to every edge
      incident to v.
      
      For our partition into regions of the locally budgeted uncertainty set, we use exactly those sets of elements
      that correspond to the same vertices in V, i.e. we define a region
      P_v = { v_e  e ∈ E, v  incident to e } for every v ∈
      V. 
      Note that these sets also form a partition of [n], and we have K=|V|. We further set Γ = 1, c =
      0 and d = 1.
  
      We show that there is a vertex cover of size at most k if and only if the
      constructed instance of the robust representative selection problem with
      locally budgeted uncertainty has a solution with objective value at most k.
      To see this we first prove the following claim.
      
          Given a feasible solution x of our instance of the robust representative
          selection problem, the robust objective value is equal to the number of
          regions P_v in which at least one element is selected, i.e.
          
      | { v ∈ V ∃ i ∈ P_v  with  x_i = 1 }|.
  
  
      
      [Proof of Claim]
          First observe that this value can be realized by the adversary by
          selecting for each region P_v with an element i ∈ P_v such that 
          x_i=1 an arbitrary such element i and set δ_i = 1. It
          is easy to see that this is a feasible solution for the adversary and
          the claimed objective value is reached.
  
          For the upper bound observe that it is only sensible to set 
          δ_i > 0 for i∈ [n] with x_i = 1. Hence by
          the definition of  we have that
  
          | { v ∈ V ∃ i ∈ P_v  with  x_i = 1 }|
          is an upper bound on the objective value of the adversary.
      
  
      Now given a vertex cover S of size k we construct a solution x by
      selecting in each T_e the element corresponding to the vertex in the
      vertex cover. If both vertices incident to e are in S we choose one of
      the two elements arbitrarily. Since |S|=k we select elements from at most
      k different regions P_v. Hence, by our claim the objective value of the
      robust representative selection problem is less or equal to k.
  
      Given a solution x to the robust representative selection problem
      with objective value k, we know by our claim that the elements selected by
      x are contained in exactly k different regions P_v_1, …,
      P_v_k.
      We define S to be the set corresponding
      to exactly those k different vertices, i.e. S = {v_1, …, v_k}. 
      Since for each T_e, e ∈ E one
      element is selected by x, also for every edge e at least one
      incident vertex is contained in S, hence S is a vertex cover of size
      k.
  
  
  
  
  The robust problem with locally budgeted uncertainty with arbitrary K is
  APX-hard for the shortest path problem on series-parallel graphs, for the minimum
  spanning tree problem, and for the s-t-min-cut problem, even if  
  for the regions it holds that |P_j| ≤ 3 for all j ∈ [K].
  
  
      The result for the shortest path and minimum spanning tree problem follows
      directly from Theorem <ref>. To see this, given an instance of
      the representative selection problem with |T_ℓ| = 2 and p_ℓ=1 for all ℓ∈ [L], we construct the graph G with vertex set V = {0,1,…,L}
      and edge set E consisting of parallel edges e_ℓ^1, e_ℓ^2 connecting vertex ℓ-1 with vertex ℓ for all ℓ∈ [L]. Here e_ℓ^1, e_ℓ^2 are in one-to-one correspondence with the two
      elements in T_ℓ. It is now easy to see that both spanning trees and paths
      from nodes 0 to L in G are in one-to-one correspondence with feasible
      solutions to the original representative selection problem.
      Using the same locally budgeted uncertainty set as for
      the representative selection problem, we find that objective values
      of corresponding solutions remain equal.
  
      To obtain the result for the s-t-min-cut problem, observe that the special instance
      of the representative selection problem is equivalent to the s-t-cut problem in a graph G
      where for each part ℓ∈ [L] of size 2 we add a special vertex v_ℓ in addition to 
      s and t and the path from s via v_ℓ to t. Then s-t-cuts correspond to selecting 
      one of the two edges from each of these paths.
  
  
  Note that the above reduction does not exclude the possibility of a
  parameterized algorithm with running time O^*(2^o(K)), even if we assume 
  the exponential time hypothesis (ETH), since
  the number of regions K in the reduction cannot be bounded by the solution
  size k of the vertex cover.
  In the following we give a direct linear parameterized reduction from 3-SAT
  to robust representative selection with locally budgeted uncertainty, which
  shows that the running time of our FPT meta-algorithm is essentially tight under
  ETH.
  
      Assuming ETH, there is no O^*(2^o(K)) time algorithm for the robust
      representative selection problem with locally budgeted uncertainty, even if
      |T_ℓ| ≤ 3 and p_ℓ=1 for all ℓ∈[L].
  
  
      We reduce from an instance of the well known 3-SAT problem.
      
  Given: A formula φ in 3-CNF with variables x_1, …,
              x_ñ and m̃ clauses, i.e.
              
      φ = (l_1,1∨ l_1,2∨ l_1,3) ∧…∧ (l_m̃,1∨
                  l_m̃,2∨ l_m̃,3),
  
              where the l are literals of the variables x.
          
  Question: Is there an assignment for x such that φ is
              true?
              
  
      
  
      The exponential time hypothesis (ETH) implies that there does not exist an algorithm to decide 3-SAT
      with running time 2^o(n), and is widely believed <cit.>.
      We define an instance of our robust problem on the element set [2 ñ
      + 3 m̃] in the following way. In Figure <ref> we illustrate
      the reduction via an
      example for a 3-SAT instance. The 
      partition of [2ñ+3m̃] for the representative selection problem consists of ñ +
      m̃ parts, one for each variable and clause. For each i ∈
      [ñ] the set T_i consists of two elements, an element e^T_i  and an element
      e^F_i. These parts are the variable gadgets and selecting e^T_i
      or e^F_i corresponds to setting x_i to true or false respectively.
      For each clause we create a part consisting of exactly three elements, i.e.
      for each j ∈ [m̃] the set T_ñ+j consists of the
      elements e^1_j, e^2_j and e^3_j.
      
      Using the locally
      budgeted uncertainty set and cost structure we will enforce that e^i_j
      can only be selected without inducing additional cost, 
      if the selection in the variable gadget corresponding
      to the variable of literal l_j,i corresponds to l_j,i being true.
      To this aim, we define the partition for the locally budgeted uncertainty
      set consisting of K = 2ñ regions P_i^T and P_i^F for each i
      ∈ [ñ]. Selecting an element inside region P_i^T or
      P_i^F corresponds to setting the variable x_i to true or false
      respectively.
      We set Γ_i^T = Γ_i^F = 1 for all i ∈ [ñ] and the
      costs to c = 0 and d = 1. In a
      similar way as in the proof of Theorem <ref>, one can prove the following claim.
      
          Given a feasible solution x of our instance of the robust representative
          selection problem, the robust objective value is equal to the number of
          regions in which at least one element is selected by x.
      
  
      Based on this, we show that φ is feasible, if and only if the
      objective value of our instance is ñ.
  
      Given a feasible assignment for φ we select in each variable gadget
      the corresponding element. Then, since φ is true, for each clause j
      ∈ [m̃] there is at least one literal l_j,i which is true. We
      select the corresponding element e^i_j in T_ñ+j. Observe
      that this selection uses exactly the ñ parts P_i^v where v
      is T if x_i is true and v is F if x_i is false.  Hence by our
      claim the objective value of this selection is ñ.
  
      For the other direction first observe, that the objective value of our
      instance cannot be smaller than ñ, since in every variable gadget
      one element must be chosen and each element e_i^v has its exclusive
      region P_i^v. Now assume that there is a selection with
      robust objective value ñ. Then by our claim for every i ∈
      [ñ] in exactly one of the two regions P_i^T and P_i^F
      an element of T_i is selected. Hence, the truth assignment to x_i
      induced by the selection in the variable gadget satisfies all the
      clauses, since otherwise in one of the clause gadgets we would have to
      select an element inside an additional region.
  
  
  This result is slightly weaker than Theorem <ref> in the
  sense that we cannot assume |T_ℓ| = 2 but only |T_ℓ| ≤ 3. The existence
  of a O^*(2^o(K)) time algorithm for this case is an open problem.
  
  
  
  Let k=max_ℓ∈[L] |T_ℓ| and Δ=max_j∈[K] |P_j|. Then the robust representative selection problem with locally budgeted uncertainty and arbitrary K inherits inapproximability results from the set cover problem with maximum cardinality of subsets Δ, and maximum number k of subsets containing any element of the ground set. 
  
  
  We use an objective-preserving reduction from the set cover problem.
  
  Given: A ground set V with |V|=ñ, and a set of subsets V_s ⊆ V, s∈ S with |S|=m̃.
  
  Question: Does there exist a set cover of size less or equal to k, i.e., a set C⊆ S with |C|≤ k such that ∪_s∈ C V_s = V?
  
  We set L=ñ and K=m̃. For each v∈ V and each s∈ S, we add an element (v,s) to set T_v. Each such element (v,s) belongs to a region P_s. We set Γ_s = 1 for all s ∈ S and the
  costs to c = 0 and d = 1. Finally, we set p_v = 1 for all sets T_v.
  
  As an example, let us assume we have ñ=4, m̃=3, and V_1 = {1,2}, V_2={2,3}, V_3 = {3,4}. Then Table <ref> illustrates the construction.
  
  By choosing one item from each set T_v, we determine by which set V_s we intend to cover it. It can be easily seen that a set cover of size k exists if and only if the robust representative selection problem with locally budgeted uncertainty has an objective value at most k. Hence, the reduction is cost-preserving, and the claim follows.
  
  
  
  Note that the inapproximability of set cover under parameters Δ and k is well-researched (see, e.g., <cit.>). If k=θ(logΔ), both problems become hard to approximate within Ω(logΔ/(loglogΔ)^2).
  
  
  
  
    §.§.§ A Polynomial Time Algorithm for the Selection Problem
  
  
  
  While the results from the previous section indicate that the robust counterpart of even simple combinatorial problems becomes hard, we now show that this is not the case for the selection problem, where = {x∈{0,1}^n : ∑_i∈[n] = p} for some integer p.
  
  To this end, use a dynamic program over how many items are taken from every partition. Let n_j=|P_j| be the number of items in region h∈[K]. If the number of items p_j taken from partition P_j is fixed, the robust problem can be decomposed:
  
      min_x∈ Xmax_c∈c^tx 
      = ∑_j∈ [K]min_x∈_jmax_c∈_jc^tx 
      =: ∑_j∈[K] f_j(p_j)
  
  where _j = {x∈{0,1}^n_j : ∑_i∈ P_j x_i = p_j} and
  _j = {c∈ℝ^n_j : c_i = c_i + δ_i,δ_i ∈ [0,d_i] ∀ i∈ P_j, ∑_i∈ P_jδ_i ≤Γ_j}.
  
  For every j∈[K] and every p_j∈{0,1,…,n_j}, 
  the value f_j(p_j) is the solution of a robust selection problem with continuous budgeted uncertainty set.
  In Theorem <ref> we explain how the whole table of these values can be precomputed efficiently.
  
  The robust selection problem with locally budgeted uncertainty thus becomes
  
      min    ∑_j∈[K] f_j(p_j) 
      s.t.    ∑_j∈[K] p_j = p 
          p_j ∈ℕ_0    ∀ j∈[K]
  
  where we use f_j(p_j) = ∞ if p_j > n_j
  
  
  The robust selection problem with locally budgeted uncertainty with arbitrary
  number of regions K can be solved in O(n log n + pn) time, hence in polynomial time.
  
  
  First we explain how to compute the complete table of values f_j(p_j)
  for all values j=1,…,K and p_j=0,…,p.
  Note that for fixed j and p_j computing
  f_j(p_j) is equivalent to solving the robust selection problem with continuous budgeted uncertainty.
  Observe that this problem is equivalent to solving
  
      min_x∈_j(c^tx + min{d^tx, Γ_j }),
   
  corresponding to the two cases of π_j=0 and π_j=1 in formulation (<ref>-<ref>).
  The optimal solution to this problem can be determined by solving the two instances of 
  the selection problem for parameter p_j with costs c and 
  (c + d) and taking the solution giving the smaller objective value. Hence, for fixed j, all values of f_j can be calculated by sorting the items in P_j once with respect to costs c, and once with respect to costs c+d. In total, this requires time O(∑_j∈[K] n_j log n_j) = O(∑_j∈[K] n_j log n) = O(n log n).
  
  We now give a dynamic program solving problems of type (<ref>-<ref>) in general form,
  based on a given table for the values of values f_j(p_j). This
  then directly implies our result for the robust selection problem.
  Let T(K',p') be defined as
  
      T(K',p') := min    ∑_j∈[K'] f_j(p_j) 
      s.t.    ∑_j∈[K'] p_j = p' 
          p_j ∈ℕ_0    ∀ j∈[K'].
  
  Then problem (<ref>-<ref>) is equivalent to computing T(K, p). It holds that T(1,p') =
  f_1(p') for all p'=0,1,…,p. It also holds that
  
      T(K', p') = min{ T(K'-1, p'-p_K') + f_K'(p_K') 
      p_K'=0,1, …, min{p',n_j}}.
  
  Hence, calculating entry T(K',p') can be done in O(n_j) time, if all preceding entries have already been calculated. In total, this means that T(K,p) can be calculated in O(∑_j∈[K]∑_p'∈[p] n_j) = O(∑_j∈[K] p n_j) = O(pn) time.
  
  Hence in total the running time of our algorithm is O(n log n + p n).
  
  
  
  
  
  
  § EXPERIMENTS
  
  
  
  
  
   §.§ Overview
  
  
  We present three experiments to quantify differences between ”classic” budgeted uncertainty sets and the locally budgeted uncertainty sets proposed in this paper. Experiments 1 and 2 use randomly generated data for the uncertain selection problem, while Experiment 3 is based on real-world data.
  
  
  In the first experiment, we assume that the uncertainty set is locally budgeted, and consider the benefit of using this information instead of using a classic budgeted set.
  
  In the second experiment, the actual regions are not known to the imagined decision maker. Instead, only sampled scenarios are provided. We analyze the differences between solutions based on classic and locally budgeted uncertainty sets fitted to the data.
  
  Finally, in the third experiment, we consider the differences between solutions based on classic and locally budgeted uncertainty sets fitted to real-world data for shortest path problems, where nothing is known about the underlying distribution.
  
  
  
  
  
  
   §.§ Experiment 1
  
  
  
  
    §.§.§ Setup
  
  
  
  In this experiment, we focus on randomly generated selection problems.
  We fix n=30. Given the number of regions K, we distribute items into the K regions as uniformly as possible. 
  For every item, we generate c_i and d_i independently and uniformly from {10,…,49}. We set Γ_j = 10|P_j| and use K=2,3,4,5. We generate 10,000 instances using the same random seed for each K, (i.e., cost coefficients of these instances are the same for each K). We consider all values p=1,…,29.
  
  Each instance is solved exactly, using the compact formulation for locally budgeted uncertainty. Additionally, we solve each instance using the classic budgeted uncertainty approach, by ignoring the partition into regions and using Γ=∑_j∈[K]Γ_j = 10n. We measure the robust objective value of both solutions with respect to the locally budgeted uncertainty set.
  
  By this setup, we already know that the approach using the locally budgeted uncertainty set must perform better. The question we answer here is how much we lose by ignoring such local information. As discussed in Section <ref>, local uncertainty naturally arises in some practical applications. Our experiment simulates the effect of using classic budgeted uncertainty in this case.
  
  
  
  
    §.§.§ Results
  
  
  In Figure <ref> we show the ratio of average objective values between the solution found by 
  the model using classic budgeted uncertainty, and by the
  model using locally budgeted uncertainty, for different values of p. The higher the ratio, the higher are the additional costs that arise by ignoring the locally budgeted uncertainty structure.
  
  
  
  Note that for small (p=1) and large (p=29) values of p, the ratio is close
  to one. Hence, the local information does not matter in this setting. The best
  choice is to buy the one item i where c_i + d_i is smallest (or
  to avoid the one item where this value is largest, respectively). For values of
  p between these two extremes, solutions differ. The region of values for p where there is a difference between solutions based on classic and locally budgeted uncertainty increases with K. For K=2 and p=11, the average cost difference is 15.6%, while this increases to 17.9% for K=5 and p=10. 
  
  
  
  
  
  
  
  
   §.§ Experiment 2
  
  
  
  
    §.§.§ Setup
  
  
  
  In the previous experiment we considered the effect if the decision maker knows the parameters of a locally budgeted uncertainty set, but chooses to ignore these and use a classic budgeted uncertainty instead. In practice, an uncertainty set is usually not given, but needs to be derived from data.
  
  Hence in this second experiment, we build locally budgeted uncertainty sets in
  the same way as before, but then sample N scenarios from the set. To create a
  sample scenario c^k with k∈[N], we choose a random value γ_j from
  {0,…,Γ_j} uniformly and distribute min{γ_j, ∑_i∈
  P_j d_i} many unit cost increases to all items i∈ P_j. We do so
  iteratively, i.e., we first begin with c^k=c, and then repeatedly
  choose an item from P_j where c^k_i ≤c_i + d_i - 1 at random,
  and increase this item's costs by one.
  
  Having constructed N scenarios, we then fit suitable classic and locally budgeted uncertainty sets. 
  The focus of this experiment is to derive the regions from the data. We therefore assume that c_i and d_i are given for each item. 
  
  
  To estimate the underlying partition into regions, we can assume
  that in a sufficiently large sample N, two items from different regions are
  not correlated. As each budget constraint applies locally, correlation can only
  be found within regions. Based on this idea, we calculate the correlation matrix
  using the available sample data. We then consider two items to be connected, if
  the absolute value of correlation is above a certain threshold (in this
  experiment, we used 0.3). Each connected component then forms its own region.
  Note that this way, the number of regions K̃ we use is not prescribed, but estimated from the data.
  
  The classic budgeted uncertainty set uses Γ̃ = max_k∈[N](∑_i∈[n] c^k_i - c_i) as an estimate for the uncertainty budget. For each region, we estimate Γ̃_j in the same way.
  
  We use n=30, p=10, K=2,…,5 and vary the sample size N from 10 to 10,000. As before, for each parameter combination, we construct and solve 10,000 instances.
  
  
  
    §.§.§ Results
  
  
  Our results are summarized in Figure <ref>. On the horizontal axis, we denote the sample size N (note the logarithmic scale). On the vertical axis, we show average objective values with respect to the original, unknown locally budgeted uncertainty set.
  
  
  
  The solid lines indicate the objective value of the solutions based on fitted classic budgeted uncertainty sets, while the dashed lines represent locally budgeted uncertainty sets. The dotted lines indicate the optimal objective value, if the actual uncertainty set were known.
  
  First note that the larger the number of regions K, the smaller become objective values overall. For the classic budgeted uncertainty set, the decrease in objective value with increasing sample size N is small, the line is mostly horizontal. This is different for the locally budgeted uncertainty set, where a significant decrease can be observed after the sample size reaches a certain threshold. This begins at around N=30, and is completed at approximately N=110. We find that even if the locally budgeted uncertainty set is not given explicitly, it is possible to take significant advantage of this model by identifying the corresponding structure in the data.
  
  
  
  
   §.§ Experiment 3
  
  
  
  
    §.§.§ Setup
  
  
  While the previous experiments used artificial data that is based on an underlying locally budgeted uncertainty set, we now consider real-world data, where no such underlying structure is known. The data we use was first introduced in <cit.>. It consists of a graph modeling the city of Chicago with 538 nodes and 1308 edges, and 4363 snapshots of traffic speed for each edge over 46 days. Figure <ref> shows the structure of the graph.
  
  
  
  The data is prepared in the same way as in <cit.>. We use each traffic speed snapshot as a scenario. Of the 4363 scenarios, we use 75% for training our models, and 25% for evaluation. We sample 200 random s-t pairs and calculate a shortest path for each pair using each of our models.
  
  The classic budgeted model is trained on the data in the same way as in Experiment 2 (see Section <ref>), where c_i and d_i are estimated from the data. To model locally budgeted uncertainty sets, we create regions by using edge sequences between any two crossings in one direction. In Figure <ref>, we show three such regions in red as an illustration. In total, this results in 546 regions.
  
  We control the degree of conservatism of our two approaches by multiplying the estimated Γ̃ value (or Γ̃_j values, respectively) with a budget factor f. We use all values of f from 0 to 0.5 in step size 0.002.
  
  For each value of f and each model, we solve the 200 shortest path problems and evaluate the path choices in-sample and out-of-sample. We then calculate the average of the average path length and the worst-case path length over the two scenario sets.
  
  
  
  
    §.§.§ Results
  
  
  We show our in-sample results in Figure <ref> and the out-of-sample results in Figure <ref>. On the horizontal axis is the average travel time (in minutes), and the vertical axis is the average worst-case travel time. The results of both models are shown as a line, starting with f=0 in the top left, and moving to the right with increasing value of f.
  
  
  
  Note that for f=0, the classic and the locally budgeted approach result in the same solution, that is, they only optimize for best-case travel times. In an ideal trade-off between average and worst-case travel time, we would expect the lines to reach from the top left corner (low average time, high worst-case time) to the bottom right corner (high average time, low worst-case time).
  
  In Figure <ref> we can see that for the classic approach, no such trade-off can be reached. With increasing budget factor, we increase the average travel time, but do not decrease the worst-case travel times. From the perspective of Pareto optimality, most of the budget factors result in dominated solutions. The locally budgeted uncertainty set, on the other hand, gives a trade-off with increasing budget factor and considerably outperforms the solutions found by the locally budgeted uncertainty set. In the out-of-sample results (Figure <ref>), the classic approach performs even worse, with the curve leading upwards to the top right. The locally budgeted solutions retain a trade-off between average and worst-case time.
  
  Overall, we see that it is possible to model the discrete real-world scenarios more accurately using 
  the locally budgeted uncertainty approach, while with the classic budgeted approach, it is not possible to capture the underlying data.
  
  
  
  
  § CONCLUSIONS AND FURTHER RESEARCH
  
  
  
  In this paper we introduced a new generalization of budgeted uncertainty sets, where there is a separate uncertainty budget for different regions of items. We showed that for constant number of regions K, the robust counterpart remains polynomially solvable if the nominal problem is solvable in polynomial time. For unbounded values of K, we show that the robust selection problem can still be solved in polynomial time, while this is not the case for the representative selection problem, even if only one item is chosen from each partition. This extends to other combinatorial problems that include the representative selection problem as a special case. Table <ref> gives an overview to these results. In addition, we show that no parameterized algorithms with running time in O^*(2^o(K)) exist. To the best of our knowledge, robust optimization problems have not been considered from the perspective of fixed parameter tractability so far.
  
  
  
  
  In computational experiments we showed that more general, locally budgeted uncertainty sets can result in better solutions than their classic counterparts using real-world data sets.
  
  Different types of classic budgeted uncertainty sets have been considered in the literature. Instead of the definition used in this paper, where
  
      = {c = c + δ : δ_i∈[0,d_i] ∀ i∈[n], ∑_i∈[n]δ_ i ≤Γ},
  
  it is possible to consider the variant
  
      = {c : c_i = c_i + d_i z_i, z_i∈[0,1] ∀ i∈[n], ∑_i∈[n] z_ i ≤Γ}.
  
  All of our theoretical results can be extended to this case. In Theorem <ref>, this means we need to consider n^K instead of 2^K subproblems. The hardness results hold as well, as we used d_i=1 in the uncertainty sets we constructed.
  
  Furthermore, the locally budgeted uncertainty set proposed in this paper can be seen in the light of data-driven robust optimization (see, e.g., <cit.>), where the aim is to find the most suitable uncertainty set to describe given data. Using local budgets extends the capabilities of classic budgeted uncertainty models, and thus gives more degrees of freedom to describe the data.
  
  From a theoretical perspective, further investigations into the parameterized running time of our
  meta-algorithm in Section <ref> are of interest. 
  Note that a minor modification of the proof of Theorem <ref> implies that
  no O^*((√(2)-ϵ)^K) algorithm for the robust representative selection problem with
  locally budgeted uncertainty exists, unless the strong exponential time hypothesis (SETH) fails.
  We conjecture that there are combinatorial optimization problems for which the constant 2 can be improved. Whether this can be done in a meta-algorithm or only for specific combinatorial optimization problems is another interesting open problem.
  
  For the second variant of locally budgeted uncertainty, mentioned in Section <ref>,
  our gap between positive and negative results is even larger. It is of major interest whether a fixed-parameter
  tractable algorithm also exist for this case, or if this slight change in the definition of 
  the uncertainty set leads to W[1]-hardness.
  
  
  10
  
  aissi2009min
  Hassene Aissi, Cristina Bazgan, and Daniel Vanderpooten.
  Min–max and min–max regret versions of combinatorial optimization
    problems: A survey.
  European journal of operational research, 197(2):427–438,
    2009.
  
  alimonti2000some
  Paola Alimonti and Viggo Kann.
  Some apx-completeness results for cubic graphs.
  Theoretical Computer Science, 237(1-2):123–134, 2000.
  
  alves2015robust
  Artur Alves Pessoa, Luigi Di Puglia Pugliese, Francesca Guerriero, and Michael
    Poss.
  Robust constrained shortest path problems under budgeted uncertainty.
  Networks, 66(2):98–111, 2015.
  
  bertsimas2018data
  Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus.
  Data-driven robust optimization.
  Mathematical Programming, 167(2):235–292, 2018.
  
  bertsimas2003robust
  Dimitris Bertsimas and Melvyn Sim.
  Robust discrete optimization and network flows.
  Mathematical Programming, 98(1):49–71, Sep 2003.
  
  bertsimas2004price
  Dimitris Bertsimas and Melvyn Sim.
  The price of robustness.
  Operations research, 52(1):35–53, 2004.
  
  bougeret2019robust
  Marin Bougeret, Artur Alves Pessoa, and Michael Poss.
  Robust scheduling with budgeted uncertainty.
  Discrete Applied Mathematics, 261:93–107, 2019.
  
  busing2012new
  Christina Büsing and Fabio D'andreagiovanni.
  New results about multi-band uncertainty in robust optimization.
  In International Symposium on Experimental Algorithms, pages
    63–74. Springer, 2012.
  
  chassein2019algorithms
  André Chassein, Trivikram Dokka, and Marc Goerigk.
  Algorithms and uncertainty sets for data-driven robust shortest path
    problems.
  European Journal of Operational Research, 274(2):671–686,
    2019.
  
  chassein2018recoverable
  André Chassein, Marc Goerigk, Adam Kasperski, and Paweł Zieliński.
  On recoverable and two-stage robust selection problems with budgeted
    uncertainty.
  European Journal of Operational Research, 265(2):423–436,
    2018.
  
  chassein2019faster
  André Chassein, Marc Goerigk, Jannis Kurtz, and Michael Poss.
  Faster algorithms for min-max-min robustness for combinatorial
    problems with budgeted uncertainty.
  European Journal of Operational Research, 279(2):308–319,
    2019.
  
  deineko2013complexity
  Vladimir G Deineko and Gerhard J Woeginger.
  Complexity and in-approximability of a selection problem in robust
    optimization.
  4OR, 11(3):249–252, 2013.
  
  garey1979computers
  Michael R Garey and David S Johnson.
  Computers and intractability, volume 174.
  freeman San Francisco, 1979.
  
  hansknecht2018fast
  Christoph Hansknecht, Alexander Richter, and Sebastian Stiller.
  Fast robust shortest path computations.
  In 18th Workshop on Algorithmic Approaches for Transportation
    Modelling, Optimization, and Systems (ATMOS 2018). Schloss
    Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  
  kasperski2016robust
  Adam Kasperski and Paweł 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.
  
  kouvelis2013robust
  Panos Kouvelis and Gang Yu.
  Robust discrete optimization and its applications, volume 14.
  Springer Science & Business Media, 2013.
  
  poss2013robust
  Michael Poss.
  Robust combinatorial optimization with variable budgeted uncertainty.
  4OR, 11(1):75–92, 2013.
  
  poss2018robust
  Michael Poss.
  Robust combinatorial optimization with knapsack uncertainty.
  Discrete Optimization, 27:88–102, 2018.
  
  saket2012new
  Rishi Saket and Maxim Sviridenko.
  New and improved bounds for the minimum set cover problem.
  In Approximation, randomization, and combinatorial optimization.
    Algorithms and techniques, pages 288–300. Springer, 2012.
  
  woeginger2003exact
  Gerhard J Woeginger.
  Exact algorithms for NP-hard problems: A survey.
  In Combinatorial optimization – eureka, you shrink!, pages
    185–207. Springer, 2003.
  
  
  
  
  
  
  
  
  
  