A Lifted Linear Programming Branch-and-Bound Algorithm for Mixed Integer Conic Quadratic Programs
Juan Pablo Vielma (jvielmaisye.gatech.edu)
Abstract: This paper develops a linear programming based branch-and-bound algorithm for mixed integer conic quadratic programs. The algorithm is based on a higher dimensional or lifted polyhedral relaxation of conic quadratic constraints introduced by Ben-Tal and Nemirovski. 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.
Keywords: nonlinear integer programming; branch and bound; portfolio optimization
Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )
Citation: INFORMS Journal on Computing 20, 438--450, 2008.
Entry Submitted: 02/28/2007
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|