Renata Sotirov, Tilburg University

Abstract

Linearizable binary quadratic problem (BQP) instances are instances whose optimal solution can be obtained by solving the corresponding linear instance of the problem. In general, BQP instances are not linearizable and for many BQPs we do not have a complete characterization of the set of the linearizable instances. However, it is not difficult to identify a subset of linearizable instances for a given BQP. In this talk we show how to exploit such subset to obtain bounds for the original problem.

In particular, we propose a 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. We also show that several known bounding approaches including the Generalized Gilmore-Lawler scheme and the first level RLT relaxation provide linearization based bounds. Finally, we demonstrate quality of linearization based bounds for the Quadratic Shortest Path problem and the Quadratic Cycle Cover Problem.