title: On a reduction for a class of resource allocation problems
authors: Martijn H. H. Schoot Uiterkamp Marco E. T. Gerards Johann L. Hurink
text: 
  Adaptive Neural Network-Based Approximation to  Accelerate Eulerian Fluid Simulation
      Dong Li
      Received: date / Accepted: date
  ====================================================================================
  
  
  
  
  
  In the resource allocation problem (RAP), the goal is to divide a given amount of resource over a set of activities while minimizing the cost of this allocation and possibly satisfying constraints on allocations to subsets of the activities. Most solution approaches for the RAP and its extensions allow each activity to have its own cost function. However, in many applications, often the structure of the objective function is the same for each activity and the difference between the cost functions lies in different parameter choices such as, e.g., the multiplicative factors. In this article, we introduce a new class of objective functions that captures the majority of the objectives occurring in studied applications. These objectives are characterized by a shared structure of the cost function depending on two input parameters. We show that, given the two input parameters, there exists a solution to the RAP that is optimal for any choice of the shared structure. As a consequence, this problem reduces to the quadratic RAP, making available the vast amount of solution approaches and algorithms for the latter problem. We show the impact of our reduction result on several applications and, in particular, we improve the best known worst-case complexity bound of two important problems in vessel routing and processor scheduling from O(n^2) to O(n log n).
  
  
  
  
  
  § INTRODUCTION
  
  
  
  The resource allocation problem (RAP) is a classical problem within operations research and has been studied extensively and continuously since the 1950s <cit.>. In its most basic and most studied form, this problem asks for the allocation of a given amount of resource over a set of activities while minimizing a given separable cost function (or, equivalently, maximizing a given separable utility function). Over the years, several variations and extensions of this basic setting have been studied, with different types of individual cost functions, additional constraints, and allocation restrictions such as integer-valued allocations <cit.>. 
  
  With regard to the constraint structure, we focus on a general version of the RAP that occurs widely in applications, namely the RAP with additional submodular constraints (see, e.g., <cit.>). In this problem, for each subset of the activities, there is an upper bound on the total amount of resource allocated to these activities and this bound is given by a submodular set function. This problem has many applications in, e.g., machine learning <cit.>, scheduling <cit.>, and game theory <cit.>. Moreover, important special cases of this problem are the RAP with box constraints (see <cit.>), the RAP with generalized bound constraints (see <cit.>), and the RAP with nested constraints (see <cit.>). Important application areas for in particular these special cases include, among many others, regularized learning <cit.>, telecommunications and energy management <cit.>, and statistics <cit.> (see also the overviews in <cit.> and <cit.>).
  
  Concerning the objective, state-of-the-art solution approaches for RAPs generally allow each activity to have its own arbitrary (convex) cost function. Although this is an interesting aspect from a mathematical point of view, it is questionable whether this is a given situation in practical problems. In applications, often the structure of the cost functions is the same for all activities (e.g., all functions are quadratic) and the difference lies primarily in different parameters for these functions (e.g., each function has different multiplicative factors). In fact, this is the case for the large majority of applications studied in (the works surveyed in) <cit.>. 
  
  Scanning existing solution approaches for RAPs, one observes that, to obtain algorithms with a low computational complexity, many approaches rely on advanced data structures and procedures to store and manipulate problem parameters and intermediate bookkeeping values. However, it is often unclear whether such structures and procedures are actually fast in practice due to the lack of computational experiments (see also <cit.>). Moreover, the fact that these algorithms are highly complex often makes it difficult to implement them, which limits their adaptability in practice where other aspects such as code maintainability and ease of use are often considered as more important (see also <cit.>).
  
  The aspects discussed above motivate us to study RAPs where the cost functions share a common structure and differ only in the parameter choice. More precisely, we introduce the notion of (a,b,f)-separable RAPs, wherein the cost function of each activity i is of the form a_i f (x_i/a_i + b_i), where f is the common convex function and a_i > 0 and b_i are given parameters that can be different for different activities i. Such cost functions are an extension of so-called d-separable functions introduced in <cit.>. Moreover, they are closely related to the concept of perspective functions <cit.>, which arise naturally in many problems in applied mathematics. In particular, most of the applications in (works surveyed in) <cit.> can be modeled as (a,b,f)-separable RAPs.
  
  In this article, we show a reduction result concerning (a,b,f)-separable RAPs with submodular constraints. More precisely, we show that for given parameters a and b and an instance of this class of RAPs, there exists a feasible solution to this instance that is optimal for any choice of the convex function f. In particular, we show that any solution that is optimal to the basic quadratic version of this RAP, i.e., where f(x_i) = 1/2 x_i^2, is also optimal for the (a,b,f)-separable version for any choice of f. This means that solving any (a,b,f)-separable RAP reduces to solving the quadratic version of this RAP and allows us to solve this problem using any tailored algorithm that solves the quadratic RAP. Thus, to solve this problem, we do not require algorithms designed to solve the more general version with arbitrary convex cost functions, which are in general much slower and less efficient than the tailored algorithms for the quadratic RAP. Moreover, especially for the quadratic RAP over box constraints, many different types of algorithms exist to solve this problem, each of which has different pros and cons given the application <cit.>. Thus, our reduction result allows us to solve a wide range of RAPs using the extensive collection of solution approaches and algorithms for quadratic RAPs.
  
  In the literature, similar results already exist for specific RAPs. For RAPs over submodular constraints, <cit.> showed that the problem with quadratic cost functions is equivalent to the problem of computing a lexicographically optimal base with regard to a given weight vector. <cit.> extends this result to a range of different strictly convex cost functions for the case of continuous variables. Their result is used in <cit.> to solve optimization problems on graphs and in <cit.> to derive efficient algorithms for processor scheduling problems. For a special case of RAPs with nested constraints, the equivalence of (a,b,f)-separable RAPs is proven in <cit.> for the case where the functions f are strictly convex and differentiable, b = 0, and with continuous variables. 
  
  Some reduction results can be derived from existing algorithms for specific applications in the literature. An example of this concerns the vessel speed optimization problem (see, e.g., <cit.>). In this problem, a ship traverses a given route between ports and must dock at each given port within a specific time window. The goal is to determine the ship's speed between each leg of the route while minimizing fuel costs. The authors in <cit.> propose a recursive-smoothing algorithm (RSA) for this problem, which is shown to be optimal by <cit.>. This algorithm does not require knowledge on the fuel cost function other than that it is convex. Thus, the optimal solution outputted by this algorithm is indifferent of the choice of cost function.
  
  Another example is the scheduling of tasks on a single processor with agreeable deadlines (see, e.g., <cit.>). Here, we are given a number of tasks that must be processed on a single processor, each of which has its own workload, arrival time, and deadline. The goal is to assign processor speeds to tasks such that all tasks are finished before their deadline while minimizing the total energy usage of the processor. This energy usage depends on the workload of each task and on the required power to maintain a given processor speed. Analogously to the vessel speed optimization problem, the processor scheduling problem can be solved using the RSA without any knowledge of the nature of the convex cost function <cit.>. Thus, also the optimal solution outputted by this algorithm does not depend on the power function.
  
  Our reduction result generalizes all the above results to general convex functions f, i.e., not necessarily strictly convex or differentiable, and to both continuous and integer variables. In particular, in the case of continuous variables and a strictly convex function f, our reduction result becomes an equivalence result since the optimal solution to any strictly convex optimization problem is unique. In fact, given the parameters a and b, an instance to RAP, and two strictly convex functions f and f̅, we show that the (a,b,f)-separable and (a,b,f̅)-separable versions of this RAP have the same unique optimal solution and are thus equivalent.
  
  
  Next to the theoretical impact of our reduction result, we demonstrate the added value of this result for several applications. For a number of problems from the areas of telecommunications, statistics, and energy management, we show that our results provide new insights and improve several existing solution approaches. In particular, we show that the vessel speed optimization problem and the processor scheduling problem mentioned above can be solved in O(n log n) time. This is an improvement over their currently best known time complexity of O(n^2).
  
  Summarizing, our technical contributions are as follows:
  
  
    * We show that (a,b,f)-separable RAPs with submodular constraints reduce to their quadratic versions, making available the more extensive collection of fast and efficient algorithms for quadratic RAPs to solve these problems.
  
    * We discuss the impact of this result on some special cases of the considered RAPs and derive new worst-case time complexity results for these cases.
  
    * We apply our results to core problems from several application areas and show how they can be solved more efficiently using our reduction result. For two of these problems, we improve their worst-case time complexity from O(n^2) to O(n log n).
  
  Moreover, on a higher level and perhaps of independent interest, our work demonstrates that methodological research on RAPs is conducted independently in many different research fields, be it under different names. As a consequence, many conceptual insights, structural properties, and solution approaches for RAPs have been re-invented and re-discovered many times over the years, both within the same field and independently in several fields. Therefore, we aim to promote a cross-disciplinary approach for studying RAPs. Such an approach will both reduce the amount of future re-discoveries and re-inventions and allow researchers to benefit from the many available different perspectives on RAPs.
  
  
  The organization of this article is as follows. In Section <ref>, we provide formal problem definitions of the studied RAPs and introduce the used notation. In Section <ref>, we prove the reduction result and in Section <ref>, we discuss the impact of this result on each of the studied RAPs. In Section <ref>, we demonstrate the impact of our reduction result on several application areas. Finally, Section <ref> contains our conclusions.
  
  
  
  § PROBLEM FORMULATION AND PRELIMINARIES
  
  
  
  In this section, we formulate the studied resource allocation problems, i.e., the RAP over submodular constraints and its special cases, and introduce the used notation and definitions. 
  
  
  
   §.§ Notation and definitions
  
  In the following, we introduce some notation and properties of  used functions and sets. For this, let 𝒩 := { 1,…,n } be the index set of the given activities. We call a convex function Φ :  ℝ^n →ℝ separable if it can be written as the sum of single-variable convex functions, i.e., if Φ(x) = ∑_i ∈𝒩ϕ_i (x_i) for some single-variable convex functions ϕ_i :  ℝ→ℝ, i ∈𝒩. Moreover, given two vectors a ∈ℝ^n_>0 and b ∈ℝ^n and a single-variable convex function f :  ℝ→ℝ, we say that Φ is (a,b,f)-separable  if each function ϕ_i can be written as
  
      ϕ_i(x_i) = a_i f (x_i/a_i + b_i ).
  
  Note that we do not pose any restrictions on f other than convexity. Hence, both f and ϕ_i are not necessarily strictly convex or differentiable. We denote the left and right derivatives of f by f^- and f^+ respectively. It follows that the left derivative ϕ_i^- of ϕ_i is given by
  
      ϕ_i^-(x_i) := lim_y ↑ x_iϕ_i(y) - ϕ_i(x_i)/y - x_i
      =
      lim_y ↑ x_ia_i f ( y/a_i + b_i ) - a_i f ( x_i/a_i + b_i )/y - x_i
      = f^-(x_i/a_i + b_i ).
  
  Analogously, the right derivative ϕ_i^+ of ϕ_i is given by ϕ_i^+ (x_i) =  f^+(x_i/a_i + b_i ). Throughout this article, we call a resource allocation problem (a,b,f)-separable if its objective function is (a,b,f)-separable.
  
  We denote the vector of ones of dimension n by e̅. Furthermore, for each index i ∈𝒩, we denote by e^i ∈ℝ^n the standard basis vector associated with i, i.e., the vector whose i^th entry is 1 and whose other entries are all zero. For a given set 𝒞⊂ℝ^n and x ∈𝒞, let ℰ_𝒞(x) denote the set of index pairs (i,k) ∈𝒩^2 for which we can always shift a small amount from x_i to x_k without violating feasibility. More precisely, we define
  
      ℰ_𝒞(x) := { (i,k) ∈𝒩^2  |  x + ϵ(e^k - e^i) ∈𝒞 for some ϵ > 0 }.
  
  Each pair in (i,k) ∈ℰ_𝒞(x) is called an exchangeable pair.
  
  Finally, let r:  2^𝒩→ℝ be a set function on the ground set 𝒩. The set function r is submodular if
  r(𝒳∪𝒴) + r(𝒳∩𝒴) ≤ r(𝒳) + r(𝒴) for any 𝒳,𝒴⊆𝒩, where we assume that r(∅) = 0.
  
  
  
  
   §.§ Problem classification
  
  The basic version of the resource allocation problem calls for an allocation x ∈ℝ^n of a given amount of resource R ∈ℝ over a set of activities 𝒩 such that a given convex cost function Φ(x) of the allocation is minimized. This problem can be formulated as follows:
  
      RAP :  min_x     Φ(x) 
      s.t.    ∑_i ∈𝒩 x_i = R.
  
  Based on this basic version, we can formulate several extensions of the problem RAP with different types of cost functions, additional constraints, and different types of decision variables. To clearly distinguish between these problems, we adapt a classification scheme similar to that in <cit.> and <cit.>, i.e., we specify each problem by three fields α/β/γ, where α specifies the objective function, β describes the constraint set, and γ specifies the nature of the decision variables.
  
  For α, we consider the following options:
  
  
    * Separable (S): Φ is separable.
  
    * (a,b,f)-separable ((a,b,f)-S): Φ is (a,b,f)-separable.
  
    * Quadratic ((a,b)-Q): Φ is (a,b,f)-separable using f(y) = 1/2y^2. This means that Φ is both separable and quadratic.
  
  
  For β, we consider the follows special constraint structures, where we use ℳ := { 1,…, m } as an index set for additional constraints:
  
  
    * Box constraints (Box): l_i ≤ x_i ≤ u_i for all i ∈𝒩.
  
    * Generalized bound constraints (GBC): Next to the box constraints also constraints of the form L_j ≤∑_i ∈𝒩_j x_i ≤ U_j, j ∈ℳ are given, where the sets 𝒩_1,…,𝒩_m form a partition of 𝒩.
  
    * Nested constraints (NC): Next to the box constraints also constraints of the form L_j ≤∑_i ∈𝒩_j x_i ≤ U_j, j ∈ℳ are given, where the sets 𝒩_1,…,𝒩_m are such that 𝒩_1 ⊂…⊂𝒩_m ⊂𝒩.
  
    * Laminar (or tree) constraints (LC): Constraints of the form L_j ≤∑_i ∈𝒩_j x_i ≤ U_j, j ∈ℳ are given, where the subsets 𝒩_1,…,𝒩_m of 𝒩 have the following property: if 𝒩_j ∩𝒩_ℓ≠∅, then either 𝒩_j ⊂𝒩_ℓ or 𝒩_j ⊃𝒩_ℓ for all j,ℓ∈ℳ.
  
    * Submodular constraints (SC): Constraints of the form ∑_i ∈𝒮 x_i ≤ r(𝒮), 𝒮⊂𝒩 and ∑_i ∈𝒩 x_i = r(𝒩) are given, where r is a given submodular function with r(𝒩) = R.
  
  Note that the constraint structures Box, GBC, and NC are special cases of the structure LC. Moreover, it can be shown that the structure LC is a special case of the structure SC (see Appendix <ref>). Thus, all constraint structures are special cases of SC. We discuss each of these special cases in more detail in Section <ref>.
  
  
  For γ we consider the following two cases:
  
  
    * Continuous decision variables (C): x ∈ℝ^n.
  
    * Integer decision variables (I): x ∈ℤ^n.
  
  
  Table <ref> summarizes the possible entries of α, β, and γ as a compact reference. To simplify the presentation, we assume that whenever we specify β, the parameters that define the corresponding constraints are fixed. For example, when we consider the problems (a,b,f)-S/LC/C and (a,b)-Q/LC/C for some vectors a,b and convex function f, we assume that the subsets 𝒩_1,…, 𝒩_m and vectors L := (L_j)_j ∈ℳ and U := (U_j)_j ∈ℳ are fixed.
  
  
  
  Finally, apart from these extensions of RAP, we study a general constraint class where a constraint x ∈𝒞 for some set 𝒞⊂ℝ^n is given. We pose no restrictions on this set other than that it is nonempty. We denote this constraint class by 𝒞 and denote the corresponding separable, (a,b,f)-separable, and (a,b)-quadratic versions of this problem by S/𝒞, (a,b,f)-S/𝒞, and (a,b)-Q/𝒞 respectively.
  
  
  
  
  
  § REDUCTION OF (A,B,F)-SEPARABLE RAPS TO QUADRATIC RAPS
  
  
  
  The goal of this section is to show for all the RAPs introduced in the previous section that their (a,b,f)-separable versions reduce to their quadratic versions. More precisely, given a constraint structure β, variable type γ, convex function f, and vectors a ∈ℝ^n_>0 and b ∈ℝ^n, we show that any optimal solution to (a,b)-Q/β/γ is also optimal for (a,b,f)-S/β/γ. This means that we can solve (a,b,f)-S/β/γ by solving (a,b)-Q/β/γ. Note that for many of these quadratic RAPs, tailored algorithms exist that are faster and more efficient than algorithms for the case with arbitrary convex cost functions. Thus, this reduction result allows us to solve (a,b,f)-S/β/γ problems using fast algorithms for their quadratic special case.
  
  
  
  We start by considering the general constrained optimization problem S/𝒞 with a convex separable objective function:
  
      S/𝒞 :  min_x     ∑_i ∈𝒩ϕ_i (x_i) 
      s.t.     x ∈𝒞,
  
  where 𝒞⊂ℝ^n. Recall that we do not assume any properties on the set 𝒞 other than that it is nonempty and that all RAPs introduced in the previous section are special instances of this problem.
  
  We show that if S/𝒞 satisfies a certain optimality condition, any optimal solution to (a,b)-Q/𝒞 is also optimal for (a,b,f)-S/𝒞. This optimality condition states that a feasible solution x to S/𝒞 is optimal if and only if moving an arbitrary amount from one variable x_i to another variable x_k while maintaining feasibility never leads to a decrease in objective value. We state this condition as Condition <ref> and give the mentioned reduction result in Theorem <ref>.
  
  Given separable convex functions ϕ_i  :  ℝ→ℝ and a set 𝒞⊂ℝ, a feasible solution x to S/𝒞 is optimal if and only if we have for each exchangeable pair (i,k) ∈ℰ_𝒞(x) that ϕ_k^+ (x_k) ≥ϕ_i^- (x_i).
  
  
  
  Let the set 𝒞, a convex function f, and a ∈ℝ^n_>0 and b ∈ℝ^n be given. If Condition <ref> is satisfied by S/𝒞 and x ∈𝒞 is optimal for (a,b)-Q/𝒞, then x is also optimal for (a,b,f)-S/𝒞.
  
  
  
  Let x be an optimal solution to (a,b)-Q/𝒞. Note that for the problem (a,b)-Q/𝒞, we have that ϕ_i(x_i) = a_i ·1/2(x_i/a_i + b_i)^2 = 1/2x_i^2/a_i + b_i x_i for all i ∈𝒩. Thus, by applying Condition <ref> to (a,b)-Q/𝒞, we have that x_k/a_k + b_k ≥x_i/a_i + b_i for all (i,k) ∈ℰ_𝒞(x). Since by convexity of f the right derivative f^+ is non-decreasing and we have f^+(y) ≥ f^-(y) for all y ∈ℝ, it follows that f^+(x_k/a_k + b_k ) ≥ f^+(x_i/a_i + b_i ) ≥ f^-(x_i/a_i + b_i ) for all (i,k) ∈ℰ_𝒞(x). Note that this is equivalent to the statement ϕ_k^+ (x_k) ≥ϕ_i^- x_i for all (i,k) ∈ℰ_𝒞(x) where ϕ_i' (y) = a_i' f(x_i'/a_i' + b_i') for all i' ∈𝒩. Thus, by applying Condition <ref> to (a,b,f)-S/𝒞, this implies that x is optimal for (a,b,f)-S/𝒞.
  
  Note that Theorem <ref> does not require the problem S/𝒞 to be a RAP. This means that this theorem and thus our reduction result is more widely applicable to other problems, provided that they satisfy Condition <ref>.
  
  
  
  It is well-known that S/SC/γ satisfies Condition <ref> for γ∈{C, I} (see, e.g., <cit.>). To gain some insight in why this is the case, we provide for the interested reader in Appendix <ref> an alternative proof for this claim for the relevant special case S/LC/γ that relies only on basic concept from convex analysis such as subgradients. It follows that Theorem <ref> can be applied to S/SC/γ and in particular also to all special cases of this problem:
  
  Let a convex function f, vectors a ∈ℝ^n_>0, b ∈ℝ^n, and entries β and γ as specified in Table <ref> be given. If x is optimal for (a,b)-Q/β/γ, then x is also optimal for (a,b,f)-S/β/γ.
  
  
  This corollary is an extension of the equivalence results in <cit.>, where the reduction result is shown for the two special cases with continuous variables where f is strictly convex and differentiable or where ϕ_i = f for all i ∈𝒩. 
  
  
  
  
  The validity of the reduction result of Theorem <ref> for RAPs with submodular constraints and its special cases implies that any algorithm for solving the quadratic version of this problem can be used to solve the (a,b,f)-separable version. In particular, any time complexity or efficiency results for the quadratic version apply also to the (a,b,f)-separable version:
  
  Let a convex function f, vectors a ∈ℝ^n_>0, b ∈ℝ^n, and entries β and γ as specified in Table <ref> be given. The worst-case time complexity of (a,b,f)-S/β/γ equals that of (a,b)-Q/β/γ.
  
  
  
  Finally, for the case of continuous variables, Theorem <ref> holds also when we replace the problem (a,b)-Q/β/C by (a,b,f̅)-S/β/C, where f̅ is a strictly convex function. This effectively turns our reduction result into an equivalence result between these two problems:
  
  Let a ∈ℝ^n_>0, b ∈ℝ^n, and entries β as specified in Table <ref> be given, and let f̅ be a strictly convex function and f be an arbitrary convex function. If x is optimal for (a,b,f̅)-S/β/C, then x is also optimal for (a,b,f)-S/β/C.
  
  
  
  Since f̅ is strictly convex, x is the unique optimal solution to (a,b,f̅)-S/β/C. It follows from Theorem <ref> that the unique optimal solution to (a,b)-Q/β/C is x and thus that x is also optimal for (a,b,f)-S/β/C.
  
  Corollary <ref> allows us to solve a given continuous (a,b,f)-separable RAP using any algorithm that solves the (a,b,f̅)-separable version of the problem for some strictly convex function f̅, i.e., not only just for quadratic objectives. This can be beneficial in cases where efficient algorithms have already been developed for a specific choice of a non-quadratic objective function, motivated by the given application.
  
  In Section <ref>, we focus in more detail on each of the special cases of α/SC/γ. In particular, using the reduction result in Theorem <ref> and Corollary <ref>, we establish worst-case complexity results for the (a,b,f)-separable versions of these problems.
  
  
  
  
  
  § ALGORITHMS AND COMPLEXITY RESULTS FOR SPECIAL CASES
  
  
  
  In this section, we first provide for each of the constraint types specified in Table <ref> a brief overview of known algorithms for the given special case and other known complexity results. In particular, we focus on algorithms and complexity results for the quadratic versions of these problems. Second, we use the complexity results on the quadratic versions of the problems to prove complexity results on the (a,b,f)-separable versions. These results are based on Theorem <ref> and Corollary <ref>, which state that we can solve each of these problems by solving the same problem with a quadratic objective function, i.e., where f(y) = 1/2y^2.
  
  As a compact reference, Tables <ref> and <ref> summarize the complexity results discussed and obtained in this section.
  
  
  
  
  
  
   §.§ α/Box/γ: Optimization over a single linear constraint
  
  
  The resource allocation problem over a single linear constraint, (a,b)-S/Box/γ, can be formulated as follows:
  
      (a,b)-S/Box/γ :  min_x    ∑_i ∈𝒩 a_i f (x_i/a_i + b_i ) 
      s.t.    ∑_i ∈𝒩 x_i = R, 
          l_i ≤ x_i ≤ u_i,    i ∈𝒩, 
          x ∈ℝ^n    if γ = C,
      ℤ^n      if γ = I.
  
  This problem and its more general version S/Box/γ have been studied since the 1950s <cit.>. Since then, many solution approaches and algorithms have been proposed for this problem, especially for the problems Q/Box/γ. We refer to <cit.> for surveys on the continuous version S/Box/C and to <cit.> for a brief but thorough review on the integer version S/Box/I.
  
  The best known complexities for S/Box/C and S/Box/I are O(n lognR/ϵ) and O(n logR/n) respectively, where ϵ is an accuracy parameter  <cit.>. Furthermore, their quadratic versions (a,b)-Q/Box/C and (a,b)-Q/Box/I can be solved in O(n) time (<cit.> and <cit.> respectively). Through Corollary <ref>, this yields the following complexity results for (a,b,f)-S/Box/γ:
  
  Both (a,b,f)-S/Box/C and (a,b,f)-S/Box/I can be solved in O(n) time.
  
  
  The linear-time algorithms for (a,b)-Q/Box/C belong to the class of so-called breakpoint search algorithms that solve the problem by efficiently searching for the optimal Lagrange multiplier corresponding to the resource constraint (<ref>) (see also <cit.>). The linear-time algorithm for (a,b)-Q/Box/I in <cit.> first solves the continuous version (a,b)-Q/Box/C of this problem using a linear-time algorithm such as in <cit.>. Subsequently, it uses this solution and a specific rounding scheme to construct an instance of (a,b)-Q/Box/I with R = O(n) that has the same optimal solution as the original instance of (a,b)-Q/Box/I. Using the algorithm in, e.g., <cit.> for S/Box/I, this instance can be solved in O(n logO(n)/n) = O(n) time.
  
  With regard to practical execution time, there are several classes of algorithms that outperform the aforementioned linear-time algorithms. For example, for the problem (a,b)-Q/Box/C, <cit.> shows that so-called variable-fixing algorithms that run in O(n^2) time are in general faster than linear-time algorithms such as in <cit.>. These algorithms first compute a solution to the problem without the box constraints (<ref>) and subsequently determine the optimal value of several variables that exceed their bounds in this solution. This process continues until none of the variables in the solution to the relaxed problem exceeds its bounds. The worst-case time complexity of O(n^2) is attained when only one variable can be fixed to its optimal value during each step in the procedure. However, this is quite a pathological case since it has the property that in the optimal solution all variables are equal to one of their bounds.
  
  Moreover, <cit.> shows that for several instances of (a,b,f)-S/Box/C, a specialized interior-point method significantly outperforms other approaches including the linear-time breakpoint search approaches. Interior-point methods are iterative approaches where each intermediate solution is obtained from the previous one by taking a step in a search direction that is the solution of a perturbed version of the Karush-Kuhn-Tucker optimality conditions (see also <cit.>). Normally, the computation of this search direction is the computationally most expensive step of the interior-point method since it requires solving a linear system involving the constraint matrix. However, by exploiting the sparse structure of the constraint matrix for S/Box/C, the number of operations required to solve this system can be reduced from O(n^3) to O(n).
  
  One reason for the in practice quite bad practical performance of linear-time algorithms for (a,b)-Q/Box/C is that they require the computation of the median of sets of numbers. However, to attain a linear-time complexity, also linear-time procedures for median finding such as in <cit.> have to be used. Such methods are in general significantly slower than alternative sorting-based approaches that run in linearithmic time <cit.>.
  
  The linear-time complexity of (a,b)-Q/Box/I is based on the linear-time complexity of (a,b)-Q/Box/C and the existence of linear-time algorithms for selecting a k^th smallest element from a collection of sorted lists <cit.>. For the latter problem, many studies refer to <cit.> for such a linear-time algorithm. Analogously to the breakpoint search algorithms for (a,b)-Q/Box/C, this algorithm requires a linear-time algorithm for median-finding to attain a linear-time complexity and may thus be slower in practice than alternative sorting-based approaches. It should be noted, however, that recently new linear-time algorithms have been developed that are based on specialized heap data structures and have been shown to have a better practical performance (see, e.g., <cit.>).
  
  
  
  
   §.§ α/GBC/γ: Optimization over generalized bound constraints
  
  Let 𝒩_1,…,𝒩_m be a partition of the index set 𝒩. Given parameters L,U ∈ℝ^m, the resource allocation problem with generalized bound constraints can be formulated as
  
      (a,b)-S/GBC/γ :  min_x    ∑_i ∈𝒩 a_i f (x_i/a_i + b_i ) 
      s.t    ∑_i ∈𝒩 x_i = R, 
          L_j ≤∑_i ∈𝒩_j x_i ≤ U_j,    j ∈ℳ, 
          l_i ≤ x_i ≤ u_i,    i ∈𝒩, 
          x ∈ℝ^n    if γ = C,
      ℤ^n      if γ = I.
   
  Applications of this problem include portfolio optimization <cit.>, transportation problems <cit.>, stratified sampling <cit.>, and electric vehicle charging <cit.>.
  
  In the literature, this problem is studied primarily with only the upper bound constraints in (<ref>). <cit.> shows that S/GBC/γ with only generalized upper bound constraints can be solved in the same time as S/Box/γ by reducing the problem to a sequence of subproblems S/Box/γ over in total n variables. <cit.> shows a similar result for (a,b)-Q/GBC/γ with both generalized lower and upper bound constraints, which yields an O(n) algorithm for solving (a,b)-Q/GBC/γ. Thus, by Corollary <ref>, also the problems (a,b,f)-S/GBC/γ can be solved in O(n) time:
  
  
  
  Both (a,b,f)-S/GBC/C and (a,b,f)-S/GBC/I can be solved in O(n) time.
  
  
  Alternatively, the continuous problem (a,b)-Q/GBC/C can be solved in O(n) time as a special case of quadratic programming with a fixed number of constraints <cit.>. 
  
  
  
  
   §.§ α/NC/γ: Optimization over nested constraints
  
  
  Let 𝒩_1,…, 𝒩_m be subsets of 𝒩 such that 𝒩_1 ⊂…⊂𝒩_m ⊂𝒩. The resource allocation problem with nested constraints, (a,b)-S/NC/γ, is stated as follows:
  
      (a,b)-S/NC/γ :  min_x    ∑_i ∈𝒩 a_i f (x_i/a_i + b_i ) 
      s.t    ∑_i ∈𝒩 x_i = R, 
          L_j ≤∑_i ∈𝒩_j x_i ≤ U_j,    j ∈ℳ, 
          l_i ≤ x_i ≤ u_i,    i ∈𝒩, 
          x ∈ℝ^n    if γ = C,
      ℤ^n      if γ = I.
  
  
  
  
  Research on this problem and the more general problem S/NC/γ has almost exclusively focused on the case with either the lower or upper nested constraints in (<ref>) but not both. We refer to <cit.> for a survey on this version of the problem.
  
  
  The most efficient algorithm for both S/NC/γ and (a,b)-Q/NC/γ is the decomposition algorithm in <cit.>. This algorithm solves the problem as a sequence of S/Box/γ subproblems where the single-variable bounds (<ref>) of each subproblem are optimal solutions to subproblems deeper in the decomposition hierarchy. The worst-case time complexity of this algorithm is O(n log m lognR/ϵ) for S/NC/C, O(n log m log R) for S/NC/I, and O(n log m) for both (a,b)-Q/NC/C and (a,b)-Q/NC/I. Thus, it follows directly from Corollary <ref> that both (a,b,f)-S/NC/C and (a,b,f)-S/NC/I can be solved in O(n log m):
  
  Both (a,b,f)-S/NC/C and (a,b,f)-S/NC/I can be solved in O(n log m) time.
  
  
  
  The algorithm in <cit.> attains the O(n log m) time complexity by utilizing the linear-time algorithms for (a,b)-Q/Box/γ to solve the subproblems. As mentioned in Section <ref>, these are not the fastest algorithms for these subproblems. As a consequence, it can be expected that using, e.g., variable-fixing algorithms <cit.> for the subproblems significantly improves the overall execution time of the algorithm.
  
  It has been shown <cit.> that infeasibility-guided algorithms such as in <cit.> are significantly faster than the decomposition algorithm in <cit.>. These algorithms first compute a solution to S/NC/γ without the nested constraints (<ref>) and, based on which nested constraint is violated most in this solution, subsequently divide the problem into two smaller instances of this problem. Analogously to the variable-fixing algorithms for (a,b)-Q/Box/C, the maximum number of divisions is O(n), which results in a worst-case time complexity of O(n^2 lognR/ϵ) for S/NC/C <cit.> and Θ(n^2 logR/n) for S/NC/I <cit.>. However, this worst-case complexity occurs only in pathological cases where each nested constraint is tight in an optimal solution, whereas it can be expected that the number of tight constraints is relatively small in practice. In particular, for the case with only upper nested constraints (<ref>), lower single-variable bounds (<ref>), and randomly generated problem parameters, it is shown in <cit.> that the expected number of tight constraints in an optimal solution to (a,b,f)-S/NC/C is O(log n).
  
  An alternative algorithm for (a,b)-Q/NC/C that attains the same time complexity as <cit.> for m=n is given in <cit.>. This algorithm is similar to the decomposition algorithm of <cit.> in the sense that it solves a (slightly different) sequence of (a,b)-Q/Box/C subproblems where the single-variable bounds for each subproblem are optimal solutions to previous subproblems. However, this algorithm avoids the time-consuming explicit computation of solutions to subproblems by exploiting the properties of a specific breakpoint searching algorithm for (a,b)-Q/Box/C and computing only the optimal Lagrange multiplier of each subproblem. As a consequence, this algorithm is shown to be one order of magnitude faster than the decomposition algorithm of <cit.>, while attaining the same worst-case time complexity of O(n log n) for m = O(n).
  
  Recently, for the problem (a,b)-Q/NC/C with only upper nested constraints, <cit.> shows that a specialized interior-point method is able to outperform the decomposition-based approach in <cit.>, which is similar to the approach in <cit.>, when the ratio m/n is larger than 0.1. Analogously to <cit.> as mentioned in Section <ref>, this method exploits the constraint structure of S/NC/C to compute search directions in O(n) time instead of O(n^3) time. Although the authors in <cit.> consider only upper nested constraints, it is straight-forward to generalize their results to problems involving also lower nested constraints <cit.>.
  
  Interestingly, <cit.> shows that we can solve the problem (a,b,f)-S/NC/C with only nested upper constraints and without the box constraints (<ref>) in O(n) time. More precisely, they show that this problem can be reduced to the problem of finding a concave cover of n points in ℝ^2 and give an O(n) time algorithm to find this cover. This algorithm is very similar to the recursive-smoothing algorithm mentioned in Section <ref> that is used to solve the vessel speed optimization problem <cit.> and processor scheduling problem with agreeable deadlines <cit.>.
  
  
  
  
   §.§ α/LC/γ: Optimization over laminar constraints
  
  Let 𝒩_1,…,𝒩_m be subsets of 𝒩 that satisfy the following property: if 𝒩_j ∩𝒩_ℓ≠∅, then either 𝒩_j ⊂𝒩_ℓ or 𝒩_j ⊃𝒩_ℓ for all j,ℓ∈ℳ. We formulate the resource allocation with laminar constraints, (a,b,f)-S/LC/γ, as follows:
  
      (a,b,f)-S/LC/γ :  min_x    ∑_i ∈𝒩 a_i f (x_i/a_i + b_i ) 
      s.t    ∑_i ∈𝒩 x_i = R, 
          L_j ≤∑_i ∈𝒩_j x_i ≤ U_j,    j ∈ℳ, 
          l_i ≤ x_i ≤ u_i,    i ∈𝒩, 
          x ∈ℝ^n    if γ = C,
      ℤ^n      if γ = I.
   
  Similarly to S/NC/γ, the problem S/LC/γ has been studied mainly with only the upper laminar constraints in (<ref>). The algorithms with the lowest computational complexities for these problems are given by <cit.> and have time complexities of O(n log n lognR/ϵ) for γ = C and O(n log n logR/n) for γ = I. For the general problem S/LC/γ, we obtain an efficient algorithm by combining results on the complexity of general separable convex optimization problems with linear constraints <cit.> and of the problem S/LC/C with a linear objective function <cit.>. More precisely, the time complexities of S/LC/C and S/LC/I are O(P_linear(8n^2,m)logRn/ϵ) and O(P_linear( 4n^2,m) logRm/n) respectively, where P_linear(n,m) is the time complexity of solving an instance of S/LC/C with a linear objective function <cit.>. The latter problem can be solved in O(n log n) time using the algorithm in <cit.>, hence we obtain a time complexity of O(n^2 log n logRn/ϵ) and O(n^2 log n logRm/n) for S/LC/C and S/LC/I respectively.
  
  With regard to the quadratic version of the problem, the special case of (a,b)-Q/LC/C with only upper laminar constraints can be solved in O(n log n) time <cit.>. This is done by reducing the problem to an instance of (a,b)-Q/NC/C with only upper nested constraints, which can be solved in O(n log n) time <cit.>. The general version of (a,b)-Q/NC/C with both lower and upper laminar constraints can be solved in O(n^2) time as an instance of the quadratic convex cost flow problem on a tree network <cit.>. Finally, the integer-valued problem (a,b)-Q/NC/I can be solved in O(n^2) time by first computing a solution to the continuous version of this problem and subsequently using a specific rounding procedure to obtain the optimal integer solution from this continuous solution <cit.>. By Corollary <ref>, this yields the following worst-case time complexities for (a,b,f)-S/LC/C and (a,b,f)-S/LC/I:
  
  
  Problem (a,b,f)-S/LC/γ can be solved in O(n^2) time. The special case (a,b)-Q/LC/C with only upper laminar constraints can be solved in O(n log n) time.
  
  
  As far as we are aware, the problem S/LC/γ has been studied primarily from an academic point of view in the literature, i.e., little attention is paid to possible applications. One relevant application that has received quite some importance in the past years is the scheduling of the (dis)charging of an electrical storage system within a smart grid (see also Section <ref>) where the energy can be drawn from each of the three phases within the low-voltage distribution network (see also <cit.>). The resulting problem is an instance of S/LC/C where the feasible set is the intersection of nested constraints (to model the storage capacity limits) and generalized upper bound constraints (to model the charging limits). We plan to investigate this topic further in future research.
  
  
  
  
   §.§ α/SC/γ: Optimization over submodular constraints
  
  Given a submodular function r over the ground set 𝒩, the (a,b,f)-separable resource allocation over submodular constraints can be formulated as follows:
  
      (a,b,f)-S/SC/γ :  min_x     ∑_i ∈𝒩 a_i f (x_i/a_i + b_i ) 
      s.t    ∑_i ∈𝒩 x_i = r(𝒩), 
         ∑_i ∈𝒮 x_i ≤ r(𝒮),   𝒮⊂𝒩, 
          x ∈ℝ^n    if γ = C,
      ℤ^n      if γ = I.
  
  
  For this problem, one can find two classes of algorithms in the literature. The first class consists of decomposition algorithms that first compute a solution to the problem without the submodular constraints (<ref>) and, based on which constraints are violated by this solution, split up the problem into two smaller instances of S/SC/γ <cit.>. Note that the infeasibility-guided algorithms for S/NC/γ as discussed in Section <ref> are based on the same principle. The best worst-case time complexities of such algorithms are O(n^2 logn r(𝒩)/ϵ + n · EO) for S/SC/C <cit.> and O(n^2( logr(𝒩)/n +  F log r(𝒩)) + n F̃) for S/SC/I <cit.>, where EO is the time required to minimize a given submodular function and F is the time required to check the feasibility of a given vector for the submodular constraints. Moreover, F̃ is the time required to determine for a given solution x that is feasible for the submodular constraints (<ref>) by how much we can increase a given variable x_i without violating any of these submodular constraints. For the quadratic problems (a,b)-Q/SC/γ, these complexities reduce to O(n^2 + n ·EO) for (a,b)-Q/SC/C and to O(n^2 F log r(𝒩) + nF̃) for (a,b)-Q/SC/I. By Corollary <ref>, these are also the complexities for solving the problems (a,b,f)-S/SC/C and (a,b,f)-S/SC/I using decomposition algorithms.
  
  The second class consists of greedy algorithms that solve the integer version S/SC/I by incrementally building an optimal solution (see, e.g., <cit.>). However, instead of incrementing the total amount of allocated resource by unit steps, these algorithms apply a scaling procedure to determine larger step sizes that speed up the building process while still maintaining feasibility of the current solution. To solve the continuous version S/SC/C, these algorithms exploit a proximity result between optimal solutions of S/SC/C and S/SC/I (see, e.g., <cit.>) that states that for any optimal solution x^* to S/SC/I there exists an optimal solution x̃ to S/SC/C such that |x̃_i - x^*_i| ≤ n-1. As a consequence, to solve S/SC/C with an given accuracy ϵ, one can scale all problem parameters by a factor ⌈n/ϵ⌉, solve the scaled problem with integer variables using the greedy algorithm, and scale back the resulting solution. The most efficient algorithms of this class run in O(n (log n + F̃) logr(𝒩)/ϵ n) time for S/SC/C and O(n (log n + F̃) logr(𝒩)/n) for S/SC/I <cit.>, which unfortunately cannot be improved for the quadratic cases (a,b)-Q/SC/C and (a,b)-Q/SC/I.
  
  
  One relevant special case of (a,b)-Q/SC/C is the problem of computing the minimum-norm point of a base polytope (see, e.g., <cit.>). This problem is equivalent to (e̅,0)-Q/SC/C and plays an important role as a subroutine in several algorithms for machine learning problems and submodular function minimization <cit.>. One of the most popular algorithms in practice for finding the minimum-norm point is Wolfe's algorithm <cit.>, which solves the problem by iteratively updating a hyperplane and the minimum-norm point on this hyperplane based on the feasibility of this point. The authors in <cit.> show that this algorithm computes an ϵ-approximate solution to (e̅,0)-Q/SC/C in O(nM^2/ϵ) time, where M is the norm of the maximum-norm point. Although there are algorithms for finding the minimum-norm point that have a better computational complexity, e.g., the aforementioned decomposition and greedy algorithms, Wolfe's algorithm has been shown to be among the fastest algorithms in practice <cit.>.
  
  
  
  
  § IMPACT ON APPLICATIONS
  
  
  
  
  The goal of this section is to show the relevance of (a,b,f)-separable resource allocation problems in applications. As we discussed in the previous section, our newly derived complexity results might not directly lead to practical faster algorithms for these problems. However, for a number of applications from the domains of telecommunications, statistics, and energy management, we show that our reduction result lead to new insights into common practices in these fields. In particular, we show that two problems in the area of vessel routing and processor scheduling can be solved in O(n log n) time rather than O(n^2) time, which was the previously known best complexity for these problems. Finally, with this collection of applications and the included references, we intent to stimulate cross-disciplinary research that leads to new structural results and algorithms for RAPs that are applicable to many different research fields.
  
  
  
  
  
   §.§ Power allocation in multi-channel communication systems
  
  
  In many telecommunication systems, data can be transmitted over several parallel channels to reduce the amount of noise experienced when transmitting the data (see, e.g., <cit.>). The amount of data that can be transmitted through a given channel i, i.e., the channel capacity, depends on the power x_i spent on this channel, its bandwidth B_i, and a “gain” parameter c_i that represents the amount of noise on the channel. One goal in these systems is to allocate a given budget of total power P^tot over a set 𝒩 of n channels such that the overall channel capacity is maximized while respecting power limits on each channel. This problem can be formulated mathematically as
  
      (P) :  max_x ∈ℝ^n    ∑_i ∈𝒩 B_i log (1 + c_i x_i) 
      s.t.    ∑_i ∈𝒩 x_i = P^tot, 
          0 ≤ x_i ≤P̅_i,    i ∈𝒩,
  
  where P̅_i is the maximum allowed power on channel i.
  
  Note that for a given channel i ∈𝒩 we have
  
      B_i log (1 + c_i x_i)
      =
      B_i log( 1/c_i + x_i/B_i· B_i c_i )
      =
      
      
      
      
      B_i log( 1/c_i + x_i/B_i)
      + B_i log(B_i c_i).
  
  Since the second term B_i log(B_i c_i) in the above expression is constant, we can replace the objective function of Problem (P) by ∑_i ∈𝒩 B_i log( 1/c_i + x_i/B_i) without changing the optimal solution to the problem. The resulting problem is an instance of (B,B̅,f)-S/Box/C with B := (B_i)_i ∈𝒩, B̅ := (1/B_i c_i)_i ∈𝒩, and f(x_i) := -log(x_i). Thus, by Corollaries <ref> and <ref>, we can solve this problem as an instance of (B,B̅)-Q/Box/C in O(n) time, i.e., we can replace each term B_i log (1 + c_i x_i) by x_i^2/B_i + x_i/B_i c_i. Note that this is more efficient than several existing approaches for solving Problem (P) that claim a linear time complexity (see, e.g., <cit.>). The reason for this is that these algorithms achieve this complexity only if the gain parameter c has already been sorted, which is however only the case for some specific communication systems (see, e.g., <cit.>).
  
  Another common objective for the channel power allocation problem (P) (see, e.g., <cit.>) is to minimize the mean square error between different channels from a set 𝒩. This objective is given by
  
      min_x ∈ℝ^n ∑_i ∈𝒩w_i/A_i x_i + D_i,
  
  where w_i, a_i, and b_i are positive parameters for each i ∈𝒩. This objective function is (a,b,f)-separable by choosing a_i := √(w_i/A_i) and b_i := D_i/√(w_i A_i) for each i ∈𝒩 and f(x_i) := 1/x_i:
  
      a_i f (x_i/a_i + b_i )
      =
      √(w_i/A_i)1/x_i √(A_i/w_i) + D_i/√(w_i A_i)
      =
      w_i/√(A_i)1/x_i √(A_i) + D_i/√(A_i)
      =
      w_i/A_i x_i + D_i.
  
  Moreover, several variations of the channel power allocation problem have been studied with, e.g., bounds on disjoint or nested subsets of allocations (see, e.g., <cit.> and <cit.> respectively). Analogously to Problem (P), one can show that these problems are instances of (a,b,f)-S/GBC/C and (a,b,f)-S/NC/C  and thus can be solved as instances of (a,b)-Q/GBC/C and (a,b)-Q/NC/C respectively.
  
  
  
   §.§ Storage operation in energy systems
  
  
  
  Storage systems are becoming a crucial part of current and future sustainable energy systems (see, e.g., <cit.>). Such systems support satisfying the energy demand of, e.g., a neighborhood, when renewable energy sources such as solar and wind are insufficient due to, e.g., unfavorable weather conditions. Commonly, the operation of the storage systems is done in a way that the stress on the overall grid is reduced as much as possible. Determining for a given time horizon the best operational schedule for the storage, i.e., how much energy should be (dis)charged at each moment to reach the overall goal in the best way, leads to an optimization problem. In this problem, we divide the overall time horizon into n equidistant time intervals of length Δ t indexed by the set 𝒩 := { 1,…,n } and determine for each interval i ∈𝒩 the (dis)charging power x_i during this interval. This amount is limited by the minimum and maximum charging rates X_min and X_max. Moreover, the charging must be done such that the storage capacity D is not exceeded. Given the initial amount of energy S_start in the storage and a desired target amount S_end at the end of the horizon, the storage operation problem can be formulated as follows (see also <cit.>):
  
      (B) :  min_x ∈ℝ^n    ∑_i ∈𝒩ϕ_i (x_i) 
      s.t.    0 ≤ S_start + Δ t ∑_i=1^j x_i ≤ D,    j ∈𝒩\{ n }, 
          S_start + Δ t ∑_i ∈𝒩 x_i = S_end, 
          X_min≤ x_i ≤ X_max,    i ∈𝒩,
  
  where the functions ϕ_i represent the desired grid objective. Note that if each function ϕ_i is convex, which is in general the case in this problem setting, this problem is an instance of S/NC/C.
  
  Three commonly seen objectives that are used to reduce grid stress and congestion are: minimal import and export of energy from the main grid (also known as energy-autarky, see, e.g., <cit.>), load profile flattening (see, e.g., <cit.>), and minimizing peak consumption (see, e.g., <cit.>). One way to model the latter case is to set a maximum level M for the overall power consumption of the neighborhood. Given the power consumption p := (p_i)_i ∈𝒩 of the neighborhood, we can model these objectives as follows:
  
      Minimizing exchange with main grid:    ϕ_i (x_i) = |x_i + p_i |; 
      Load profile flattening:    ϕ_i (x_i) = (x_i + p_i)^2; 
      Threshold peak shaving:    ϕ_i (x_i) =  0    if  x_i + p_i ≤ M, 
      f(x_i + p_i)    if  x_i + p_i > M,
  
  where f is a convex non-decreasing function with f(M) = 0. Note that for the objective of load profile flattening, Problem (B) is an instance of (e̅,p)-Q/NC/C, where e̅ is the vector of ones. Moreover, for the other two objectives, Problem (B) is an instance of (e̅,p,f)-S/NC/C where f is the absolute value function or the piecewise function
  
      f (y) = 
      0    if  y ≤ M, 
      f(y)    if  y > M.
  
  It follows by Corollary <ref> that the optimal solution to (e̅,p)-Q/NC/C is also optimal for (e̅,p,f)-S/NC/C for these two functions. This implies that we can schedule the storage (dis)charging such that all three objectives are satisfied simultaneously by aiming for load profile flattening. This is an effect that can also be observed for other renewable energy systems such as photovoltaic (solar panel) systems and electric vehicle charging (see, e.g., <cit.>) and heat pumps (see, e.g., <cit.>). Moreover, energy tariff systems that employ piecewise linear cost functions have been shown to be able to flatten the load profile, i.e., the objective modeled by a quadratic cost function (see, e.g.,  <cit.>). Since such tariff systems are simpler to explain to end users, they are more likely to be accepted than systems using quadratic cost functions while still achieving the desired objective of load profile flattening.
  
  
  
  
   §.§ Stratified sampling
  
  
  Stratified sampling is a sampling method suitable for situations where it is likely that a random sample is not a proper representation of the population <cit.>. Such a situation occurs, e.g., when several subclasses of the population score extremely on the to-be-estimated characteristic. To deal with this specific case, we partition the given population into n so-called strata with sizes N_1,…, N_n that, ideally, represent the aforementioned subclasses. Given the desired overall sample size R, the goal is to determine for each stratum i ∈𝒩 := { 1,…,n } the number of samples x_i drawn from this stratum while minimizing the variance of the given characteristic. Following the formulation in <cit.>, the optimal sample allocation is the solution of the following optimization problem:
  
      min_x ∈ℤ^n    ∑_i ∈𝒩(N_i^2 S_i^2/x_i - N_i S_i^2 ) 
      s.t.    ∑_i ∈𝒩 x_i = R, 
          0 ≤ x_i ≤ N_i,    i ∈𝒩,
  
  where S_i^2 is the variance of the characteristic within stratum i. Similarly to <cit.>, the sample bounds of 0 and N_i can be chosen differently to ensure a minimum or maximum number of samples drawn from a given stratum.
  
  Let D ∈ℝ^n be a vector with D_i := N_i^2 S_i^2 for all i ∈𝒩. Then the above problem is an instance of the problem (D,0,f)-S/Box/I with f(x_i) = 1/x_i. Thus, by Corollary <ref>, we can solve this problem as an instance of (D,0)-Q/Box/I in O(n) time. Note that, in contrast to the approaches in, e.g., <cit.>, this complexity depends only on the number n of strata and not on the actual strata sizes N_1,…,N_n or desired sample size R. As a consequence, our reduction result yields a promising approach to determine optimal sample sizes in large datasets, which can contain billions of samples (see, e.g., <cit.>).
  
  
  
   §.§ Vessel speed optimization
  
  
  A recent trend in ship routing is to actively manage the ship's sailing speed to reduce fuel costs and carbon emissions <cit.>. As a consequence, when determining the routes of a fleet of ships to deliver cargo within given timing constraints, one must be able to determine the minimum cost of having a ship sail a given route. This problem is known as the vessel speed optimization problem (see, e.g., <cit.>). In this problem, we are given a route between n+1 ports starting at port 0 at time t^start and required to finish at time t^end at port n. The distance between consecutive ports i-1 and i is given by d_i and each port i must be serviced by the ship within a given time window [A_i, D_i]. The goal is to determine for each leg i ∈𝒩 := { 1,…,n } of the tour, i.e., for each distance d_i, a speed v_i such that the fuel cost of sailing at these speeds is minimized. Following <cit.>, we formulate this problem as follows:
  
      (V) :  min_t ∈ℝ^n+1,  v ∈ℝ^n    ∑_i ∈𝒩 d_i c(v_i) 
      s.t.     t_i + d_i/v_i = t_i+1,    i ∈{ 0 }∪𝒩\{ n }, 
          A_i ≤ t_i ≤ D_i,    i ∈𝒩\{ n }, 
          t_0 = t^start,  t_n = t^end, 
          v^min≤ v_i ≤ v^max,    i ∈𝒩.
  
  Here, v^min and v^max are the minimum and maximum cruising speeds and c is a non-decreasing convex function that models the relation between sailing speed and fuel costs per unit distance.
  
  From this formulation, it follows by induction on i that t_i = t^start + ∑_k=1^i d_k/v_k for all i ∈𝒩 and that t^start + ∑_k=1^n d_k/v_k = t^end. Let x_i := d_i/v_i and q(x_i) := c(1/x_i). It follows that
  
      d_i c(v_i) = d_i c ( d_i/x_i)
      = d_i q ( x_i/d_i).
  
  Note that q is convex since c is non-decreasing. This means that Problem (V) is equivalent to the following convex optimization problem:
  
      min_x ∈ℝ^n    ∑_i ∈𝒩 d_i q ( x_i/d_i) 
      s.t.     A_i - t^start≤∑_k=1^i x_i ≤ D_i - t^start,    i ∈𝒩\{ n }, 
         ∑_i ∈𝒩 x_i = t^end - t^start, 
         d_i/v^max≤ x_i ≤d_i/v^min,    i ∈𝒩.
  
  This problem is an instance of (d,0,q)-S/NC/C. Hence, by Corollary <ref>, this problem and thus Problem (V) can be solved in O(n log n) time by, e.g., the fast algorithm in <cit.>. This result is relevant since Problem (V) often occurs as a subproblem in fleet routing algorithms <cit.> and thus using a faster algorithm for this subproblem can lead to significant speed-ups for the overall algorithm.
  
  
  
   §.§ Speed scaling
  
  
  
  
  Efficient energy usage is an important topic within the development of computing systems <cit.>. To reduce energy consumption, modern computer processors can adjust their speed to save energy while still meeting their performance constraints. This leads to scheduling problems where a set of tasks needs to be scheduled and processor speeds need to be chosen such that all tasks are executed before their deadline (see <cit.> for a survey). One special case of these types of scheduling problems is the case where the deadlines are agreeable, i.e., deadlines are ordered according to the arrival times of the tasks (see also <cit.>). In this problem, we are given n tasks indexed by the set 𝒩 that must be processed on a single processor. Each task i ∈𝒩 has an arrival time A_i, deadline D_i, and amount of work w_i that can be interpreted as the amount of operations and calculations the processor must execute to perform this task. The goal is to select for each task i an execution speed s_i and starting time B_i such that each task is processed before its deadline and the total energy usage of the processor is minimized.
  
  Since the deadlines are agreeable we have that D_i ≤ D_k if A_i ≤ A_k for any two tasks i,k ∈𝒩. Moreover, in an optimal schedule, the tasks can be scheduled in non-decreasing order of their deadlines <cit.>. This means that we can formulate this speed scaling problem as follows (see also <cit.>:
  
      (S) :  min_s ∈ℝ^n  B ∈ℝ^n    ∑_i ∈𝒩 p(s_i) w_i/s_i
      s.t.     B_i + w_i/s_i≤ D_i,    i ∈𝒩, 
          B_i ≥ A_i,    i ∈{ 1,…,n }, 
          B_i + w_i/s_i≤ B_i+1,    i ∈𝒩\{ n }, 
          0 < s_i ≤ s^max,    i ∈𝒩,
  
  where s^max is the maximum processor speed and p is a convex function that models the relation between processor speed and its energy usage. Note that we can impose a nonzero lower bound on each s_i so that the feasible set of this problem is guaranteed to be closed. Since we must choose the speeds such that each task can be executed in the maximum time that is available for it, we have that w_i/s_i≤ D_i - A_i. This yields a lower bound on s_i of w_i/D_i - A_i that is nonzero since w_i > 0 and D_i > A_i. 
  
  If the processor is active until the latest deadline regardless of the scheduling of the tasks, then there exists an optimal schedule with no idle time <cit.>. This means that we can add without loss of generality the constraint B_i = ∑_k=1^i w_i/s_i for all i ∈𝒩 to the formulation of Problem (S). Let x_i := w_i/s_i for all i ∈𝒩 and q(x_i) := x_i p(1/x_i) (note that q is convex). It follows that
  
      p(s_i) w_i/s_i = p(w_i/x_i) x_i = w_i q(x_i/w_i).
  
  Using the lower bound on s_i, the added constraint on B_i, the transformation x_i = w_i/s_i, and the function q, we can reformulate Problem (S) to
  
      min_x ∈ℝ^n    ∑_i ∈𝒩 w_i q (x_i/w_i) 
      s.t.     A_i+1≤∑_k=1^i x_k ≤ D_i,    i ∈𝒩\{ n }, 
         ∑_i ∈𝒩 x_i = D_n, 
         w_i/s^max≤ x_i ≤ D_i - A_i,    i ∈𝒩.
  
  This is an instance of (w,0,q)-S/NC/S. Hence, by Corollary <ref>, this problem and thus Problem (S) can be solved in O(n log n) time. This result also leads to complexity improvements for speed scaling problems that can be reduced to Problem (S), e.g., for the multi-core processor scheduling problem considered in <cit.>.
  
  Recently, <cit.> applied the equivalence result in <cit.> to improve the time complexity of several other speed scaling problems. Together with the result in this section, this suggests that there is a great potential for using the reduction result in this article to contribute to more efficient algorithms within this research field.
  
  
  
  
  § CONCLUSIONS AND OUTLOOK
  
  
  
  In this article, we studied the resource allocation problem (RAP) with additional submodular constraints. We proved that the class of RAPs whose objective function is (a,b,f)-separable can be solved efficiently as quadratic RAPs if a certain optimality condition of the general separable problem is satisfied. Using this reduction result, we derive new worst-case time complexity results on several relevant special cases of the studied problem. Moreover, we have shown the impact of our reduction result on several core problems in wireless communications, smart grids, statistics, routing, and processor management.
  
  One major direction for future research is the extension of the reduction result to other problems. The most intuitive starting point for this is to search for other optimization problems that satisfy the required optimality condition. Promising candidates for this are problems that are variations on the RAPs studied in this article, e.g., RAPs with interval and cardinality constraints <cit.> and with additional nonseparable terms in the objective functions <cit.>.
  Besides this more technical direction, in the light of a more cross-disciplinary approach towards the study of RAPs, it is worthwhile to identify more research fields and applications, next to the ones that we discussed in this article, where RAPs are being studied and where our results can have impact and lead to new insights.
  
  
  
  
  § ACKNOWLEDGMENTS
  
  This research has been conducted within the SIMPS project (647.002.003) supported by NWO and Eneco.
  
  
  
  
  
  
  § LAMINAR CONSTRAINTS ARE A SPECIAL CASE OF SUBMODULAR CONSTRAINTS
  
  
  In this appendix, we show that laminar (or tree) constraints are a special case of submodular constraints. Recall that
  
  
    * laminar constraints are of the form L_j ≤∑_i ∈𝒩_j x_i ≤ U_j, j ∈ℳ, where the subsets 𝒩_1,…,𝒩_m of 𝒩 have the property that either 𝒩_j ∩𝒩_ℓ = ∅, 𝒩_j ⊂𝒩_ℓ, or 𝒩_j ⊃𝒩_ℓ for all j,ℓ∈ℳ;
  
    * submodular constraints are of the form ∑_i ∈𝒮 x_i ≤ r(𝒮), 𝒮⊂𝒩 and ∑_i ∈𝒩 x_i = r(𝒩), where r is a submodular function.
  
  For this, we use a result from <cit.> on so-called cross-free families of subsets. A family ℱ⊆ 2^𝒩 is called cross-free if none of its elements cross, i.e., for any two subsets 𝒳, 𝒴∈ℱ we have that at least one of the sets 𝒳∩𝒴, 𝒳∩ (𝒩\𝒴), (𝒩\𝒳) ∩𝒴, or (𝒩\𝒳) ∩ (𝒩\𝒴) is empty. For a given cross-free family ℱ containing ∅ and 𝒩 and for any set function r :  ℱ→ℛ with r(∅) = 0, the set
  
      ℬ(ℱ,r) := { x ∈ℝ^n  |  ∑_i ∈𝒳 x_i ≤ r(𝒳)  ∀𝒳∈ℱ,  ∑_i ∈𝒩 x_i = r(𝒩) }
  
  is a base polyhedron <cit.>. This means that there exists a submodular function r'  :  2^𝒩→ℝ such that 
  
      ℬ(ℱ,r) = { x ∈ℝ^n  |  ∑_i ∈𝒳 x_i ≤ r'(𝒳)  ∀𝒳⊂𝒩,  ∑_i ∈𝒩 x_i = r(𝒩) } .
  
  Thus, we can show that laminar constraints are a special case of submodular constraints if for a given feasible set 𝒞' determined by laminar constraints we can find a cross-free family ℱ and a set function r :  ℱ→ℝ such that ℬ(ℱ,r) = 𝒞'.
  
  For given laminar constraints L_j ≤∑_i ∈𝒩_j x_i ≤ U_j, j ∈ℳ and a feasible set 𝒞' := { x ∈ℝ^n  |  L_j ≤∑_i ∈𝒩_j≤ U_j, j ∈ℳ}, we define the following family of subsets of 𝒩:
  
      𝒩' := {𝒩_j  |  j ∈ℳ}∪{𝒩\𝒩_j  |  j ∈ℳ} .
  
  Note, that the feasible set 𝒞' is equal to ℬ(𝒩',r'), where r' :  𝒩' →ℝ is a set function on 𝒩' given by
  
      r'(𝒳) := 
      U_j    if  X = 𝒩_j  for some  j ∈ℳ, 
      
      R - L_j    if  X = 𝒩\𝒩_j  for some  j ∈ℳ.
  
  We claim that 𝒩' is a cross-free family, which immediately implies that the set ℬ(𝒩',r') is a base polyhedron and thus that laminar constraints are a special case of submodular constraints. For this, we consider for two different sets 𝒳, 𝒴∈𝒩' four cases:
  
  
    * If 𝒳 = 𝒩_j and 𝒴 = 𝒩_ℓ for some j, ℓ∈ℳ, then either 𝒳∩𝒴= ∅, 𝒳⊂𝒴, or 𝒳⊃𝒴. The latter two cases imply that 𝒳∩ (𝒩\𝒴) = and (𝒩\𝒳) ∩𝒴 = ∅ respectively. Thus, in all three cases, 𝒳 and 𝒴 do not cross.
  
    * If 𝒳 = 𝒩_j and 𝒴 = 𝒩\𝒩_ℓ for some j, ℓ∈ℳ, then either 𝒳∩ (𝒩\𝒴)= ∅, 𝒳⊂ (𝒩\𝒴), or 𝒳⊃ (𝒩\𝒴). The latter two cases imply that 𝒳∩𝒴 = ∅ and (𝒩\𝒳) ∩ (𝒩\𝒴) = ∅ respectively. Thus, in all three cases, 𝒳 and 𝒴 do not cross.
  
  
    * If 𝒳 = 𝒩\𝒩_j and 𝒴 = 𝒩_ℓ for some j, ℓ∈ℳ, we can use the argument in case 2 with the roles of 𝒳 and 𝒴 interchanged to conclude that 𝒳 and 𝒴 do not cross.
  
    * If 𝒳 = 𝒩\𝒩_j and 𝒴 = 𝒩\𝒩_ℓ for some j, ℓ∈ℳ, then either (𝒩\𝒳) ∩ (𝒩\𝒴)= ∅, (𝒩\𝒳) ⊂ (𝒩\𝒴), or (𝒩\𝒳) ⊃ (𝒩\𝒴). The latter two cases imply that (𝒩\𝒳) ∩𝒴 = ∅ and 𝒳∩ (𝒩\𝒴) = ∅ respectively. Thus, in all three cases, 𝒳 and 𝒴 do not cross.
  
  
  
  
  
  § AN ALTERNATIVE PROOF THAT CONDITION <REF> HOLDS FOR THE RESOURCE ALLOCATION PROBLEM WITH LAMINAR CONSTRAINTS
  
  
  Here we present an alternative proof of the claim that Condition <ref> holds for the resource allocation problem with laminar constraints (S/LC/γ). Before we prove this result in Lemma <ref>, we first show that the difference between any two feasible solutions x and z of S/LC/γ can be written as a nonnegative combination of vectors in ℰ_𝒞'(x), where 𝒞' is the feasible set of S/LC/γ. In other words, z-x belongs to the cone generated by the vectors in ℰ_𝒞'(x). To this end, we present the following procedure to obtain this combination. Starting from the solution x̅^0 := x, we construct a series of intermediate vectors (x̅^t)_t ≥ 0 that finally leads to z by iteratively transferring amounts between two variables. We do this in such a way that the distance ∑_i ∈𝒩 |z_i - x̅^t_i| reduces as t increases and becomes zero for some t̅≥ 0, meaning that x̅^t̅ = z. To ensure finiteness of this process, we always choose two variables with indices i,k such that x̅^t_i > z_i and x̅^t_k < z_k. By transferring an amount of λ_ik := min(x̅^t_i - z_i, z_k - x̅^t_k) between those variables, we have for the subsequent vector x̅^t+1 that either x̅^t+1_i = z_i or x̅^t+1_k = z_k. By repeating this process, we finally reach an intermediate vector x̅^t̅ that equals z. For each selected pair (i,k), the value λ_ik represents a positive coefficient in the desired conic combination.
  
  To ensure that each index pair with a positive coefficient is an exchangeable pair (see also Lemma <ref>), i.e., is in ℰ_𝒞'(x), we restrict the choice of index pair in the procedure in the following way. First, we order the subsets such that 𝒩_j⊂𝒩_j' implies j > j' for all j,j' ∈ℳ. Moreover, we define 𝒩_0 := 𝒩. Now we iterate through the subsets from 𝒩_m to 𝒩_0 and during iteration j we allow only exchanges between variables whose indices belong to the current subset 𝒩_j.
  
  The procedure is summarized in Algorithm <ref>. In this algorithm, for any j ∈{ 0 }∪ℳ, t_j is the last iteration index such that no exchanges are allowed between a variable whose index is in 𝒩_j and a variable whose index is not in 𝒩_j. 
  
  
  In Lemma <ref>, we prove several properties of the output λ of the algorithm and of the intermediate vectors (x̅^t)_t ≥ 0.
  
  The following statements hold for the output λ and the sequence of intermediate vectors (x̅^t)_t ≥ 0 of Algorithm <ref> when applied to two feasible solutions x and z to S/LC/γ:
  
  
    * 
  ∑_i ∈𝒩x̅_i^t = C for all t ≥ 0.
  
    * If x_i^t > z_i for a given t ≥ 0, then z_i ≤x̅_i^t'≤x̅_i^t≤ x_i for all t' > t;
  
    * If x_i^t < z_i for a given t ≥ 0, then z_i ≥x̅_i^t'≥x̅_i^t≥ x_i for all t' > t;
  
    * If x_i^t = z_i for a given t ≥ 0, then x_i^t' = z_i for all t' > t.
  
    * For a given j and t ≥ t_j, we have that either x̅_i^t≤ z_i for all i ∈𝒩_j or x̅_i^t ≥ z_i for all i ∈𝒩_j.
  
    * Each index pair (i,k) ∈𝒩^2 is selected at most once over the entire course of the algorithm.
  
    * For a given j and any t ≤ t_j, it holds that ∑_ℓ∈𝒩_jx̅^t_ℓ = ∑_ℓ∈𝒩_j x_ℓ.
  
    * z-x = ∑_(i,k) ∈𝒩^2λ_ik(e^k - e^i).
  
  
  
  
  Part (1): Follows by induction on t since ∑_ℓ∈𝒩x̅_ℓ^t+1 = ∑_ℓ∈𝒩x̅_ℓ^t + λ_ik - λ_ik = ∑_ℓ∈𝒩x̅_ℓ^t for all t ≥ 0 and x̅^0 = x.
  
  Part (2): For a given t ≥ 0, we have that x̅^t_i > z_i implies that either x̅^t+1_i = x̅^t_i (if i is not selected during iteration t) or z_i ≤x̅^t+1_i < x̅^t_i (if i is selected during iteration t). Thus, we have that x̅^t_i > z_i implies that z_i ≤x̅^t+1_i ≤x̅^t_i. By induction, one can deduce that if x_i^t > z_i, then z_i ≤x̅^t'_i ≤x̅^t_i ≤ x_i for all t ≥ 0 and t' > t.
  
  Part (3): Is analogous to the proof of Part (2).
  
  Part (4): If x_i^t = z_i, then i will not be selected anymore as part of an exchangeable pair. Hence, x_i^t = x_i^t+1 = … = z_i.
  
  Part (5): By definition of t_j, we have that either x̅^t_j_ℓ≥ z_ℓ for all ℓ∈𝒩_j or x̅^t_j_ℓ≤ z_ℓ for all ℓ∈𝒩_j. It follows directly from Parts (2)-(4) that in the first case x̅^t_ℓ≥ z_ℓ for all ℓ∈𝒩_j and that in the second case x̅^t_ℓ≤ z_ℓ for all ℓ∈𝒩_j.
  
  Part (6): If the pair (i,k) is chosen during some iteration t, then either x̅^t+1_i = z_i or x̅^t+1_k = z_k. Thus, at least one of the indices i,k cannot be chosen again as part of a pair, hence the pair (i,k) is selected at most once.
  
  Part (7): For a given t ≤ t_j, let (i,k) denote the selected pair during iteration t-1. Thus, there is a subset 𝒩_j' with j' > j such that i,k ∈𝒩_j'. By the ordering of the subsets, we have either 𝒩_j∩𝒩_j' = ∅ or 𝒩_j'⊂𝒩_j. Thus, either both or neither of the indices i and k are in 𝒩_j. This implies that ∑_ℓ∈𝒩_jx̅_ℓ^t = ∑_ℓ∈𝒩_jx̅_ℓ^t-1. By induction on t, it follows that ∑_ℓ∈𝒩_jx̅_ℓ^t = ∑_ℓ∈𝒩_jx̅_ℓ^0 =  ∑_ℓ∈𝒩_j x_ℓ.
  
  Part (8): Follows from Part (6) and the fact that λ_ik = 0 if the pair (i,k) has not been chosen during any iteration.
  
  
  
  Lemma <ref> implies that for any two feasible solutions x and z, the difference z-x can be written as a nonnegative combination of the vectors (e^k - e^i)_(i,k) ∈𝒩^2. We strengthen this result in Lemma <ref> by proving that z-x can be written as a nonnegative combination of the vectors in ℰ_𝒞'(x).
  
  Let λ and (x̅^t)_t ≥ 0 be the output of Algorithm <ref> applied to two feasible solutions x and z of the problem S/LC/γ. If λ_ik > 0 for a given pair (i,k) ∈𝒩^2, then (i,k) ∈ℰ_𝒞'(x) and λ_ℓ,i = λ_k,ℓ = 0 for all ℓ∈𝒩.
  
  
  
  Note that for any two indices i,k ∈𝒩, the solution x + ϵ (e^k - e^i) is feasible for some ϵ > 0 if and only if we have for each subset 𝒩_j that contains i but not k that ∑_ℓ∈𝒩_j x_ℓ > L_j, and for each subset 𝒩_j' that contains k but not i that ∑_ℓ∈𝒩_j' x_ℓ < U_j'. Let 𝒩_j' be the minimal subset that contains both i and k, i.e., there is no other subset 𝒩_j such that 𝒩_j ⊂𝒩_j' and i,k ∈𝒩_j. If λ_ik > 0, then there exists t_j'+1 < t ≤ t_j' such that the pair (i,k) has been selected during iteration t. Thus, x̅_i^t > x̅_i^t+1≥ z_i and x̅_k^t < x̅_k^t+1≤ z_k. By Parts (2) and (3) of Lemma <ref>, this means that x_i > z_i and x_k < z_k and that x̅^t_i ≥ z_i and x̅^t_k ≤ z_k for all t ≥ 0. By Part (5) of Lemma <ref>, this means that for any subset 𝒩_j that contains i but not k we have that x̅^t_j_ℓ≥ z_ℓ for all ℓ∈𝒩_j since j > j'. In particular, we have by Part (2) that x̅^t_j_i > z_i since x̅^t_i > z_i. It follows from feasibility of z and Part (7) that L_j ≤∑_ℓ∈𝒩_j z_ℓ < ∑_ℓ∈𝒩_jx̅^t_j_ℓ = ∑_ℓ∈𝒩_j x_ℓ. Analogously, we can show that U_j > ∑_ℓ∈𝒩_j x_ℓ. Thus, the solution x + ϵ(e^k - e^i) is feasible for some ϵ > 0, hence (i,k) ∈ℰ_𝒞'(x).
  
  Note that for any ℓ∈𝒩, we can only have that λ_ℓ i >0 if there is some iteration t with x̅^t_i < z_i. Since x̅^t_i ≥ z_i for all t ≥ 0, we must have that λ_ℓ i = 0. Analogously, we must have that λ_k ℓ = 0 since x̅^t_k ≤ z_k for all t ≥ 0.
  
  
  
  
  Lemma <ref> implies that we can partition 𝒩 into three subsets such that one subset contains all indices i for which λ_ik > 0 for at least one k ∈𝒩, one subset contains all indices i for which λ_ki > 0 for at least one k ∈𝒩, and one subset contains all indices i such that λ_ik = λ_ki = 0 for all k ∈𝒩. More precisely, we can define the following partition of 𝒩:
  
      ℒ(x)    := { i ∈𝒩 |  λ_ik > 0  for some  k ∈𝒩}, 
      𝒰(x)    := { i ∈𝒩 |  λ_ki > 0  for some  k ∈𝒩}, 
      ℱ(x)    := 𝒩\ (ℒ(x) ∪𝒰(x))
      = { i ∈𝒩 |  λ_ik = λ_ki = 0  for all  k ∈𝒩}.
  
  Using this partition and Lemma <ref>, we can show that S/LC/γ satisfies Condition <ref>.
  
  For γ∈{C,I}, the problem S/LC/γ satisfies Condition <ref>.
  
  
  
  First, we prove the “only if”-part. Suppose x is optimal for S/LC/γ and there exists an index pair (i,k) ∈ℰ_𝒞'(x) such that ϕ_k^+(x_k) < ϕ_i^-(x_i). By definition of ℰ_𝒞'(x) and the left and right derivatives ϕ_k^+ and ϕ_i^-, there exists ϵ > 0 such that x + ϵ(e^k - e^i) is feasible and
  
      ϕ_k (x_k + ϵ) + ϕ_i (x_i - ϵ) < ϕ_k (x_k) + ϕ_i (x_i).
  
  This implies that the objective value of x + ϵ(e^k-e^i) is smaller than that of x. Hence, x cannot be optimal, which is a contradiction. It follows that ϕ_k^+(x_k) ≥ϕ_i^-(x_i) for all (i,k) ∈ℰ_𝒞'(x).
  
  Second, we prove the “if”-part. Let x be a feasible solution such that ϕ_k^+(x_k) ≥ϕ_i^-(x_i) for all (i,k) ∈ℰ_𝒞'(x) and let z be an arbitrary feasible solution. Moreover, let λ∈ℝ^n × n denote the output of Algorithm <ref> when applied to x and z. By Lemma <ref> and definition of the sets ℒ(x), 𝒰(x), and ℱ(x), we have that
  
      z-x    = ∑_(i,k) ∈𝒩^2λ_ik(e^k - e^i)
      = ∑_(i,k) ∈ℰ_𝒞'(x)λ_ik(e^k - e^i) 
         = ∑_(i,k) ∈ℰ_𝒞'(x),
       i ∈ℒ(x)λ_ik(e^k - e^i) 
      = ∑_(i,k) ∈ℰ_𝒞'(x),
       i ∈ℒ(x), 
       k ∈𝒰(x)λ_ik(e^k - e^i).
  
  We define the following subgradient g ∈ℝ^n at the solution x:
  
      g_i 
      := ϕ_i^-(x_i)    if  i ∈ℒ(x), 
      
      := ϕ_i^+(x_i)    if  i ∈𝒰(x), 
      ∈ [ϕ_i^-(x_i),ϕ_i^+(x_i)]    if  i ∈ℱ(x).
  
  By convexity of the functions ϕ_i, it follows that
  
      ∑_i ∈𝒩 (ϕ_i(z_i) - ϕ_i(x_i))
         ≥
      g^⊤ (z - x)
      =
      ∑_(i,k) ∈ℰ_𝒞'(x),
       i ∈ℒ(x), 
       k ∈𝒰(x)λ_ik g^⊤(e^k - e^i)  
         = ∑_(i,k) ∈ℰ_𝒞'(x),
       i ∈ℒ(x), 
       k ∈𝒰(x)λ_ik g^⊤(e^k - e^i) 
      = 
      ∑_(i,k) ∈ℰ_𝒞'(x),
       i ∈ℒ(x), 
       k ∈𝒰(x)λ_ik (ϕ_k^+(x_k) - ϕ_i^-(x_i))
       ≥ 0.
  
  It follows that x is optimal since z is an arbitrary feasible solution.
  
  
  
  
  
  
  abbrv
  
  
  
  
  
  