The linearization problem of a binary quadratic problem and its applications

Research output: Contribution to journalArticleScientificpeer-review

9 Citations (Scopus)

Abstract

We provide several applications of the linearization problem of a binary quadratic problem. We propose a new lower bounding strategy, called the linearization-based scheme, that is based on a simple certificate for a quadratic function to be non-negative on the feasible set. Each linearization-based bound requires a set of linearizable matrices as an input. We prove that the Generalized Gilmore-Lawler bounding scheme for binary quadratic problems provides linearization-based bounds. Moreover, we show that the bound obtained from the first level reformulation linearization technique is also a type of linearization-based bound, which enables us to provide a comparison among mentioned bounds. However, the strongest linearization-based bound is the one that uses the full characterization of the set of linearizable matrices. Finally, we present a polynomial-time algorithm for the linearization problem of the quadratic shortest path problem on directed acyclic graphs. Our algorithm gives a complete characterization of the set of linearizable matrices for the quadratic shortest path problem.
Original languageEnglish
Pages (from-to)229-249
JournalAnnals of Operations Research
Volume307
Issue number1-2
DOIs
Publication statusPublished - Dec 2021

Keywords

  • Binary quadratic program
  • Generalized Gilmore–Lawler bound
  • Linearization problem
  • Quadratic assignment problem
  • Quadratic shortest path problem

Fingerprint

Dive into the research topics of 'The linearization problem of a binary quadratic problem and its applications'. Together they form a unique fingerprint.

Cite this