Enumerative inequalities in integer programming

For a linear integer programming problem, thelocal information contained at an optimal solution of the continuous linear programming extension stems from the theory of L.P. solutions. This paper proposes the use ofenvironmental information (of a global nature but pertaining to the discrete vicinity of), in order to isolate the set of integer solutions which may be considered as true candidates for the optimum. The concept ofenumerative 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 anyvalid cut.This paper was presented at the 7th Mathematical Programming Symposium 1970, The Hague, The Netherlands.