Solving Lift-and-Project Relaxations of Binary Integer Programs

DOI10.1137/040609574zbMath1113.90100OpenAlexW2007218093MaRDI QIDQ5470217

Dieter Vandenbussche, Samuel Burer

Publication date: 30 May 2006

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/b05779dd54417a5738a807064c5a16a5b847dd1a

zbMATH Keywords

integer programmingsemidefinite programmingaugmented Lagrangianlift-and-project relaxations

Mathematics Subject Classification ID

Semidefinite programming (90C22) Integer programming (90C10) Nonlinear programming (90C30) Combinatorial optimization (90C27)

Related Items (45)

Taking advantage of symmetry in some quadratic assignment problems ⋮ Copositive and semidefinite relaxations of the quadratic assignment problem ⋮ Douglas-Rachford splitting method for semidefinite programming ⋮ Mathematical Programming Models and Exact Algorithms ⋮ Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound ⋮ Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem ⋮ A survey for the quadratic assignment problem ⋮ A boundary point method to solve semidefinite programs ⋮ An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem ⋮ Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps ⋮ Semidefinite programming relaxations for graph coloring and maximal clique problems ⋮ Bounds for the quadratic assignment problem using the bundle method ⋮ SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning ⋮ The stable set problem: clique and nodal inequalities revisited ⋮ Strong lift-and-project cutting planes for the stable set problem ⋮ Semidefinite approximations for quadratic programs over orthogonal matrices ⋮ SDP-based branch-and-bound for non-convex quadratic integer optimization ⋮ Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms ⋮ Alternating direction augmented Lagrangian methods for semidefinite programming ⋮ A Repeated Route-then-Schedule Approach to Coordinated Vehicle Platooning: Algorithms, Valid Inequalities and Computation ⋮ Partitioning through projections: strong SDP bounds for large graph partition problems ⋮ Sinkhorn Algorithm for Lifted Assignment Problems ⋮ Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry ⋮ A Graphics Processing Unit Algorithm to Solve the Quadratic Assignment Problem Using Level-2 Reformulation-Linearization Technique ⋮ Level 2 Reformulation Linearization Technique–Based Parallel Algorithms for Solving Large Quadratic Assignment Problems on Graphics Processing Unit Clusters ⋮ On the Lovász theta function and some variants ⋮ A new lift-and-project operator ⋮ A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations ⋮ Measuring instance difficulty for combinatorial optimization problems ⋮ Globally solving nonconvex quadratic programming problems via completely positive programming ⋮ Optimizing a polyhedral-semidefinite relaxation of completely positive programs ⋮ A new relaxation framework for quadratic assignment problems based on matrix splitting ⋮ Valid inequalities for mixed integer linear programs ⋮ An algorithm for the generalized quadratic assignment problem ⋮ Block Coordinate Descent Methods for Semidefinite Programming ⋮ Projection Methods in Conic Optimization ⋮ SDP Relaxations for Some Combinatorial Optimization Problems ⋮ Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting ⋮ A linear formulation with \(O(n^2)\) variables for quadratic assignment problems with Manhattan distance matrices ⋮ A proximal augmented method for semidefinite programming problems ⋮ A Level-3 Reformulation-Linearization Technique-Based Bound for the Quadratic Assignment Problem ⋮ Strengthening Chvátal-Gomory Cuts for the Stable Set Problem ⋮ An alternating direction method for solving convex nonlinear semidefinite programming problems ⋮ Scalable Semidefinite Programming ⋮ Exact Solution of Two Location Problems via Branch-and-Bound

Uses Software

• CSDP
• LAPACK
• QAPLIB
• SDPLR

This page was built for publication: Solving Lift-and-Project Relaxations of Binary Integer Programs