LOT-SIZING POLYHEDRA WITH A CARDINALITY CONSTRAINT

Given a family of mixed 0-1 polyhedra, we suppose that the convex hull of solutions is known. Now we add a cardinality constraint such that the sum of the 0-1 variables is exactly k. When is the resulting polyhedron integral, or when does the resulting linear program have an integral optimal solution for all values of k? Various equivalent conditions are given, and it is shown that uncapacitated lot-sizing polyhedra have this property when the production costs are nonincreasing over time.