Advanced

Generalized roof duality

Kahl, Fredrik LU and Strandmark, Petter LU (2012) In Discrete Applied Mathematics 160(16-17). p.2419-2434
Abstract
The roof dual bound for quadratic unconstrained binary optimization is the basis for several methods for efficiently computing the solution to many hard combinatorial problems. It works by constructing the tightest possible lower-bounding submodular function, and instead of minimizing the original objective function, the relaxation is minimized. However, for higher-order problems the technique has been less successful. A standard technique is to first reduce the problem into a quadratic one by introducing auxiliary variables and then apply the quadratic roof dual bound, but this may lead to loose bounds. We generalize the roof duality technique to higher-order optimization problems. Similarly to the quadratic case, optimal relaxations are... (More)
The roof dual bound for quadratic unconstrained binary optimization is the basis for several methods for efficiently computing the solution to many hard combinatorial problems. It works by constructing the tightest possible lower-bounding submodular function, and instead of minimizing the original objective function, the relaxation is minimized. However, for higher-order problems the technique has been less successful. A standard technique is to first reduce the problem into a quadratic one by introducing auxiliary variables and then apply the quadratic roof dual bound, but this may lead to loose bounds. We generalize the roof duality technique to higher-order optimization problems. Similarly to the quadratic case, optimal relaxations are defined to be the ones that give the maximum lower bound. We show how submodular relaxations can efficiently be constructed in order to compute the generalized roof dual bound for general cubic and quartic pseudo-boolean functions. Further, we prove that important properties such as persistency still hold, which allows us to determine optimal values for some of the variables. From a practical point of view, we experimentally demonstrate that the technique outperforms the state of the art for a wide range of applications, both in terms of lower bounds and in the number of assigned variables. (C) 2012 Elsevier B.V. All rights reserved. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Roof duality, Higher-order, MRF, Computer vision
in
Discrete Applied Mathematics
volume
160
issue
16-17
pages
2419 - 2434
publisher
Elsevier
external identifiers
  • wos:000308849200009
  • scopus:84865103957
ISSN
1872-6771
DOI
10.1016/j.dam.2012.06.009
language
English
LU publication?
yes
id
56b71a24-0da0-4f44-b3e4-8bc07f2e80a1 (old id 3132755)
date added to LUP
2012-11-27 07:47:48
date last changed
2017-03-05 03:17:09
@article{56b71a24-0da0-4f44-b3e4-8bc07f2e80a1,
  abstract     = {The roof dual bound for quadratic unconstrained binary optimization is the basis for several methods for efficiently computing the solution to many hard combinatorial problems. It works by constructing the tightest possible lower-bounding submodular function, and instead of minimizing the original objective function, the relaxation is minimized. However, for higher-order problems the technique has been less successful. A standard technique is to first reduce the problem into a quadratic one by introducing auxiliary variables and then apply the quadratic roof dual bound, but this may lead to loose bounds. We generalize the roof duality technique to higher-order optimization problems. Similarly to the quadratic case, optimal relaxations are defined to be the ones that give the maximum lower bound. We show how submodular relaxations can efficiently be constructed in order to compute the generalized roof dual bound for general cubic and quartic pseudo-boolean functions. Further, we prove that important properties such as persistency still hold, which allows us to determine optimal values for some of the variables. From a practical point of view, we experimentally demonstrate that the technique outperforms the state of the art for a wide range of applications, both in terms of lower bounds and in the number of assigned variables. (C) 2012 Elsevier B.V. All rights reserved.},
  author       = {Kahl, Fredrik and Strandmark, Petter},
  issn         = {1872-6771},
  keyword      = {Roof duality,Higher-order,MRF,Computer vision},
  language     = {eng},
  number       = {16-17},
  pages        = {2419--2434},
  publisher    = {Elsevier},
  series       = {Discrete Applied Mathematics},
  title        = {Generalized roof duality},
  url          = {http://dx.doi.org/10.1016/j.dam.2012.06.009},
  volume       = {160},
  year         = {2012},
}