Testing cut generators for mixed-integer linear programming

被引：12
|
作者：
Margot F. [1 ]
机构：
[1] Tepper School of Business, Carnegie Mellon University, Pittsburgh
来源：
Mathematical Programming Computation | 2009年 / 1卷 / 01期
关键词：
90C11 Mixed-integer programming; 90C57 Polyhedral combinatorics; branch-and-bound; branch-and-cut;
D O I：
10.1007/s12532-009-0003-7
中图分类号：
学科分类号：
摘要：
In this paper, a methodology for testing the accuracy and strength of cut generators for mixed-integer linear programming is presented. The procedure amounts to random diving towards a feasible solution, recording several kinds of failures. This allows for a ranking of the accuracy of the generators. Then, for generators deemed to have similar accuracy, statistical tests are performed to compare their relative strength. An application on eight Gomory cut generators and six Reduce-and-Split cut generators is given. The problem of constructing benchmark instances for which feasible solutions can be obtained is also addressed. © Springer and Mathematical Programming Society 2009.
引用
收藏
页码：69 / 95
页数：26
相关论文
共 50 条
12345