Minimally infeasible set-partitioning problems with balanced constraints
成果类型：
Article
署名作者：
Conforti, Michele; Di Summa, Marco; Zambelli, Giacomo
署名单位：
University of Padua
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.1070.0250
发表日期：
2007
页码：
497-507
关键词：
摘要：
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 vertical bar 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.
来源URL：