An algorithm for the separation of two-row cuts

• 成果类型: Article
• 署名作者: Louveaux, Quentin; Poirrier, Laurent
• 署名单位: University of Liege
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0597-9
• 发表日期: 2014
• 页码: 111-146
• 关键词: minimal-inequalities; simplex tableau; integer; rows

摘要

We consider the question of finding deep cuts from a model with two rows of the type . To do that, we show how to reduce the complexity of setting up the polar of from a quadratic number of integer hull computations to a linear number of integer hull computations. Furthermore, we present an algorithm that avoids computing all integer hulls. A polynomial running time is not guaranteed but computational results show that the algorithm runs quickly in practice.