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

DOI10.1007/BF01580072zbMath0919.90112OpenAlexW2078979423MaRDI QIDQ1290621

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-bound max-cut problem semidefinite program quadratic (0,1)-programming

Mathematics Subject Classification ID

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

Related Items

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