Prize‐collecting set multicovering with submodular pricing

• DOI: http://doi.org/10.1111/itor.12420
• Author: Daniel Porumbel
• Published date: 01 July 2018
• Date: 01 July 2018

Intl. Trans. in Op. Res. 25 (2018) 1221–1239

DOI: 10.1111/itor.12420

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Prize-collecting set multicovering with submodular pricing

Daniel Porumbel

CEDRIC CS Laboratory, ConservatoireNational des Arts et M ´

etiers, Paris, France

E-mail: daniel.porumbel@cnam.fr [Porumbel]

Received 4 October 2016; receivedin revised form 24 January 2017; accepted 4 April 2017

Abstract

We consider a ground set Eand a submodular function f:2

E→Racting on it. We first propose a “set

multicovering”problem in which the value (price) of any S⊆Eis f(S). Weshow that the linear program (LP)

of this problem can be directly solved by applying a submodular function minimization (SFM) algorithm on

the dual LP. However, the main results of this study concern prize-collecting multicovering with submodular

pricing, that is, a more general and more difficult “multicovering” problem in which elements can be left

uncovered by payinga penalty. Weformulate it as a large-scale LP (with 2|E|variables representing all subsets

of E) that could be tackled by column generation (CG; 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

frameworkthat optimizes all these O(n)functions within the same asymptotic running time as solving a single

SFM, that is, in O(n7γ+n8),wheren=|E|and γis the complexity of one submodular evaluation. Besides

solving the problem, the proposed approach can be useful to (a) simultaneously find the best solution of up

to O(n5)functions under strong map relations in O(n8γ+n9)time, (b) perform sensitivity analysis in very

short time (even at no extra cost), and (c) revealcombinatorial insight into the primal–dual optimal solutions.

We present several potential applications throughout the paper, from production planning to combinatorial

auctions.

Keywords:submodular function; column generation; set multi-covering; large-scale linear programs

1. Introduction

A function f:2

E→Ris submodular if and only if f(S)+f(T)≥f(S∪T)+f(S∩

T), ∀S,T⊆E. A function fis called supermodular if the inequality is reversed, that is, if

f(S)+f(T)≤f(S∪T)+f(S∩T), ∀S,T⊆E. The optimization literature is replete with ap-

plication examples in which one needs to perform submodular function minimization (SFM),

that is, find a subset S⊆Eof minimum submodular value f(S). A vast body of work has been

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

1222 D. Porumbel / Intl. Trans. in Op. Res. 25 (2018) 1221–1239

dedicated to SFM and important progress has been made over the last five decades (see, chrono-

logically, papers such as Edmonds, 1970; Lov´

asz, 1983; Schrijver, 2000; Fleischer and Iwata, 2003;

Iwata, 2003; McCormick, 2005; Nagano, 2007; Sharma et al., 2007; Iwataand Nagano, 2009; Orlin,

2009). This paper is devoted to a classical “set multicovering” problem (cover wecopies of each

e∈Ewith subsets S⊆Eof minimum total price) in which subsets S⊆Eare valued at a price of

f(S)by a submodular function f. The main result concern the prize-collecting formulation of this

problem, that is, a long-acknowledged set-covering variant (Balas, 1989) in which some of the we

copies can be left uncovered by paying a penalty xe.

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 (Barnhart et al., 1998;

Briant et al., 2008). 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⊆Esatisfying a

knapsack constraint) that cover wecopies of each e∈E. Our “set-covering” problem can always be

formulatedin this manner, but the column of subset S⊆Ehas 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 Sis f(S), then this subproblem is an SFM problem, as it

asks to minimize a submodular function minus a linear function, that is, f(S)−e∈Sze,whereze

is the dual value of e.

The disadvantage of a pure CG algorithm is that it might need too many iterations, that is,

generate too many columns by solving an 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

polytope1discovered by Edmonds (1970) 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

Ethat we construct as follows. Given that each element eis demanded wetimes, we construct an

embedding sequence of subsets EkEk−1···E0=Esuch that Ekcontain the most demanded

elements (highest we), Ek−1\Ekcontain the second most demanded elements, Ek−2\Ek−1contain

the next most demanded ones,etc. We will show in Section 3.2 that the most general problemversion,

the prize-collecting multicovering 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(n7γ+n8),thatis,

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, Orlin, 2009, to our knowledge), the FIF is better

suited to SFM over a family of subsets or over a strong map sequence of submodular functions.

In fact, it can simultaneously be found in O(n8γ+n9)time the optimal solution for a strong map

sequence of up to O(n5)pricing scenarios (Section 3.3.2.2), which is faster than applying O(n5)

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

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies