Cutting planes for RLT relaxations of mixed 0-1 polynomial programs

• 成果类型: Article
• 署名作者: Fomeni, Franklin Djeumou; Kaparis, Konstantinos; Letchford, Adam N.
• 署名单位: Lancaster University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0863-8
• 发表日期: 2015
• 页码: 639-658
• 关键词: quadratic knapsack-problem; assignment problem; REPRESENTATIONS; optimization; hierarchy; polytope

摘要

The reformulation-linearization technique, due to Sherali and Adams, can be used to construct hierarchies of linear programming relaxations of mixed 0-1 polynomial programs. As one moves up the hierarchy, the relaxations grow stronger, but the number of variables increases exponentially. We present a procedure that generates cutting planes at any given level of the hierarchy, by optimally weakening linear inequalities that are valid at any given higher level. Computational experiments, conducted on instances of the quadratic knapsack problem, indicate that the cutting planes can close a significant proportion of the integrality gap.