Concavity cuts for disjoint bilinear programming

Citation
S. Alarie et al., Concavity cuts for disjoint bilinear programming, MATH PROGR, 90(2), 2001, pp. 373-398
Citations number
15
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
0025-5610 → ACNP
Volume
90
Issue
2
Year of publication
2001
Pages
373 - 398
Database
ISI
SICI code
0025-5610(200104)90:2<373:CCFDBP>2.0.ZU;2-M
Abstract
We pursue the study of concavity cuts for the disjoint bilinear programming problem. This optimization problem has two equivalent symmetric linens max min 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 p ropose a branch and bound algorithm which make use of concavity cuts. We al so present a procedure that eliminates degenerate solutions. Extensive comp utational experiences are reported. Sparse problems with up to 500 variable s 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.