Purdue University Graduate School
HyunJuOhDissertation.pdf (760.07 kB)


Download (760.07 kB)
posted on 2022-12-09, 03:46 authored by Hyun-Ju OhHyun-Ju Oh

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.


NSF CMMI #1727989, Krannert doctoral funds


Degree Type

  • Doctor of Philosophy


  • Management

Campus location

  • West Lafayette

Advisor/Supervisor/Committee Chair

Mohit Tawarmalani

Additional Committee Member 2

Yanjun Li

Additional Committee Member 3

Thanh Nguyen

Additional Committee Member 4

Philip Thompson

Usage metrics



    Ref. manager