Optimization Online


Exact Algorithms for Combinatorial Optimization Problems with Submodular Objective Functions

Frank Baumann (frank.baumann***at***tu-dortmund.de)
Sebastian Berckey (sebastian.berckey***at***inform-software.com)
Christoph Buchheim (christoph.buchheim***at***tu-dortmund.de)

Abstract: Many combinatorial optimization problems have natural formulations as submodular minimization problems over well-studied combinatorial structures. A standard approach to these problems is to linearize the objective function by introducing new variables and constraints, yielding an extended formulation. We propose two new approaches for constrained submodular minimization problems. The first is a linearization approach that requires only a small number of additional variables. We exploit a tight polyhedral description of this new model and an efficient separation algorithm. The second approach uses Lagrangean decomposition to create two subproblems which are solved with polynomial combinatorial algorithms; the first subproblem corresponds to the objective function while the second consists of the constraints. The bounds obtained from both approaches are then used in a branch and bound-algorithm. We apply our general results to problems from wireless network design and mean-risk optimization. Our experimental results show that both approaches compare favorably to the standard techniques.

Keywords: combinatorial optimization; submodular function minimization; lagrangean relaxation

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Technical Report, TU Dortmund

Download: [PDF]

Entry Submitted: 03/30/2012
Entry Accepted: 03/30/2012
Entry Last Modified: 04/02/2012

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