Cut-Generating Functions for Integer Variables

• 成果类型: Article
• 署名作者: Yildiz, Sercan; Cornuejols, Gerard
• 署名单位: Carnegie Mellon University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2016.0781
• 发表日期: 2016
• 页码: 1381-1403
• 关键词: minimal valid inequalities; PROGRAMS

摘要

For an integer linear program, Gomory's corner relaxation is obtained by ignoring the nonnegativity of the basic variables in a tableau formulation. In this paper, we do not relax these nonnegativity constraints. We generalize a classical result of Gomory and Johnson characterizing minimal cut-generating functions in terms of subadditivity, symmetry, and periodicity. Our result is based on the notion of generalized symmetry condition. We also prove a 2-slope theorem for extreme cut-generating functions in our setting, in the spirit of the 2-slope theorem of Gomory and Johnson.