On duality gap in binary quadratic programming
From MaRDI portal
Publication:454277
DOI10.1007/s10898-011-9683-4zbMath1278.90296OpenAlexW2079013783WikidataQ57445443 ScholiaQ57445443MaRDI QIDQ454277
J. Herrera, D. Rodríguez-Gómez
Publication date: 1 October 2012
Published in: Journal of Global Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10898-011-9683-4
duality gapbinary quadratic programmingsemidefinite programming relaxationcell enumeration of hyperplane arrangement
Related Items
Complexity and Polynomially Solvable Special Cases of QUBO, Tightening a copositive relaxation for standard quadratic optimization problems, New semidefinite programming relaxations for box constrained quadratic program, The unconstrained binary quadratic programming problem: a survey, Improved estimation of duality gap in binary quadratic programming using a weighted distance measure, A polynomial case of convex integer quadratic programming problems with box integer constraints, Parametric Lagrangian dual for the binary quadratic programming problem, Convex reformulation for binary quadratic programming problems via average objective value maximization, On linear conic relaxation of discrete quadratic programs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
- On the stability of a dual weak vector variational inequality problem
- Solutions and optimality criteria for nonconvex constrained global optimization problems with connections between canonical and Lagrangian duality
- A solvable class of quadratic 0-1 programming
- Laplacian eigenvalues and the maximum cut problem
- Topics in semidefinite and interior-point methods
- Novel approaches to hard discrete optimization
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- Reverse search for enumeration
- Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem
- On the gap between the quadratic integer programming problem and its semidefinite relaxation
- Lower bound improvement and forcing rule for quadratic binary programming
- Global Optimality Conditions for Quadratic Optimization Problems with Binary Constraints
- Polynomially Solvable Cases of Binary Quadratic Programs
- Duality Gap Estimation of Linear Equality Constrained Binary Quadratic Programming
- Spectral bounds for the maximum cut problem
- Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
- Minimum cuts and related problems
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Construction of test problems in quadratic bivalent programming
- Convex Relaxations of (0, 1)-Quadratic Programming
- Semidefinite Programming
- Handbook of semidefinite programming. Theory, algorithms, and applications
- A polynomial case of unconstrained zero-one quadratic optimization