Facets of an Assignment Problem with a 0-1 Side Constraint Abdo Y. Alfakih, Katta G. Murty Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109 Tongnyoul Yi Samsung Data Systems, Seoul, S. Korea 120-020 Technical Report 96-22 December 1996

Facets of an Assignment Problem with a 0 - 1 Side Constraint Abdo Y. Alfakih1, Tongnyoul Yi2, and Katta G. Murtyl* 1Department of IOE, University of Michigan Ann Arbor, MI 48109-2117, USA 2Samsung Data Systems, Seoul, S. Korea 120-020. December 19, 1996 Abstract We show that the problem of finding a perfect matching satisfying a single equality constraint with 0-1 coefficients in an n x n incomplete bipartite graph, polynomially reduces to a special case of the same problem called the partitioned case. Finding a solution matching for the partitioned case in the incomplete bipartite graph,.is equivalent to minimizing a partial sum of the variables over Q',2 = the convex hull of incidence vectors of solution matchings for the partitioned case in the complete bipartite graph. An important strategy to solve this minimization problem is to develop a polyhedral characterization of Q 'l2. Towards this effort, we present two large classes of valid inequalities for Q'~2, which are proved to be facet inducing using a facet lifting scheme. Key Words: Constrained assignment problem, integer hull, facet inducing inequalities, facet lifting scheme. * author for correspondence. E-mail: katta-murty(7umich.edu

1 Introduction The well-known assignment problem of order n deals with minimizing a linear objective function involving n2 variables x = (xi: i,j = 1,..., n), usually written in the form of a square matrix of order n, subject to constraints (1)-(4). Associating the variable xzj with the edge (i,j) in the complete bipartite graph Kn,n G = (I, J, I x J), where I = {1,...,n}, J = {1,...,n}, each assignment x = (xij), i.e., feasible solution of (1)(4), is associated with the perfect matching {(i,j): Xij = 1} in G. We will also find it convenient to associate the variable xj and edge (i,j) in G, with the (i,j)th cell in the two dimensional array I x J. With the values of the variables entered in their associated cells in the array, each assignment becomes a permutation matrix. However, in many applications, we need to find an assignment which has a specified value for a given objective function, rather than an assignment that minimizes it; i.e., we need to find a solution x = (xij) to the following system n Zxii= 1 forall i=l1,...,n (1) j=1 x ij=1 forall j=-1,...,n-1 (2) i=l xij > 0 for all i,j = 1,...,n (3) xij C {0,1} for all i,j = 1,..., n (4) n n E cx =r (5) i=1 j=l An example of such an application arises in the core management of pressurized water nuclear reactors [2, 4]. Solving (4)-(5) is NP-hard when cij are general integers [3]. The problem of solving (1)-(5) when all c,, are 0 - 1 has been described in [7] as a mysterious problem. In this special case necessary and sufficient conditions for the existence of a feasible solution to (1)-(5) have been derived in [6, 5], and an 0(n25) algorithm for either finding a feasible solution to (1) -(5) or concluding that it is infeasible is also given in [6]. 1

