CRPC-TR99788-S						September 1999

Title: Concavity Cuts for Disjoint Bilinear Programming

Authors: Stephane Alarie, Charles Audet, Brigitte Jaumard, and Gilles
Savard

Submitted September 1999

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.

------------------------------------------------------------------------------
Stephanie Alarie (alaries@ai.polymtl.ca)
Department of Electrical Engineering and Computer Science
Ecole Polytechnique de Montreal

Charles Audet (charlesa@camm.rice.edu)
Department of Computational and Applied Mathematics
Rice University

Brigitte Jaumard (brigitt@crt.umontreal.ca)
Gilles Savard (gilles@crt.umontreal.ca)
Department of Mathematics and Industrial Engineering
Ecole Polytechnique de Montreal