Interior Point Methods for Combinatorial Optimization

J. E. Mitchell, P. M. Pardalos, and M. G. C. Resende

Handbook of Combinatorial Optimization, D.-Z. Du and P.M. Pardalos, eds., Kluwer Academic Publishers, vol. 1, pp. 189-298, 1998


In this paper, we review recent interior point approaches for solving combinatorial optimization problems. We discuss in detail techniques for linear and network programming, branch and bound and branch and cut methods, nonconvex potential function minimization, lower bounding techniques, and semidefinite programming relaxations.

PostScript file of full paper

PDF file of full paper

Mauricio G.C. Resende's Home Page

Last modified: 28 June 2002

Copyright Notice