An Improved Interior-Point Cutting-Plane Method for Binary Quadratic Optimization

DOI10.1016/j.endm.2010.05.094zbMath1237.90179OpenAlexW2039616602MaRDI QIDQ2883644

Miguel F. Anjos, Alexander Engau, Anthony Vannelli

Publication date: 13 May 2012

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2010.05.094

zbMATH Keywords

combinatorial optimizationinterior-point methodssemidefinite relaxationscutting-plane methodsbinary quadratic programswarmstarts

Mathematics Subject Classification ID

Semidefinite programming (90C22) Sensitivity, stability, parametric optimization (90C31) Combinatorial optimization (90C27)

Related Items

On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems, Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem

Uses Software

• Biq Mac

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• Polynomiality of infeasible-interior-point algorithms for linear programming
• Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
• Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes
• On Interior-Point Warmstarts for Linear and Combinatorial Optimization
• On Semidefinite Programming Relaxations of the Traveling Salesman Problem
• A Study of Indicators for Identifying Zero Variables in Interior-Point Methods
• On the Identification of Zero Variables in an Interior-Point Framework
• Computational Experience with an Interior Point Cutting Plane Algorithm
• Handbook of semidefinite programming. Theory, algorithms, and applications