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 language | English |
---|---|
Pages (from-to) | 229-249 |
Journal | Annals of Operations Research |
Volume | 307 |
Issue number | 1-2 |
DOIs | |
Publication status | Published - Dec 2021 |
Keywords
- Binary quadratic program
- Generalized Gilmore–Lawler bound
- Linearization problem
- Quadratic assignment problem
- Quadratic shortest path problem