Daniel Porumbel

Prize-Collecting Set Multi-Covering With Submodular Pricing

 for a CG algorithm for Set-Covering problems with submodular pricing. However, we do not solve this large-scale LP by CG, but we solve it in polynomial time by exploiting its integrality properties. More exactly, after appropriate restructuring, the dual LP can be transformed into an LP that has been thoroughly studied (as a primal) in the SFM theory. Solving this LP reduces to optimizing a strong map of O(n) submodular functions. For this, we use the Fleischer-Iwata framework [6] that optimizes all these O(n) functions within the same asymptotic running time as solving a single SFM, i.e., in O(n 7 γ + n 8 ), where n = |E| and γ is the complexity of one submodular evaluation. Besides solving the problem, the proposed approach can be useful to: (1) simultaneously find the best solution of up to O(n 5 ) functions under strong map relations in O(n 8 γ + n 9 ) time, (2) perform sensitivity analysis in very short time (even at no extra cost), (3) reveal combinatorial insight into the primal-dual optimal solutions. We present several potential applications along the paper, from production planning to combinatorial auctions.

Introduction

A function f : 2 E → R is submodular if and only if f (S)+f (T ) ≥ f (S ∪T )+f (S ∩T ), ∀S, T ⊆ E. A function f is called supermodular if the inequality is reversed, i.e., if f (S) + f (T ) ≤ f (S ∪ T ) + f (S ∩ T ), ∀S, T ⊆ E. The optimization literature is replete with application examples in which one needs to perform Submodular Function Minimization (SFM), i.e., find a subset S ⊆ E of minimum submodular value f (S). A vast body of work has been dedicated to SFM and important progress has been done over the last five decades (see, chronologically, papers such as [START_REF] Edmonds | Submodular functions, matroids, and certain polyhedra[END_REF][START_REF] Lovász | Submodular functions and convexity[END_REF][START_REF] Schrijver | A combinatorial algorithm minimizing submodular functions in strongly polynomial time[END_REF][START_REF] Fleischer | A push-relabel framework for submodular function minimization and applications to parametric optimization[END_REF][START_REF] Iwata | A faster scaling algorithm for minimizing submodular functions[END_REF][START_REF] Mccormick | Submodular function minimization[END_REF][START_REF] Nagano | On convex minimization over base polytopes[END_REF][START_REF] Sharma | Approximation algorithms for prize collecting forest problems with submodular penalty functions[END_REF][START_REF] James B Orlin | A faster strongly polynomial time algorithm for submodular function minimization[END_REF][START_REF] Iwata | Submodular function minimization under covering constraints[END_REF]). This paper is devoted to a classical Set Multi-Covering problem (cover w e copies of each e ∈ E with subsets S ⊆ E of minimum total price) in which subsets S ⊆ E are valued at a price of f (S) by a submodular function f . The main result concern the prize-collecting formulation of this problem, i.e., a long-acknowledged set-covering variant [START_REF] Balas | The prize collecting traveling salesman problem[END_REF] in which some of the w e copies can be left uncovered by paying a penalty x e .

A classical approach to such problems uses an Integer Linear Program (ILP) with 2 |E| columns representing all subsets of E. After linear relaxation, this leads to an LP with prohibitively many variables that is typically optimized by Column Generation (CG) methods [START_REF] Barnhart | Branchand-price: Column generation for solving huge integer programs[END_REF][START_REF] Briant | Comparison of bundle and classical column generation[END_REF]. A paradigmatic example of such CG LPs is the Gilmore-Gomory model for Cutting-Stock. It asks to find the minimum number of columns (subsets S ⊆ E satisfying a knapsack constraint) that cover w e copies of each e ∈ E. Our Set-Covering problem can always be formulated in this manner, but the column of subset S ⊆ E has a price (objective function coefficient) of f (S) instead of 1. To optimize such LPs, a CG approach would first start out with a restricted set of columns; then, at each iteration, a negative reduced cost column would be added by solving a CG pricing subproblem. If the price of S is f (S), then this subproblem is a SFM problem, as it asks to minimize a submodular function minus a linear function, i.e., f (S) -e∈S z e , where z e is the dual value of e.

The disadvantage of a pure CG algorithm is that it might need too many iterations, i.e., generate too many columns by solving a SFM problem. To overcome this, we show that the dual of the CG program can be written as an LP that has been thoroughly studied as a primal program in SFM. In fact, if the objective is not formulated in a prize-collecting manner, we obtain the submodular polytope in the dual CG LP. In a prize-collecting formulation, we obtain a well-known polytope1 discovered by Edmonds [START_REF] Edmonds | Submodular functions, matroids, and certain polyhedra[END_REF] and used by most combinatorial SFM algorithms. The program associated to this polytope has integer optimum dual solutions, and so, the CG program has an integer solution and there is no need for branching to solve it.

Section 3 presents all proposed algorithms; they rely on performing SFM over O(n) subsets of E that we construct as follows. Given that each element e is demanded w e times, we construct an embedding sequence of subsets E k E k-1 • • • E 0 = E such that E k contain the most demanded elements (highest w e ), E k-1 \ E k contain the second most demanded elements, E k-2 \E k-1 contain the next most demanded ones, etc. We will show in Section 3.2 that the most general problem version, the Prize-Collecting Multi-Covering With Submodular Pricing, can be solved by performing SFM over the above family of subsets. This can be done by optimizing a strong map sequence of submodular functions, using only one call to the Fleischer-Iwata algorithm of complexity O(n 7 γ + n 8 ), i.e., we use the push-relabel Fleischer-Iwata Framework (FIF).

