Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
From MaRDI portal
Publication:1290621
DOI10.1007/BF01580072zbMATH Open0919.90112OpenAlexW2078979423MaRDI QIDQ1290621FDOQ1290621
Authors: Christoph Helmberg, Franz Rendl 
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
Recommendations
Cites Work
- Application of cut polyhedra. I
- Applications of cut polyhedra. II
- An Interior-Point Method for Semidefinite Programming
- Geometry of cuts and metrics
- The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
- Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm
- Laplacian eigenvalues and the maximum cut problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- .878-approximation algorithms for MAX CUT and MAX 2SAT
- Roof duality, complementation and persistency in quadratic 0–1 optimization
- Title not available (Why is that?)
- On a positive semidefinite relaxation of the cut polytope
- Computational aspects of a branch and bound algorithm for quadratic zero- one programming
- The max-cut problem on graphs not contractible to \(K_ 5\)
- The cut polytope and the Boolean quadric polytope
- Some Network Flow Problems Solved with Pseudo-Boolean Programming
- On the Facial Structure of the Set of Correlation Matrices
- Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
- Experiments in quadratic 0-1 programming
- An algorithm for quadratic zero-one programs
- Nonpolyhedral Relaxations of Graph-Bisection Problems
- The indefinite zero-one quadratic problem
- Combinatorial properties and the complexity of a max-cut approximation
- Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture
- Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
- The hypermetric cone is polyhedral
- Node and edge relaxations of the max-cut problem
- Solving the max-cut problem using eigenvalues
- The expected relative error of the polyhedral approximation of the max- cut problem
- Connection between semidefinite relaxations of the max-cut and stable set problems
Cited In (83)
- On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems
- Cutting planes for RLT relaxations of mixed 0-1 polynomial programs
- A note on representations of linear inequalities in non-convex mixed-integer quadratic programs
- A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs
- A semidefinite programming based polyhedral cut and price approach for the maxcut problem
- Cuts for mixed 0-1 conic programming
- A new separation algorithm for the Boolean quadric and cut polytopes
- An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach
- Solving unconstrained binary quadratic programming problem by global equilibrium search
- Quadratic reformulations of nonlinear binary optimization problems
- Improved semidefinite bounding procedure for solving max-cut problems to optimality
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Semidefinite relaxations for partitioning, assignment and ordering problems
- An unconstrained quadratic binary programming approach to the vertex coloring problem
- A linearization framework for unconstrained quadratic (0-1) problems
- Probabilistic GRASP-tabu search algorithms for the UBQP problem
- The unconstrained binary quadratic programming problem: a survey
- A strong conic quadratic reformulation for machine-job assignment with controllable processing times
- Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
- Algorithms – ESA 2005
- Experiments in quadratic 0-1 programming
- Stochastic quadratic knapsack with recourse
- Two-stage quadratic integer programs with stochastic right-hand sides
- Global optimality conditions for quadratic \(0-1\) optimization problems
- Parametric Lagrangian dual for the binary quadratic programming problem
- Convex relaxations for mixed integer predictive control
- Solving quadratic semi-infinite programming problems by using relaxed cutting-plane scheme
- Predictive control for hybrid systems. Implications of polyhedral pre-computations
- Certifiably optimal sparse inverse covariance estimation
- Computing exact solution to nonlinear integer programming: convergent Lagrangian and objective level cut method
- Application of semi definite relaxation and variable neighborhood search for multiuser detection in synchronous CDMA
- LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
- Extending the QCR method to general mixed-integer programs
- Disjunctive Cuts for Nonconvex MINLP
- The Boolean Quadric Polytope
- Continuous Approaches to the Unconstrained Binary Quadratic Problems
- Solving Quadratic Programming by Cutting Planes
- An efficient combined DCA and B\&B using DC/SDP relaxation for globally solving binary quadratic programs
- Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
- Knapsack problem with probability constraints
- Stochastic nuclear outages semidefinite relaxations
- Ellipsoid Bounds for Convex Quadratic Integer Programming
- Generating cutting planes for the semidefinite relaxation of quadratic programs
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- A semidefinite programming heuristic for quadratic programming problems with complementarity constraints
- Computational Approaches to Max-Cut
- On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods
- Mathematical Programming Models and Exact Algorithms
- Efficient semidefinite branch-and-cut for MAP-MRF inference
- Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem
- Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem
- An Active-Set Method for Second-Order Conic-Constrained Quadratic Programming
- Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints
- Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- Reoptimization in Lagrangian methods for the \(0\)-\(1\) quadratic knapsack problem
- Building an iterative heuristic solver for a quantum annealer
- On characterization of maximal independent sets via quadratic optimization
- Recent Progress in Interior-Point Methods: Cutting-Plane Algorithms and Warm Starts
- Continuous representations and functional extensions in combinatorial optimization
- Manifold relaxations for integer programming
- Calmness of partial perturbation to composite rank constraint systems and its applications
- ``Miniaturized linearizations for quadratic 0/1 problems
- Spectral bundle methods for non-convex maximum eigenvalue functions: first-order methods
- A simplified binary artificial fish swarm algorithm for 0-1 quadratic knapsack problems
- A compact variant of the QCR method for quadratically constrained quadratic \(0-1\) programs
- A framework for solving mixed-integer semidefinite programs
- Title not available (Why is that?)
- Closed-form formulas for evaluating \(r\)-flip moves to the unconstrained binary quadratic programming problem
- Introduction to QUBO
- \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM
- An improved interior-point cutting-plane method for binary quadratic optimization
- A guide to conic optimisation and its applications
- Bounds for Random Binary Quadratic Programs
- On the impact of running intersection inequalities for globally solving polynomial optimization problems
- An entropy-regularized ADMM for binary quadratic programming
- A new global algorithm for max-cut problem with chordal sparsity
- A note on the 2-circulant inequalities for the MAX-cut problem
- A matrix nonconvex relaxation approach to unconstrained binary polynomial programs
- A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems
- A preconditioned iterative interior point approach to the conic bundle subproblem
This page was built for publication: Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1290621)
