|
Article Excerpt
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 [greater than or equal to] 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
1. Introduction. Determining if a system Ax = 1 has a 0, 1 solution, where A is a 0, 1 matrix (i.e., finding a feasible solution for the set-partitioning problem) is NP-complete in general. When the matrix A is balanced, however, the problem can be formulated as a linear program (Berge [2]), and is therefore polynomial. Furthermore, under the assumption that A is balanced, if the set-partitioning problem is infeasible, this fact can be shown by a simple combinatorial certificate (Conforti et al. [4]), which is an extension of Hall's condition for the existence of a perfect matching in a bipartite graph. It is therefore natural to look for a combinatorial algorithm that either finds a solution to a given set-partitioning problem with balanced constraints, or the certificate of infeasibility for such a problem. Finding such an algorithm, however, seems to be difficult.
To achieve a better understanding of those balanced matrices for which the set-partitioning problem is infeasible, we characterize the matrices that are minimal with such property, meaning that they do not admit a solution to the set-partitioning problem, while all proper row-submatrices do (we call such matrices minimally nonpartitionable).
Because, in the balanced case, finding a solution to the set-partitioning problem is equivalent to finding a basic solution to a linear program, we start by looking at general systems of linear constraints that are infeasible. If a system of linear constraints has no feasible solution, obviously there exists a subset of constraints that is still infeasible and is minimal with such property. More generally, in [section] 2 we study systems of linear constraints that are not feasible but that admit a solution whenever we remove a constraint from a specified subset S of the rows (we call such systems minimally infeasible with respect to S).
In [section]3, we apply results from the previous section and a theorem of Conforti et al. [4] to obtain combinatorial properties of minimally nonpartitionable balanced matrices. We also show that these matrices essentially characterize all systems of constraints of the form Ax ~ 1, x [greater than or equal to] (where Ax ~ 1 denotes a system of equations and inequalities with constraint matrix A and right-hand side 1) that are minimally infeasible with respect to the rows of A, when A is balanced.
2. Infeasible systems of linear inequalities. We study linear systems of equations and inequalities that are infeasible.
Given an integer n, we denote by [n] the set {1, ..., n}. Given an m x n matrix A with entries [a.sub.ij], i [member of] [m], j [member of] [n], we will denote by [a.sup.i] the ith row of A, and by [a.sub.j] the jth column of A. Also, for any i [member of] [m] we will denote with [A.sup.i] the (m - 1) x n submatrix of A obtained by removing the ith row. Given a subset S of [m], we will denote [bar.S] = [m]\S, and by [A.sub.s] the row-submatrix of A induced by the rows in S. Given a matrix A and a vector b, we denote by Ax ~ b a system
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
for some partition [S.sub.1], [S.sub.2], [S.sub.3] of the rows of A.
Given a system Ax ~ b, if [bar.A] is a submatrix of A and [bar.b] is the restriction of b to the rows of [bar.A], we denote by [bar.A] ~ [bar.b] a system where the direction of the inequalities is consistent with the direction in Ax ~ b.
Given a system Ax ~ b and a subset S of the rows of A, we say that Ax ~ b is minimally infeasible with respect to S if Ax ~ b has no solution, but [A.sup.i] x ~ [b.sup.i] is feasible for every row index i [member of] S; a solution of such system is a mate of row [a.sup.i]. When S = [m], we say that the system is minimally infeasible.
An orientation of Ax ~ b with respect to S is obtained from Ax ~ b by substituting every equation [a.sup.i] x = [b.sub.i], i [member of] S, with either [a.sup.i] x [b.sub.i].
A restriction with respect to S of Ax ~ b is a system obtained from Ax ~ b by substituting some of the inequalities [a.sup.i] x [less than or equal to] [b.sub.i] or [a.sub.i]x > [b.sub.i], i [member of] S, with [a.sup.i] x = [b.sub.i].
THEOREM 2.1. Let Ax ~ b be a minimally infeasible system with respect to S.
(i) Every restriction w.r.t. S of Ax ~ b is also minimally infeasible w.r.t. S.
(ii) Ax ~ b admits a unique orientation w.r.t. S, say Ax [??] b, that is infeasible. Furthermore, Ax [??] b is minimally infeasible w.r.t. S.
(iii) rk([A.sub.s]) [greater than or equal to] [absolute value of S] - 1. In particular, rk([A.sub.s]) = [absolute value of S] - 1 if and only if [A.sub.s] x ~ [b.sub.s] is minimally infeasible, while rk([A.sub.s]) = [absolute value of S] if and only if [A.sub.s] x ~ [b.sub.s] is feasible.
PROOF. (i) Let R [subset or equal to] S be the set of constraints that are set to equality. The proof is by induction on [absolute value of R], the case [absolute value of R] = being trivial. We only need to show that, for any h [member of] R, the system [A.sub.h]x ~ [b.sub.h], [a.sub.h]x = [b.sub.h], denoted by Ax ~ b, is minimally infeasible w.r.t. S, since we can then apply induction to Ax ~' b and R\{h}. Consider the case where the hth constraint in Ax ~ b is of the form [a.sub.h]x < [b.sub.h] (the case [a.sub.h] x = [b.sub.h] is trivial, while the case [a.sub.h] x [greater than or equal to] [b.sub.h] is analogous).
Because Ax ~ b is infeasible, Ax ~' b is also infeasible. Thus we need only to show that [A.sub.i]x ~' [b.sub.i] has a solution for every i [member of] S. Let [x.sub.i] and [x.sub.h] be solutions to [A.sub.i] x ~ [b.sub.i] and [A.sub.h] x [b.sub.h], respectively. Clearly, [x.sub.h] is a solution for [A.sub.h] x ~ [b.sub.h] and [a.sub.h] [x.sub.h] > [b.sub.h], and if [a.sub.h] [x.sub.i] = [b.sub.h], then [x.sub.i] is a solution for [A.sup.i] x ~ [b.sup.i]. Thus we may assume i [not equal to] h and [a.sub.h] [x.sup.i] - [b.sub.h] and [beta] = [b.sub.h] - [a.sup.h] [x.sup.i] > 0, the vector y = ([alpha] / ([alpha] + [beta])) [x.sup.i] + ([beta]/([alpha] + [beta])) [x.sup.h] is a solution to [A.sup.i] x ~' [b.sup.i].
(ii) Let 1 [subset or equal to] be the set of constraints of Ax ~ b with index in S that are of the form [a.sup.i] x = [b.sub.i], i [member of] I. For every i [member of] 1, let [x.sup.i] be a mate of [a.sup.i]. Clearly, for every i [member of] I, [a.sup.i] [x.sup.i]...
|
