Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem

DOI10.1007/S10107-005-0637-9zbMath1278.90263OpenAlexW2050336256MaRDI QIDQ868442

Sourour Elloumi, Alain Billionnet

Publication date: 5 March 2007

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

Full work available at URL: https://doi.org/10.1007/s10107-005-0637-9

zbMATH Keywords

integer programmingexperimentsmax-cutconvex quadratic relaxationquadratic 0-1 optimizationsemidefinite positive relaxation

Mathematics Subject Classification ID

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

Related Items (75)

BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints ⋮ A simultaneous diagonalization-based quadratic convex reformulation for nonconvex quadratically constrained quadratic program ⋮ On exact solution approaches for bilevel quadratic 0-1 knapsack problem ⋮ Mathematical Programming Models and Exact Algorithms ⋮ The Random QUBO ⋮ QUBO Software ⋮ Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations ⋮ Generating cutting planes for the semidefinite relaxation of quadratic programs ⋮ On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study ⋮ Conic approximation to quadratic optimization with linear complementarity constraints ⋮ On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods ⋮ Structured linear reformulation of binary quadratically constrained quadratic programs ⋮ Geometric relationship between parallel hyperplanes, quadrics, and vertices of a hypercube ⋮ An efficient combined DCA and B\&B using DC/SDP relaxation for globally solving binary quadratic programs ⋮ Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming ⋮ Solving \(k\)-cluster problems to optimality with semidefinite programming ⋮ A Feasible Active Set Method for Strictly Convex Quadratic Problems with Simple Bounds ⋮ Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems ⋮ Quadratic Convex Reformulations for Semicontinuous Quadratic Programming ⋮ Partial Lasserre relaxation for sparse Max-Cut ⋮ Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods ⋮ The unconstrained binary quadratic programming problem: a survey ⋮ An exact quadratic programming approach based on convex reformulation for seru scheduling problems ⋮ An entropy-regularized ADMM for binary quadratic programming ⋮ Faster exact solution of sparse maxcut and QUBO problems ⋮ An exact cutting plane method for the Euclidean max-sum diversity problem ⋮ A new global algorithm for max-cut problem with chordal sparsity ⋮ Minimizing weighted earliness-tardiness on a single machine with a common due date using quadratic models ⋮ Solving the Production and Maintenance Optimization Problem by a Global Approach ⋮ New formulations of the multiple sequence alignment problem ⋮ A new branch-and-bound approach to semi-supervised support vector machine ⋮ An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach ⋮ The symmetric quadratic traveling salesman problem ⋮ A column generation approach for the unconstrained binary quadratic programming problem ⋮ Improved semidefinite bounding procedure for solving max-cut problems to optimality ⋮ On duality gap in binary quadratic programming ⋮ LMI-based robust mixed-integer model predictive control for hybrid systems ⋮ A compact variant of the QCR method for quadratically constrained quadratic \(0-1\) programs ⋮ Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations ⋮ Extending the QCR method to general mixed-integer programs ⋮ An enhanced MILP-based branch-and-price approach to modularity density maximization on graphs ⋮ Global solution of non-convex quadratically constrained quadratic programs ⋮ A Unified Approach to Mixed-Integer Optimization Problems With Logical Constraints ⋮ A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs ⋮ Quadratic reformulations of nonlinear binary optimization problems ⋮ Quadratic convex reformulation for nonconvex binary quadratically constrained quadratic programming via surrogate constraint ⋮ Quadratic convex reformulation for quadratic programming with linear on-off constraints ⋮ The minimum distance superset problem: formulations and algorithms ⋮ 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 ⋮ Improving a Lagrangian decomposition for the unconstrained binary quadratic programming problem ⋮ A new effective branch-and-bound algorithm to the high order MIMO detection problem ⋮ Convex relaxations for mixed integer predictive control ⋮ Parametric Lagrangian dual for the binary quadratic programming problem ⋮ Convex reformulation for binary quadratic programming problems via average objective value maximization ⋮ An intuitionistic fuzzy set based \(S^3\)VM model for binary classification with mislabeled information ⋮ A filled function method for quadratic programs with binary constraints† ⋮ DC decomposition based branch-and-bound algorithms for box-constrained quadratic programs ⋮ Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems ⋮ A semi-supervised random vector functional-link network based on the transductive framework ⋮ Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results ⋮ Reformulations in Mathematical Programming: Definitions and Systematics ⋮ A binarisation heuristic for non-convex quadratic programming with box constraints ⋮ Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation ⋮ Spectral bounds for the maximum cut problem ⋮ Lagrangean decompositions for the unconstrained binary quadratic programming problem ⋮ Solution of Boolean quadratic programming problems by two augmented Lagrangian algorithms based on a continuous relaxation ⋮ 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 ⋮ DC Programming and DCA for Challenging Problems in Bioinformatics and Computational Biology ⋮ The potential of quantum annealing for rapid solution structure identification ⋮ AN IMPROVED CONVEX 0-1 QUADRATIC PROGRAM REFORMULATION FOR CHANCE-CONSTRAINED QUADRATIC KNAPSACK PROBLEMS ⋮ 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 ⋮ Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition

Uses Software

• Unnamed Item
• AMPL
• CPLEX
• OR-Library
• SDP_S

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pseudo-Boolean optimization
• Zur effektiven Lösung von booleschen, quadratischen Optimierungsproblemen
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• Second order cone programming relaxation of nonconvex quadratic optimization problems
• Adaptive Memory Tabu Search for Binary Quadratic Programs
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• Class of global minimum bounds of polynomial functions
• A tight bound for the boolean quadratic optimization problem and its use in a branch and bound algorithm¹
• An Implicit Enumeration Algorithm for Quadratic Integer Programming
• A NEW SECOND-ORDER CONE PROGRAMMING RELAXATION FOR MAX-CUT PROBLEMS
• A Spectral Bundle Method for Semidefinite Programming
• Convex Relaxations of (0, 1)-Quadratic Programming
• Quadratic binary programming and dynamical system approach to determine the predictability of epileptic seizures

This page was built for publication: Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem