This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Conforti, M. Articles by Zambelli, G. Search for Related Content

Minimally Infeasible Set-Partitioning Problems with Balanced Constraints

Dipartimento di Matematica Pura ed Applicata, Università di Padova, Via Trieste 63, 35121 Padova, Italy
Dipartimento di Matematica Pura ed Applicata, Università di Padova, Via Trieste 63, 35121 Padova, Italy
Dipartimento di Matematica Pura ed Applicata, Università di Padova, Via Trieste 63, 35121 Padova, Italy
conforti{at}math.unipd.it
mdsumma{at}math.unipd.it
giacomo{at}math.unipd.it

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.

Key Words: set partitioning; infeasible systems of linear inequalities; balanced matrices
History: Received: March 23, 2005; revision received: February 16, 2006;