In the sequel we assume that all cij are 0 or 1, and 0 < r < n, r integer. In this paper we investigate some polyhedral aspects of this special case. System (1)-(5) is defined on the complete bipartite graph G, i.e., all the n2 variables ij are allowed to assume values 0 or 1. This feature is used crucially in the algorithm discussed in [6] for solving (1)-(5). However, in applications, the problem is usually defined on an incomplete bipartite graph; i.e., we are given a subset of edges F called the subset of forbidden edges, or missing edges of G and all the variables x j for (i,j) C F are deleted from system (1)-(5) and we need to solve the remaining system. This is equivalent to imposing a new constraint xij = 0 for all (i,j) C F (6) Whether an efficient algorithm exists for the problem in an incomplete graph, i.e., for solving (1)-(6) remains an open question. Whether it is on the complete graph or incomplete graph, our problem belongs to a special case called the partitioned case if there exist partitions I = I1 U I2, J = J1 U J2 such that i for all(, () C (1 x J) U (12 x J2) cii = 0 for all (i,j) C (I1 x J2) U (I x J1) In this partitioned case, the cells in the two dimensional array I x J are partitioned into 4 blocks: B1 - II x J1, B2 = I, x J2, B3 = 12 x J2, and B4 = I2 x J1. Let ]Ill = i, [J1j = n2. The following facts have been proved in [6, 8] for this partitioned case, in the complete graph. (i) In this case, for any t = 1 to 4, (i,j): Bt n {(p,q): Xpq = 1}1 is the same, say rt, for all solutions x = (xpq) of (1) to (5), and if such a solution exists, then rl = (-n + r + n1 + n2)/2. r2 = (n - r + n - n2)/2, r3 = (n + r - n - n2)/2, r4= (n - r - nl + 12)/2 since r2 = n1 - r1, r4 = n2 - r, and r3 = n - r - r2- r4. (ii) In this case, system (1) to (5) has a solution iff n + r + n1 + n2 is an even number, and all the rl, r2, r3, r4 given in (i) are > 0. Hence all the r for which system (1) 2

to (5) has a solution in this case have the same odd-even parity, and the set of all such r form an arithmetic progression in which consecutive elements differ by 2. Furthermore, in this partitioned case, the following 6 constraints: '(i,j)EB i rt, t = 1 to 4; Z(i)eBiuB3 xij = r; Z(i,j)EB2UB4 ij = n - r; are all equivalent to each other in the sense that any one of them can replace (5) in system (1) to (5), leading to an equivalent system. In particular, consider Xij = r (7) (i,j)EB1 In this case, system (1) to (5); or the equivalent system (1) to (4) and (7), has a solution iff ri is a nonnegative integer and max{0, ni + n2 -n} < r1 < min{n1, 12}. Color the edge (i,j) in G ( and the cell (i,j) in the array I x J) red if cj = 1, blue if Cj = 0. Then any solution to (1)-(5) is the incidence vector of a perfect matching in G with exactly r red edges. Such a perfect matching will be called a solution matching. With this coloring, the complete graph G, or the incomplete graph H = (I, J, E = (I x J)\F) belongs to the partitioned case if there exists partitions I = 1 UI2, J = J UJ2 such that edge (i,j is redge s iff (i,j) (I x J) U (I2 x J2) edge (i,j) is blue iff (i,j) E (I1 x J2) U (1 x J2) Consider the incomplete graph case as defined earlier. The following lemma gives the necessary and sufficient conditions for the incomplete graph H to belong to the partitioned case. Lemma 1 Consider the incomplete colored bipartite graph H = (I, J, E) where E (I x J)\F. H belongs to the partitioned case iff there exists no cycle in H containing an odd number of red edges. Proof. Since H is bipartite, if a cycle in H contains an odd number of red edges, it must also contain an odd number of blue edges and vice versa. If partitions exist as defined earlier, clearly there can be no cycle containing an odd number of red edges in H. 3

Suppose there exist no cycle containing an odd number of red edges. Let HR = (I, J,ER), HB = (I, J,EB) denote the subgraphs of H induced by the red and blue edges respectively but each of them containing all the nodes. Under these assumptions HR cannot be a connected graph, for suppose it is connected. Take any blue edge (i, j). Since HR is connected, there exists a red simple path P say in HR from i to j. Then P U {(i,j)} is a simple cycle containing an odd number, 1, of blue edges, contradicting our assumption. So HR must consist of two or more connected components. Construct an auxiliary graph X = (A', A) by the following rules: 1. Each node in AT represents a connected component in HR. 2. Nodes p and q in Ar are joined by an edge (p, q) E A iff there is at least one blue edge in H connecting one of the nodes in connected component p of HR and another node from connected component q of HR. By the hypothesis, the graph X contains no odd cycles. Hence X is bipartite. Suppose a bipartition for X is A/i, AV2. Now place node i C I in I1 if the component of HR containing node i is in NAi, or in 12 if that component is in A/2. Similarly place node j C J in J1 if the component of HR containing node j is in Aj1, or in J2 if that component is in A2. Then the edges in H in blocks 11 x J1 and I2 x J2 can not be blue, since the two nodes on any edge from these blocks come from the same connected component of HR. On the other hand, the edges in H in blocks I1 x J2 and 12 x J1 can not be red, since the two nodes on any edge from these blocks come from different components in HR. Therefore, partitions I = I1 U 12^ J = J1 U J2 satisfy the conditions given in (8) I. We will show now that the problem of solving (1)-(5) on the incomplete bipartite graph H can be solved in polynomial time iff there exists a polynomial time algorithm for the same type of problem belonging to the partitioned case. Theorem 1 The problem of solving (1)-(5) on the incomplete bipartite graph H polynomially reduces to a problem of the samn type belonging to the partitioned case Proof. We consider two cases: 4

Case 1: Suppose that H has no cycles containing an odd number of red edges. In this case by Lemma 1, our problem itself belongs to the partitioned case. Case 2: H has at least one cycle containing an odd number of red edges. Let HR = (I, J, ER), HB = (I, J, EB) denote the subgraphs of H induced by the red and blue edges respectively. We will now enlarge H into a new bipartite graph H* by adding 21ERI new nodes and 2IERI new edges by the following rule: Replace each edge (i,j) C ER by a path i,(i, uj), uj,(ujj, vj), vj, (vj,j),j; (see Figure 1), where uij, vij are two new nodes corresponding to the original red edge (i,j) in H. On this path color the new edges (i, uj) and (vij,j) red; and color the new edge (uij, vij) blue. Clearly the new graph H* has n* = 2n + 2\ERI nodes and IEBI + 3 ERI = IE I + 2\ERI edges. Also notice that any cycle in H* that contains a new node of the type uij say, must also include the nodes vij,i,j. Also each cycle in the original graph H that contains a red edges and b blue edges becomes a cycle containing 2a red edges and a + b blue edges. Hence all cycles in H* have an even number of red edges so by Lemma 1 the colored graph H* belongs to the partitioned case. By replacing each red edge (i.j) in a perfect matching with r red edges in H by the pair of edges (i, u-), (v-ijj) it becomes a perfect matching with 2r red edges in the new graph H*. Also every perfect matching in H* that contains the red edge (i, ui) must also contain the red edge (vijj), as otherwise the node Vij will remain unmatched. Thus red edges in each perfect matching in H* occur in pairs, each pair belonging to a path of the form in Figure 1. Thus by replacing each pair of red edges in a path of the form in Figure 1 by the edge on the left of Figure 1 in the original graph H, every perfect matching with 2r red edges becomes a. perfect matching in H with r red edges. Thus finding a perfect matching in H containing r red edges is equivalent to finding a perfect matching in the new graph H* containing 2r red edges, and this is a problem of the same type as the original problem, but belonging to the partitioned case I. 5

( Red j- ) ( - Red u} Blue v Red i ) Edge in original Path with new nodes uij, vij replacing the red graph H. edge (i,j). Figure 1: Because of Theorem 1, algorithmic studies of the problem of solving (1)-(6) on the incomplete graph H can be restricted to the partitioned case without any loss of generality. So in the sequel we focus our attention on the partitioned case. Also, solving (1)-(6) is equivalent to the optimization problem min (i,j)EF Xij (9) subject to (1) - (5) (9) is a 0-1 integer program defined on the complete graph G which we assume belongs to the partitioned case. An- important strategy for solving a 0-1 integer program is to develop a polyhedral characterization of the convex hull of its set of feasible solutions, i.e., obtain a linear inequality representation for it. In this paper, we focus on a polyhedral characterization for (1)-(5) in the partitioned case. We present two large classes of facetinducing inequalities ( each containing an exponential number of inequalities) for this problem [1]. However, these classes do not completely characterize the convex hull of the set of feasible solutions of (1)-(5). 6

2 The Results We consider the system (1) to (5) defined on the complete graph G belonging to the partitioned case with partitions, I = I1 U I2, J = J1 U J2, blocks B1, B2, B3?a4, and nl, n2, rl to r4 as defined earlier. When one of the sets among I1, 12 is 0, and one of the sets among J1, J2 is 0, all the edges in G have only one color, and all extreme points of the set of feasible solutions of (1), (2), (3), (5) satisfy (4) automatically. The same property holds when exactly one of the 4 sets among 1, 12, J1, J2 is 0, and the other three are nonempty. So, we assume O < ni < n, < n2 < n, and without loss of generality, we assume that the rows and columns of the array are rearranged so that I1 = {1,2,.... ni}, 12 = {1l + 1,..., n}. J1 = {1,2,...,n2}, J2 = {n2 + 1,...,7n} (See Figure 2). Define Pnr2 = Set of feasible solutions of (1), (2), (3), (7) [ or equivalently (1), (2), (3), (5)] nrl = Integer hull of P,2 defined as conv({x: x C Pnlrn and x integer }) = convex hull of set of feasible solutions of (1), (2), (4), (7). It can be shown that Pnlr 7 0 iff max{0, ni + n2- n} < rl < min{nli, z2}, which It can be shown that Pnj n2 we assume. The polytope defined by (1),(2), and (3) is the well-known assignment, or Birkoff polytope KA with integral extreme points. However, with the side constraint (7), Pnnri2 may have fractional extreme points. For example, when n = 4, n1 = n2 = 2, r1 = 1, 1 X11 = X14 = X22 = X23 = X32 = X34 = X41 = X43 = 2 x= 0 otherwise is a fractional extreme point of P241. Hence, Q,2 may not be equal to Pn In the sequel, an assignment x = (x-j) of order n is represented as a permutation (71, 2,...~ Os,...,on) such that xsa = 1 for s = 1,2,...,n, xj = 0 otherwise. For example, the diagonal assignment is represented by the permutation (1,2,..., n). 7

2.1 Dimension and the Trivial Facets of Q 2nl Here, we present the conditions under which Qn'n2 coincides with Pnjn2. For the general case when Q.~i2 + Pn^12, we establish that dim(QOr2 ) = dim(P1".2) = n2 - 2n when I when 2 ' 1 nl,n2 1n2 Qn,n2 0 Lemma 2 Let KA be the assignment polytope, i.e., set of feasible solutions of (1), (2), (3). If one or more of r1, r2, r3, r4 are 0, Qnlr = pnjr2 = a face of KA. Proof. From Theorem 1 we know that in system (1), (2), (3), (5), the constraint (5) can be replaced by 7E xj-=rt (10) (i,j)EBt for any t = 1 to 4. Hence Pn,2 is the set of feasible solutions of (1), (2), (3), and (10). But if rt = 0, under (3), constraint (10) is equivalent to xij = 0 for each (i,j) C Bt (11) Hence in this case Pn2 is the set of feasible solutions of (1), (2), (3), (11), which by definition is a face of KA, and hence all its extreme points are 0 - 1 vectors. Hence Q"l = P"nr = a face of KA in this case. I Qnl,n2 rl In2 Theorem 2 Suppose that rt > 1 for all t =1 to 4, and Qnl2 0. Then Qn;r2 and Pnirn both have the same dimension n2 - 2n. Also, each non-negativity restriction in (3) is a facet-inducing inequality for Qn'2r Proof. Dim Pnl = n2 - 217 can be shown rather easily. Hence, dim Qnl2 < n2 - 2n. Now assume that dim Q''Tnr < 72 _ 27n then there exists a hyperplane H = {x E IR2: =1 EjZ=1 oaijxij = f} containing Qn,Li2 but not P'n2. i.e., H is not defined by a linear combination of the equality constraints (1), (2), and (7). We will show that no such hyperplane H can exist thus establishing that dim Qnl2 = n2 - 2n. 8

Let Ax = b represent the system of equality constraints (1), (2), and (7). Then A is a full row rank 2n x n2 matrix. Let x~ be a solution matching in Qnr,2 and A = (B, N) be a partition of A into basic, nonbasic parts with B being a 2n x 2n basis for A, corresponding to basic vector XB containing the basic variables X1,n2+r2 —1 X2,n2+r2 —2 * * * Xn +r4-1,1 Xnli+r4,n Xnl +r4+l, n-1i ~ ~ ~ n X,n2+r2 Xl,n2+r2 X2,n2+r2-1 * * * X Xnl1+r4,1 I Xn1+r4-4+1,n i Xnlr4+2,n-1, ~ ~-~ Xn,n2+r2+1 with the basic variables in the top row having value 0 in x~ ( the cells marked with (o) in Figure 2), and those in the bottom row having value 1 in x~ ( the cells marked with a (*) in Figure 2). Let XN denote the vector of nonbasic variables. From the results in [6] we know that in the partitioned case under discussion here, the rows and columns of the array can be rearranged so that the matched cells in any solution matching appear along one of the diagonals like the one marked with (*)'s in Figure 2. Let (aB aN) be the corresponding rearrangement of the row vector (a'ij). Hence H = {x IRn2: aBXB + aNXN = /} Let H = {x E IR2: BXB + a^NXN = /} where (aB, a, 3) = (aB, aN, /) - A (B,, b) where AX IR2n will be chosen appropriately. By construction H contains Q^nlr12. Now if we can show that ^B = 0, &N = 0, and /3 = 0, for a proper choice of A, it would follow that the equation defining H, is a linear combination of the equality constraints (1), (2), and (7), thus arriving at a contradiction. To establish this, let AT = aBB-1. Then aB = 0. Represented as a permutation of (1,2,..,n), x~ is (n2+r2, n2+r2-1, 2+r2-2...,,n,n-1,..., n2+r2 1) 9

