Linear Reformulations of Integer Quadratic Programs

Let (QP) be an integer quadratic program that consists in minimizing a quadratic function subject to linear constraints. In this paper, we present several linearizations of (QP). Many linearization methods for the quadratic 0-1 programs are known. A natural approach when considering (QP) is to reformulate it into a quadratic 0-1 program. However, this method, that we denote BBL (Binary Binary Linearization), leads to a quadratic program with a large number of variables and constraints. Our new approach, BIL (Binary Integer Linearization), consists in reformulating (QP) into a particular quadratic integer program where each quadratic term is the product of an integer variable by a 0-1 variable. The obtained integer linear program is significantly smaller than in the BBL approach. Each reformulation leads to an integer linear program that we improve by adding valid inequalities. Finally, we get 4 different programs that we compare from the computational point of view.