On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods
DOI10.1007/S10107-012-0628-6zbMATH Open1282.90121OpenAlexW1979596467MaRDI QIDQ359624FDOQ359624
Authors: Jérôme Malick, Frédéric Roupin 
Publication date: 12 August 2013
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-012-0628-6
Recommendations
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- scientific article; zbMATH DE number 1894380
- Mixed linear and semidefinite programming for combinatorial and quadratic optimization
- Semidefinite and Lagrangian relaxations for hard combinatorial problems
combinatorial optimizationnonlinear programmingquasi-Newtonsemidefinite programmingLagrangian duality0-1 quadratic programming
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Semidefinite programming (90C22)
Cites Work
- CSDP, A C library for semidefinite programming
- Numerical optimization. Theoretical and practical aspects. Transl. from the French
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Numerical Optimization
- Title not available (Why is that?)
- A Spectral Bundle Method for Semidefinite Programming
- Regularization methods for semidefinite programming
- Some numerical experiments with variable-storage quasi-Newton algorithms
- A nonsmooth version of Newton's method
- Computing a nearest symmetric positive semidefinite matrix
- Title not available (Why is that?)
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Title not available (Why is that?)
- An Interior-Point Method for Semidefinite Programming
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Handbook on semidefinite, conic and polynomial optimization
- From linear to semidefinite programming: an algorithm to obtain semidefinite relaxations for bivalent quadratic problems
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- Computational aspects of a branch and bound algorithm for quadratic zero- one programming
- Partial Lagrangian relaxation for general quadratic programming
- Numerical study of semidefinite bounds for the \(k\)-cluster problem
- Solving Graph Bisection Problems with Semidefinite Programming
- Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- Solving \(k\)-cluster problems to optimality with semidefinite programming
- Different Formulations for Solving the HeaviestK-Subgraph Problem
- Seizure warning algorithm based on optimization and nonlinear dynamics
- SDP relaxations in combinatorial optimization from a Lagrangian viewpoint.
- Combining semidefinite and polyhedral relaxations for integer programs
- Exploiting Sparsity in SDP Relaxation for Sensor Network Localization
- The spherical constraint in Boolean quadratic programs
Cited In (10)
- Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods
- Improved semidefinite bounding procedure for solving max-cut problems to optimality
- A semidefinite approach for the single row facility layout problem
- Continuous extensions on Euclidean combinatorial configurations
- A generalized computing paradigm based on artificial dynamic models for mathematical programming
- Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster
- Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained quadratic optimization problems
- Quadratic Combinatorial Optimization Using Separable Underestimators
- Solving \(k\)-cluster problems to optimality with semidefinite programming
- An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating
Uses Software
This page was built for publication: On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q359624)