While this approach is not necessarily faster than (naively) applying O(n) times the fastest-available SFM optimizer (i.e., Orlin's algorithm [START_REF] James B Orlin | A faster strongly polynomial time algorithm for submodular function minimization[END_REF], to our knowledge), the FIF is more well-suited to SFM over a family of subsets or over a strong map sequence of submodular functions. In fact, it can simultaneously find in O(n 8 γ + n 9 ) time the optimal solution for a strong map sequence of up to O(n 5 ) pricing scenarios (Section 3.3.2.2), which is faster than applying O(n 5 ) times a black-box optimizer. Such simultaneity properties can be further used to perform sensitivity analysis, especially if one can anticipate possible data changes and formalize them using strong map functions. Last but not least, by investigating how the arcs of the push-relabel FIF approach generalize on our problem (Section 3.2.1), we reveal more combinatorial insight into the problem structure.

Several applications are presented along the paper, starting with Examples 2.1.A-2.1.B and finishing with Section 4 on related work. For instance, Section 4.1 shows that the related Submodular Cost Set-Covering (SCSC) does not verify one of the main assumptions required in this work, i.e., the price of columns is not submodular. The "submodular cost" part in SCSC does not refer to the valuation over the power set of E, but over the power set of a family of subsets of E.

The remainder of this paper is organized as follows. Section 2 introduces the LP models. Section 3 presents solution methods for these LPs, followed by a sensitivity analysis (Section 3.3) and extensions towards optimization with parametric pricing functions (Section 3.3.2). Section 4 is devoted to related ideas and applications, followed by conclusions in the last section.

Problem Formal Model

A Set Multi-Covering problem is defined on a ground set E = {1, 2, . . . , n}, a vector of demands w = [w 1 w 2 . . . w n ] and a pricing (valuation) function f : 2 E → R. The goal is to find a family of subsets of the form S ⊆ E of minimum total value (cost) that cover exactly w e copies each element e ∈ E. 2 We assume w e ∈ Z + , ∀e ∈ E, but some fractional situations will also be discussed. We only consider here functions f that are submodular over the power set of E and that satisfy f (∅) = 0 (any submodular function can be normalized to this form).

It is often more convenient to use the following submodularity definition. We say f : 2 E → R is submodular if and only if:

f (S ∪ {e}) -f (S ) ≥ f (S ∪ {e}) -f (S), ∀S ⊆ S S ∪ {e} ⊆ E (2.1)

A Basic CG Model and Two Motivating Applications

In light of above (2.1), the notion of submodular pricing captures the idea of diminishing marginal pricing: the value added by a new element e to a larger set S is smaller than the value added by e to a smaller set S ⊆ S. For the sake of clarity, we formulate an introductory, very simple, application of Set-Covering with Submodular Pricing.

Example 2.1.A. Consider a customer that needs to purchase (exactly) w e copies of each product e ∈ E. A seller applies a submodular function f to set prices over product bundles S ⊆ E. What selection of product bundles minimizes the total price for the customer?

When above f is non-decreasing (a reasonable condition unless selling at unfairly low prices as in dumping), f is a matroid rank function. The following application better reveals the more global notion of submodularity (e.g., f is either positive or negative, and usually not monotone).

Example 2.1.B. We consider a set E of facilities such that each facility e ∈ E has a (production) demand to work exactly w e time slots (days). There is a fixed cost c e > 0 per each slot (day) of work at e. We also consider a benefit b e,e > 0 when facilities e and e work at the same time-e.g., a cost reduction due to resource sharing or resource complementarity. Formally, we define the submodular function f (S) = e∈S c ee,e ∈S b e,e . The goal is to find a work schedule for all facilities that minimizes the total cost. We formulate below the primal-dual linear relaxation of Set-Covering with Submodular Pricing. Program (2.2a) has 2 n variables π S (one for each S ⊆ E) and could be optimized by a classical CG routine that would iteratively solve the pricing sub-problem: min S⊆E f (S) -e∈S z e . However, our solution method is presented in Section 3.1, where we will use the fact that the optimal solution of (2.2a) is always integer.

min S⊆E f (S)π S z e : S e π S = w e ∀e ∈ E π S ≥ 0 ∀S ⊆ E (2.2a) max w z π S : e∈S z e ≤ f (S) ∀S ⊆ E z e ∈ R ∀e ∈ E P (f ) (2.2b)

Prize Collecting and Edmond's Submodular Polytope

Prize-collecting is a property of covering problems that has been long acknowledged in the optimization literature [START_REF] Balas | The prize collecting traveling salesman problem[END_REF]. The constraint "cover exactly w e copies of e ∈ E" simply becomes "cover at most w e copies but pay a penalty x e for any uncovered copy". The examples 2.1.A-2.1.B evolve as follows.

Example 2.2.A. Use the same interpretation from Example 2.1.A, but the customer's exact request of purchasing w e copies of e ∈ E evolves: there is still a need for w e copies, but the customer is not willing to pay more than x e for a copy of e (to add e to some bundle). We interpret x e as a threshold price for product e, i.e., the customer has the possibility of purchasing e from an external source at a price of x e .

Example

z e ≤ f (S) ∀S ⊆ E z e ∈ R ∀e ∈ E (2.3b)
We observe that similar (reversed) primal-dual programs arise in the SFM literature. To bring us closer to a SFM model, we will reformulate this model so as to replace the "≤ x e " constraint of (2.3b) with a "≤ 0" constraint, as it is common in SFM. The reformulation will also reveal a natural justification for calling such problems "prize-collecting".

Variable σ e represents the number of copies of e left uncovered. If all elements would be left uncovered, a primal solution would be σ e = w e , ∀e ∈ E and π S = 0, ∀S ⊆ E; the (penalty) price to pay would be e∈E w e x e . By replacing σ e with w e -S e π S in the objective function of (2.3a), the objective min e x e σ e + S⊆E f (S)π S becomes min e x e w ee S e x e π S + S⊆E f (S)π S = e∈E x e w e + min S⊆E (f (S) -e∈S x e )π S , which can be written x w + min S⊆E f (S)π S , where f (S) is submodular function:

f (S) = f (S) - e∈S x e (2.4)
Taking e∈E w e x e as a reference (penalty) price, our objective is interpreted as follows: start from the reference price and minimize it by selecting subsets S ⊆ E; each such selection brings an objective function increase f (S) and a reduction e∈S x e . This later term actually removes the penalty for letting e uncovered, i.e., it is a "prize" for covering e. To keep a limit w e on the number of cost-reduction prizes for e ∈ E, one imposes S e π S ≤ w e ; implicitly, σ e is w e -S e π S and it can never be negative. The primal-dual programs (2.3)-(2.3b) can be restated without primal variables σ: [17, § 3]. However, our solution method cannot be applied on this PCF model, as there is an essential difference: they use a (vertex) ground set V , but the PCF submodular function π acts on sets of subsets of V (i.e., it is defined on 2 2 V instead of 2 V ). Comprehensive comparisons with this form of submodularity are further provided in Section 4.1, as it often arises in Submodular Cost Set Covering.

w x+ min S⊆E f (S)

The Proposed Solution Method

We first discuss solution methods for the simpler Multi-Covering with Submodular Pricing in Section 3.1. However, the main contributions of this section concern the more general Prize-Collecting Multi-Covering in Section 3.2. In Section 3.3, we perform a very fast sensitivity analysis based on the methods from Section 3.2.

Basic Multi-Covering with Submodular Pricing

A primal approach

The primal LP (2.2a) can be solved relatively straightforwardly using a decomposition on the covering demand values. We denote the minimum demand by w 0 = min{w i : i ∈ [1.

.n]}. The fact that we need w e copies of each element e allows us to separate the first w 0 copies of each e ∈ E from the rest w e -w 0 . This way, we can incrementally construct the solution: after covering w 0 copies of each e ∈ E, one can remove these demands and solve a residual problem (and all elements with w e = w 0 vanish). With regards to the these first w 0 copies, it is better to cover them by selecting w 0 times the full set E instead of selecting w 0 layers of some partition of E (because

f (E) ≤ i∈[1..m] f (E i ) for any partition {E 1 , E 2 , . . . , E m } of E).
More formally, the primal problem could be solved by constructing an inclusion sequence of subsets

E k E k-1 . . . E 1 E 0 = E.
We start with E 0 = E and inductively construct E +1 E by removing the lowest-demand elements from E , i.e., E +1 = E -{e ∈ E : w e = w }, where w l = min e∈E w e .

By developing this construction, the optimal primal solution becomes π * S = w -w -1 if S = E for some ∈ [0..k] (consider w -1 = 0) and 0 otherwise. Since this optimal solution π * of (2.2a) is integer, we actually solved both the integer and the fractional Set-Covering with Submodular Pricing. The optimal would still be integer if one allowed the subsets to be selected a fractional number of times.

The advantage of the above method is that it can simply compute the primal CG optimal solution π * in O(n 2 ) time. Indeed, as long as the effective optimal objective value does not need to be calculated, the sets E 0 , E 1 , . . . E k can be determined without any submodular function evaluation. The very low complexity O(n 2 ) of this algorithm makes it more effective (both in practice and in theory) than any CG method that would need to call a SFM algorithm at each iteration.

A dual method

The above pure primal approach has certain limitations: without calculating dual values, it cannot be used for sensitivity analysis (as in Section 3.3.1), it cannot be generalized to other covering versions and it does not reveal in-depth combinatorial properties. We will see that a dual standpoint does merit serious consideration and we hereafter use it to address all remaining questions.

To determine the dual solution in programs (2.2a)-(2.2b), we need to investigate submodular polytopes. Recall that (2.2b) actually maximizes a linear objective w z over the submodular polyhedron P (f ). It is not difficult to check that if w ≥ 0, then the optimum solution belongs to the base polyhedron, i.e., to the face e∈E z e = f (E). This follows from the fact that if the "≤ f (E)" constraint of P (f ) is not tight, one can always increase some z e -this can be verified using (2.1). However, an optimal solution to (2.2b) is generated by the well-known Greedy algorithm using a linear order ≺ such that e 1 ≺ e 2 ≺ • • • ≺ e n , where w e1 ≥ w e2 ≥ • • • ≥ w en . Furthermore, Greedy also determines the optimal solution π * in (2.2a):

π * S = w ei-1 -w ei if S = {e 1 , e 2 , .
. . e i-1 }, π * S = 0 otherwise ∀i = n, . . . , 2, and π * E = w en . It is not difficult to check this is the same solution as the one obtained by the primal approach above.

Prize-Collecting Multi-Covering

The objective of (2.5b) is w x + max w z. By ignoring the reference (penalty) price w x, we obtain the program below. One should keep in mind that this reference penalty will still be later used in the sensitivity analysis when we will investigate the effect of changing the demands w (Section 3.3.1) or the penalties x (Section 3.3.2.3).

max w z π S : e∈S z e ≤ f (S) ∀S ⊆ E z e ≤ 0 ∀e ∈ E (3.1)
Theorem 1. The optimum of (3.1) can be determined only using a restricted (basic) family of submodular constraints e∈S z e ≤ f (S ), where S belongs to an inclusion sequence

S k S k-1 • • • S 0 . Each S is a minimizer of f over all S ⊆ E , where E belongs to an inclusion sequence E k E k-1 . . . E 0 = E such that E +1 = E -{e ∈ E : w e = min e∈E w e }, ∀ ∈ [0..k].
Proof. Let us start with any optimal solution z * of (3.1) and consider its family

T ⊆ 2 E of z * -tight sets, i.e., T = {S ⊆ E : e∈S z * e = f (S)}.
Let us take S 0 = S∈T S; since the union and intersection of z * -tight sets is also z * -tight (see [START_REF] Mccormick | Submodular function minimization[END_REF]Lemma 2.3] for a proof), S 0 is also z * -tight. Using z * e ≤ 0, ∀e ∈ S 0 , it is clear that S 0 is a minimiser of f over T . We will further prove that S 0 is also a minimizer of f over 2 E . We now show that z * e = 0, ∀e ∈ E 0 -S 0 . Assume z * e < 0 for some e ∈ E 0 -S 0 : since such e cannot belong to any z * -tight set, one could feasible increase z * e and thus increase the objective function value-impossible given the optimality of z * . As such, S 0 is a maximal minimizer of f on ground set E 0 = E.

