Tightening methods based on nontrivial bounds on bilinear terms

We develop tightening and solution methods for optimization problems containing bilinear terms. We focus on the bilinear term w= xy with nonnegative variables x∈ [x^L, x^U] and y∈ [y^L, y^U] , where w is semi-continuous and upper and lower bounded by w^U and w^L when positive. w^U and w^L are said to be nontrivial upper and lower bounds if w^U is smaller than x^Uy^U and w^L is greater than x^Ly^L, respectively. We derive a family of valid linear constraints and show that, when one of the nontrivial bounds is active, such constraints are tangent to one branch of the hyperbola that represents the bilinear term. We propose different preprocessing methods for generating strong constraints from the family. Computational results demonstrate the effectiveness of the proposed methods in terms of reducing optimality gap and computational time.