Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Two useful computational tricks for Quadratic Programming: hybrid SDP bounding procedures and a new linearisation technique

Fabio Furini, Emiliano Traversi

Published Jan 1, 2014• 0 citations
OpenAlex

Abstract

Quadratic programming problems have received an increasing amount of attention in the recent years, both from the theoretical and practical point of views. For this class of problems, we studied two different useful computational tricks.The first one is the exploitation of Semidefinite Programming (SDP) relaxation within the framework provided by Mixed Integer Nonlinear Programming (MINLP) solvers. We included the SDP relaxation in a state-of-the-art MINLP solver as an additional bounding technique and demonstrated that this idea could be computationally useful. The Quadratic Stable Set Problem is adopted as the case study. The tests indicate that the Hybrid SDP Bounding Procedure allows an average 50% cut of the overall computing time and a cut of more than one order of magnitude for the branching nodes.The second one is a new linearisation technique. We computationally prove that the new formulation, called Extended Linear Formulation, can be effective for different classes of problems in practice. Our tests are based on two sets of classical BQPs from the literature, i.e., the Unconstrained BQP and the Maximum Cut of edge-weighted graphs. Finally we discuss the relations between the Linear Programming relaxations of the different linearisation techniques presented and we discuss the elimination of constraint redundancy which is effective at speeding up the computational convergence.

Related papers

Large-Scale Binary Quadratic Optimization Using Semidefinite Relaxation and Applications

Peng Wang, Chunhua Shen, Anton van den Hengel +1 more

In computer vision, many problems can be formulated as binary quadratic programs (BQPs), which are in general NP hard. Finding a solution when the problem is of large size to be of practical interest typically requires relaxation. Semidefinite relaxation usually yields tight bounds, but its computational complexity is high. In this work, we present a semidefinite programming (SDP) formulation for BQPs, with two desirable properties. First, it produces similar bounds to the standard SDP formulation. Second, compared with the conventional SDP formulation, the proposed SDP formulation leads to a considerably more efficient and scalable dual optimization approach. We then propose two solvers, namely, quasi-Newton and smoothing Newton methods, for the simplified dual problem. Both of them are significantly more efficient than standard interior-point methods. Empirically the smoothing Newton solver is faster than the quasi-Newton solver for dense or medium-sized problems, while the quasi-Newton solver is preferable for large sparse/structured problems.

arXiv:1411.7564•IEEE Transactions on Pattern Analysis and Machine Intelligence•Mar 11, 2016•59 citations

An unconstrained approach for solving low rank SDP relaxations of {-1, 1} quadratic problems

Luigi Grippo, Laura Palagi, Mauro Piacentini +1 more

We consider low-rank semidefinite programming (LRSDP) relaxations of ±1 quadratic problems that can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function and we define an effcient and globally convergent algorithm for finding critical points of the LRSDP problem. Finally, we test our code on an extended set of instances of the Max-Cut problem and we report comparisons with other existing codes.

•Sep 1, 2009•0 citations

Quadratic Convex Reformulation : a Computational Study of the Graph Bisection Problem

Alain Billionnet, Sourour Elloumi, Marie-Christine Plateau

Given an undirected graph G = (V, E), we consider the graph bisection problem, which consists in partitioning the nodes of G in two disjoined sets with p and n − p nodes respectively such that the total weight of edges crossing between subsets is minimal. We apply QCR to it, a general method, presented in [4], which combines semidefinite programming (SDP) and Mixed Integer Quadratic Programming (MIQP). This method solves exactly general 0-1 quadratic programs (called (QP)) with linear constraints. It is composed of two phases: Phase I is devoted to reformulate (QP) into a new problem, equivalent to (QP), with a convex quadratic function; Phase II consists in submitting this new problem to a mixed-integer convex quadratic solver. Computational results reported in this paper show that the present approach is competitive with state-of-the-art methods for the graph bisection problem.

•Jan 1, 2006•9 citations

Binary quadratic problems: theoretical and computational approach

Pablo Luiz Braga Soares

The main objective of this work is to show the application of linear and nonlinear programming methods to deal with problems whose natural 0−1 formulation has a quadratic objective function. To this end, we develop an extension of the t-linearization technique and show how to apply it to quadratic problems such as Maximum Cut, Maximum Diversity and Maximum Edge-Weighted Clique. In addition, we review the hyperbolic smoothing technique and show how to apply it to the maximum cut problem. We carry out a theoretical study of each problem, where we particularly present the development of new valid inequalities for each of them. We perform computational experiments to evaluate the performance of each technique separately, as well as combined with the proposed new constraints. The experiments attest the quality of the bounds obtained as well as the strength of the new inequalities. We develop an exact method for each problem, based on the presented techniques. For the maximum cut and maximum edge-weighted clique, we compare our method with linearized formulations. For maximum diversity, we compare our method with linearized formulations and with our implementation of the best exact method, which does not use mathematical solvers, known in the literature. Computational experiments with instances of the literature show superior performance of our method.

