Efficient semidefinite branch-and-cut for MAP-MRF inference

DOI10.1007/s11263-015-0865-2zbMath1398.62259arXiv1404.5009OpenAlexW1808553187MaRDI QIDQ1800052

Peng Wang, Chunhua Shen, Anton van den Hengel, Philip H. S. Torr

Publication date: 19 October 2018

Published in: International Journal of Computer Vision (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1404.5009

zbMATH Keywords

semidefinite programmingbranch and cutMarkov random fieldMAP inference

Mathematics Subject Classification ID

Random fields; image analysis (62M40) Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Uses Software

• SCIP
• L-BFGS-B
• SDPT3
• CPLEX
• SDPLR
• PLASMA
• SCIP-SDP
• OpenGM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving semidefinite-quadratic-linear programs using SDPT3
• Lifting and separation procedures for the cut polytope
• An efficient combined DCA and B\&B using DC/SDP relaxation for globally solving binary quadratic programs
• Alternating direction augmented Lagrangian methods for semidefinite programming
• The spherical constraint in Boolean quadratic programs
• A cutting-plane algorithm with linear and geometric rates of convergence
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• On implementing a primal-dual interior-point method for conic quadratic optimization
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• A semidefinite programming approach to the quadratic knapsack problem
• Branching rules revisited
• Cutting-plane training of structural SVMs
• The partition problem
• LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
• A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
• Introduction to nonlinear and global optimization
• A Newton-CG Augmented Lagrangian Method for Semidefinite Programming
• Anytime AND/OR depth-first search for combinatorial optimization
• MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming
• Graphical Models, Exponential Families, and Variational Inference
• Computer Codes for Problems of Integer Programming
• Clique-Web Facets for Multicut Polytopes
• An Efficient Heuristic Procedure for Partitioning Graphs
• Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
• Algorithm 778: L-BFGS-B
• An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Primal-Dual Interior-Point Methods for Self-Scaled Cones
• A Computational Study of Search Strategies for Mixed Integer Programming
• On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs
• Quadratic knapsack relaxations using cutting planes and semidefinite programming
• On the cut polytope
• A dual approach to solving nonlinear programming problems by unconstrained optimization
• Combining semidefinite and polyhedral relaxations for integer programs
• Regularization Methods for Semidefinite Programming
• Norm-Product Belief Propagation: Primal-Dual Message-Passing for Approximate Inference
• Sparse Approximate Solutions to Semidefinite Programs
• Investigation of some branch and bound strategies for the solution of mixed integer linear programs
• Geometry of cuts and metrics
• Introduction to global optimization.

This page was built for publication: Efficient semidefinite branch-and-cut for MAP-MRF inference