A Lifted Linear Programming Branch-and-Bound Algorithm for Mixed-Integer Conic Quadratic Programs

This paper develops a linear–programming–based branch–and–bound algorithm for mixed–integer conic quadratic programs. The algorithm is based on a known higher–dimensional or lifted polyhedral relaxation of conic quadratic constraints. The algorithm is different from other linear–programming–based branch–and–bound algorithms for mixed–integer nonlinear programs in that it is not based on cuts from gradient inequalities and it sometimes branches on integer feasible solutions. The algorithm is tested on a series of portfolio optimization problems. It is shown that it significantly outperforms commercial and open–source solvers based on both linear and nonlinear relaxations.