J1 J2 r2 n2 I1 n1 B_ o* Br o -I- __*o __ 0* o0 -k 0 -* - 0 ~-A-0 o 0* 0 -0 -Q- --- ----- -— ~~ ~~~~~0 — r~ I2 Figure 2: The double lines indicate the row and column partitions, and the four blocks B1, B2, B3, and B4 are shown. The 2n' basic cells corresponding to basic vector XB are marked with (o) or (*). 10

Then x~ = 0. Since Qn'r2 lies in H, it follows that aBX4 + aNXN = /. Since aB =0 and Ax = 0 it follows that 3 = 0. Thus it remains to show that aN = 0. Towards this effort, let x1 be the assignment 1 = (n2 + r2 - 1, n2 + r2, n2 + r2 - 2..., 1, n, n -1,... n2 +r2 + 1) whose representation as a permutation is obtained by interchanging the first two elements in the permutation corresponding to x~ ( when represented as permutation matrices, x1 is obtained by interchanging rows 1 and 2 in x~). By the hypothesis in the theorem nl = rl + r2 > 2, and hence the interchange does not alter the number of allocations within each of the four blocks, i.e., x1 is also a solution matching, or x1 C Qn, r So or two columns ( both within J1 or both within J2), and for each k = 2 to n2 - 2n, using the equation j^ = clearyi^ = 0 we are able to hat thone more component of aN is zero. In the end we have AN = 0. This establishes that dim Q^' = n2 - 2n. Now select any variable Xpq. From the above procedure it is clear that the dimension of the set of all solution matchings in each of which Xpq=0 has dimension n2 - n- 1. This implies that the face F = {x C Qw r Xpq 0} is a facet of Q r I 2.2 Some Non Trivial Facet s (of Qwit We assume that all of r1, r2. r3 and 14 > 1. This automatically implies n > 4. Proposition 1 Let ij = (xij i C Ij C.), w here I, J are arbitrary noneempty sets, be the incidence matrix of a matching in I x J. And let CR, ICc be subsets of I, J respectively such that ICRI < |J\icl and I clc < JI\iCRI Then >1E j- + E C e j + E x\-j < ~KR + lICC ieKCR jetCc iCKhR jEJ\Vc iEI\kR j3ECC 11

Equality holds for the matching Xij= -(ij i C I,j C J) where 1 for each i C KR, for some j C J\Cc ij = 1 for each j E Kc, for some i e I\CR 0 otherwise Proof. This follows directly from the definition of a matching. 2.2.1 The First Class of Facets Facet-inducing inequalities for Qnlr 2 of the first class are characterized by a cell (p, q) C I x J called the primary defining cell or just the defining cell, and a nonempty set of row indices KCR, and a nonempty set of column indices ACc. Look at the four blocks in our partition (Figure 2). Blocks B1, B2 lie in the same rows of the array, so we say that each of them is the row adjacent block of the other. Similarly, in blocks B3, B4, each is row adjacent block to the other. In the same way in the pairs (B1, B4), (B2, B3), each is the column adjacent block of the other. We say that two given blocks are adjacent if they are either row adjacent or column adjacent. The defining cell (p, q) for the first class of facets can be any cell in the array. Suppose it is contained in block Bt. Let It, Jt denote the set of row and column indices of Bt respectively. Let Bu be the row adjacent block of Bt, and B, the column adjacent block of Bt. Let Bw be the remaining block which is not adjacent to Bt. Let I denote the set of row indices of By, and J denote the set of column indices of Bu. (i.e., I = I\It and J = J\Jt) Then the defining subset of row indices ICR must be a nonempty proper subset of I, and the defining subset of column indices ICc must be a nonempty proper subset of J, together they have to satisfy \RI + |1 c| = 1 + rw Lemma 3 bet (p, q) be the defining cell and kCR, ACc be the defining sets of row and column indices selected as discussed above. Then Xpq+ E xpj+ E xq - E XXj <1 (12) jeKc iER iI\AkR, jeJ\V is a valid inequality for Qnn 2 12

Proof. First we observe that in any assignment x = (Ij: i E I, j E J) Xpq + E Xpj + E X.q (13) jEgc iEIKR is equal to 0, 1, or 2. This is easy to see since each of these terms is either 0 or 1 and since all of them can not be 1 at the same time. For an assignment x E Qnrl if the expression in (13) is equal to either 0 or 1, our lemma holds trivially. Therefore, assume that the expression in (13) is equal to 2 for an assignment x E Qnrl. This holds only when Xpq = 0, and EjEcc Xpj = -ZiEC xiq 1. Suppose that xpjo = Xiq = 1 where jo E IC and io e CR. Thus E x, = zjo= 0 (14) jeJ ieI Since x G Qnrl, 2 we have E(i,j)eB xj = rw. i.e., Z ij + E Xij E X ij + X ij = rw ieCRR E, jeeCc iZEiR, jeeJ\k iEi\CE R, jEJ\Ac Using Proposition 1 and (14) it follows that E;Xj + E xzj + E xj < IKCR\{ioo} + IlCc\{jo}l = r -1 iEiCR, jEKC iEKR, jEJ\Kc iEi\K, jEKc hence ZEi\- iEJ\cc Zij > 1 and hence (12) holds for x and the lemma follows. I As an example consider the case where n = 5, nl = 2, n2 = 3 and rl = 1. Hence r2 = r3 = 1 and r4 = 2. Let the defining cell be (1,1), and the defining sets be ACR = {3}, ICc = {4}. The valid inequality (12) corresponding to these choices is X11 + X14 + X31 - 45 - 55 < 1 which is a valid inequality for Q:'. Note that all the nonzero coefficients in (12) are +1 or -1. It is helpful to have a pictorial representation of inequality (12). In Figure 3, we show the array with the defining cell (p,q) and the defining subsets iCR, ICc, and the cells in the array whose variables appear with a +1 coefficient (marked by + symbol), and those with a -1 coefficient (marked by - symbol) in this inequality. 13

q p kRI Bt Bu +.++.-+++ + + I BV Bw I IH I I: B, I I II. I B,~~~~ Figure 3: Pictorial representation of signs of lines indicate the row and column partitions. nonzero coefficients in (12). The double 14

Theorem 3 The valid inequality (12) in Lemma 3 is a facet-inducing inequality for n,rl nl,n2 ' The proof of Theorem 3 is given in Section 2.3 Inequalities (12) define the first class of facet-inducing inequalities for Qnn. For defining these inequalities, the defining cell (p, q) can be selected as any cell in the array, so there are n2 ways of choosing it. Once the defining cell (p, q) is selected, the number of ways of selecting the defining subsets CR, ACc is N=1 N rw + 1-N where N = IICRI and rw + 1 - N = I\Ccl, this number grows exponentially with III,IJl and rw. Hence the total number of these first class of facet-inducing inequalities for Qnrl2 grows exponentially with n1, n2, r1. 2.2.2 The Second Class of Facets Facet-inducing inequalities in this class are characterized by two defining cells called the primary and secondary defining cells, and by two defining subsets of row indices, and two defining subsets of column indices. The primary defining cell, (p,q) say, can be any cell in the array. -Suppose it is contained in block Bt. The second class of facet-inducing inequalities for Qnr2 only exist for the primary defining cell (p, q) E Bt if the numbers r, r, corresponding to the row adjacent block Bu, the column adjacent block By of Bt, are both > 2. If this condition is satisfied, the secondary defining cell, (m, 1) say, can be any cell in the adjacent blocks B, or By of Bt satisfying min p, 1 f q. Let Bw be the block not adjacent to Bt. If (m, 1) C Bu, the defining subsets of column indices Cc,,&c, say, can be any nonempty proper subsets of the column indices of the blocks Bu, Bt respectively satisfying the condition that 1 IKCc, q f kCc; and the defining subsets of row indices, kCR, ICR, say, can be any nonempty mutually disjoint 15

proper subsets of the row indices of B, which together satisfy KICcl + \iRI = 1 + r,, and ICcl + ICRI = rv. If (m, 1) BV, the column adjacent block of Bt, the defining subsets of column indices, Cc, ICc, can be any nonempty mutually disjoint proper subsets of the column indices of B,; and the defining subsets of row indices, ACR, KZR can be any nonempty proper subsets of the row indices of Bv, Bt respectively satisfying the condition that m B ACR, P f CR; which together satisfy \)Cc\ + IKCRI = 1 + r,, and \kCcl + I CRI = ru. For this case where the secondary defining cell (m, 1) G Bv we have the following lemma. Lemma 4 Let the primary defining cell be (p, q) from block Bt, and suppose its row adjacent block Bu satisfies ru > 2. Let I be the set of row indices of block By, and J be the set of column indices of block Bu. Let It, Jt be the sets of row and column indices of Bt. Let (m, 1) C Bv be the secondary defining cell, and let the defining subsets of row and column indices KCR, AiR, kCc, and IKc be selected as discussed above. Let Bw be the block not adjacent to Bt (i.., B,, = x J). Then Xpq + E Xpj + E X - z xi j'ec iZR iei\(KRu{m}) jEJ\kc S Xmj - E xi3 (15) jeJ\()CcUCc) iEIt\(kRU{p}) jeJ\(ACcUKc) -, E S il <1 it I\(kRUkRU{p,m}) is a valid inequality of Qn2' Proof. For any assignment x E Qnr 2 the sum xpq + 5 Xpj + Xiq (16) jEKc iEiCR is equal to 0, 1, or 2. If the expression in (16) is equal to either 0 or 1 the lemma follows trivially. Therefore, assume that the expression in (16) is equal to 2. This holds when 16