We generate by induction all sets E 0 , E 1 , . . . E k and S 0 , S 1 , . . . S k . Given constructed sets from S 0 , S 1 , . . . S , ≥ 0 and E 0 , E 1 , . . . E , we inductively construct S +1 . In fact, the construction of E +1 from E is already specified in the hypothesis: remove from E all elements e of minimum demand, i.e., elements e ∈ E for which w e = w = min e∈E w e , equivalent to E +1 = {e ∈ E : w e > w }.

Take S +1 as the union of all z * -tight sets containing only elements of E +1 .

S +1 = S∈T ,S⊆E +1 S (*)
Let us prove that z * e = 0, ∀e ∈ E +1 -S +1 . Assume there is e ∈ E +1 -S +1 with z * e < 0 and consider all z * -tight sets that contain e. The intersection S e = e∈S∈T S needs to be z * -tight (see [START_REF] Mccormick | Submodular function minimization[END_REF]Lemma 2.3]). This intersection S e cannot contain only elements of E +1 , because this would put e into S +1 , using (*) above. Take any e ∈ S e -E +1 : one can feasibly decrease z * e and increase z * e by the same sufficiently small > 0 (since e, e ∈ S e , they always appear together in z * -tight sets that contain e). Such change would increase the objective function value by (w e -w e ), which is positive using: (1) w e > w = min e ∈E w e from the construction of E +1 and (2) w ≥ w e from the fact that w < w e would put e into E +1 .

This objective increase contradicts the optimality of z * : the assumption z * e < 0 is false. In a flow pushrelabel interpretation, one would say e → e is a (demand-indexed) arc of strictly positive capacity over which one can perform a push that decreases net flow z * e in e and increases z * e . The above paragraph showed that z * e = 0, ∀e ∈ E +1 -S +1 ; we can also use notation z * (E +1 -S +1 ) = e∈E +1 -S z * e = 0. Since S +1 is the largest z * -tight subset of E +1 , S +1 is a (maximal) minimizer of f over all subsets of E +1 . Additionally, S +1 ⊆ S , because S +1 is constructed in (*) from z * -tight sets S ⊆ E +1 that also belong to E E +1 ; all these z * -tight sets do arise in the S construction using the same (*). The induction step is proved; one stops at k = when E +1 = ∅.

