| Title: | Generalized Roof Duality |
| Fulltext: |  |
| Authors: | Kahl, Fredrik and Strandmark, Petter |
| Year: | 2012 |
| Publication: | Discrete Applied Mathematics |
| Volume: | 160 |
| Issue: | 16-17 |
| Pages: | 2419--2434 |
| Document Type: | Journal Paper |
| Status: | Published |
| Refereed: | Yes |
| Keywords: | optimization, globalvision, ffl, vinst |
| Publisher: | Elsevier |
| BibTeX item: |  |
| 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. Source code available for download. |
Similar Publications
- Journal paper:
An Efficient Optimization Framework for Multi-Region Segmentation based on Lagrangian Duality
Johannes Ulén
Petter Strandmark
Fredrik Kahl - Conference paper:
Tighter Relaxations for Higher-Order Models based on Generalized Roof Duality
Johan Fredriksson
Carl Olsson
Petter Strandmark
Fredrik Kahl - Conference paper:
Generalized Roof Duality for Pseudo-Boolean Optimization
Fredrik Kahl
Petter Strandmark
Questions: webmaster
Last updated: 2012-01-17
Centre for Mathematical Sciences, Box 118, SE-22100, Lund. Phone: 046-222 00 00