Solving quadratic (0,1)-problems by semidefinite programs and cutting planes

DOI10.1007/BF01580072zbMath0919.90112OpenAlexW2078979423MaRDI QIDQ1290621

Franz Rendl, Christoph Helmberg

Publication date: 3 June 1999

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01580072

zbMATH Keywords

branch-and-boundmax-cut problemsemidefinite programquadratic (0,1)-programming

Mathematics Subject Classification ID

Quadratic programming (90C20) Boolean programming (90C09)

Related Items (77)

On characterization of maximal independent sets via quadratic optimization ⋮ Stochastic Quadratic Knapsack with Recourse ⋮ An Improved Interior-Point Cutting-Plane Method for Binary Quadratic Optimization ⋮ BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints ⋮ On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems ⋮ A strong conic quadratic reformulation for machine-job assignment with controllable processing times ⋮ Disjunctive Cuts for Nonconvex MINLP ⋮ Introduction to QUBO ⋮ The Boolean Quadric Polytope ⋮ Mathematical Programming Models and Exact Algorithms ⋮ Building an iterative heuristic solver for a quantum annealer ⋮ Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations ⋮ Probabilistic GRASP-tabu search algorithms for the UBQP problem ⋮ Generating cutting planes for the semidefinite relaxation of quadratic programs ⋮ Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem ⋮ LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison ⋮ Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem ⋮ Stochastic nuclear outages semidefinite relaxations ⋮ An efficient combined DCA and B\&B using DC/SDP relaxation for globally solving binary quadratic programs ⋮ Manifold relaxations for integer programming ⋮ A note on the 2-circulant inequalities for the MAX-cut problem ⋮ The unconstrained binary quadratic programming problem: a survey ⋮ Ellipsoid Bounds for Convex Quadratic Integer Programming ⋮ An entropy-regularized ADMM for binary quadratic programming ⋮ A new global algorithm for max-cut problem with chordal sparsity ⋮ A preconditioned iterative interior point approach to the conic bundle subproblem ⋮ Continuous Approaches to the Unconstrained Binary Quadratic Problems ⋮ On the impact of running intersection inequalities for globally solving polynomial optimization problems ⋮ A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems ⋮ Knapsack problem with probability constraints ⋮ An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach ⋮ Two-stage quadratic integer programs with stochastic right-hand sides ⋮ Calmness of partial perturbation to composite rank constraint systems and its applications ⋮ A matrix nonconvex relaxation approach to unconstrained binary polynomial programs ⋮ Certifiably optimal sparse inverse covariance estimation ⋮ Improved semidefinite bounding procedure for solving max-cut problems to optimality ⋮ Bounds for Random Binary Quadratic Programs ⋮ A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem ⋮ Solving unconstrained binary quadratic programming problem by global equilibrium search ⋮ A compact variant of the QCR method for quadratically constrained quadratic \(0-1\) programs ⋮ A note on representations of linear inequalities in non-convex mixed-integer quadratic programs ⋮ Extending the QCR method to general mixed-integer programs ⋮ A guide to conic optimisation and its applications ⋮ \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM ⋮ A framework for solving mixed-integer semidefinite programs ⋮ Computing exact solution to nonlinear integer programming: convergent Lagrangian and objective level cut method ⋮ Continuous representations and functional extensions in combinatorial optimization ⋮ A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs ⋮ Quadratic reformulations of nonlinear binary optimization problems ⋮ Reoptimization in Lagrangian methods for the \(0\)-\(1\) quadratic knapsack problem ⋮ A semidefinite programming heuristic for quadratic programming problems with complementarity constraints ⋮ Convex relaxations for mixed integer predictive control ⋮ Global optimality conditions for quadratic \(0-1\) optimization problems ⋮ Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem ⋮ Parametric Lagrangian dual for the binary quadratic programming problem ⋮ Application of semi definite relaxation and variable neighborhood search for multiuser detection in synchronous CDMA ⋮ A semidefinite programming based polyhedral cut and price approach for the maxcut problem ⋮ Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ Recent Progress in Interior-Point Methods: Cutting-Plane Algorithms and Warm Starts ⋮ Computational Approaches to Max-Cut ⋮ Predictive control for hybrid systems. Implications of polyhedral pre-computations ⋮ Efficient semidefinite branch-and-cut for MAP-MRF inference ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method ⋮ A linearization framework for unconstrained quadratic (0-1) problems ⋮ An Active-Set Method for Second-Order Conic-Constrained Quadratic Programming ⋮ Closed-form formulas for evaluating \(r\)-flip moves to the unconstrained binary quadratic programming problem ⋮ Cuts for mixed 0-1 conic programming ⋮ A new separation algorithm for the Boolean quadric and cut polytopes ⋮ Spectral bundle methods for non-convex maximum eigenvalue functions: first-order methods ⋮ Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut ⋮ Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition ⋮ Cutting planes for RLT relaxations of mixed 0-1 polynomial programs ⋮ A simplified binary artificial fish swarm algorithm for 0-1 quadratic knapsack problems ⋮ An unconstrained quadratic binary programming approach to the vertex coloring problem ⋮ ``Miniaturized linearizations for quadratic 0/1 problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The indefinite zero-one quadratic problem
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Combinatorial properties and the complexity of a max-cut approximation
• Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture
• Experiments in quadratic 0-1 programming
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• The hypermetric cone is polyhedral
• Laplacian eigenvalues and the maximum cut problem
• Node and edge relaxations of the max-cut problem
• Connection between semidefinite relaxations of the max-cut and stable set problems
• The cut polytope and the Boolean quadric polytope
• Application of cut polyhedra. I
• Applications of cut polyhedra. II
• The expected relative error of the polyhedral approximation of the max- cut problem
• On a positive semidefinite relaxation of the cut polytope
• Solving the max-cut problem using eigenvalues
• Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• An algorithm for quadratic zero-one programs
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• An Interior-Point Method for Semidefinite Programming
• On the Facial Structure of the Set of Correlation Matrices
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• Geometry of cuts and metrics

This page was built for publication: Solving quadratic (0,1)-problems by semidefinite programs and cutting planes