Optimization Online


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

Juan Pablo Vielma (jvielma***at***isye.gatech.edu)
Shabbir Ahmed (shabbir.ahmed***at***isye.gatech.edu)
George L. Nemhauser (george.nemhauser***at***isye.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
Entry Accepted: 03/01/2007
Entry Last Modified: 07/29/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society