A roof linearization algorithm to obtain a tight upper bound for integer nonseparable quadratic programming

We study in this paper a general case of integer quadratic multi-knapsack problem (QMKP) where the objective function is non separable. An upper bound is proposed for (QMKP) which is computed via two steps. We first rewrite (QMKP) into an equivalent separable mixed integer quadratic program (QPx,y), using Gauss decomposition of the quadratic terms matrix. We then suggest an original technique, we call roof linearization, to linearize (QPx,y) so as to obtain a mixed integer linear program which optimal value provides an upper bound for both (QPx,y) and (QMKP). Preliminary computational experiments are conducted so as to assess that the proposed algorithm provides a tight upper bound in fast CPU times.