Enumerative inequalities in integer programming

作     者：Burdet, Claude-Alain 

作者机构：Carnegie-Mellon University Pittsburgh Pennsylvinia United States 

出 版 物：《Mathematical Programming》 (Math. Program.)

年 卷 期：1972年第2卷第1期

页      面：32-64页

学科分类：07[理学] 070104[理学-应用数学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

摘      要：For a linear integer programming problem, the local information contained at an optimal solution {Mathematical expression} of the continuous linear programming extension stems from the theory of L.P. solutions. This paper proposes the use of environmental information (of a global nature but pertaining to the discrete vicinity of {Mathematical expression}), in order to isolate the set of integer solutions which may be considered as true candidates for the optimum. The concept of enumerative inequalities is introduced and it is shown how it can be obtained in the context of the convex outer-domain theory of Balas, Young, et al. Generally speaking, enumerative inequalities can be made arbitrarily strong (deep), but at the cost of an increasing amount of work (i.e. enumeration) for their construction. In particular cases, however, very little global information can produce enumerative inequalities stronger than any valid cut. © 1972 North-Holland Publishing Company.