We still have to determine the optimum objective function value OPT= w z * based only on (3.5) for an intuitive graphical representation of these inclusion sequences (Section 3.2.1). We write

E k E k-1 . . . E 0 = E and S k ⊆ S k-1 • • • ⊆ S 0 -see also
w z * = =k =0 e∈E -E +1 w e z * e ,

and let us focus on determining

e∈E -E +1 w e z * e for a fixed ∈ [0..k]. We argued above that z * e = 0, ∀e ∈ E -S . However, it is not clear how exactly z * is defined over S -E +1 , but we will see this is not really necessary. Indeed, we only need to determine e∈S -E +1 w e z e ; since all e ∈ S -E +1 have the same demand value w , this sum can be written

w z * (S -E +1 ). Using z * (E +1 ) = z * (S +1 ) = f (S +1 ), it is clear that z * (S -E +1 ) = z * (S ) -z * (E +1 ) = f (S ) -f (S +1
). The optimum objective function value becomes:

OPT=w z * = =k =0 w l (f (S ) -f (S +1 )) = w 0 f (S 0 ) + k =1 (w -w -1 )f (S ) (3.2)
We mention that an analogous result of this theorem can be found in [16, §44.2], where w z is maximized over z ∈ R E : e∈S z e ≤ f (S) . While this polytope is not the same as the one from (3.1), one can relate the two polytopes using the techniques from [16, 44.1]. Please let us present the consequences of this theorem.

The primal optimal solution π * in (2.5a) follows from above (3.2), i.e., using

S⊆E f (S)π * S = OPT = w 0 f (S 0 ) + k =1 (w -w -1 )f (S ), the optimal primal solution is : π * S0 = w 0 , π * S = w -w -1 , ∀ ∈ [1..k] and π * S = 0, ∀S ∈ 2 E -{S 0 , S 1 , . . . S k }. A Strong Map Sequence of functions can be constructed from the inclusion sequence E k E k-1 • • • E 0 .
We define the following family of E -kernel functions (∀ ∈ [0..k]):

f (S) = f (S ∩ E ) + e∈S-E (|f (e)| + 1), (3.3)
As a sum between a submodular function and a unimodular one, f is submodular. One can check that if f (S ) = min S⊆E f (S), then f (S ) = f (S l ) = min S⊆E f (S). The strict positivity of |f (e)| + 1 only ensure that all minimisers of f belong to E . Furthermore, we show that the following is a strong map sequence of submodular functions : The Push-Relabel Fleischer-Iwata framework [START_REF] Fleischer | A push-relabel framework for submodular function minimization and applications to parametric optimization[END_REF] is tailored especially for strong map sequences of submodular functions. In fact, we showed that the proposed problem can be solved by minimizing the strong map sequence (3.4). The Fleischer-Iwata framework performs this task in O((n 7 + kn 2 )γ + n 8 ) asymptotic running time. Since constructing all E and f requires less than O(n 8 ) and k is asymptotically smaller than O(n 5 ), the total asymptotic running time is O(n 7 γ + n 8 ).

f k → f k-1 → . . . f 1 → f 0 = f (3.4)

Combinatorial Structure of Optimal z *

A graphical representation of the inclusion sequences can further clarify the situation. Without restricting generality, we consider that

E = {1, 2, . . . n} is indexed such that w n ≥ w n-1 • • • ≥ w 1 . This series actually contains k +1 distinct demand values w k > w k-1 • • • ≥ w 0 .
The last element with demand w is here denoted e l , ∀ ∈ [0..k]. All elements from e -1 to e -1 have demand w -1 and they form set

E -1 -E , see (3.5) below. S0 S k-1 S k n, n -1 . . . . . . e k , E k e k -1, . . . . . . e k-1 , E k-1 e k-1 -1, . . . . . . . . . e 1 -1, . . . . . . , e 0 . . . E1 E0=E (3.5)
The value of optimal z * over the whole E can be constructed by a Greedy approach on a restricted set of variables. The proof of Theorem 1 only shows that z * e = 0, ∀e ∈ E -S , ∀ ∈ [0..k] and let us fix these values. To determine z * e on all other e ∈ l∈[1.

.k] S -E +1 , we can apply a Greedy approach based on a linear order e 1 ≺ e 2 ≺ e 3 . . . e n that is consistent with:

S k ≺ S k-1 -E k ≺ • • • ≺ S 1 -E 2 ≺ S 0 -E 1
A solution z ≺ generated by Pure Greedy can have strictly positive values z ≺ ei , as calculated by the Pure Greedy formula z ≺ ei = f ({e 1 , e 2 , . . . , e i }) -f ({e 1 , e 2 , . . . , e i-1 }). To overcome this, we can simply change the Greedy formula to z * ei ← z -(z ≺ ei ) = min(z ≺ ei , 0). However, this can only be used to determine one optimal solution. All optimal solutions can be generated using the classical base polyhedron SFM approach: remove negativity constraints in (3.1), impose e∈E z e = f (E) and replace the objective with e∈E w e z -(z e ), so as to construct an equivalent base polyhedron model. 3 Any solution of (3.1) can be seen as a projection (via z -) of a solution in the base polyhedron, using [START_REF] Mccormick | Submodular function minimization[END_REF]Lemma 2.4]. As such, any optimal solution can be generated by projecting a linear combination of solutions constructed by Pure Greedy on the base polyhedron.

A Flow Network enriched with Demand-Indexed Arcs can be associated to the base polyhedron formulation, generalizing classical SFM approaches. For instance, push-relabel algorithms [START_REF] Schrijver | A combinatorial algorithm minimizing submodular functions in strongly polynomial time[END_REF][START_REF] Fleischer | A push-relabel framework for submodular function minimization and applications to parametric optimization[END_REF] define arcs e → e for any e, e ∈ E with z e < 0 and z e > 0 (we use the arc directions from [START_REF] Mccormick | Submodular function minimization[END_REF], i.e., e → e could stand for a path from k 1 to k 4 in [12, Fig. 1]) and they are still valid. Indeed, the Greedy solution of an order ≺ such that e ≺ e would not get worse by reversing e and e : this amounts to a non-strict increase of z e < 0 and a non-strict decrease of z e > 0 (e.g., by a sufficiently small value), which can only increase z -(z e ) + z -(z e ). This way, one tries to find orders ≺ * satisfying e ≺ * e for e and e as above, so as to move strictly positive components to the right. Our model generalizes this by introducing demand-indexed arcs e → e even for z e , z e < 0: such an arc can be constructed when w e > w e , e.g., when e ∈ S l+1 -E l+2 and e ∈ S l -E l+1 (in this case, w e ≥ w l+1 > w ≥ w e ). As above, a Greedy solution of an order ≺ such that e ≺ e would not get worse by reversing e and e : this can only increase z e and decrease z e at least by the same sufficiently small value , yielding an increase of the objective by (w e -w e ), as in one argument in the proof of Theorem 1.

