Computational experience with an interior point cutting plane algorithm

被引：32

作者：

Mitchell, JE ^{[1
]}

机构：

[1] Rensselaer Polytech Inst, Dept Math Sci, Troy, NY 12180 USA

来源：

SIAM JOURNAL ON OPTIMIZATION | 2000年 / 10卷 / 04期

关键词：

interior point methods; integer programming; cutting planes; linear ordering; Ising spin glasses; max cut;

D O I：

10.1137/S1052623497324242

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

There has been a great deal of success in the last 20 years with the use of cutting plane algorithms to solve specialized integer programming problems. Generally, these algorithms work by solving a sequence of linear programming relaxations of the integer programming problem, and they use the simplex algorithm to solve the relaxations. In this paper, we describe experiments using a predictor-corrector interior point method to solve the relaxations. For some problems, the interior point cod requires considerably less time than a simplex based cutting plane algorithm.

引用

页码：1212 / 1227

页数：16