« search calendars« CRM/DIMACS Workshop on Mixed-Integer Nonlinear Programming

« Linearization Based Bounds for Binary Quadratic Problems

Linearization Based Bounds for Binary Quadratic Problems

October 09, 2019, 9:00 AM - 10:00 AM


Auditorium (Amphitheatre Banque Nationale)

HEC Montreal

Cote-Sainte-Catherine Building

Click here for map.

Renata Sotirov, Tilburg University

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.