An improved linearization strategy for zero-one quadratic programming problems

Hanif D. Sherali, J. Cole Smith

Research output: Contribution to journalArticlepeer-review

43 Scopus citations


We present a new linearized model for the zero-one quadratic programming problem, whose size is linear in terms of the number of variables in the original nonlinear problem. Our derivation yields three alternative reformulations, each varying in model size and tightness. We show that our models are at least as tight as the one recently proposed in [7], and examine the theoretical relationship of our models to a standard linearization of the zero-one quadratic programming problem. Finally, we demonstrate the efficacy of solving each of these models on a set of randomly generated test instances.

Original languageEnglish (US)
Pages (from-to)33-47
Number of pages15
JournalOptimization Letters
Issue number1
StatePublished - 2007
Externally publishedYes


  • Bilinear programming
  • Integer programming
  • Linearization
  • Quadratic programming
  • Reformulation-linearization technique (RLT)

ASJC Scopus subject areas

  • Control and Optimization
  • Business, Management and Accounting (miscellaneous)


Dive into the research topics of 'An improved linearization strategy for zero-one quadratic programming problems'. Together they form a unique fingerprint.

Cite this