Optimization Online


Maximizing submodular utility functions combined with a set-union operator over a discrete set

Stefano Coniglio(s.coniglio***at***soton.ac.uk)
Fabio Furini(fabio.furini***at***iasi.cnr.it)
Ivana Ljubić(ivana.ljubic***at***essec.edu)

Abstract: We study a discrete optimization problem calling for the maximization of a sub- modular, concave, and differentiable function f combined with a set-union operator. The latter models a covering relationship between two ground sets, a set of items and a set of metaitems. The goal of the problem is to find an optimal subset of metaitems such that the total utility of the items they cover, as determined by f, is maximized. This problem, which is a generalization of the one introduced by Ahmed and Atamtürk [2011], can be modeled as a mixed integer nonlinear program involving binary decision variables associated with the items and metaitems. In the paper, we propose a double-epigraph decomposition method which allows for projecting out the variables associated with the items by separately exploiting the structural properties of the function f and of the set-union operator. With this technique, the function f is linearized using an outer-approximation technique, whereas the set-union operator is linearized in two ways: (i) via a reformulation based on submodular cuts, and (ii) via a Benders decomposition. We compare the strength of the two resulting mixed integer linear programming reformulations and embed them into two corresponding branch- and-cut algorithms. We compare them experimentally to a standard reformulation based on submodular cuts as well as to a state-of-the-art global-optimization solver. The results reveal that, on our testbed, the method based on combining an outer approximation with Benders cuts significantly outperforms the other ones.

Keywords: Submodular maximization · Branch-and-Cut · Benders decomposition

Category 1: Integer Programming

Category 2: Nonlinear Optimization

Category 3: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 04/02/2020
Entry Accepted: 04/02/2020
Entry Last Modified: 04/02/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society