scientific article; zbMATH DE number 1302172

From MaRDI portal
Publication:4247439





One of the major breakthroughs of the last decades in solving large scale linear optimization problems is the interior point algorithm initiated by N. Karmarkar (published in 1984). The present paper gives an overview on how to apply this algorithm to the solution of combinatorial optimization (CO) problems. After introducing the basic principle for linear programs -- in particular in the context of network flows -- the authors describe its use in branch and bound (branch and cut) approaches. As prominent examples the quadratic assignment problem, the linear ordering problem, and the spin glass problem are covered in some depth. The paper is concluded by working out the interrelation between interior point methods and nonlinear optimization approaches to solve CO like semidefinite optimization and nonconvex potential functions. For the entire collection see [Zbl 0903.90001].











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4247439)