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, Cornuéjols, Kapoor, and Vušković 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.