Fast Sensitivity Analysis using Optimal z * and the Push-Relabel Framework

Since the input parameters (e.g., demand w e , penalty x e (∀e ∈ E), price function f , etc) might represent managerial decisions, the choice of the best parameter values might be the main issue to be studied. For such purposes, we propose two sensitivity analysis methods: (i) Section 3.3.1 below, in which we make use of some primal-dual combinatorial properties studied in Section 3.2.1, and (ii) Section 3.3.2 that exploits the Fleischer-Iwata Framework (FIF) [START_REF] Fleischer | A push-relabel framework for submodular function minimization and applications to parametric optimization[END_REF][START_REF] Schrijver | A combinatorial algorithm minimizing submodular functions in strongly polynomial time[END_REF].

While the FIF is not necessarily the fastest solution method for our problem (applying Orlin Algorithm [START_REF] James B Orlin | A faster strongly polynomial time algorithm for submodular function minimization[END_REF] O(n) times requires less asymptotic running time), it is very fast and well-suited for sensitivity analysis, because it can simultaneously minimize up to O(n 5 ) functions in strong map relations. If some parameter changes can be anticipated and formalized using strong map relations (Section 3.3.2), the FIF can determine in advance updated optimal solutions for any of up to O(n 5 ) possible parameter changes-in some cases (Section 3.3.2.1), this comes at no extra computational complexity cost.

Sensitivity Analysis Using the π * -z * Duality

We here focus on the effects of demand changes (modifications of w). Some natural questions might be: how can one rapidly update the optimal solution if product i is no longer needed by the customer (in Example 2.1.A) ? What happens if certain locations in Example 2.1.B are required to perform some extra work? Instead of re-optimizing after any such demand change, the optimum value can be more rapidly updated by exploiting the value of an optimum (CG dual) z * .

In classical LP sensitivity analysis [7, Ch. 6], one interprets z * e as a shadow price describing the instantaneous change, per unit of constraint S e π S ≤ w e , in the optimum objective value obtained by relaxing this constraint in (2.5a). Given the high degeneracy of (2.5a), we will actually define and use z * min (e) and z * max (e), the minimum and respectively maximum value of z * e over all optimal z * , that can be found using the method from Section 3.2.1. If e ∈ E -S for some l ∈ [1..k], then z * max (e) = z * min (e) = 0. Otherwise, e ∈ S -E +1 for some ∈ [0..k] (using E k+1 = ∅). Using (2.1) on (3.5), the minimum (respectively maximum) z * e is realized if order ≺ puts e last (respectively, first) in S -E +1 . One can check in (3.5) that: (i) the first case puts e at the last position of S and, (ii) the second case puts e right after all elements of E +1 . Case (i) leads to z * min (e) = f (S ) -f (S -{e}) and case (ii

) to z * max (e) = f (E +1 ∪ {e}) -f (E +1
). The demand changes do not modify the feasibility of an optimal z * in (3.1) or (2.5b). If one performs substitution w e ← w e + α (with α > 0), the reference penalty w x is increased by αx e (α penalties more) and w z * is increased by αz * e . As such, substitution w e ← w e + α leads to an objective increase of at least α(x e + z * max (e)). This simply results from calculating the objective function change induced on a solution z * such that z * e = z * max (e). Conversely, a demand decrease w e ← w e -α leads to a total objective increase of α(-x e -z * min (e)) or even more according to the structural changes triggered on the sets E 1 , E 2 , . . . E k . However, if any of the above minimum objectives increases is greater than 0, the demand changes surely increases the total objective value. Perhaps rather surprisingly at a first glance, by increasing the demand, the total price can sometimes decrease: if f (|S|) = 0, ∀S E and f (E) = -M , the substitution w e → max e ∈E w e , ∀e ∈ E reduces the cost to very small values-considering M very large.

Sensitivity Analysis using the Fleischer-Iwata Framework

If certain parameter changes could be formulated by extending the strong map sequence (3.4), it is possible to anticipate them at very limited complexity costs. The Fleischer-Iwata Framework can determine in advance certain updated optimal solutions. The total complexity is either multiplied by one n factor (i.e., O(n 8 γ + n 9 )) or even unchanged in some cases ( § 3.3.2.1), and this, even for extended sequences of length up to O(n 5 ).

Solving the problem simultaneously for several demand vectors Take linear order

n ≺ n -1 ≺ n -2 ≺ • • • ≺ 1 that is consistent with the inclusion sequence E k E k-1 .
. . E 0 = E. Consider now that demand vector w is changed to w ; the new vector generates its own inclusion sequence

E k E k-1 . . . E 0 = E that satisfies the following property: ∀ ∈ [0..k], ∈ [0..k ], either E ⊆ E or E ⊇ E .
This ensures the existence of a mixed inclusion sequence, for instance:

E k E k -1 • • • E k -j1+1 ⊆ E k ⊆ E k -j1 • • • E k -j2+1 ⊆ E k-1 ⊆ . . . E k -j k • • • E 0 ⊆ E 0 = E One can easily generalize the strong map sequence f k → f k-1 → . . . f 0 from (3.4): use (3.
3) to define new E -kernel functions for all new E subsets above. These new kernel functions form a strong map sequence that include (3.4). As such, the Fleischer-Iwata framework requires the same asymptotic running time O(n 7 γ + n 8 ) to provide the minimizer of f over all subsets of E and E (with l ∈ [0..k ] and ∈ [0..k]), and so, solve the problem simultaneously for both w and w .

Let us finish with a simple example. An increment-only demand change w → w (i.e., w e -w e ∈ {0, 1}, ∀e ∈ E) does generate a valid mixed inclusion sequence. For a fixed ∈ [1..k], one needs to use a linear order ≺ that places all e ∈ E with w e = w e + 1 before all other e ∈ E . The incremented elements lead to new subsets E embedded between E +1 and E (E +1 ⊆ E ⊆ E ). This idea can be generalized: instead of simple increments, consider any larger variations only within [0, w l+1 -w ], or only within [-(w -w l-1 ), 0].

Pricing functions in strong map relations Possible changes in the pricing function can be anticipated and formulated as strong map sequences of the form

f m → f m-1 → . . . f 0 = f = f -1 → f -2 → . . . f -p . A E -kernel function f i
can be directly defined by applying (3.3) from Section 3.1 on f i , ∀i ∈ {m, m -1, . . . , -p + 1, -p}. These E -kernel functions also form a strong map sequence

