On the Complexity of a Special Basis Problem in LP Katta G. Murty Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 Technical Report 90-19

On the Complexity of a Special Basis Problem in LP Katta G. Murty Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109-2117, USA August 9, 1990 Abstract In a linear program (LP) in standard form, we show that the problem of finding a cheapest feasible basic vector among those containing a specified variable as a basic variable, is an NP-hard problem. Key Words: Linear progam, feasible basic vector, NP-hard problem. 1

1 Introduction: We consider the linear program (LP) minimize z(x) = cx subject to Ax b (1) x-O where all the data is integer and A is an m x n matrix of rank m. A feasible basic vector for (1) is a vector of m variables called basic variables among x,..., x, associated with a linearly independent set of columns in (1), the basic solution corresponding to which is feasible. See [3] for definitions of LP terminology. Define the cost of a basic vector to be the cost of the associated basic feasible solution. The problem of finding the cheapest feasible basic vector for (1) containing a specified subset of variables as basic variables has been studied in [2] for its relationship with the travelling salesman problem, and there by shown to be NP-hard. Here we will investigate the following special case of this problem. Problem 1: Find a cheapest feasible basic vector for (1) among those containing one specified variable as a basic variable. In this note we show that Problem 1 is NP-hard. 2 The Equal Sums Partition Problem The input to this problem is n postivie integers dl,...,, d whose sum is w, even. It is required to find a subset S1 C {l,...,n} such that S1 and its complement S2 satisfy ZE dj = dj = w/2. We will consider the following slightly modified version. jESi jES2 Problem 2: Find a subset S1 C {1,..., n} satisfying -2 + (w/2) - E dj - 2 + (w/2). jESi Thus, if S1 is a solution to problem 2 and S2 its complement, then | dj - dj i 4 jESi jES2 (it is actually 0 or 2, or 4). It is well known that problem 2 is NP-hard [1]. We will now show that problem 2 can be formulated as a special case of problem 1 through a balanced transportation model. We will assume that all of dI,..., dn are = 2. 2

3 The Transportation Model We will construct a 3 x (n + 1) balanced transportation model corresponding to problem 2, with the following data Column 11 2...| n n+l Supply Rowl -a -.. +1 2_+1 2 i =w,+ 3 1 _ _ 1 - r I _I I I (2) Demand di d2l... Idn 3 A similar model has been used in [4] by Partovi to show the NP-hardness of another transportation related problem. Here we also have an objective function which is required to be minimized. The cost coefficient is zero in all the cells except cell (1, n + 1) where it is -a, a being a positive integer. Clearly this is a special case of (1). The variable xij in this model is associated with cell (i,j), i = 1 to 3, j = 1 to n + 1, so here, instead of basic vectors of variables, we will talk about the corresponding basic sets of cells. We have the following facts on (2) from well known results on the transportation problem [3]. i) Every basic set for (2) consists of (n + 3) basic cells. ii) If 6 is a feasible basic set for (2) in which all the cells in column (n + 1) are basic cells, then / contains exactly one cell among (1,j), (2,j) as a basic cell for each j = 1 to n [4]. In this case let S,(/3) = {j 1 j n, and (r,j) is a basic cell in /3},r 1,2. Then (S1(/3),S2(/)) is a partition of {1,...,n}, and E dj = 2 for r = 1,2, and jES.(p) hence Si(/) is a solution for problem 2. In the basic feasible solution (BFS) of (2) associated with f,, all the variables xr,n+l are equal to 1 for r = 1, 2, 3, and hence the cost of / is -a < 0. Conversely if (S1, S2) is a partition of {1,..., n} satisfying E dj = 2, r = 1,2, define jES, / ={(1,j) jESI}U{(2,j): jES2}U{(1,n+l),(2, n+l), (3,n+l)}. Then P is a feasible basic set for (2) with its cost equal to -a < 0. Now we define the special case of Problem 1 corresponding to (2). Problem 3: Find the cheapest feasible basic set of cells for (2) among those containing (2, n + 1) as a basic cell. 3

