The Bipartite Boolean Quadratic Programming Problem

We consider the Bipartite Boolean Quadratic Programming Problem (BQP01), which generalizes the well-known Boolean Quadratic Programming Problem (QP01). The model has applications in graph theory, matrix factorization and bioinformatics, among others. BQP01 is NP-hard. The primary focus of this thesis is on studying algorithms and polyhedral structure from a linearization of its integer programming formulation. We show that when the rank of the associated m x n cost matrix Q is fixed, BQP01 can be solved in polynomial time. Further, for the rank one case, we provide an O(n log n) algorithm. The complexity reduces to O(n) with additional assumptions. Further, we observe that BQP01 is polynomially solvable if m = O(log n). Similarly, when the minimum negative eliminator of Q is O(log n), the problem is shown to be polynomially solvable. We then develop several heuristic algorithms for BQP01 and analyze them using domination analysis. First, we give a closed-form formula for the average objective function value A(Q, c, d) of all solutions. Computing the median objective function value however is shown to be NP-hard. We prove that any solution with objective function value no worse than A(Q, c, d) dominates at least 2^(m+n-2) solutions and provide an upper bound for the dominance ratio of any polynomial time approximation algorithms for BQP01. Further, we show that some powerful local search algorithms could produce solutions with objective function value worse than A(Q, c, d) and propose algorithms that guarantee a solution with objective function value no worse than A(Q, c, d). Finally, we study the structure of the polytope BQP^(m;n) resulting from linearization of BQP01. We develop various approaches to obtain families of valid inequalities and facet-defining inequalities of BQP^(m,n) from those of other related polytopes. These approaches include rounding coeffcients, using the linear transformation between BQP^(m,n) and the corresponding cut polytope, and applying triangular elimination.