Resource title

Minimally infeasible set-partitioning problems with balanced constraints

Resource image

image for OpenScout resource :: Minimally infeasible set-partitioning problems with balanced constraints

Resource description

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 Vukovi 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.

Resource author

Resource publisher

Resource publish date

Resource language

en

Resource content type

Resource resource URL

http://eprints.lse.ac.uk/31698/

Resource license