Theorem 1: There exists a subset S1 C {1,..., n} which is a solution for problem 2, iff the objective value associated with an optimum feasible basic set for problem 3 is < 0. Proof: From (ii) above, we already know that there exists and S1 C {1,...,n} satisfying Z, dj = w/2 iff there exists a feasible basic set for (2) containing all the cells in column jESi (n+1) as basic cells and the cost of such a basic set is -a < 0. Let iL be a feasible basic set of cells for (2) containing (2, n + 1) as a basic cell, with negative cost. Since (1, n +1) is the only cell in (2) associated with a nonzero cost coefficient, this implies that (1, n + 1) must also be a basic cell in,i. There must be at least one basic cell in row 3. If (3, n + 1) is also a basic cell in i1, this case is covered above, so we assume that (3, n + 1) is not a basic cell in 3/. Let (3,p) be a basic cell in 31, where 1 _ p - n. By assumption, each of dj - 2, j = 1 to n; so for feasibility there must be at least one basic cell among (1,j) and (2,j) for each j = 1 to n. (1, n + 1), (2,n + 1), (3,p) are already basic cells in /3 and there are a total of only n + 3 basic cells. These facts imply that for each 1 < j _ n, exactly one of (l,j) or (2,j) is a basic cell in 3i. Define for r = 1,2 Sr(/1) = {j: (r,j) is a basic cell in,h}. So S1(/3) and S2(/1) forms a partition of {l,...,n}. Let x = ({i,) be the BFS of (2) associated with,3i. Since the cost of I is < 0, l,n+l > 0, so its value is either 1 or 2 or 3. So x2,n+1 is either 2 or 1 or 0. X3,p = 1. So, for r = 1,2,j E S,(/1)\{p}, xr,, = dj. And if (t,p) is the basic cell in / among (l,p),(2,p), then t,p = dp - 1. Therefore for t = 1,2, we have ~2 dj if pfSt(/i) n o jES,(/i) tj - + 1 - t,n+l= j=EZ dj - 1, if p St(/) jSt(/i ) All the possibilities in this case are summarized in the following table. 4

Values of (. l,n+i,t2,n+1) Location of p Summary of Position (3,0) pESl(/31) ) I dj=w+l, dj=w-1 jES2(P1) jESi (i) peS2(A/) > dj= -2, >Z d,=j +2 jESi(fl) jES2 (,1) (2,1) pe S1(A) E dj:=, w dj- w jES2(/1) jESi(/1) p E S2(32) d = -1, >1 di 3= +1 2 2 jeSl(__) jES2 (31) (1,2) p ES1((1) Z dj = -1, d= 2+1 jES2(31) jESi (1i) p ES2(]_1) 1 dj =2, dj = 2 jEsl (Pa) jES2(?l) Hence I| dj - > djl _ 4 always, and therefore S1(/3i) is a solution for jESi (3i) jES2(a1) problem 2. To prove the converse, let S1 C {1,..., n} be a solution for problem 2. If > dj =2, jESi this case is covered by (ii) as discussed above. If E dj = - 1, let 32 be the basic set {(l,j): j E S1}U{(2,j): j V S1}U{(2,p), (1, n+ jESg 1), (2,n + 1)} where p is any element in the complement of Si. If > dj = w + 1, replace Si jESi by its complement and construct /2 exactly in the same way. It can be verified that /2 is a feasible basic set for (2), and in the BFS x = (xi) associated with it 1,n+1 = 2 and hence the cost of,/2 is -2a < 0. If E dj = t 2, let P3 bethebasicset {(l,j): j E S}U{(2,j): j V S1}U{(2,p),(1,n+ jESi 1), (2, n + 1)} where p is any element in the complement of S1. If EjEs, dj = + 2, replace S1 by its complement, and construct 33 exactly the same way. It can be verified that 3h is feasible to (2) and in the BFS x = (iij) associated with it -1,n+1 = 3 and hence the cost of /3 = -3a < 0. * Since problem 2 is NP-hard, by Theorem 1 it follows that problem 3 is NP-hard. Hence problem 1, of which problem 3 is a special case, is also NP-hard. Clearly, the decision problem version of problem 1 or 3 is also in NP, and hence it is NP-complete. 5

References 1. M.R. Garey and D.S. Johnson, Computers and Intractiability-A Guide to the Theroy of NP-Completeness, W.H. Freeman and Co., NY, 1980. 2. K.G. Murty, "A Fundamental Problem in Linear Inequalities with Applications to the Traveling Salesman Problem", Mathematical Programming, 2 (1972) 296-308. 3. K.G. Murty, Linear Programming, Wiley, NY, 1983. 4. M.H. Partovi, "Complexity of Identifying a Feasible Basic Vector Involving Specific Variables in a Transportation Problem", Technical Report, 1989 6