Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Electronic Notes in Discrete Mathematics

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

Alexander Engau, Miguel F. Anjos, Anthony Vannelli

Published Jul 20, 2010• 3 citations
Publisher
DOI
10.1016/j.endm.2010.05.094

Related papers

Improved row-by-row method for binary quadratic optimization problems

Rupaj Kumar Nayak, Nirmalya Kumar Mohanty

Annals of Operations Research•Jul 27, 2018•3 citations

Cuts and heuristics for nonconvex quadratic optimization

Luce, Robert

Solving nonconvex quadratic optimization problems to global optimality is a challenging task. For this problem class Gurobi takes a branch-and-bound approach, so the building blocks for the solver are: A relaxation of the problem to solve at the nodes, cutting planes to reduce the feasible region of the relaxation, and heuristics to compute primal feasible solutions. Here we discuss the latter two building blocks in more detail, focussing on so-called PSD cuts, and a heuristic based on an interior point method.

•Feb 23, 2022•0 citations

Unconstrained binary quadratic optimization

Erich Steiner, Th. M. Liebling, Komei Fukuda +1 more

•Jan 1, 2000•1 citation

Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization

Michael Jünger, Sven Mallach

The exact solution of the NP-hard (nondeterministic polynomial-time hard) maximum cut problem is important in many applications across, for example, physics, chemistry, neuroscience, and circuit layout—which is also due to its equivalence to the unconstrained binary quadratic optimization problem. Leading solution methods are based on linear or semidefinite programming and require the separation of the so-called odd-cycle inequalities. In their groundbreaking research, F. Barahona and A. R. Mahjoub have given an informal description of a polynomial-time algorithm for this problem. As pointed out recently, however, additional effort is necessary to guarantee that the inequalities obtained correspond to facets of the cut polytope. In this paper, we shed more light on a so enhanced separation procedure and investigate experimentally how it performs in comparison with an ideal setting where one could even employ the sparsest, most violated, or geometrically most promising facet-defining odd-cycle inequalities. Summary of Contribution: This paper aims at a better capability to solve binary quadratic optimization or maximum cut problems and their various applications using integer programming techniques. To this end, the paper describes enhancements to a well-known algorithm for the central separation problem arising in this context; it is demonstrated experimentally that these enhancements are worthwhile from a computational point of view. The linear relaxations of the aforementioned problems are typically solved using fewer iterations and cutting planes than with a nonenhanced approach. It is also shown that the enhanced procedure is only slightly inferior to an ideal, enumerative, and, in practice, intractable global cutting-plane selection.

INFORMS journal on computing•Feb 11, 2021•8 citations

Binary Unconstrained Quadratic Optimization Problem

Gary A. Kochenberger, Fred Glover, Haibo Wang

Springer eBooks•Jan 1, 2013•9 citations

A Rank-Two Feasible Direction Algorithm for the Binary Quadratic Programming

Xuewen Mu, Yaling Zhang

Based on the semidefinite programming relaxation of the binary quadratic programming, a rank-two feasible direction algorithm is presented. The proposed algorithm restricts the rank of matrix variable to be two in the semidefinite programming relaxation and yields a quadratic objective function with simple quadratic constraints. A feasible direction algorithm is used to solve the nonlinear programming. The convergent analysis and time complexity of the method is given. Coupled with randomized algorithm, a suboptimal solution is obtained for the binary quadratic programming. At last, we report some numerical examples to compare our algorithm with randomized algorithm based on the interior point method and the feasible direction algorithm on max-cut problem. Simulation results have shown that our method is faster than the other two methods.

Journal of Applied Mathematics•Jan 1, 2013•1 citation
Solving nonconvex quadratic optimization problems to global optimality is a challenging task. For this problem class Gurobi takes a branch-and-bound approach, so the building blocks for the solver are: A relaxation of the problem to solve at the nodes, cutting planes to reduce the feasible region of the relaxation, and heuristics to compute primal feasible solutions. Here we discuss the latter two building blocks in more detail, focussing on so-called PSD cuts, and a heuristic based on an interior point method.
The exact solution of the NP-hard (nondeterministic polynomial-time hard) maximum cut problem is important in many applications across, for example, physics, chemistry, neuroscience, and circuit layout—which is also due to its equivalence to the unconstrained binary quadratic optimization problem. Leading solution methods are based on linear or semidefinite programming and require the separation of the so-called odd-cycle inequalities. In their groundbreaking research, F. Barahona and A. R. Mahjoub have given an informal description of a polynomial-time algorithm for this problem. As pointed out recently, however, additional effort is necessary to guarantee that the inequalities obtained correspond to facets of the cut polytope. In this paper, we shed more light on a so enhanced separation procedure and investigate experimentally how it performs in comparison with an ideal setting where one could even employ the sparsest, most violated, or geometrically most promising facet-defining odd-cycle inequalities. Summary of Contribution: This paper aims at a better capability to solve binary quadratic optimization or maximum cut problems and their various applications using integer programming techniques. To this end, the paper describes enhancements to a well-known algorithm for the central separation problem arising in this context; it is demonstrated experimentally that these enhancements are worthwhile from a computational point of view. The linear relaxations of the aforementioned problems are typically solved using fewer iterations and cutting planes than with a nonenhanced approach. It is also shown that the enhanced procedure is only slightly inferior to an ideal, enumerative, and, in practice, intractable global cutting-plane selection.
Based on the semidefinite programming relaxation of the binary quadratic programming, a rank-two feasible direction algorithm is presented. The proposed algorithm restricts the rank of matrix variable to be two in the semidefinite programming relaxation and yields a quadratic objective function with simple quadratic constraints. A feasible direction algorithm is used to solve the nonlinear programming. The convergent analysis and time complexity of the method is given. Coupled with randomized algorithm, a suboptimal solution is obtained for the binary quadratic programming. At last, we report some numerical examples to compare our algorithm with randomized algorithm based on the interior point method and the feasible direction algorithm on max-cut problem. Simulation results have shown that our method is faster than the other two methods.