Minimally infeasible set-partitioning problems with balanced constraints

We study properties of systems of linear constraints that are minimally infeasible with respect to some subset S of constraints. (i.e., systems that are infeasible but that become feasible on removal of any constraint in S). We then apply these results and a theorem of Conforti, Cornuejols, Kapoor, and Vuskovic to a class of 0, 1 matrices, for which the linear relaxation of the set-partitioning polytope LSP(A) = (x : Ax = 1, x >= 0) is integral. In this way, we obtain combinatorial properties of those matrices in the class that are minimal (w.r.t. taking row submatrices) with the property that the set-partitioning polytope associated with them is infeasible.