f m → f m-1 → . . . f 0 = f = f -1 → f -2 → . . . f -p . For each ∈ [0..k] ,
k =0 O(|E | 7 γ +|E | 8 ): if |E | ≤ n (l+1) 1/6 , this complexity sum is dominated by O(n 7 γ) ∞ =0 1 (l+1) 7/6 + O(n 8 ) ∞ =0 1 (l+1) 8/6 = O(n 7 γ + n 8
). We used the fact that the hyperharmonic series

∞ =1 1 n s converges to the Riemann zeta function ζ(s) if s > 1.
The example below shows that the proposed O(n 8 γ +n 9 ) solution method is not only useful for sensitivity analyses, but also for parametric optimization associated to a strong map sequence of functions. We now consider a scenario in which the benefit sets B cannot be easily identified (due to absence of information, or, why not, poor understanding). However, suppose one can indicate (anticipate) a linear order B 1 ≺ B 2 ≺ . . . B n : if i ≺ j, then it is easier to obtain benefits from simultaneous work in B i than in

B j . Denoting ≺ (B i ) = {B 1 , B 2 , . . . B i }, ∀i ∈ [1.
.n ], the following functions form a strong map sequence:

f ≺(B1) → f ≺(B2) → f ≺(B3) → f ≺(B n ) .
As long as n ∈ O(n 5 ), the Fleischer-Iwata framework can simultaneously find the optimal solution for all above functions within O(k(n 7 γ + n 8 )) = O(n 8 γ + n 9 ) asymptotic running time. To the best of our knowledge, this is not possible with other FSM algorithms. A more naive approach would require applying the fastest available SFM optimizer up to nn times.

3.3.2.3

Changing the Non-Covering Penalties x First, recall that x e can be interpreted as a threshold pricepoint for e, e.g., in Example 2.2.A, the customer is not willing to pay more than x e to add article e to an existing bundle. Reasonable questions might be: what happens if the threshold pricepoint x e increases or decreases for some e ∈ E? Can one anticipate such variations and construct in advance alternatives solutions with no computational overhead? What is the return on the investment necessary for buying an asset that could generate any e ∈ E at some price x 1 e ≤ x e ? A substitution x e ← x 1 e , ∀e ∈ E would first modify the reference penalty w x. The submodular pricing function f (S) = f (S) -e∈S x e (see (2.4)) is replaced with f 1 (S) = f (S) + e∈S x e -x 1 e . Function f 1 only differs from f by some unimodular increases x e -x 1 e ≥ 0 on e ∈ S; this can be used to prove the strong map relation f 1 → f . One can further consider more penalty reductions by formulating a gradual sequence x > x 1 > x 2 > . . . x m . For instance, the first elements from this series might represent penalty reductions on a few e ∈ E, followed by reductions on increasingly larger subsets of E towards the end of the series.

Such sequences of price reductions generate strong map relations f m → f m-1 → . . . f 1 → f , generalizing f 1 → f . Using the approach described just above ( § 3.3.2.2), the minimizers of all such functions can be generated in O(n 8 γ + n 9 ) time, as long as m ∈ O(n 5 ).

Related Problems and Ideas

Submodular Cost Set Covering

Given ground set (universe) E and a family N ⊆ 2 E of subsets of E, Submodular Cost Set Cover [START_REF] Iwata | Submodular function minimization under covering constraints[END_REF] is a problem defined using a function f N : 2 N → R that is submodular over the power set of N ; the goal is to find S N ⊆ N such that f N (S N ) is minimized and S∈S N S = E. We obtain Submodular Edge Cover by simply considering (E, N ) as a graph: N contains only subsets of E with two elements. It is useful to interpret Submodular Cost Set Cover on a bipartite graph: consider vertices N ∪ E and add arcs from N to E such that S → e is an arc ⇔ S e (with S ∈ N and e ∈ E). The objective is to select some S N ⊆ N that is incident to all e ∈ E and that minimizes f N (S N ). Certain papers also introduce a polymatroid rank function f cover : 2 N → Z + such that f cover (S N ) is the number of vertices e ∈ E incident to S N , see [START_REF] Lovász | Submodular functions and convexity[END_REF]Ex. 1.4]; the covering condition can be expressed f cover (S N ) = f cover (N ).

The submodularity of f N : 2 N → R does not imply submodularity over the power set of E. Let us prove this with a simple example: E = {1, 2, 3} and N = {A, B, C, D}, where A = {1}, B = {2}, C = {2, 3}, D = {3}; define f N (S N ) = S∈S N g S , ∀S N ⊆ N , where g A = g B = g D = 1 and g C = 3. If one would try to extend this definition to a CG setting with submodular pricing over the power set of E, the four columns below could be obtained.

f N ({A})=1 f N ({A, B})=2 f N ({A, D}) = 2 f N ({A, C}) = 4 1 1 1 1 2 2 3 3
The above column pricing is not submodular over the power set of {1, 2, 3}: there is no diminishing marginal pricing as in (2.1). The marginal value of {2} is increasing from 1 = f N ({A, B}) -f N ({A}) (i.e., add {2} to {1}, see second column compared to the first) to 2 = f N ({A, C}) -f N ({A, D}) (add {2} to {1, 3}, see last column compared to the third).

Submodular Cost Set Cover is also more complex in the sense that the number of variables of the associated LP can be much larger. If |N | ∈ O(2 n ), the (natural) use of one variable per subset of N leads to a doubly-exponential number of variables O(2 2 n )-consider, for instance [9, § 4.4] with a large N . This phenomenon is also discussed in the first paragraph of [17, § 6]; their starting program (called (PCF-IP), p. 2, § 1) is similar to (2.3a), but their submodular function π has domain 2 2 V , where V is a ground set.

However, Set-Covering with Submodular Pricing can be seen as a particular case of Submodular Cost Set Cover as follows: (i) set N = {{e 1 }, {e 2 }, . . . {e n }} and (ii) choose an appropriate definition for f N , i.e., f N (S N ) = f ( S∈S N S), ∀S N ⊆ N . Due to these particularizations, our primal CG LPs (e.g., (2.2a) or (2.5a)) have SFM polytopes as dual LPs (e.g., (2.2b) or (2.5b)); this allowed us to use Greedy to show that these LPs have integer primal optimal solutions (when the demands w are integer). On the other hand, "Submodular Cost" covering problems have similar LPs with fractional optimal solutions; they are often tackled by rounding methods, leading to approximation results [START_REF] Iwata | Submodular function minimization under covering constraints[END_REF].

Convex Minimization on the Base Polyhedron

A classical approach in SFM consists of restating (3.1) as an optimization problem over the base polyhedron. Using the arguments from [12, § 2.4], one can propose the following equivalent formulation:

