The linearization problem of a binary quadratic problem and its applications

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...

Full description

Saved in:
Bibliographic Details
Published in:Annals of operations research 2021-12, Vol.307 (1-2), p.229-249
Main Authors: Hu, Hao, Sotirov, Renata
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Assignment problem
Business and Management
Combinatorics
Graph theory
Graphs
Linear programming
Linearization
Mathematical optimization
Matrices
Operations research
Operations Research/Decision Theory
Optimization
Original Research
Polynomials
Quadratic equations
Quadratic functions
Shortest-path problems
Theory of Computation
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. We also 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.
ISSN:0254-5330
1572-9338
DOI:10.1007/s10479-021-04310-x