Tightening piecewise McCormick relaxations for bilinear problems

We address nonconvex bilinear problems where the main objective is the computation of a tight lower bound for the objective function to be minimized. This can be obtained through a mixed-integer linear programming formulation relying on the concept of piecewise McCormick relaxation. It works by dividing the domain of one of the variables in each bilinear term into a given number of partitions, while considering global bounds for the other. We now propose using partition-dependent bounds for the latter so as to further improve the quality of the relaxation. While it involves solving hundreds or even thousands of linear bound contracting problems in a pre-processing step, the benefit from having a tighter formulation more than compensates the additional computational time. Results for a set of water network design problems show that the new algorithm can lead to orders of magnitude reduction in the optimality gap compared to commercial solvers. (C) 2014 Elsevier Ltd. All rights reserved.