Artigo Acesso aberto Revisado por pares

Tightening piecewise McCormick relaxations for bilinear problems

2014; Elsevier BV; Volume: 72; Linguagem: Inglês

10.1016/j.compchemeng.2014.03.025

ISSN

1873-4375

Autores

Pedro M. Castro,

Tópico(s)

Advanced Optimization Algorithms Research

Resumo

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.

Referência(s)