Xpjo = 1 for some jo E IC and Xioq = 1 for some io E KR. Then by Proposition 1 we have ZE X + XE X + E X < IACR\{io}0 + lAc\{jo}l (17) iEKR jEKCc iECKR jEJ\K iEi\KCR jEIC Two cases will be considered Case 1: Xmj = 0 for all j E KCc. Then since Z(i,j)EB Xij = rw and since IKR\{io}l + I\{cjo}l = rw - 1 it follows that E ^Xj > 1 iZI\KR iEJ\Kc and since jic Xmj = 0 by assumption, it follows that SE Xj + E > 5j m 1 iEi\(KRu{m}) iEJ\kc jEJ\(kcUkc) and (15) holds for x. Case 2: xmj, = 1 for some jl Cc. Then if (17) holds as a strict inequality, and by the same argument as in case 1, we have >iEI\( Ru{m})?eJ\Cx >x 1, and (15) holds for x. Therefore, assume that (17) holds as an equality. By Proposition 1, this corresponds to the case where for each i C A-R\{io}, xij = 1 for some j E J\Kc; and for each iE ACc\{jo}, xij = 1 for some i C I\(ICR U {m}). This implies that l = O for all i kR U {m} (18) E xij =-0 (19) iEIt\{p} jEkc Now applying Proposition 1 to block Bu and using (19) we have X + 5E Xj + E < I RI + IkCl\{ j}l (20) iEL-R jEACc iEKR jEJ\Kc iEIt\hR jEIc if (20) holds as a strict inequality and since Z(ij)eBuj = ru and |KR| + Ikc\{ji} = ru- 1 it follows that 5RUE jXml) >1 ieIt\(KRU{p}) jEJ\(CCUkCc) 17

