Solving Multidimensional 0-1 Knapsack Problem by P Systems with Input and Active Membranes

Solving Multidimensional 0-1 Knapsack Problem by P Systems with Input and Active Membranes Linqiang PAN1,2, Carlos MARTIN-VIDE2 1Department of Control Science and Engineering Huazhong University of Science and Technology Wuhan 430074, Hubei, People’s Republic of China E-mail: [email protected] 2Research Group on Mathematical Linguistics Rovira i Virgili University Pl. Imperial T`arraco 1, 43005 Tarragona, Spain Abstract. P systems are parallel molecular computing models based on processing multisets of objects in cell-like membrane structures. In this paper we give a membrane algorithm to multidimensional 0–1 knapsack problem in linear time by recognizer P systems with input and with active membranes using 2-division. This algorithm can also be modified to solve general 0–1 integer programming problem. 1 Introduction The P systems are a class of distributed parallel computing devices of a biochemical type, introduced in [4], which can be seen as a general computing architecture where various types of objects can be processed by various operations. It comes from the observation that certain processes which take place in the complex structure of living organisms can be considered as computations. Since Gh. P˘aun introduced it, computer scientists and biologists, et al. have contributed enriching the field with their different points of view. For a motivation and detailed description of various P system models, please refer to [4, 6]. Membrane division – inspired from cell division well-known in biology – is the most investigated way for obtaining an exponential working space in a linear time, and solving on this basis hard problems, typically NP-complete problems, in polynomial (often, linear) time. Details can be found in [5, 6, 11]. Recently, PSPACE-complete problems were also attacked in this way (see [13, 1]). In [8] P´erez-Jim´enez et al. solve satisfiability problem in linear time with respect to the number of variables and clauses of propositional formula by recognizer P systems with input and with active membranes using 2-division. Thus the multidimensional 0–1 knapsack problem belonging to the class of NP-complete problems can also be solved in a polynomial time by P systems with input and with active membranes using 2-division. One can get this kind of solution by the reduction of multidimensional 0–1 knapsack problem to 342 satisfiability problem in order to apply those P systems which solve satisfiability problem in a linear time. But the process of reduction is usually cumbersome and time consuming (polynomial time). On the other hand, it still remains open that how one can reduce an NP problem to another NP-complete problem by P systems. So, in this paper, we directly give a membrane algorithm to solve multidimensional 0–1 knapsack problem in linear time by recognizer P systems with input and with active membranes using 2-division. Here, we focus in the design of a family of P systems that solves multidimensional 0–1 knapsack problem, not in the formal verification of the membrane algorithm. As discussed in section 4, this algorithm is not difficult to be modified to solve the general 0–1 integer programming problem. The paper is organized as follows: in section 2 the notion of recognizer P system is introduced, which is the model of computation to solve multidimensional 0–1 knapsack problem, and the polynomial complexity class in computing with membranes is recalled; section 3 gives a membrane algorithm to solve multidimensional 0–1 knapsack problem in linear time by recognizer P systems with active membranes using 2-division; in section 4 some discussion is presented. 2 P Systems We start by introducing P systems with active membranes due to [5], where more details can also be found. Figure 1: A membrane structure and its associated tree ' & $ % ' & $ % # "Ã ! # "Ã ! ¾ ½ » ¼ ' & $ % ' & $ % º ¹ · ¸ 1 234 5 6 7 8t t ¶ ¶ ¶ ¶ ¶ SSSS Stt ¢ ¢ ¢ ¢ ¢ AAAAtt t t 1 2 3 4 5 6 7 8 Amembrane structure is represented by a Venn diagram and is identified by a string of correctly matching parentheses, with a unique external pair of parentheses; this external pair of parentheses corresponds to the external membrane, called the skin. A membrane without any other membrane inside is said to be elementary. For instance, the structure in Figure 1 contains 8 membranes; membranes 3, 5, 6 and 8 are elementary. The string of parentheses identifying this structure is µ= [1[2[5]5[6]6]2[3]3[4[7[8]8]7]4]1. All membranes are labeled; here we have used the numbers from 1 to 8. We say that the number of membranes is the degree of the membrane structure, while the height of the 343 tree associated in the usual way with the structure is its depth. In the example above we have a membrane structure of degree 8 and of depth 4. In what follows, the membranes can be marked with + or −, and this is interpreted as an “electrical charge”, or with 0, and this means “neutral charge”. We will write [i]+ i,[i]− i,[i]0 iin the three cases, respectively. The membranes delimit regions, precisely identified by the membranes (the region of a membrane is delimited by the membrane and all membranes placed immediately inside it, if any such a membrane exists). In these regions we place objects, which are represented by symbols of an alphabet. Several copies of the same object can be present in a region, so we work with multisets of objects. A multiset over an alphabet Vis represented by a string over V: the number of occurrences of a symbol a∈Vin a string x∈V∗(V∗is the set of all strings over V; the empty string is denoted by λ) is denoted by |x|aand it represents the multiplicity of the object ain the multiset represented by x. AP system with active membranes and 2-division is a construct Π = (O, H, µ, w1, . . . , wm, R), where: (i) m≥1 (the initial degree of the system); (ii) Ois the alphabet of objects; (iii) His a finite set of labels for membranes; (iv) µis a membrane structure, consisting of mmembranes, labelled (not necessarily in a one-to-one manner) with elements of H; (v) w1, . . . , wmare strings over O, describing the multisets of objects placed in the m regions of µ; (vi) Ris a finite set of developmental rules, of the following forms: (a) [ha→v]α h, for h∈H, α ∈ {+,−,0}, a ∈O, v ∈O∗ (object evolution rules, associated with membranes and depending on the label and the charge of the membranes, but not directly involving the membranes, in the sense that the membranes are neither taking part in the application of these rules nor are they modified by them); (b) a[h]α1 h→[hb]α2 h, for h∈H, α1, α2∈ {+,−,0}, a, b ∈O (communication rules; an object is introduced in the membrane, possibly modified during this process; also the polarization of the membrane can be modified, but not its label); (c) [ha]α1 h→[h]α2 hb, for h∈H, α1, α2∈ {+,−,0}, a, b ∈O (communication rules; an object is sent out of the membrane, possibly modified during this process; also the polarization of the membrane can be modified, but not its label); 344 (d) [ha]α h→b, for h∈H, α ∈ {+,−,0}, a, b ∈O (dissolving rules; in reaction with an object, a membrane can be dissolved, while the object specified in the rule can be modified); (e) [ha]α1 h→[hb]α2 h[hc]α3 h, for h∈H, α1, α2, α3∈ {+,−,0}, a, b, c ∈O (division rules for elementary membranes; in reaction with an object, the membrane is divided into two membranes with the same label, possibly of different polarizations; the object specified in the rule is replaced in the two new membranes by possibly new objects); (f) [h0[h1]α1 h1. . . [hk]α1 hk[hk+1 ]α2 hk+1 . . . [hn]α2 hn]α0 h0 →[h0[h1]α3 h1. . . [hk]α3 hk]α5 h0[h0[hk+1 ]α4 hk+1 ...[hn]α4 hn]α6 h0, for k≥1, n > k, hi∈H, 0≤i≤n, and α0, . . . , α6∈ {+,−,0}with {α1, α2}={+,−}; if the membrane with the label h0contains other membranes than those with the labels h1, . . . , hnspecified above, then they must have neutral charges in order to make this rule applicable; these membranes are duplicated and then are part of the contents of both new copies of the membrane h0 (division of non-elementary membranes; this is possible only if a membrane contains two immediately lower membranes of opposite polarization, + and −; the membranes of opposite polarizations are separated in the two new membranes, but their polarization can change; always, all membranes of opposite polarizations are separated by applying this rule). For a detailed description of using these rules we refer to [5, 6]. Here we only mention that the rules are used in the non-deterministic maximally parallel manner customary in membrane computing in the bottom-up manner: in any given step, one uses first the evolution rules of type (a), then the other rules which also involve a membrane; moreover, one uses first the rules of types (b), (c), (d), (e), and then those of type (f). It is important to note that at one step a membrane hcan be subject of only one rule of types (b)-(f). In this way, we get transition from a configuration of the system to the next configuration. A sequence of transitions is a computation. A computation is halting if no other rules can be applied in its last configuration. To understand what it means that a problem can be solved in polynomial time by P systems, it is necessary to recall some complexity measure for P systems as described in [9]. Consider a decision problem Aand denote by A(n) an instance of Aof size n. Given a class Xof membrane systems and a total function f:N→N(for example, linear and polynomial functions), we say that problem Abelongs to MCX(f) if a family of membrane systems ΠA= (ΠA(1),ΠA(2), . . .) of type Xexists such that: 1. ΠAis a uniform family: there is a Turing machine which constructs ΠA(n) in polynomial time starting from n. 2. Each ΠA(n) is confluent: there is a distinguished object yes such that either in every computation of ΠA(n) the object yes is send out from the system, or this happens in no computation. 345 3. ΠA(n) is sound: that is, ΠA(n) sends out the object yes if and only if the answer to ΠA(n) is “yes”. 4. ΠAis f-efficient: that is, ΠAalways halts in at most f(n) steps. The polynomial complexity classes associated with a family of membrane systems, X, are defined as follows: PMCX=[ fpolynomial MCX(f). In [6], the definition of these complexity classes is based on a semi-uniform construction of P systems solving a problem A: one starts not from n, but from an instance A(n). For a clearer description of the difference between uniform P systems and semi-uniform P systems, please refer to [7]. In what follows, we use recognizer P systems. First of all, following [7, 9] we consider P systems with input. Such a device is a tuple (Π,Σ, i0), where: – Π is a P system, with the alphabet of objects Γ and initial multisets w1,· · · , wm (associated with membranes labelled by 1,···, m, respectively). – Σ is an (input) alphabet strictly contained in Γ and such that w1,· · · , wmare multisets over Γ −Σ. –i0is the label of a distinguished membrane (of input). If wis a multiset over Σ, then the initial configuration of (Π,Σ, i0) with input wis (µ, w0 1,· · · , w0 m), where w0 i=wifor i6=i0, and w0 i0=wi0∪w. The computations of a P system with input are defined in a natural way. Note that the initial configuration is obtained by adding the input multiset wover Σ to the initial configuration of the system Π. Now, a recognizer P system is a P system with input, (Π,Σ, i0), such that: 1. The alphabet of objects contains two distinguished elements yes,no. 2. All computations of the system halt. 3. If Cis a computation of Π, then either the object yes or the object no (but not both) have to be sent out to the environment, and only in the last step of the computation. We say that Cis an accepting (respectively, rejecting) computation if the object yes (respectively, no appears in the environment in the halting configuration of C. 3 Solving Multidimensional 0–1 Knapsack Problem by Recognizer P Systems with Active Membranes 3.1 Problem Formulation The 0–1 Multidimensional Knapsack Problem (MKP) is a well known NP-complete combinatorial problem [2]. The decision MKP can be formulated as follows: given an integer k, an objective function f(x1,· · · , xn) = n P j=1 cjxj, and constraints n P j=1 wijxj≤bi, for i= 1,···, m,xj∈ {0,1}, for j= 1,· · · , n, where cj,wi,j and biare nonnegative integers, 346 decide whether or not there exists an assignment of variables xjsuch that it satisfies the constraints and the objective function is greater than or equal to k. MKP is an important combinatorial optimization problem both from a theoretic and practical point of view, which can formulate many practical problems such as capital budgeting where project jhas profit cjand consume (wij) units of resource i. The goal is to determine a subset of the nprojects such that the total profit is maximized and all resource constrains are satisfied. Other important applications include cargo loading [12] cutting stock problems, and processor allocation in distributed systems [3]. The special case of MKP with m= 1 is the classical knapsack problem (KP). It is well known that the KP is not strongly NP-hard because there are polynomial approximation algorithms to solve it. This is not the case for the general MKP. In the framework of cellular computing, a membrane algorithm to solve KP is developed [10]. In the next subsection, we will give membrane algorithm for the general MKP. 3.2 Membrane Algorithm for Multidimensional 0–1 Knapsack Problem We present a solution of MKP via a brute force algorithm, in the framework of recognizer P systems with active membranes using 2-division. Given an instance uof MKP as shown in the above subsection, for convenience, we call n P j=1 wijxj≤bi(1 ≤i≤m) the ith constraint inequality, and n P j=1 cjxj≥kthe (m+ 1)th inequality. Let us consider a polynomial bijection, h i, between N∗l(l≥2) and N∗, defined as follows: hy1, y2i= (y1+y2)(y1+y2+ 1)/2 + y1,hy1, y2, y3i=hhy1, y2i, y3i, and hy1,· · · , yl−1, yli=hhy1,· · · , yl−1i, yli, where N∗denotes the set of nonnegative integers. We define the size function h(u) = hn, k, b1,···, bmi, and the input function g(u) = xw11 1,1xw21 2,1· · · xwm1 m,1xc1 m+1,1· · · xw1n 1,n xw2n 2,n · · · xwmn m,n xcn m+1,n, where the first subscript iof xi,j denotes the ith inequality, the second subscript jof xi,j corresponds to the variable xj. For each hn, k, b1,· · · , bmi, we consider the recognizer P system (Π(hn, k, b1,· · · , bmi),Σ(hn, k, b1,· · · , bmi), i0), where Σ(hn, k, b1,· · · , bmi) = {xi,j |1≤i≤m+ 1,1≤j≤n},i(hn, k, b1,···, bmi) = 2 and Π(hn, k, b1,· · · , bmi) = (Γ(n, k, b1,· · · , bm),{1,2},[1[2]2]1, w1, w2, R), Γ(n, k, b1,···, bm) is defined as follows: Γ(m, n) = Σ(hn, k, b1,· · · , bmi)∪ {di|1≤i≤3n+ 2 m X i=1 bi+ 3m+ 2k+ 1} ∪ {ri,j, si,j |1≤i≤m, 1≤j≤2n}∪{ai,j, ti,j |1≤i≤m, 0≤j≤2n} ∪ {qi,j |0≤i≤2 max{b1,· · · , bm}+ 1,1≤j≤m} ∪ {qi,m+1 |0≤i≤2k+ 1}∪{d+, d−, e0, λ, yes,no}. The initial content of each membrane is: w1=∅and w2=d1ab1 1,0ab2 2,0· · · abm m,0tk m+1,0. The set of rules, R, is given by (we also give explanation about the use of these rules during the computations): 1. [2di]0 2→[2di]+ 2[2di]− 2,1≤i≤n. By using a rule of (1), a membrane with label 2 is divided into two membranes with the same label, but with different polarizations. These rules allow us to have exponential workspace in linear time. 347 2. [2xi,1→ri,1]+ 2, 1 ≤i≤m. [2xm+1,1→sm+1,1]+ 2. [2xi,1→λ]− 2, 1 ≤i≤m+ 1. The rules of (2) try to implement a process allowing membranes with label 2 to encode the assignment of the variable x1, in such a way that if the variable x1 takes value 1, then the objects xi,1(1 ≤i≤m) evolve to objects ri,1, and the objects xm+1,1evolve to objects sm+1,1, in the corresponding membranes with label 2 and positive charge; otherwise, the objects xi,1will disappear in the corresponding membranes with label 2 and negative charge. 3. [2xi,j →xi,j−1]+ 2, 1 ≤i≤m+ 1, 2 ≤j≤n. [2xi,j →xi,j−1]− 2, 1 ≤i≤m+ 1, 2 ≤j≤n. The evolving process described previously is always made with respect to the variable x1. Hence, the rules of (3) take charge of making a cyclic path through all the variables to get that, initially, the first variable is x1, then x2, and so on. 4. [2di]+ 2→[2]0 2di, 1 ≤i≤n. [2di]− 2→[2]0 2di, 1 ≤i≤n. di[2]0 2→[2di+1]0 2, 1 ≤i≤n−1. The rules of (4) are used as controllers of the generating process of the assignments of all variables and the encoding of the coefficients: the objects diare sent to the membrane with label 1 at the same time the assignments are made, and they come back to the membranes with label 2 to start the division of these membranes. 5. [2ri,j →ri,j+1]0 2, 1 ≤i≤m, 1 ≤j≤2n−1. [2sm+1,j →sm+1,j+1]0 2, 1 ≤j≤2n−1. [2ai,j →ai,j+1]0 2, 1 ≤i≤m, 0 ≤j≤2n−1. [2tm+1,j →tm+1,j+1]0 2, 0 ≤j≤2n−1. The use of objects r1,2n, a1,2n, sm+1,2n, tm+1,2nin the rules (8), (11) and (14) makes necessary to perform a rotation of these objects. This is the mission of the rules of (5). 6. [1di→di+1]0 1,n≤i≤3n−3. [1d3n−2→d3n−1e0]0 1. Through the counter-objects di, the rules of (6) control the rotation of the objects ri,j,sm+1,j,ai,j and tm+1,j in the membranes with label 2, so that their second subscripts are unified to 2n. 7. e0[2]0 2→[2q0,1]− 2. [1d3n−1→d3n]0 1. The application of the rules of (7) will show that the system is ready to check whether the constraint inequalities are satisfied by the assignment of variables encoded by an internal membrane. 8. [2r1,2n]− 2→[2]0 2λ. [2a1,2n]0 2→[2]− 2λ. These rules implement the comparison (that is, they check whether the constraint inequality holds or not). They work as a loop that erases objects r1,2nand a1,2n one by one alternatively, changing the charge of the membrane in each step. We 348 will see that if the checking had an affirmative result, then the membrane would get positively charged, and the checking of the next inequality will be activated. 9. [2q2j,i →q2j+1,i]− 2, for j= 0,· · · ,max{b1,· · · , bm}, 1 ≤i≤m. [2q2j+1,i →q2j+2,i]0 2, for j= 0,· · · ,max{b1,· · · , bm} − 1, 1 ≤i≤m. A counter that controls the previous loop is described here. The subscript of qj,i and the electric charge of the membrane give enough information to point out if the number of objects ri,2nis not greater than (less than or equal to) the number of objects ai,2n. 10. [2q2j+1,i]− 2→[2]+ 2q0,i+1, for j= 0,· · · ,max{b1,· · · , bm}, 1 ≤i≤m. If an assignment verifies the ith constraint inequality, then inside the corresponding membrane that encodes it there will not be more objects ri,2nthan ai,2n. This forces the loop described in (9) to stop: the moment will come when there are no objects ri,2nleft, and then the rule [2q2j,i →q2j+1,i]− 2will be applied but it will not be possible to apply the rule [2r1,2n]− 2→[2]0 2# at the same time. Thus, an object q2w(i)+1 will be present in the membrane with negative charge, where w(i) = n P j=1 wij, so the rule (10) will be applied. 11. [2ri,2n→ri−1,2n]+ 2, for 2 ≤i≤m. [2ai,2n→ai−1,2n]+ 2, for 2 ≤i≤m. [2si,2n→si−1,2n]+ 2, for 2 ≤i≤m+ 1. [2ti,2n→ti−1,2n]+ 2, for 2 ≤i≤m+ 1. The comparison process described in the rules of (8) is always made with respect to the first constraint inequality. Hence the rules of (11) take charge of making a cyclic path through all the constraint inequality. (for the objective function inequality, we have different comparison process, as shown later in rules of (14), (15) and (16).) 12. q0,i+1[2]+ 2→[2q0,i+1]− 2, for 1 ≤i≤m−1. The membranes with positive charge mean that the assignments encoded by them have verify the first iconstraint inequality. The objects q0,i+1 enter the membranes with the label 2 and positive charge, changing the charge to negative to allow the checking for next inequality to begin (using rules of types (8), (9), (10)). 13. q0,m+1[2]+ 2→[2q0,m+1]+ 2. If there is at least one assignment which verify all the constraint inequalities, then objects q0,m+1 appear in the skin membrane. In the next step, by the rule of (13), these objects enter the membranes with label 2 and positive charge. At the same time, the objects s1,2nand t1,2nappear in the membranes encoding assignments which verify all the constraint inequalities (using rules of (11)). Now the system is ready for checking the objective function inequality. 14. [2s1,2n]+ 2→[2]0 2λ. [2t1,2n]0 2→[2]+ 2λ. The checking loop is designed for objective function as rules of (8) for constraint inequalities, but the electric charges involved are now neutral and positive. 15. [2q2j,m+1 →q2j+1,m+1]+ 2, for j= 0,· · · , k. [2q2j+1,m+1 →q2j+2,m+1]0 2, for j= 0,· · · , k −1. The counter qj,m+1 controls the previous loop described in the rules of (14). 349 16. [2q2k+1,m+1]+ 2→[2]0 2yes. [2q2k+1,m+1]0 2→[2]0 2yes. If an assignment verifies the objective function inequality, then in the membrane encoding this assignment there are not less objects s1,2nthan objects t1,2n. This causes the rules from (15) to apply ktimes each, and after that the first subscript of qj,2nwill be j= 2k. Then the rule [2q2j,m+1 →q2j+1,m+1]+ 2will be applied (possibly together with [2s1,2n]+ 2→[2]0 2λ) and one of the rules from (16) will produce the object yes reporting that this assignment verifies the objective function inequality. 17. [1di→di+1]0 1, for i= 3n, · · · ,3n+ 2 m P i=1 bi+ 3m+ 2k+ 1. [1dl→d+d−]0 1, where l= 3n+ 2 m P i=1 bi+ 3m+ 2k+ 1. Before the answer is sent out to the environment, all of the membrane should have either ended their checking stage successfully (checking the constraint inequalities and objective function inequality) or got to a blocking state otherwise. The counter djgives enough time to deal with the worst case. The condition for worst case (i.e. the case that the checking stage will last longer) is that the assignment with all variables taking value 1 is a solution (i.e. it verifies the constraint inequalities and the objective function inequality). The number of computational steps will be maximum if n P j=1 wij =bi, for i= 1,· · · , n. 18. [1d+]0 1→[1]+ 1d+. [1d−→no]+ 1. [1yes]+ 1→[1]0 1yes. [1no]+ 1→[1]0 1no. The output process is activated. The skin membrane needs to be positively charged before the answer is send out to the environment. Object d+takes charge of this, and, then, if the answer is affirmative, an object yes will be sent out changing the charge of the skin to neutral. Otherwise, an object no will be sent out changing the charge of the skin to neutral. From the previous explanation of the use of rules, one can easily see how this P system works. It is easy to prove that the designed P system is deterministic, confluent, and sound. The family is polynomially uniform by Turing machines. It can be observed that the above description of the evolution rules is computable in an uniform way, in particular from the constants n,m,k, and bi,i= 1,···, m. Now, we prove that the family Π= (Π(t))t∈Nsolves the MKP in linear time. The computational process of the designed P system with input g(u) can be structured in four stages: a stage of generation of all assignments of variables; a stage of synchronization; a stage of checking whether there is an assignment which satisfies the constraint inequalities and the objective function inequality; and a stage of output. The generation is controlled by the objects di, with 1 ≤i≤n. – The presence in the skin of one object di, with 1 ≤i≤n, will show that all possible partial assignments associated with {x1,· · · , xi}have been generated. 350