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

Linearization Techniques for 0/1 Quadratic Programming

Serigne Guèye, Philippe Yves Paul Michelon

Published Jan 1, 2001• 0 citations
OpenAlex

Related papers

Structured linear reformulation of binary quadratically constrained quadratic programs

Shan Jiang, Shu‐Cherng Fang, Tiantian Nie +1 more

Optimization Letters•Nov 17, 2018•1 citation

Linear transformation based solution methods for non-convex mixed integer quadratic programs

Eric Newby, M. Montaz Ali

Optimization Letters•Dec 26, 2015•1 citation

Linearization Techniques for unconstrained 0/1 Quadratic problems

Serigne Guèye, Philippe Yves Paul Michelon

•Jan 1, 2002•0 citations

On linear conic relaxation of discrete quadratic programs

Tiantian Nie, Shu‐Cherng Fang, Zhibin Deng +1 more

A special reformulation-linearization technique based linear conic relaxation is proposed for discrete quadratic programming (DQP). We show that the proposed relaxation is tighter than the traditional positive semidefinite programming relaxation. More importantly, when the proposed relaxation problem has an optimal solution with rank one or two, optimal solutions to the original DQP problem can be explicitly generated. This rank-two property is further extended to binary quadratic optimization problems and linearly constrained DQP problems. Numerical results indicate that the proposed relaxation is capable of providing high quality and robust lower bounds for DQP.

Optimization methods & software•Jan 28, 2016•12 citations

Approximation Algorithms for Quadratic Programming

Minyue Fu, Zhi-Quan Tom Luo, Yinyu Ye

Journal of Combinatorial Optimization•Mar 1, 1998•78 citations

Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques

Wei Xia, Juan C. Vera, Luis F. Zuluaga

We reformulate a (indefinite) quadratic program (QP) as a mixed-integer linear programming (MILP) problem by first reformulating a QP as a linear complementary problem, and then using binary variables and big-M constraints to model its complementary constraints. To obtain such reformulation, we use fundamental results on the solution of perturbed linear systems to impose bounds on the QP’s dual variables without eliminating any of its (globally) optimal primal solutions. Reformulating a nonconvex QP as a MILP problem allows the use of current state-of-the-art MILP solvers to find its global optimal solution. To illustrate this, we compare the performance of this MILP-based solution approach, labeled quadprogIP, with quadprogBB, BARON, and CPLEX. In practice, quadprogIP is shown to typically outperform by orders of magnitude quadprogBB, BARON, and CPLEX on standard QPs. Also, unlike quadprogBB, quadprogIP is able to solve QP instances in which the dual feasible set is unbounded. The MATLAB code quadprogIP and the instances used to perform the reported numerical experiments are publicly available at https://github.com/xiawei918/quadprogIP .

arXiv:1511.02423•INFORMS journal on computing•Jul 19, 2019•55 citations
A special reformulation-linearization technique based linear conic relaxation is proposed for discrete quadratic programming (DQP). We show that the proposed relaxation is tighter than the traditional positive semidefinite programming relaxation. More importantly, when the proposed relaxation problem has an optimal solution with rank one or two, optimal solutions to the original DQP problem can be explicitly generated. This rank-two property is further extended to binary quadratic optimization problems and linearly constrained DQP problems. Numerical results indicate that the proposed relaxation is capable of providing high quality and robust lower bounds for DQP.
We reformulate a (indefinite) quadratic program (QP) as a mixed-integer linear programming (MILP) problem by first reformulating a QP as a linear complementary problem, and then using binary variables and big-M constraints to model its complementary constraints. To obtain such reformulation, we use fundamental results on the solution of perturbed linear systems to impose bounds on the QP’s dual variables without eliminating any of its (globally) optimal primal solutions. Reformulating a nonconvex QP as a MILP problem allows the use of current state-of-the-art MILP solvers to find its global optimal solution. To illustrate this, we compare the performance of this MILP-based solution approach, labeled quadprogIP, with quadprogBB, BARON, and CPLEX. In practice, quadprogIP is shown to typically outperform by orders of magnitude quadprogBB, BARON, and CPLEX on standard QPs. Also, unlike quadprogBB, quadprogIP is able to solve QP instances in which the dual feasible set is unbounded. The MATLAB code quadprogIP and the instances used to perform the reported numerical experiments are publicly available at https://github.com/xiawei918/quadprogIP .