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

Eva K. Lee and John E. Mitchell

An interior-point algorithm within a parallel branch-and-bound framework for solving nonlinear mixed integer programs is described. The nonlinear programming relaxations at each node are solved using an interior point SQP method. In contrast to solving the relaxation to optimality at each tree node, the relaxation is only solved to near-optimality. Analogous to employing advanced bases in simplex-based linear MIP solvers, a ``dynamic'' collection of warmstart vectors is kept to provide ``advanced warmstarts'' at each branch-and-bound node. The code has the capability to run in both shared-memory and distributed-memory parallel environments. Preliminary computational results on various classes of linear mixed integer programs and quadratic portfolio problems are presented.

Technical Report LEC 97-08, Industrial and Systems Engineering, Georgia Institute of Technology.