Tightening piecewise McCormick relaxations for bilinear problems
We address nonconvex bilinear problems where the main objective is the computation of a tight lowerbound for the objective function to be minimized. This can be obtained through a mixed-integer linearprogramming formulation relying on the concept of piecewise McCormick relaxation. It works by dividi...
| Autor principal: | |
|---|---|
| Formato: | article |
| Idioma: | eng |
| Publicado em: |
2016
|
| Assuntos: | |
| Texto completo: | http://hdl.handle.net/10400.9/2947 |
| País: | Portugal |
| Oai: | oai:repositorio.lneg.pt:10400.9/2947 |
| Resumo: | We address nonconvex bilinear problems where the main objective is the computation of a tight lowerbound for the objective function to be minimized. This can be obtained through a mixed-integer linearprogramming formulation relying on the concept of piecewise McCormick relaxation. It works by dividingthe domain of one of the variables in each bilinear term into a given number of partitions, while consid-ering global bounds for the other. We now propose using partition-dependent bounds for the latter so asto further improve the quality of the relaxation. While it involves solving hundreds or even thousands oflinear bound contracting problems in a pre-processing step, the benefit from having a tighter formula-tion more than compensates the additional computational time. Results for a set of water network designproblems show that the new algorithm can lead to orders of magnitude reduction in the optimality gapcompared to commercial solvers. |
|---|