scientific article; zbMATH DE number 1302172
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].
- Penalty parameter for linearly constrained 0--1 quadratic programming
- A new penalty parameter for linearly constrained 0--1 quadratic programming problems
- Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
- Descent direction algorithm with multicommodity flow problem for signal optimization and traffic assignment jointly
- A constraint generation algorithm for large scale linear programs using multiple-points separation
- scientific article; zbMATH DE number 1047684 (Why is no real title available?)
- scientific article; zbMATH DE number 1047685 (Why is no real title available?)
- scientific article; zbMATH DE number 1489805 (Why is no real title available?)
- GMRES-accelerated ADMM for quadratic objectives
- A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP
- scientific article; zbMATH DE number 4197756 (Why is no real title available?)
- Interior point and semidefinite approaches in combinatorial optimization
- An algorithm for nonlinear optimization problems with binary variables
- Fuzzy goal programming: complementary slackness conditions and computational schemes
- A discrete dynamic convexized method for nonlinear integer programming
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)