Premium
Prize‐collecting set multicovering with submodular pricing
Author(s) -
Porumbel Daniel
Publication year - 2018
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12420
Subject(s) - submodular set function , set (abstract data type) , mathematics , mathematical optimization , function (biology) , time complexity , column generation , linear programming , scale (ratio) , computer science , algorithm , physics , quantum mechanics , evolutionary biology , biology , programming language
Abstract We consider a ground set E and a submodular functionf ¯ : 2 E → R acting on it. We first propose a “set multicovering” problem in which the value (price) of any S ⊆ E isf ¯ ( S ) . We show 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 paying a penalty. We formulate 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 framework that optimizes all these O ( n ) functions within the same asymptotic running time as solving a single SFM, that is, 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 (a) simultaneously find the best solution of up to O ( n 5 ) functions under strong map relations in O ( n 8 γ + n 9 ) time, (b) perform sensitivity analysis in very short time (even at no extra cost), and (c) reveal combinatorial insight into the primal–dual optimal solutions. We present several potential applications throughout the paper, from production planning to combinatorial auctions.