Concavity cuts for disjoint bilinear programming |
| |
| Authors: | Stéphane Alarie Charles Audet Brigitte Jaumard Gilles Savard |
| |
| Affiliation: | (1) école Polytechnique de Montréal, GRPR and Département de génie électrique et génie informatique, C.P. 6079, Succursale Centre-Ville, Montréal (Québec), H3C 3A7, Canada email: alaries@ai.polymtl.ca, CA;(2) école Polytechnique de Montréal, GERAD and Département de mathématiques et de génie industriel, C.P. 6079, Succursale Centre-Ville, Montréal (Québec), H3C 3A7, Canada email: {charlesa,gilles}@crt.umontreal.ca, CA;(3) école Polytechnique de Montréal, GERAD and Département de génie électrique et génie informatique, C.P. 6079, Succursale Centre-Ville, Montréal (Québec), H3C 3A7, Canada email: brigitt@crt.umontreal.ca, CA |
| |
| Abstract: | We pursue the study of concavity cuts for the disjoint bilinear programming problem. This optimization problem has two equivalent symmetric linear maxmin reformulations, leading to two sets of concavity cuts. We first examine the depth of these cuts by considering the assumptions on the boundedness of the feasible regions of both maxmin and bilinear formulations. We next propose a branch and bound algorithm which make use of concavity cuts. We also present a procedure that eliminates degenerate solutions. Extensive computational experiences are reported. Sparse problems with up to 500 variables in each disjoint sets and 100 constraints, and dense problems with up to 60 variables again in each sets and 60 constraints are solved in reasonable computing times. Received: October 1999 / Accepted: January 2001?Published online March 22, 2001 |
| |
| Keywords: | : concavity cuts disjoint bilinear programming linear maxmin programming branch and bound algorithm global optimization |
| 本文献已被 SpringerLink 等数据库收录！ |
|