•Jan 1, 2018•0 citations

Beyond binarity: Semidefinite programming for ternary quadratic problems

Frank de Meijer, Veronica Piccialli, Renata Sotirov +1 more

We study the ternary quadratic problem (TQP), a quadratic optimization problem with linear constraints where the variables take values in $\{0, \pm 1\}$. While semidefinite programming (SDP) techniques are well established for $\{0,1\}$- and $\{\pm 1\}$-valued quadratic problems, no dedicated integer semidefinite programming framework exists for the ternary case. In this paper, we introduce a ternary SDP formulation for the TQP that forms the basis of an exact solution approach. We derive new theoretical insights in rank-one ternary positive semidefinite matrices, which lead to a basic SDP relaxation that is further strengthened by valid triangle, RLT, split and $k$-gonal inequalities. These are embedded in a tailored branch-and-bound algorithm that iteratively solves strengthened SDPs, separates violated inequalities, applies a ternary branching strategy and computes high-quality feasible solutions. We test our algorithm on TQP variations motivated by practice, including unconstrained, linearly constrained and quadratic ratio problems. Computational results on these instances demonstrate the effectiveness of the proposed algorithm.

arXiv:2603.28979•Mar 30, 2026•1 citation

A Direct SDP Approach for Constrained Quadratic Binary Optimization Problems

MilaNedic, Zvmcevap

This repository contains the source code, computational experiments, analysis, and benchmarks accompanying the paper A Direct SDP-Based Framework for Certified Bounds for Constrained Quadratic Binary Optimization Problems. The repository implements a direct semidefinite programming (SDP) approach for constrained quadratic binary optimization, designed to obtain strong bounds for exact optimization. The SDP relaxation is strengthened using quadratized linear constraints and triangle (hypermetric) inequalities. To address the numerical infeasibility of SDP solutions obtained from numerical solvers such as MOSEK, the framework includes a correction procedure that converts approximate SDP solutions into mathematically certified bounds suitable for use in Branch-and-Bound algorithms. The repository also implements an adaptation of the Goemans–Williamson randomized hyperplane rounding scheme to constrained binary optimization, together with problem-specific feasibility restoration. Computational experiments are provided for the Sparsest k-Subgraph and Maximum Independent Set problems. The work presented in this repository was funded and developed under the QBIQ project (project no. 644), funded by the Slovenian Research and Innovation Agency (ARIS) through the Applied Projects programme. The code and accompanying data are intended to facilitate reproducibility of the computational results and provide a foundation for further research on exact SDP-based methods for constrained quadratic binary optimization.

