Exact Algorithms for Combinatorial Optimization Problems with Submodular Objective Functions

Frank Baumann (), Sebastian Berckey () and Christoph Buchheim ()
Additional contact information
Frank Baumann: Technische Universität Dortmund, Fakultät für Mathematik
Sebastian Berckey: INFORM Institut für Operations Research und Management GmbH
Christoph Buchheim: Technische Universität Dortmund, Fakultät für Mathematik

A chapter in Facets of Combinatorial Optimization, 2013, pp 271-294 from Springer

Abstract: 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 time 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 branch and bound-algorithms. 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 Problem; Separation Problem; Transmission Cost; Submodular Function; Subgradient Method (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-38189-8_12

Ordering information: This item can be ordered from
http://www.springer.com/9783642381898

DOI: 10.1007/978-3-642-38189-8_12

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().