max e∈E w e z -(z e ) e∈S z e ≤ f (S) ∀S E e∈E z e = f (E) , (4.1)
where z -(z e ) = min(z e , 0). The linear constraints define the base polyhedron, i.e., it is the submodular polyhedron facet that verifies with equality the constraint associated to E. We can say that the objective is to minimize e∈E -g e (z e ) over the base polyhedron, where g e (z e ) = w e z e if z e ≤ 0 and g e (z e ) = 0 if z e > 0 (for all e ∈ E). Since -g e is convex, this is a convex minimization problem over a base polyhedron. Such problems have been already studied in the literature [START_REF] Nagano | On convex minimization over base polytopes[END_REF]. However, to the best of our knowledge, the convex optimization approaches do not yet solve programs like (4.1) for the following reasons: (i) differentiable functions are usually used (above -g e is not differentiable in 0) and (ii) strict convexity is usually required [START_REF] Nagano | On convex minimization over base polytopes[END_REF]. Regarding (ii), -g e is not strictly convex because it does not verify -g(z + z ) > -g(z ) + -g(z ), ∀z , z ∈ R (linear functions do not satisfy strict convexity).

Applications Well-Suited for the Proposed Approach

Combinatorial Auctions and Supermodular Function Maximization

Column Generation (CG) is a common technique for solving Combinatorial Auction Problem (CAP) models with prohibitively many columns [4, § 3.5]. In this context, program (2.5a) is interpreted as in Example 2.2.A, but with an objective representing the seller (auctioneer): E is a set of articles offered in an auction, a subset S ⊆ E is a bundle that can be sold to bidders. The auctioneer has w e copies of each article e ∈ E; e can either be sold in a bundle S e or be kept to be sold later at a threshold price x e . The optimum of (2.5a) is actually the minimum profit that the auctioneer can obtain by selling all articles.

The relevant goal of an auctioneer is profit maximization. For this purpose, we transform the model: negate the objective function coefficients and the minimization objective becomes a maximization one, but bundle prices become -f (S) (∀S ⊆ E); the threshold prices become -x e , ∀e ∈ E. If -f is supermodular, f is submodular; by minimizing w x + min S⊆E f (S)π S in (2.5a), one actually maximizes -w x + min S⊆E -f (S)π S . As such, one actually solves the Combinatorial Auction Problem (CAP) with supermodular bundle pricing: given supermodular bid function -f : 2 E → R, select the bids that maximize the total sales profit.

While submodularity is a more popular pricing method in well-known package deals (with diminishing marginal prices), supermodular bundle pricing is also commonly used in game theory or economics to model bundle synergy [START_REF] Vainsencher | Bundle selling by online estimation of valuation functions[END_REF]. For instance, in finance, a diversified portfolio (bundle) is more valuable (less risky) than the total value of its constituent assets. In art, a large (complete) collection is worth more than the sum of its constituent articles. Generally speaking, bundle synergy captures the idea that the whole is worth more than the sum of its parts, see interesting examples in [START_REF] Vainsencher | Bundle selling by online estimation of valuation functions[END_REF]. As such, CAP bid functions are often super-additive [START_REF] De Vries | Combinatorial auctions: A survey[END_REF]: a bid on S ∪ S needs to be more profitable for the auctioneer than the sum of the bids on S and S -otherwise, the auctioneer ignores bid on S ∪ S , considering it less profitable than the separate bids on S and S . Supermodularity is a stronger condition that super-additivity, but still reasonable in auctions: given article e ∈ E, it is natural for a collector to bid more on some new article e to extend a rich collection S than to extend a incomplete collection S S. This translates into increasing marginal prices: the bid function -f satisfies -f (S ∪ {e}) -(-f (S)) ≥ -f (S ∪ {e}) -(-f (S )), ∀S ⊆ S S ∪ {e} ⊆ E, a sufficient supermodularity condition, using (2.1).

Let us investigate a classical formulation (CAP1 in [4, § 3.1]) in which there is a set N of bidders with bid functions -f j (∀j ∈ N ). After notational translations and some simplifications, this CAP1 model can be written as a generalization of (2.5a), using variable π j S to indicate that bundle S is sold to bidder j ∈ N .

min j∈N S⊆E f j (S)π j S = max j∈N S⊆E -f j (S)π j S j∈N S e π j S ≤ w e ∀e ∈ E π j S ∈ Z + ∀S ⊆ E, j ∈ N (4.2)
For such models, CG is even more well-suited to iterative auctions [4, § 4.3]. In iterative auctions, the dual values z e are used by the bidders to update their functions and propose better columns. However, the above LP is already more complicated than (2.5a), because its dual LP (generalizing (2.5b)) actually requires optimizing over the intersection of |N | sub-modular polytopes. The dual of CAP1 leads in [4, § 3.4.5], under super-additivity and non-decreasing conditions, to an instance of the polymatroid intersection problem, which is polynomially solvable. In light of these observations it would be interesting to find whether our approach could be modified to optimize models like (4.2), but this is a subject for later research.

From SFM to Set-Covering Models: A Multi-Level Location-Supply Example

In general, most submodular function f : 2 E → R can generate a Prize Collecting Multi-Covering with Submodular Pricing application. For this, we can usually apply a multi-level extension that constructs program (2.3a) by assigning to each e ∈ E a number of levels (separate covering requests) w e : each selection of S e covers a separate level of e. In fact, it is this technique that generated Examples 2.1.A and 2.1.B: the levels w e represent copies of products in the former case and working days in the latter; in this section, w e will represent a number of available quality levels. We will also exemplify a minimization reformulation technique to ensure that f is an appropriate function for minimization, i.e., even if function f below does not initially have a coherent cost minimization interpretation, a bi-level modelling can make it well-suited to the objective of (2.3a). These two techniques are presented on a generalization of a Simple Plant Location Problem [10, eq. ( 6)]; in fact, we present it using an equivalent warehouse terminology, inspired by the submodular function (noted f ) from [12, ex. 1.4]. CG models with more complex submodular pricing functions already exist in the location-inventory literature [START_REF] Shen | A joint location -inventory model[END_REF]Appendix B].

We consider a community composed of a set of retail stores R and a set E of potential locations for warehouses. An external warehouse operator is hired to distribute supplies from warehouses to retails stores. We propose a bi-level modelling, with two types of decisions:

-open a warehouse at e ∈ E: this yields a benefit φ e for the community (more economic activity in e, less unemployment) and a cost of αφ e for the external operator. This level of decisions are taken by the community;

-serve retail store r from e: this represents a price b re to be payed by the community and a benefit βb re to be realized by the operator (β > 0), i.e., a part of this benefit βb re is realized by making retail store r pay a proportional price b re . We consider that the decision of serving retail store r from e rests only with the external operator. As such, the operator naturally maximizes its benefit for serving r ∈ R, i.e., the benefit for serving r is β max e∈S b re , where S ⊆ E is the set of open warehouses (decision take above).

