@InProceedings{Werner-CVPR-2008, IS = { zkontrolovano 16 Jan 2009 }, UPDATE = { 2008-08-28 }, author = {Werner, Tom{\'a}{\v s}}, title = {High-arity Interactions, Polyhedral Relaxations, and Cutting Plane Algorithm for Soft Constraint Optimisation ({MAP-MRF})}, year = {2008}, pages = {109--116}, booktitle = {CVPR 2008: Proceedings of the 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition}, publisher = {Omnipress}, address = {Madison, USA}, isbn = {978-1-4244-2243-2}, issn = {1063-6919}, book_pages = {2954}, month = {June}, day = {24-26}, venue = {Anchorage, USA}, organization = {IEEE Computer Society}, annote = {LP relaxation approach to soft constraint optimisation (i.e. MAP-MRF) has been mostly considered only for binary problems. We present its generalisation to n-ary problems, including a simple algorithm to optimise the LP bound, n-ary max-sum diffusion. As applications, we show that a hierarchy of gradually tighter polyhedral relaxations of MAP-MRF is obtained by adding zero interactions. We propose a cutting plane algorithm, where cuts correspond to adding zero interactions and the separation problem to finding an unsatisfiable constraint satisfaction subproblem. Next, we show that certain high-arity interactions, e.g. certain global constraints, can be included into the framework in a principled way. Finally, we prove that n-ary max-sum diffusion finds global optimum for n-ary supermodular problems.}, keywords = {soft constraint satisfaction, Markov random fields, MRF, Gibbs energy minimization, linear programming relaxation, supermodular constraints, global soft constraints}, authorship = {100}, project = {ICT-215078 DIPLECS, MSM6840770038}, prestige = {important}, note = {CD-ROM}, psurl = {[[paper pdf], [errata pdf], [slides pdf]]}, }