Generalized Chvatal-Gomory closures for integer programs with bounds on variables

• 成果类型: Article
• 署名作者: Dash, Sanjeeb; Gunluk, Oktay; Lee, Dabeen
• 署名单位: International Business Machines (IBM); IBM USA; Cornell University; Institute for Basic Science - Korea (IBS)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01539-5
• 发表日期: 2021
• 页码: 393-425
• 关键词: elementary closure; formulations

摘要

Integer programming problems that arise in practice often involve decision variables with one or two sided bounds. In this paper, we consider a generalization of Chvatal-Gomory inequalities obtained by strengthening Chvatal-Gomory inequalities using the bounds on the variables. We prove that the closure of a rational polyhedron obtained after applying the generalized Chvatal-Gomory inequalities is also a rational polyhedron. This generalizes a result of Dunkel and Schulz on 0-1 problems to the case when some of the variables have upper or lower bounds or both while the rest of them are unbounded.