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

Polynomial time solvable algorithms to a class of unconstrained and linearly constrained binary quadratic programming problems

Shenshen Gu, Rui Cui, Peng Jiao

Neurocomputing•Mar 9, 2016•5 citations

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 Y

Journal of Combinatorial Optimization•Mar 1, 1998•79 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.