Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
From MaRDI portal
Publication:1025986
DOI10.1016/j.dam.2007.12.007zbMath1169.90405OpenAlexW2146361854MaRDI QIDQ1025986
Alain Billionnet, Marie-Christine Plateau, Sourour Elloumi
Publication date: 23 June 2009
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/105392
semidefinite programminggraph bisectionexperimentsconvex quadratic programmingquadratic 0-1 programmingtask allocationdensest \(k\)-subgraph
Related Items
Numerical Study of Semidefinite Bounds for the k-cluster Problem ⋮ Dantzig-Wolfe reformulations for binary quadratic problems ⋮ A simultaneous diagonalization-based quadratic convex reformulation for nonconvex quadratically constrained quadratic program ⋮ An optimal approach for the critical node problem using semidefinite programming ⋮ The Random QUBO ⋮ Semidefinite relaxation for two mixed binary quadratically constrained quadratic programs: algorithms and approximation bounds ⋮ Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster ⋮ On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study ⋮ On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods ⋮ SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY ⋮ Structured linear reformulation of binary quadratically constrained quadratic programs ⋮ Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming ⋮ Solving \(k\)-cluster problems to optimality with semidefinite programming ⋮ On the quadratic model for unrelated parallel machine scheduling problem with restrictive common due date ⋮ Reconstructing convex matrices by integer programming approaches ⋮ Maximum probability O-D matrix estimation in large-sized networks ⋮ Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms ⋮ Quadratic Convex Reformulations for Semicontinuous Quadratic Programming ⋮ Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods ⋮ An exact quadratic programming approach based on convex reformulation for seru scheduling problems ⋮ An efficient compact quadratic convex reformulation for general integer quadratic programs ⋮ Minimizing weighted earliness-tardiness on a single machine with a common due date using quadratic models ⋮ An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach ⋮ The symmetric quadratic traveling salesman problem ⋮ Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming ⋮ Using quadratic convex reformulation to tighten the convex relaxation of a quadratic program with complementarity constraints ⋮ A compact variant of the QCR method for quadratically constrained quadratic \(0-1\) programs ⋮ Quadratic Combinatorial Optimization Using Separable Underestimators ⋮ Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations ⋮ An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating ⋮ A note on representations of linear inequalities in non-convex mixed-integer quadratic programs ⋮ Extending the QCR method to general mixed-integer programs ⋮ Spectral Relaxations and Branching Strategies for Global Optimization of Mixed-Integer Quadratic Programs ⋮ Scheduling with earliness-tardiness penalties and parallel machines ⋮ A neurodynamic approach to zero-one quadratic programming ⋮ Global solution of non-convex quadratically constrained quadratic programs ⋮ The MIN-cut and vertex separator problem ⋮ An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations ⋮ Quadratic convex reformulation for nonconvex binary quadratically constrained quadratic programming via surrogate constraint ⋮ The demand weighted vehicle routing problem ⋮ Quadratic convex reformulation for quadratic programming with linear on-off constraints ⋮ Combining QCR and CHR for convex quadratic pure 0--1 programming problems with linear constraints ⋮ A computational study on the quadratic knapsack problem with multiple constraints ⋮ QPLIB: a library of quadratic programming instances ⋮ Intersection cuts for nonlinear integer programming: convexification techniques for structured sets ⋮ Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem ⋮ On Minimal Valid Inequalities for Mixed Integer Conic Programs ⋮ Reformulations in Mathematical Programming: Definitions and Systematics ⋮ Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation ⋮ Solution of Boolean quadratic programming problems by two augmented Lagrangian algorithms based on a continuous relaxation ⋮ Semidefinite approximation bound for a class of nonhomogeneous nonconvex quadratically constrained quadratic programming problem ⋮ Relaxing Nonconvex Quadratic Functions by Multiple Adaptive Diagonal Perturbations ⋮ Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method ⋮ On linear conic relaxation of discrete quadratic programs ⋮ The linearization problem of a binary quadratic problem and its applications ⋮ Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations ⋮ Computational comparison of exact solution methods for 0-1 quadratic programs: recommendations for practitioners ⋮ Decision Diagram Decomposition for Quadratically Constrained Binary Optimization ⋮ AN IMPROVED CONVEX 0-1 QUADRATIC PROGRAM REFORMULATION FOR CHANCE-CONSTRAINED QUADRATIC KNAPSACK PROBLEMS ⋮ Parametric convex quadratic relaxation of the quadratic knapsack problem ⋮ Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems ⋮ On the separation of split inequalities for non-convex quadratic integer programming ⋮ On solving the densestk-subgraph problem on large graphs ⋮ Mathematical optimization ideas for biodiversity conservation
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The indefinite zero-one quadratic problem
- Discrete location problems with push-pull objectives
- An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
- 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
- Clustering and domination in perfect graphs
- On the quadratic assignment problem
- Lagrangean decomposition for integer nonlinear programming with linear constraints
- A reformulation-linearization technique for solving discrete and continuous nonconvex problems
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- Semidefinite programming in combinatorial optimization
- A branch-and-cut algorithm for the equicut problem
- The basic algorithm for pseudo-Boolean programming revisited
- Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs
- Upper bounds and exact algorithms for \(p\)-dispersion problems
- A Mathematical View of Interior-Point Methods in Convex Optimization
- An algorithm for quadratic zero-one programs
- A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
- An Implicit Enumeration Algorithm for Quadratic Integer Programming
- A New Lower Bound for the Quadratic Assignment Problem
- An efficient algorithm for a task allocation problem
- Solving Graph Bisection Problems with Semidefinite Programming
- A Spectral Bundle Method for Semidefinite Programming
- A Decomposition Method for Quadratic Zero-One Programming
- Further Reduction of Zero-One Polynomial Programming Problems to Zero-One linear Programming Problems
- A new bound for the quadratic assignment problem based on convex quadratic programming
- Best reduction of the quadratic semi-assignment problem
- Different Formulations for Solving the HeaviestK-Subgraph Problem