and (15) holds for x. Therefore assume that (20) holds as an equality. This corresponds to the case where for each i AkR, xij = 1 for some j C J\kCc U {ji}; and for each j E KC U {ji}. xj = 1 for some i E It\(KR U {p}) which implies that xzi = 0 for all i E kR U {p}. Therefore, by (18) and the fact that ZEIXZi = 1 it follows that iEI\(RUKRU{p,m})xil = 1 Thus, (15) holds for x and the lemma follows I. A similar lemma for the case where the secondary defining cell (m, 1) C Bu is Lemma 5 Let the primary defining cell be (p, q) from block Bt, and suppose its column adjacent block By satisfies rv > 2. Let I be the set of row indices of block B,, and J be the set of column indices of block Bu. Let It, Jt be the sets of row and column indices of Bt. Let (m, 1) G Bu be the secondary defining cell, and let the defining subsets of row and column indices IR, kR, ACC, and kc be selected as discussed above. Let Bw be the block not adjacent to Bt (i.e., B= I x J). Then Xpq + Xpj + E Xiq - Xi jECk ZEKR izEi\E R jEJ\(kcu{l}) - E xi - E xi- (21) iEI\(KRUkR) iEI\(kRUKR) jEJt\(Pc)u{q}) - S Xmj < 1 jEJ\(kccukcu{q,l}) is a valid inequality of Qnl;2' The proof of Lemma 5 is similar to that of Lemma 4. As an example consider the case where n = 8, nI = 4, n2 = 4, and ri = r2 = r3 = r4 = 2. Then, selecting (p, q) = (1, 1) C B1, (m, 1) = (5,2) B4, ICR = {6}, ICc = {6, 7}, KR = {2}, Kc = {5} satisfying all the conditions for selection mentioned above, leads to the valid inequality for Q8:. X11 + X16 + X17 + X61 - X32 - X38 - X42 - X48 -X58 - X72 - X75 - 78 - X82 - 85 - X88 < 1 18

q 1 -4 c /cc 4 p +1 II+:++*-.+ Bt Bu -B -—...~- - m /kR Figure 4: Pictorial representation of signs of nonzero coefficients in (15) In Figure 4, we give a pictorial representation of inequality (15). It shows the array with the defining cells (p, q) e Bt, (m, 1) E By and the defining subsets kR, KCc, KR, kC? and the cells in the array whose variables appear with a +1 coefficient (marked by + symbol), and those with a -1 coefficient ( marked by - symbol) in the inequality. Theorem 4 The valid inequalities (15 ) or (21) defined in Lemmas 4,5 are facet-defininq inequalities for Qnrl provided that both r, r,, > 2. Theorem 4 will be proved in section 2.3. Notice that in Lemma 4 we only require ru > 2 for (15) to be a valid inequality for Qn,' '. Correspondingly in Lemma 5 we only require rV 2 for (21) to be a valid inequality for Qnl 2. But Theorem 4 establishes that these are facet-inducing when both r,, rV > 2. Unfortunately, these two nontrivial classes of facets do not provide a complete description of the polytope nQri2 as demonstrated by the following fractional point x = 19