•Aug 25, 2026•0 citations
Quadratic programming problems have received an increasing amount of attention in the recent years, both from the theoretical and practical point of views. For this class of problems, we studied two different useful computational tricks.The first one is the exploitation of Semidefinite Programming (SDP) relaxation within the framework provided by Mixed Integer Nonlinear Programming (MINLP) solvers. We included the SDP relaxation in a state-of-the-art MINLP solver as an additional bounding technique and demonstrated that this idea could be computationally useful. The Quadratic Stable Set Problem is adopted as the case study. The tests indicate that the Hybrid SDP Bounding Procedure allows an average 50% cut of the overall computing time and a cut of more than one order of magnitude for the branching nodes.The second one is a new linearisation technique. We computationally prove that the new formulation, called Extended Linear Formulation, can be effective for different classes of problems in practice. Our tests are based on two sets of classical BQPs from the literature, i.e., the Unconstrained BQP and the Maximum Cut of edge-weighted graphs. Finally we discuss the relations between the Linear Programming relaxations of the different linearisation techniques presented and we discuss the elimination of constraint redundancy which is effective at speeding up the computational convergence.
In computer vision, many problems can be formulated as binary quadratic programs (BQPs), which are in general NP hard. Finding a solution when the problem is of large size to be of practical interest typically requires relaxation. Semidefinite relaxation usually yields tight bounds, but its computational complexity is high. In this work, we present a semidefinite programming (SDP) formulation for BQPs, with two desirable properties. First, it produces similar bounds to the standard SDP formulation. Second, compared with the conventional SDP formulation, the proposed SDP formulation leads to a considerably more efficient and scalable dual optimization approach. We then propose two solvers, namely, quasi-Newton and smoothing Newton methods, for the simplified dual problem. Both of them are significantly more efficient than standard interior-point methods. Empirically the smoothing Newton solver is faster than the quasi-Newton solver for dense or medium-sized problems, while the quasi-Newton solver is preferable for large sparse/structured problems.
We consider low-rank semidefinite programming (LRSDP) relaxations of ±1 quadratic problems that can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function and we define an effcient and globally convergent algorithm for finding critical points of the LRSDP problem. Finally, we test our code on an extended set of instances of the Max-Cut problem and we report comparisons with other existing codes.
Given an undirected graph G = (V, E), we consider the graph bisection problem, which consists in partitioning the nodes of G in two disjoined sets with p and n − p nodes respectively such that the total weight of edges crossing between subsets is minimal. We apply QCR to it, a general method, presented in [4], which combines semidefinite programming (SDP) and Mixed Integer Quadratic Programming (MIQP). This method solves exactly general 0-1 quadratic programs (called (QP)) with linear constraints. It is composed of two phases: Phase I is devoted to reformulate (QP) into a new problem, equivalent to (QP), with a convex quadratic function; Phase II consists in submitting this new problem to a mixed-integer convex quadratic solver. Computational results reported in this paper show that the present approach is competitive with state-of-the-art methods for the graph bisection problem.
The main objective of this work is to show the application of linear and nonlinear programming methods to deal with problems whose natural 0−1 formulation has a quadratic objective function. To this end, we develop an extension of the t-linearization technique and show how to apply it to quadratic problems such as Maximum Cut, Maximum Diversity and Maximum Edge-Weighted Clique. In addition, we review the hyperbolic smoothing technique and show how to apply it to the maximum cut problem. We carry out a theoretical study of each problem, where we particularly present the development of new valid inequalities for each of them. We perform computational experiments to evaluate the performance of each technique separately, as well as combined with the proposed new constraints. The experiments attest the quality of the bounds obtained as well as the strength of the new inequalities. We develop an exact method for each problem, based on the presented techniques. For the maximum cut and maximum edge-weighted clique, we compare our method with linearized formulations. For maximum diversity, we compare our method with linearized formulations and with our implementation of the best exact method, which does not use mathematical solvers, known in the literature. Computational experiments with instances of the literature show superior performance of our method.
We study the ternary quadratic problem (TQP), a quadratic optimization problem with linear constraints where the variables take values in {0,±1}\{0, \pm 1\}{0,±1}. While semidefinite programming (SDP) techniques are well established for {0,1}\{0,1\}{0,1}- and {±1}\{\pm 1\}{±1}-valued quadratic problems, no dedicated integer semidefinite programming framework exists for the ternary case. In this paper, we introduce a ternary SDP formulation for the TQP that forms the basis of an exact solution approach. We derive new theoretical insights in rank-one ternary positive semidefinite matrices, which lead to a basic SDP relaxation that is further strengthened by valid triangle, RLT, split and kkk-gonal inequalities. These are embedded in a tailored branch-and-bound algorithm that iteratively solves strengthened SDPs, separates violated inequalities, applies a ternary branching strategy and computes high-quality feasible solutions. We test our algorithm on TQP variations motivated by practice, including unconstrained, linearly constrained and quadratic ratio problems. Computational results on these instances demonstrate the effectiveness of the proposed algorithm.
This repository contains the source code, computational experiments, analysis, and benchmarks accompanying the paper A Direct SDP-Based Framework for Certified Bounds for Constrained Quadratic Binary Optimization Problems. The repository implements a direct semidefinite programming (SDP) approach for constrained quadratic binary optimization, designed to obtain strong bounds for exact optimization. The SDP relaxation is strengthened using quadratized linear constraints and triangle (hypermetric) inequalities. To address the numerical infeasibility of SDP solutions obtained from numerical solvers such as MOSEK, the framework includes a correction procedure that converts approximate SDP solutions into mathematically certified bounds suitable for use in Branch-and-Bound algorithms. The repository also implements an adaptation of the Goemans–Williamson randomized hyperplane rounding scheme to constrained binary optimization, together with problem-specific feasibility restoration. Computational experiments are provided for the Sparsest k-Subgraph and Maximum Independent Set problems. The work presented in this repository was funded and developed under the QBIQ project (project no. 644), funded by the Slovenian Research and Innovation Agency (ARIS) through the Applied Projects programme. The code and accompanying data are intended to facilitate reproducibility of the computational results and provide a foundation for further research on exact SDP-based methods for constrained quadratic binary optimization.