Interior Point Methods for Combinatorial Optimization
Download the paper,
postscript or pdf.
Author:
John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj@rpi.edu
A survey paper which appeared as Chapter 11
in
"Interior
Point Methods in Mathematical Programming", edited by
Tamas Terlaky,
published by Kluwer Academic Publishers,
1996.
Abstract:
Research on using interior point algorithms to solve
combinatorial optimization and integer programming problems is surveyed.
This paper discusses
branch and cut methods for integer programming problems,
a potential reduction method based on transforming an integer programming
problem to an equivalent nonconvex quadratic programming problem,
interior point methods for solving network flow problems,
and methods for solving multicommodity flow problems, including an
interior point column generation algorithm.
Download the paper,
postscript or pdf.
Return to my list of papers.