This project was part of Asteroide's thesis, done in collaboration with his academic adviser, Prof. Santanu S. Dey.
Bipartite bilinear programs (BBPs) are especial cases of Quadratically Constrainted Quadratic Programs (QCQPs). Specifically, a BBP is a optimization problem where the variables can be partitioned into two sets such that fixing the variables in any one of the sets results in a linear program (LP). Nevertheless, any QCQP can be converted into a BBP instance with the introduction of new variables.
Asteroide has implemented several cutting planes algorithms using intersections cuts and valid inequalities derived from the Boolean quadratic polytope. These techniques were not effective for the set of instances he was working on, which lead him and coauthors to develop a methodology to compute the exact convex hull of a bipartite bilinear constraint via decomposition. Later, this methodology lead them to design a specialized branch-and-bound algorithm to solve sparse BBP instances. The proposed algorithm was implemented and tested on ten instances of a new application from Civil Engineering and reduced the average duality gap from 68.43% (commercial solver BARON) to 12.9%.
They are now looking for new applications and improving the algorithm to solve non-sparse instances as well.