Computational Experience of an Interior-Point Algorithm in a Parallel Branch-and-Cut Framework

Eva K. Lee and John E. Mitchell

December 1996

Abstract:

An interior-point algorithm within a branch-and-bound framework for solving nonlinear mixed integer programs is described. In contrast to solving the relaxation to optimality at each tree node, the relaxation is only solved to near-optimality. Analogous to using advanced bases for warmstart solutions in the case of linear MIP, a ``dynamic'' collection of warmstart vectors is kept. Computational results on various classes of nonlinear mixed integer programs are presented.

Lee, School of Industrial and Systems Engineering, Georgia Institute of Technology, GA 30332-0205. Supported in part by NSF/NATO grant GER-9452935, and by NSF grant 9501584. evakylee@columbia.edu

Mitchell, Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, New York. Supported in part by ONR grant N00014-94-1-0391. mitchj@rpi.edu