(xij) defined by X11 = X15 = X24 = X27 = X35 = X38 = X43 = X44 = X56 = X57 = X62 = X66 = X73 = X78= X81 = X82 = -, Xij = 0, otherwise. 1 It can be verified that x is an extreme point of the polytope P24 and that it satisfies all first class facet-inducing inequalities for Q81. Since both r1 and r2 are < 2 (in fact equal to 1) for Q8,:2 we do not have a pair of nonadjacent blocks both of whose r-numbers are > 2. Hence the second class of inequalities of the form (15), (21) are not facet-inducing for this problem. 2.3 A Facet Lifting Procedure In this section, a lifting procedure for facets of Qnr2 is presented. Given a facet F of Qn12, we show how to lift F into a facet F* of Qn+l,rl Qn+l, Q+l+l and oQnlln2 I nl +1,n2 l nn+1,n2 +1l Q n2 +1 This procedure is used to prove Theorems 3 and 4 using mathematical induction. All symbols with a star (*) refers to assignments of order n + 1. For any matrix A, we denote its ith row vector by Ai., and its jth column vector by A.j. Lemma 6 Let Zn1 EZ;= ajxzj < ao be a non trivial facet-inducing inequality for Qnri2 and let A* (a*) be the (n + 1) x (n + 1) matrix derived from A = (aij) such that A A.jo A* Ajoi (22) Aio. 0 for any io E {n + 1,..., n} and any jo E {n2 + 1,...,n} satisfying a j = 0. Then,+1l Tn+l axij < a is a facet-inducing inequality for Qn+l2rl provided that it is a valid inequality foT it. Proof. Let F = {x C Qnln2 =: -=l 1 j =l a0} and F* ={x C Qn+lj T =1 _,jnll aijxij = ao}. Then there exist n2- 2n affinely independent assignments x1,2,.. 2-2n F and for every () 1, n there exists at least x1,x2,...,Ix in F, and for every (i,j) { n {1, n} there exists at least 20

I. -2 xk E {Zx1 X2,..., x -2n} such that xk = 1. The last assertion follows since otherwise if xk = 0 for all xk G {xI, x2..., xn -2n} then F would be contained in the intersection of two facetal hyperplanes xrs = 0 and i=l n=l1 aijxij = ao contradicting the assumption that F is a facet of Qnrl2 Let {xilxz2,... xi} C {x1,x2,... n2- such that xj = i2 = {.i Z2jo -..= xxo = 1. Likewise, let {xj3, x2,..., xn-} C {x x2,..., x-2n} such that Xi _ -2 -l -1 iol io2 - - zion-1 - Let x*k, for k 1 2,..., n2 -2n, be the assignments of order n + 1 defined as IX. X. _o / - n= then x1 X*2 X*n2-2n belong to F* Xnn+l= 1, x = x for i,j,,...,n then *... belong t since by construction an+1,n+ = O. Let x*il, *i2,..., x be the assignments of order n + 1 derived from xi', xi2,..., xi by switching columns jo and n + 1 and by setting xlijo = 1 for all k = i1,i2,...,i,. Then x*i,X *i2,..., xi belong to F* since A*_+l = A*. Likewise, let x*lx**j2... x*jn- be the assignments of order n + 1 de-.30 '. ' rived from xj1, x2,..., xn-1 by switching rows io and n + 1 and by setting x*k = 1 for all k = jl,j2,. jn-1 Then x*j X*j2....x*j-1 belong to F* since A*+1 = A*. Clearly, x*1 x*2,..., X*2-2n, *1. x *in xn, x*, 2,..., *jn-1 are affinely independent. Thus dim F* = n2 = (n + 1)2 - 2(n + 1) - 1 I Using a similar argument as in Lemma 6, it can be shown that if Z C I axijz.j < ao is a facet-inducing inequality for Qnr2 then n n+l n n n+l n E bx* < ao, < ao, E E dx < ao i=O j=1 i=0 j=0 i=1 j=0 are facet-inducing inequalities for Q"j2n+', Qn+rl+l, and Qnl+1T1 respectively provided that they are valid inequalities. B' = (b*), C* = (c*), and D* = (d*j) are defined by B* (| - A ) Ako. 0 Ak.), D* O ) A, D*- AAmoA A A. jo \A.=o A 0 \ ~ Aio for any ko C {1,...,ni}, any jo E {22 + 1,...,n}, any mo G {l,...,n2), and any io C {ni + 1,...,n} satisfying akjo = 0, akomo = 0, and aimo- = 0. 21

Proof of theorem 3. For ease of notation, and without loss of generality assume that the defining cell (p, q) belongs to Block B1. Thus, I = 12 = {ni + 1, n1 + 2,..., n} and = 2, 2 2..,and = r3. The proof is by induction on 7, the order of the assignment. For n = 4, nl = n2 = 2 and ri = 1. Let (p, q) = (1, 1) and ICR = C = {3}. Then X11 + X13 + X31 - X44 < 1 (23) is a facet-defining inequality of Q2'2 since it is a valid inequality of Q4'1 by Lemma 3 and since the following 8 feasible assignments, represented as permutations, are affinely independent and satisfy (23) as an equality. Recall that dim Q4' = 8. x1 =(1,3,4,2) x2 (1,4,3,2) X3 =(1,4,2,3) X4 (2,4,1,3) X5 = (3,1,4,2) 6 = (3,2,4,1) 7 = (3,2, 1,4) 8 = (4,2, 1,3) Now assume n > 4 and that the assertion is true for assignments of order n, using the lifting procedure in Lemma 6, we will show that it is true for assignments of order n + 1. Let n=i Zj'=1 ajxij <- 1 be a facet-inducing inequality of form (12), shown in Figure 3, for the problem of order 7n (i.e., for Q; 2); and let (p, q) be its defining cell, KR (kIc) be its defining subset of row( column) indices. We will refer to this valid inequality as VI(n). Consider the problem of order (n + 1) and its corresponding array I* x J*. Then 1* x J* is obtained from I x J, I = J = {1, 2,..., n} by the addition of one new row and one new column. The new row can be added either at the top or at the bottom of the n x n array, and the new column call be added either to the left or to the right of the n x n array, leading to four separate cases: Case 1: The added row and the added column are n + 1 and n + 1. This corresponds to the polytope Qn+l^[1 where r- = r3 + 1. ( Recall that symbols with (*) refer to the problem of order n + 1). Then VI(n) can be lifted in two ways: 22

1. Select io to be any row C kCR and jo to be any column e J2\Kc. Note that for this selection aijo = O. Hence, E+i1 +l a x < 1, where A* (a ) as defined in (22), is a valid inequality of Qn+li1 since it is of the form (12), with defining cell (p, q), % = iCR U In + 1}, and KIC = KCc; and by Lemma 6 it is facet-inducing. 2. Select jo to be any column C ICc and io to be any row C I2\KR Using the same argument as in 1, it follows that the valid inequality for Ql+11rl with defining cell (p, q), and c* = CcU{n+lI and KCC = -)R is also facet-inducing. Case 2: The added row and the added column are 0 and n + 1 respectively. This corresponds to the polytope Q,+1lr where r* = r2 + 1. Select jo to be any column C J2\c, and io to be any row ({1, 2,..., n}\{p}). Notice that for this selection As is a row of all O's. Using the same argument as in case 1, it follows that the valid inequality for Qn+jri1 with defining cell (p, q) and IC = Cc, K: = ICR is facet-inducing. Case 3: The added row and the added column are 0 and 0 respectively. This corresponds to the polytope Qn+l'',+ where r = r 4 + 1. Select jo to be any column C {1,2,.., \ and a o to nd o o any row ({1, 2,... ni}\{p}). For this selection A = A* = 0. Using the same argument as in case 1, it follows that the valid inequality for Q -+ 1 -with defining cell (p,q) and IC7 = ICc, ACU = CR is facet-inducing. Case 4: The added row and the added column are n + 1 and 0 respectively. This corresponds to the polytope Q + where r* = r4 + 1. Select io to be any row C I2\ICR and jo to be any column C ({1, 2,..., n2}\{q}). Using the same argument as in case 1, it follows that the valid inequality for Qnl2+1 with defining cell (p, q) and ICc = ICc, kI = CR is facet-inducing. Now assume n > 4, we will show that every valid inequality of the form (12) for the problem of order n + 1 can be established as being facet-inducing by lifting some 23

facet-inducing inequality of the form (12) for the problem of order n. Since n + 1 > 5, for the problem of order n + 1 at least one of the r s > 2 for t=l to 4. Assume that r* > 2 and consider the valid inequality of form (12) for the problem of order n + 1 with defining cell (p, q) and defining subsets kC and )K:. We will refer to this inequality by VI(n + 1). Then |C Ic + kCk| > 3. Thus either IKCI or i| I must be > 2. 1. If IKICI > 2. Let io be any row C KIC and jo be any column E J2\KC and consider the problem P(n) of order n associated with array (I*\{io}) x (J*\{jo}). Then the inequality obtained from VI(n + 1) by deleting io from IC* is of form (12) with defining cell (p, q), ICR = KR\{io}, and KCc = ICK; and hence it is a facet-inducing inequality for problem P(n). Furthermore, VI(n + 1) can be established as facetinducing for the problem of order n + 1 by lifting this inequality as in Case 1 above. 2. If IKCI > 2. Let jo be any column EC KC and io be any row e I2\KC. Then the inequality of form (12) with defining cell (p, q) and KCc = IC\{jo}, and KR -= K is a facet-inducing inequality for problem P(n), and we can establish that VI(n + 1) is facet-inducing for the problem of order n + 1 by lifting this inequality as in Case 1 above. Similarly, if r2 > 2 let io be any row c (I \{p}), and let jo be any column C J*\kc. If r > 2 let io be any row C (Ij*\{p}), and let jo be any column C (Jj*\{q}). If r4 > 2 let zo be any row E (I2*\IC) and let jo be any column e (Ji*\{q}). Then in all these cases, it is easy to show that the inequality with defining cell (p, q) and KCc = KCEU, and ICR = kC is of form (12) and hence it is a facet-inducing inequality for the problem of order n associated with the array (I*\{io}) x (J*\{jo}) and that VI(n + 1) can be established to be facet inducing for the problem of order n + 1 by lifting this inequality as in Cases 2,3, and 4 respectively. I 24

Proof of Theorem 4. We assume that the secondary defining cell (m, 1) C B,. A proof similar to the following applies when (m, 1) E Bu. Also we use induction on n, the order of the assignment. For n = 6, nl = n2 = 3 and r1 = 1. Let (p, q) = (1,1), (m, 1) = (4, 2), Cic = {5}, Cc = {4}, /CR = {5}, and CR = {2}. Then x11 + x15 + x51 - x32 - x36- x46- x62 - x64 - x66 1 (24) is a facet-defining inequality of Q6 3 since it is a valid inequality of Q6 1 by Lemma 3 and since the following 24 feasible assignments, represented as permutations, are affinely independent and satisfy (24) as an equality. Recall that dim Q3,3 =24. x1 (1,4,5,2,6,3) x2=(1,5,4,2,6,3) x3=(1,6,4,5,2,3) x4 =(1,6,4,2,5,3) x5 (1,6,4,2,3,5) x6 (1,6,4,3,2,5) x7 (1,6,5,4,2,3) x8 = (1,6,5,2,4,3) x9= (2,6,4,5,1,3) X10 (3,6,4,2,1,5) x11 = (5,1,4,2,6,3) 12 = (5,2,4,6,1,3) 13 = (5,2,4,1,6,3) x14= (5,2,4,3,6,1) X15= (5,2,4,3,1,6) x16= (5,2,6,4,1,3) x17= (6,2,4,5,1,3) x18= (5,3,4,2,6,1) x19 =(5,4,1,2,6,3) x20 = (5,6,2,4,1,3) x21 = (4,6,3,2,1,5) 22 (5,4,3,2,6,1) x23=(5,6,3,4,1,2) x24 =(5,6,3,2,1,4) Now assume n > 6 and that the assertion is true for assignments of order n, using the lifting procedure in Lemma 6, we will show that it is true for assignments of order 7. + 1 Without loss of generality, we assume that the primary defining cell (p,q) C B1. Thus = I2= {n + 1,..., n}, J J2 = {n2 + 1,..., n}, and rw = r3. Let JZ=: j=1 aijxij < 1 be a facet-inducing inequality of form (15), shown in Figure 4, for the problem of order n (i.e., for Qnr}2); and let (p, q), (m, 1) be respectively its primary and secondary defining cells, kR, AR, ICc, and kc be its defining subset of row and column indices. We will refer to this valid inequality as VII(n). Consider the problem of order (n + 1) and its corresponding array I* x J*. Then I* x J* is obtained from I x J, I = J = {1,2,..., n} by the addition of one new row 25

and one new column. As in the proof of Theorem 3, the new row can be added either at the top or at the bottom of the n x n array, and the new column can be added either to the left or to the right of the n x n array, leading to four separate cases: Case 1: The added row and and the added column are n +1 and n + 1. This corresponds to the polytope is Qn+1;r' where r* = r3 + 1. Then VII(n) can be lifted in two ways. 1. Select io to be any row E ACR and jo to be any column e J2\(ACcU KCc). Note that for such selection aioo = 0. Hence, E+11 E+l ax < 1, where A* = (a*) as defined in (22), is a valid inequality of Q7+1'1 since it is of the form (15) with defining cells (p, q) and (m, 1), and defining subsets kC* = ICR U {n + 1}, KC* = Cc, C = Kc, and kC = kCR; and by Lemma 6 it is facet-inducing. 2. Select jo to be any column E ICC and io to be any row G I2\(ICRU{m}). Using The same argument as in 1, it follows that the valid inequality for Qn+1,r with defining cells (p, q) and (m, I) and defining subsets KC = kc U {n + 1} and C = CR, AC = -Cc, and kR = iCR is also facet-inducing. Case 2: The added row and the added column are 0 and n + 1 respectively. This corresponds to the polytope Q n+ll where r* = r2 + 1. Then VII(n) can also be lifted in two ways 1. Select jo to be any column C 0Cc and io to be any i C {1,2,...,n}\({p}U ICR). Using the same argument as in Case 1, it follows that the valid inequality for Qn+lr1 with defining (p,q) and (m, 1) and defining subsets AC* = KAR, IC = ICc, KIC = kc U {n + 1}, and KC = KCR is facet-inducing. 2. Select io to be any row EC KR and jo to be any column C J2\(ICU IC). Using the same argument as in Case 1, it follows that the valid inequality for Qn++1,2 with defining (p,q) and (m, ) and defining subsets ICK = ICR, IC = Ic, IC~ = Kc, and IC = ICR U {n + 1} is facet-inducing. 26

Case 3: The added row and the added column are 0 and 0 respectively. This corresponds to the polytope Q +1+1% where r* = ri + 1. Select jo to be any column C {1,2,...,n2}\ ({q} U {I}) and and io to be any row E {1, 2,..., nl}\({p} U KR). For this selection, A*. = O. Using the same argument as in Case 1, it follows that the valid inequality for Q+it'2+1 with defining (p, q) and (m, 1) and defining subsets KIC= KCR, = Kc, KC = - c, and KC = CR, is facet-inducing. corresponds to the polytope Qn+1,ri where r* = r4 + 1. Select io to be any row e I2\(ACR U {m}) and jo to be any column e {1, 2,...., n2}\({q} U {1}). Using the same argument as in Case 1, it follows that the valid inequality for Qn+12,ri with defining (p, q) and (m, 1) and defining subsets AC7 = KR, KC* = KC, C= KCc, and = KCR is facet-inducing. Now assume that n > 6, we will show that every valid inequality of form (15) for the problem of order n + 1 can be obtained by lifting some valid inequality of form (15) for the problem of order n. Consider the valid inequality of form (15) for the problem of order n +1 with primary and secondary defining cells (p, q), (m, 1), and defining subsets C*K, /A, C, and Ac. Refer to this inequality as VII(n + 1). Since n + 1 > 7, for the problem of order n + 1, one of the following must hold. r > 2, r > 3, r > 3, or r> 2, If r5 > 2. In this case IkCI + \KC*I > 3 which implies that either |ICK| > 2 or IK|C > 2. 1. if |IC > 2. Let io be any row VE k and jo be any column E J2\(KC U iC ) and consider the problem P2(n) of order 72 associated with array I*\{io} x J*\{jo}. Then the inequality obtained from VII(n7 + 1) by deleting io from KR4 is of form (15) with defining cells (p,q), (m.l), and defining subsets KR = KC?\{io}, KCC = K:C R = kCR, ICC = KC; and hence it is a valid inequality for problem P2(n). Furthermore, VII(n + 1) can be lifted from this valid inequality as in Case 1. 27

2. if IKCI > 2. Let jo be any column E KIC and io be any row e I2\(ICR U {m}). Then the inequality obtained from VII(n + 1) by deleting jo from KC is of form (15) with defining cells (p, q), (m, 1), and defining subsets KIC = KC\{jo}, KR = R, CR = jC, KC = IC; and hence it is a valid inequality for problem P2(n), and VII(n +1) can be lifted from it. If r* > 3. In this case IKC I + IkCI > 3 which implies that either IKRI > 2 or ICI| > 2. 1. if \ICK > 2. Let io be any row E IC* and jo be any column E J2\(K U Kc). Then the inequality obtained from VII(n + 1) by deleting io from KC is of form (15) with defining cells (p, q), (m, 1), and defining subsets ICR = AC*\{io}0, KC = KC,R =R ICK, Cc = C*; and hence it is a valid inequality for problem P2(n), and VII(n + 1) can be lifted from it. 2. if KC| > 2. Let jo be any column E KIC and io be any row E I*\(iK U {p}). Then the inequality obtained from VII(n + 1) by deleting jo from KC is of form (15) with defining cells (pq), (m, 1), and defining subsets KCe = KC\{jo}, KC = MC, IR = KI, IkR = KC; and hence it is a valid inequality for problem P2(n), and VII(n + 1) can be lifted from it. If r* > 3, let io be any row E I*\(KR U {nm}) and jo be any column E j1\({q} U {1}). If r* > 2,. let io be any row E I\(KhR U {p}) and jo be any column E I*\({q} U {l}). Then in both these cases the inequality with defining cells (p,q), (m, 1), and defining subsets KCc = KC, Kc = IC, KR = i^ ^R = AR is of form (15); and hence it is a valid inequality for problem P2(n), and VII(n + 1) can be lifted from it. I 3 Summary and Concluding Remarks We have derived two large classes of facet inducing inequalities, the number in each grows exponentially with the order of the problem, for the the partitioned case of the 0-1 problem (9). Whereas the first class of facet-inducing inequalities comes into play for 28

n > 4, the second class plays a role only for n > 6. We have also shown that the general problem (9) polynomially reduces to the partitioned case. These classes together with the non-negativity constraints on the variables do not completely characterize the convex hull of integer feasible solutions of the problem. Currently we are investigating other facet-inducing inequalities for the problem that may lead to a complete characterization of its integer hull. We are also investigating whether all the facet-inducing inequalities for this problem can be shown to have coefficients 0, +1, or -1 only. References [1] Abdo Y. Alfakih. Facets of an Assignment Problem with a 0-1 Side Constraint. PhD thesis, the University of Michigan, 1996. [2] J. Brans, M. Leclercq, and P. Hansen. An algorithm for optimal reloading of pressurized water reactors. In M. Ross, editor, Operations Research '72, pages 417-428. North-Holland, 1973. [3] R. Chandrasekaran, S. Kabadi, and K. G. Murty. Some NP-Complete problems in linear programming. Operations Research letters, 1:101-104, 1982. [4] A. Gupta and J. Sharma. Tree search method for optimal core management of pressurized water reactors. Computers and Operations Research, 8:263-266, 1981. [5] A. V. Karzanov. Maximum matchings of a given weight in complete and complete bipartite graphs. Kibernetika 1 7-11. English translation in CYBNAW 23 (1) 8-13, 1987. [6] K. G. Murty, C. Spera, and T. Yi. Matchings in colored networks. University of Michigan Tech. Report, 1993. 29

[7] C. H. Papadimitriou. Polytopes and complexity. In W. R. Pulleyblank, editor, Progress in Combinatorial Optimization, pages 209-305. Academic Press Canada, 1984. [8] Tongnyoul Yi. Bipartite Matchings with Specified Values for a 0-1 Linear Function. PhD thesis, the University of Michigan, 1994. 30