An improved linearization strategy for zero-one quadratic programming problems

Hanif D. Sherali, J. Cole Smith

Research output: Contribution to journalArticlepeer-review

35 Scopus citations

Abstract

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
Volume1
Issue number1
DOIs
StatePublished - Dec 1 2007
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Control and Optimization

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

Cite this