HyunJuOhDissertation.pdf

In this thesis, we devise a new finite branch-and-bound algorithm for disjoint bilinear programs. In these problems, there are two vectors of variables, $\b{x}$ and $\b{y}$, and two polytopes $P_{\b{x}}$ and $P_{\b{y}}$ such that $\b{x}$ (resp. $\b{y}$) is chosen from $P_{\b{x}}$ (resp. $P_{\b{y}}$) so that a bilinear objective function is minimized. By a bilinear objective, we mean that the objective becomes linear when either one of $\b{x}$ or $\b{y}$ is fixed. 

  This branch-and-bound scheme uses a relaxation that is derived using the reformulation-linearization technique (RLT). The RLT relaxation is constructed by taking products of constraints and linearizing the bilinear terms using introduced variables. The quality of this relaxation improves as higher order products and the corresponding monomial terms are linearized. Although it is known that, as RLT relaxations are constructed with increasingly higher order linearizations, the relaxation eventually converges to the true optimal value. However, no finite convergence properties are known. In contrast, we show that the first level of the RLT hierarchy suffices to convexify the problem when one of the polytopes is a simplex. Then, using this insight we devise a new class of relaxations by combining RLT with a variant of the double description procedure, where the latter lifts a polytope into a simplex in a finite number of steps.  This leads us to a finite hierarchy of relaxations that converges to the optimal value. Although this hierarchy is finite, from a computational perspective, we find that the relaxations grow rapidly in size. However, we utilize the insight to derive a simplicial branch-and-bound scheme, that expresses each polytope as a union of simplices allowing us to converge finitely to the optimal solution for the problem. We perform preliminary numerical experiments to show that this approach holds promise and competes favorably with state-of-the-art methods on larger instances.