The linearization problem of a binary quadratic problem and its applications

Research output: Contribution to journalArticleScientificpeer-review

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
JournalAnnals of Operations Research
Publication statusAccepted/In press - 2021

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