USING SEPARATION ALGORITHMS TO GENERATE MIXED INTEGER MODEL REFORMULATIONS

被引：108

作者：

MARTIN, RK

机构：

[1] Graduate School of Business, University of Chicago, Chicago, IL 60637

来源：

OPERATIONS RESEARCH LETTERS | 1991年 / 10卷 / 03期

关键词：

INTEGER PROGRAMMING MODELS; CUTTING PLANE ALGORITHMS; MODEL REFORMULATION;

D O I：

10.1016/0167-6377(91)90028-N

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The linear relaxation of mixed integer programming models can be strengthened by introducing auxiliary variables. We develop a new method for generating auxiliary variable reformulations for problems where the separation algorithm for finding violated cuts can be formulated as a linear program. Our results have important consequences for integrality proofs and efficient formulations.

引用

页码：119 / 128

页数：10

共 26 条

[1] DISJUNCTIVE PROGRAMMING AND A HIERARCHY OF RELAXATIONS FOR DISCRETE OPTIMIZATION PROBLEMS [J].