Aggregation and mixed integer rounding to solve mips
成果类型：
Article
署名作者：
Marchand, H; Wolsey, LA
署名单位：
University of London; London School Economics & Political Science; Universite Catholique Louvain
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.49.3.363.11211
发表日期：
2001
页码：
363-371
关键词：
摘要：
In this paper, we discuss the use of mixed integer rounding (MIR) inequalities to solve mixed integer programs. MIR inequalities are essentially Gomory mixed integer cuts. However, as we wish to use problem structure, we insist that MIR inequalities be generated from constraints or simple aggregations of constraints of the original problem. This idea is motivated by the observation that several strong valid inequalities based on specific problem structure can be derived as MIR inequalities. Here we present and test a separation routine for such MIR inequalities that includes a heuristic row aggregation procedure to generate a single knapsack plus continuous variables constraint, complementation of variables, and finally the generation of an MIR inequality. Inserted in a branch-and-cut system, the results suggest that such a routine is a useful additional tool for tackling a variety of mixed integer programming problems.