If the community decides to open warehouses S ⊆ E, the operator has a benefit of f α,β (S) = -α e∈S φ e + β r∈R max e∈S b re and the community has to pay a total price of f (S) = -e∈S φ e + r∈R max e∈S b re . It is possible to have a benefit both for the community (f (S) < 0) and for the operator (f α,β (S) > 0). However, a natural objective for the community is to chose to open warehouses S for which f (S) is minimized; f is actually the submodular function [START_REF] Mccormick | Submodular function minimization[END_REF]Ex. 4], but the objective is now cost minimization instead of benefit maximization. Without a bi-level modelling, it is not coherent to minimize f while using cost terms like max e∈S b re .

To get closer to program (2.3a), the multi-level extension associates to each e ∈ E a maximum level w e . This could be seen as a maximum quality level of the produced articles (e.g., in equivalent Plant Location Interpretation) or of the available storage capacities: w e = 1 when only storage of non-perishable items is available in e, w e = 2 for storage of (long-lasting) food, w e = 3 for refrigerated storage, w e = 4 for frozen storage, etc. We consider that if e ∈ E is able to work at level w e , e can also work at lower levels, e.g., a frozen warehouse can also be used as a refrigerated warehouse. For any e ∈ E with w e available levels, a solution that only uses only w i -σ e levels is penalized by x e σ e , i.e., unused capacities or levels. For the community, the objective is to minimize the cost; the full program can be written exactly as (2.3a).

Conclusions

We presented a solution method based on SFM for Prize-Collecting Multi-Covering with Submodular Pricing. The practical relevance of this class of problems is underlined by revealing applications in rather unexpected domains, ranging from production planning and warehouse location to combinatorial auctions (see Examples 2.2.A-2.2.B or Section 4.3). The problem can be formulated using an LP with 2 n variables (columns); this LP can be optimized using a Column Generation (CG) model with a submodular pricing sub-problem. This type of CG algorithms was already applied for a location-inventory problem [START_REF] Shen | A joint location -inventory model[END_REF] and we hope that our alternative algorithm sheds useful light into the topic.

Our solution method resides in the fact that, after an appropriate reformulation (Section 2.2), the above CG LP has a dual LP that is thoroughly studied as a primal program in SFM [12, § 2.4]. This, in turn, shows that the optimal solution of the CG (fractional) LP is always integer; it can be constructed within O(n 7 γ + n 8 ) asymptotic running time, using the Fleischer-Iwata push-relabel algorithm for strong map sequences of submodular functions (Section 3). A more naive approach would be applying O(n) times the fastest-available SFM optimizer as a black-box tool. However, by getting more combinatorial insight into push-relabel models (e.g., see Section 3.2.1), the proposed approach provides other advantages. For instance, it reveals two faster sensitivity analysis techniques: (i) exploit the combinatorial structure of the optimal primal-dual solutions in submodular polytopes (Section 3.3.1) or (ii) formulate input parameter changes as strong map sequences of functions (Section 3.3.2). Furthermore, we showed that our solution method can actually determine the optimal solution for any of the O(n 5 ) possible pricing scenarios discussed in Section 3.3.2.2 using O(n 8 γ + n 9 ) time, (significantly) more rapidly than naively calling O(n 6 ) times a faster SFM black-box optimizer.

First, recall that

  two functions f and f are in a strong-map relation f → f if and only if f (S ∪ T ) -f (S) ≥ f (S ∪T )-f (S), ∀S, T ⊆ E. The proof goes on by induction on T , considering any fixed S ⊆ E. Starting with T = ∅, the strong map inequality f (S ∪ T ) -f (S) ≥ f -1 (S ∪ T ) -f -1 (S) is clearly verified. We show it is still verified after substituting T ← T ∪ {e}, ∀e ∈ E -(S ∪ T ). Since e can belong to any of E l E l-1 ⊆ E, there are three cases depending on its position: (i) if e ∈ E -E -1 , both sides increase by |f (e)| + 1; (ii) if e ∈ E -1 -E , the left side increases by |f (e)| + 1 and the right side by f ((E -1 ∩ (S ∪ T )) ∪ {e}) -f (E l-1 ∩ (S ∪ T )), and (iii) if e ∈ E l , the left side increases by f ((E ∩ (S ∪ T )) ∪ {e}) -f (E l ∩ (S ∪ T )) and right side by f ((E -1 ∩ (S ∪ T )) ∪ {e}) -f (E l-1 ∩ (S ∪ T )). Both cases (ii) and (iii) produces left increases larger than or equal to the right one, by virtue of (2.1).

  this sequence can be optimized by the parametric Fleischer-Iwata framework of complexity O(n 7 γ + n 8 ). This complexity bound holds as long p + m ∈ O(n 5 ), because each of the m+p+1 functions f i induces an additional computational overhead of O((m+p)n 2 γ) [6, § 3]. By considering all k + 1 possible values of , the total complexity is O(k(n 7 γ + n 9 )) = O(n 8 γ + n 9 ). In fact, the complexity at each value of can be refined to O(|E | 7 γ + |E | 8 ), because only |E | elements matter at level . This way, the total complexity is

Example 3 .

 3 3.2.B Continuing with Examples 2.1.B and 2.2.B, we consider a family of subsets B = {B 1 , B 2 , . . . B n } ⊆ 2 E ; we note b i the benefit resulting from simultaneous work in B i . A submodular pricing function can be defined with a similar formula as in Example 2.1.B: f B (S) = e∈S c e -Bi∈B Bi⊆S b i .

  2.2.B. Continuing with Example 2.1.B, we consider that there is still a workload of w e days on each e ∈ E. However, it is possible to work fewer days in e by paying a penalty of x e for each non-working day. One can consider that x e bears the cost of executing the workload of one day by external means.

	The penalties x are usually positive, but negative values can also be coherent-e.g., if the costs c e are
	much smaller than the benefits b e,e in Example 2.1.B. A first primal-dual relaxation of Prize-Collecting
	Multi-Covering with Submodular Pricing is a generalization of (2.2a)-(2.2b):
	min e x e σ e + S⊆E f (S)π S		max w z
	z e : σ e + S e π S = w e ∀e ∈ E σ e ≥ 0 ∀e ∈ E	(2.3a)	σ e : z e ≤ x e π S : e∈S
	π S ≥ 0	∀S ⊆ E

The polytope {ze : ze ≤ f (S)∀S, ze ≤ 0∀e ∈ E} for submodular function f .

The constraint of exactly covering the given set can be seen as a partitioning constraint. However, the "covering logic" will be more obvious in the prize-collecting versions studied from Section 2.2 on.

The base polyhedron approach is a classical technique in SFM, see Section

4.2 for references and (4.1) for the exact mathematical model.