Solving the Bin-Packing Problem by Means of Tissue P System with 2-Division

Solving the Bin-Packing Problem by Means of Tissue P System with 2-Division Hepzibah A. Christinal1, Rose Rani John1, D. Abraham Chandy1, and Miguel A. Guti´errez-Naranjo2 1Karunya University, Coimbatore, Tamilnadu, India [email protected], [email protected], [email protected] 2Department of Computer Science and Artificial Intelligence, University of Seville, 41012 Seville, Spain [email protected] Abstract. The ability of tissue P systems with 2-division for solving NP problems in polynomial time is well-known and many solutions can be found in the literature to several of such problems. Nonetheless, there are very few papers devoted to the Bin-packing problem. The reason may be the difficulties for dealing with different number of bins, capacity and number of objects by using exclusively division rules that produce two offsprings in each application. In this paper we present the design of a family of tissue P systems with 2 division which solves the Bin-packing problem in polynomial time by combining design techniques which can be useful for further research. 1 Introduction Membrane computing was born from the assumption that the processes taking place within the compartmental structure of a living cell can be interpreted as computations [26]. From the beginning, the computational complexity of the membrane algorithms has been a vivid research area [25]. In particular, there is a large amount of papers dealing with the P versus NP problem in the framework of membrane computing [22]. The P versus NP problem is one of the most important unsolved problem in computer science and it was chosen as one of the seven Millennium Prize Problems [11]. The precise statement of the problem was introduced in 1971 by Stephen Cook [1], although it was essentially mentioned in a personal communication between G¨odel and von Neumann [10]. The problem of deciding whether P and NP complexity classes are same or not is not yet solved but the efforts for solving it have contributed to the development of new research areas full of interesting open questions. One of them is the research of frontiers of tractability, i.e., to identify some features of the computational models such that the corresponding device is able to solve NP problems or not depending on the endowment of such features. In membrane computing there exists an extensive literature devoted to this type of problem (see [22] and the references therein) and the present paper is a novel contribution in such research line. We consider here a variant of one of the most popular P systems architectures: tissue P systems. Such model was firstly presented in [16,17] by placing the cells in a general graph instead of a tree-like graph as in the cell-like model. Under the hypothesis P=NP, Zandron et al. [33] established the limitations of P systems that do not use membrane division concerning the efficient solution of NP-complete problems. From this premise, P˘aun et al. presented in [28] the model of tissue P systems endowed with cell division, which can solve NP-problems. Since then, many other variants have been presented, e.g., [6,12,13,18,19]. In this way, all solutions of NP-complete problems in membrane computing rely on the possibility of P systems to obtain exponential space in polynomial time1. Besides creating an exponential amount of cells in polynomial time, to solve NP-complete problems, we need to be able to effectively use that workspace, by making objects interact. For instance, it is known that, even with membrane division, without polarizations and without dissolution only problems in Pmay be solved [9]. The cell division proposed in [28] was inspired in the mitosis of alive cells and consists on the division of one cell into two offsprings. The most extended use of this type of rules is obtaining an exponential amount of cells in linear time, since 2ncells can be obtained from an initial one after nsteps. The ability of tissue P systems with 2-division for solving NP problems is well known [19], nonetheless, the study of new problems requires the effort of solving specific designs which, on the one hand, makes stronger the theory and on the other hand, can provide new ideas for unsolved problems in membrane computing. In particular, the design of a solution for the Bin-packing problem by using 2- division presents important subproblems whose solution can be useful for further development of the theory. The intrinsic difficulty of this problem explains that there are very few papers [23,24] devoted to this problem in the vast literature of solutions for NP problems in membrane computing. The problem can be stated as follows: Given a set A={s1,...,s n},a weight function ω:A→Nand two constants b∈N,c∈Ndecide whether or not there exists a partition of Ainto bsubsets such that their weights do not exceed c.The traditional strategy for designing a solution of an NP-problem has a first stage where an exponential amount of cells is created and each feasible candidate to be a solution is placed into one of the exponential amount of available cells. In the Bin-packing problem, this generation of feasible candidates consists on considering all the possibilities for distributing the nobjects among the bbins. This means that bnfeasible candidates should be encoded in the corresponding multisets and placed into bndifferent cells. The 2-division proposed in [28] fits perfectly when the exponential growth of the number of candidates is on basis 2, as in the SAT problem (e.g., [2,7]) or the Partition problem [5,8] or even on basis 3 by performing a new division on 1Such solutions are technically correct, but, of course, the exponential generation of new working space has evident limits from a practical point of view. Any practical implementation of P systems solving NP-problems with physical support only could solve small instances of the problem. one of the offsprings, as in the 3-COL problem [4]. In our case, the problem is different, since the number of necessary membranes depends on the parameter b. In this way, the designed family of tissue P systems must be able to build bn membranes in polynomial time on band nfor each band nby using 2-division. This leads us to solve two subproblems: The first one is place each of the n objects in one of the bbins (if the distribution condition of objects is satisfied). This means that we need to represent each of the symbols in {0,...,b−1}with a 2-division process for each object siwith i∈{1,...,n}. And the second problem is to implement such distribution of nobjects, one for each object in the set A. In the next sections, we explain the details of the corresponding solutions. The paper is organized as follows. In Sect. 2, the formal description of the used model of P systems is recalled. Section 3is devoted to the main ideas related to recognizer P systems, the framework for solving decision problems. Our solution is presented in Sect. 4and the paper ends with some conclusions and hints for future work. 2 Tissue P Systems with Cell Division In the first definition of the model of tissue P systems [16,17] the membrane structure did not change along with the computation. Based on the biological mitosis,P˘aun et al. presented in [28] a tissue P system model endowed with 2-division is one of the most used and well-known P system models nowadays. We briefly recall their syntax and semantics. Formally2,atissue P system with cell division of degree q≥1 is a tuple of the form Π=(Γ, E,Σ,w 1,...,w q,R,i in,i out), where: 1. Γis a finite alphabet, whose symbols will be called objects. 2. E⊆Γis the alphabet of the environment. 3. Σ⊂Γis the input alphabet. 4. w1,...,w qare strings over Γ. 5. Ris a finite set of rules of the following form: (a) Communication rules:(i, u/v, j), for i, j ∈{0,1,2,...,q},i=j,u, v∈Γ∗. (b) Division rules:[a]i→[b]i[c]i, where i∈{1,2,...,q}and a, b, c ∈Γ. 6. iin,i out ∈{0,1,2,...,q}are the input and output labels, respectively. A tissue P system with cell division of degree q≥1 can be seen as a set of q cells (each one consisting of an elementary membrane) labelled by 1,2,...,q.We shall use 0 as the label of the environment, and iin and iout denote, respectively, the input and output regions (which can be a region inside a membrane or the environment). 2The reader is supposed to be familiar with the basic concepts of membrane computing. See [29] for details. The communication rules determine an implicit net of channels, where the nodes are the cells and the edges indicate if it is possible for pairs of cells to communicate directly. This is a dynamic graph, in which new nodes can be produced by the application of division rules. Note also that the connections only depend on the label of the cell, and thus when a cell is divided, the two new cells will have identical connections. Nevertheless, this graph is just an intuition, we shall not handle it explicitly along the computations. The strings w1,...,w qdescribe the multisets of objects placed in the qcells of the system. We interpret that E⊆Γis the set of objects placed in the environment, each one of them in an arbitrary large amount of copies. The communication rule (i, u/v, j) can be applied over two cells iand jsuch that uis contained in cell iand vis contained in cell j. The application of this rule means that the objects of the multisets represented by uand vare interchanged between the two cells. The division rule [a]i→[b]i[c]ican be applied over a cell icontaining object a. The application of this rule divides this cell into two new cells with the same label. All the objects in the original cell are replicated and copied in each of the new cells, with the exception of the object a, which is replaced by the object b in the first new cell and by cin the second one. Rules are used as usual in the framework of membrane computing, that is, in a maximally parallel way. In one step, each object in a membrane can only be used for one rule (non-deterministically chosen when there are several possibilities), but any object which can participate in a rule of any form must do it, i.e., in each step we apply a maximal set of rules. This way of applying rules has only one restriction when a cell is divided, the division rule is the only one which is applied for that cell in that step; the objects inside that cell do not evolve in that step. 3 Recognizer P Systems The notion of recognizer P system is general enough to cover many P system variants. Such P systems are a well-known model of P systems which are basic for the study of complexity aspects in membrane computing. Roughly speaking, a recognizer P system is a P system which takes some information as input and outputs a distinguished object which can be considered as a decision on the input. Of course, some other conditions are imposed, but the general framework does not depend on the type of rules or the membrane structure of the P system. Next, we briefly recall some basic ideas related to them. A detailed description, is given in [21,22]. In recognizer P systems all computations halt; there are two distinguished objects traditionally called yes and no (used to signal the result of the computation), and exactly one of these objects is sent out to the environment (only) in the last computation step. Let us recall that a decision problem Xis a pair (IX,θ X) where IXis a language over a finite alphabet (the elements are called instances)andθXis a predicate (a total Boolean function) over IX.LetX=(IX,θ X) be a decision problem. A polynomial encoding of Xis a pair (cod, s) of polynomial time computable functions over IXsuch that for each instance w∈IX,s(w)isa natural number representing the size of the instance and cod(w) is a multiset representing an encoding of the instance. Polynomial encodings are stable under polynomial time reductions. Let Rbe a class of recognizer P systems with input membrane. A decision problem X=(IX,θ X) is solvable in a uniform way and polynomial time by a family Π=(Π(n))n∈Nof P systems from R– we denote this by X∈PMCR– if the family Πis polynomially uniform by Turing machines, i.e., there exists a polynomial encoding (cod, s)fromIXto Πsuch that the family Πis polynomially bounded with regard to (X, cod, s); this means that there exists a polynomial function psuch that for each u∈IXevery computation of Π(s(u)) with input cod(u) is halting and, moreover, it performs at most p(|u|) steps; the family Π is sound and complete with regard to (X, cod, s). 4 The Solution to Bin Packing Problem In this section we provide a family of tissue P systems with 2-division which solves the Bin-packing problem in polynomial time. Before giving the formal description of the P system, we provide some hints about how the problem has been solved. As pointed out in the Introduction, each of the nobjects can potentially be placed on one of the bbins. In such way, bncandidates (and hence bncells) should be built in polynomial time by using 2-division. The solution needs the preprocess of the parameter m, where mis the least integer which satisfies b≤2m, i.e., m=log2b. In the same way, by generating 2mcells with m2-division steps we can assure that at least bcells are generated. The idea of considering a number of logarthmic steps is not new in the design of membrane computing solutions (see, e.g., [3]). Nevertheless, the mere generation of b(or more) cells are not enough. Each object siof the set A={s1,...,s n}must be placed in one of the bins {0,...,b−1}, where each membrane encoding a different bin has been generated by 2-division. In this way, the natural encoding of each number in {0,...,b−1}is performed by a binary representation Cm−1Cm−2...C 0where3 Ci∈{Ti,F i}for i∈{0,...,b−1}. In this way, each 2-division will produce an object Tior Fiin each offspring and the value iwill control the number of the division in the iterative process of building 2mcells. This process will be controlled by the set of rules R1 (see below). From the 2mgenerated cells, only bof them are necessary in our solution. The remaining 2m−bcells (if any) will remain inactive. This means that we only need rules for control bdifferent values {0,...,b−1}. Such values are originally represented via a binary representation by using mobjects. Nonetheless, for the sake of readability, in our solution we propose to take a decimal representation by a unique symbol object bjwith j∈{0,...,b−1}. The trick for recovering such notation is controlled by the set of rules R2 (see below). 3Tiand Fistand for True and False in the i−th position and, as usual, represents 1 and 0 in a binary representation. The key idea of such set of rules consists of keeping in each cell of label 1 an object bkwhich acts as an accumulator in the index i(with b0at the beginning). The different values of the binary representation Cm−1Cm−2...C 0 with Ci∈{Ti,F i}arrive sequentially to the cell: – If the object Tiarrives and k+2 idoes not exceed the value b−1 then, the objects Tiand bkare traded against a new object bk+2i.Ifk+2 i≥b, then the corresponding membrane does not encode one of the possible bins (enumerated from 0 to b−1) and it stays inactive during the remaining computation steps. – If the object Fiarrives, nothing is added to the accumulator and the object bkdoes not change. Bearing in mind these considerations, the proposed solution can be split in to the following stages: –Generation and Calculation stage: In this stage the bncandidates for solution are generated (each of the nobjects in A={s1,...,s n}can go to one of the bbins). For each si,2m+ 3 steps are performed and the number of steps in this stage is O(m·n). During the generation stage, the process of assigning an object sito a bin is performed ntimes. After each assignment, the free capacity of the corresponding bin (represented by objects pj) is decreased in an amount equal to the weight w(si) if it is possible. This decrement is performed by the set of rules R4 which send pairs of objects representing unit of weights and units of free capacity to the environment. If there is no free capacity enough for such assignment, some objects representing weights will not be sent to the environment. –Checking stage: This stage is performed in parallel in the all bncells which represent candidates (let us recall that the 2m−bcells extra generated in each construction process keep inactive). This stage consists on checking if all the objects representing weights have been sent to the environment. If there is no such objects in the corresponding cell, then the candidate placed in such membrane represents a solution to the Bin-packing problem. Otherwise, if there is one or more object in the cell, then the assignment of objects to cells does not satisfy the restriction and it is not a solution to the problem. –Output stage: Finally, the output stage controls that only one object yes or only one object no is sent to the output cell in the last step of computation. Each instance of the Bin-packing Problem is stated by a set of nobjects, A={s1,...,s n}, a set of weights ω(A)={ω(s1),...,ω(sn)}and two constants b∈N(the number of bins) and c∈N(the capacity). We propose a family of tissue P systems with 2-division which solves the Bin-packing Problem where each tissue P system of the family depends on the parameters n,band c. For the sake of simplicity, we will consider a pre-computed extra parameter m=log2b which only depends on b. Let us notice that the set of objects A={s1,...,s n} is encoded as the multiset sw(s1) 1,...,s wsn n, i.e., the weight of the object siis represented in its multiplicity. Such multiset is placed in the input cell in the initial configuration and the computation starts. Each tissue P system of the family is of the following form4: Π(n, b, c, m)=(Γ, E,Σ,w 1,w 2,R,i in,in out) where: –Γis the alphabet of objects used in the computation Γ=E∪Σ∪{A0,b 0,d 1,z 1,x 0}∪{pi:i∈{0,...,b−1}} –Eis the set of objects initially placed in the environment. E={yes,no,g,f 0,f 1,y 0,y 1,#} ∪{Ti,k iki,r i:i∈{0,...,m−1}} ∪{Ai:i∈{0,...,m}} ∪{bi:i∈{0,...,b−1}} ∪{qi,h i:i∈{0,...,b−1}} ∪{zi,d i:i∈{2,...,n}} ∪{xi:i∈{1,...,n∗(2m+3)+1} ∪{ki,j :i∈{0,...,b−1}j∈{0,1}} –Σ={si:i∈{1,...,n}} is the input alphabet. – Initially, the initial configuration has only two cells. The initial multisets are w1=A0b0d1zc 1pc 0...p c b−1and w2=x0,1 – The following are the set of rules R: R1. [Ai]1→[Ti]1[Fi]1:0≤i≤m−1 These rules control the generation of new membranes by division. Since b≤2m, it is guaranteed that after mapplications of 2-division rules, the number of membranes is enough for encoding bbins. Each of the offsprings has an object Tior Fiof the corresponding number in binary encoding. Cm−1Cm−2...C 0with Ci∈{Ti,F i}. R2. (1,T ibk−2i/bkAi+1,0) : 0 ≤i≤m−1,0≤k≤min{b−2i,2i}−1 (1,F i/Ai+1,0) : 0 ≤i≤m−1 As pointed out above, the binary number Cm−1Cm−2...C 0with Ci∈{Ti,F i} is not stored in such form in the cells. Each cell with label 1 has an object bk(initially b0) which can be considered as an accumulator for the decimal representation of the number Cm−1Cm−2...C 0with Ci∈{Ti,F i}. If a new object Tiarrives to the cell by the application of a division rule, then Tiand bkare traded against one object bk+2iif bk+2iis the index of one of the bins, 4As usual, we omit the parameters in the description for the sake of readability. i.e., if it belongs to {0,...,b−1}. Let us remark that the application of the rule also brings an object Ai+1 and the cell is prepared for a new division. If k+2 i≥b, then the rule is not applied, the object Ai+1 is not brought into the cell and the cell remains inactive. If an object Fiarrives, the accumulator bkis not modified. R3. (1,A mbr/qc rkr,0):r∈{0,...,b−1} When the object Amarrives to a cell 1, the calculus of brhas finished. This means that the corresponding object sifrom A={s1,...,s n}is placed on the r−th bin. In order to help in the subtraction of the weight of the object sifrom the free capacity of the bin r,cobjects qrare brought into the cell. An object kr,0is also brought for technical reasons. R4. (1,z isiqrpr/#) : i∈{1,...,n}r∈{0,...,b−1} This set of rules is the key in the calculus of the total weigh associated to each bin. Its usage exploits the massive parallelism of P systems and the maximal application of the rules. Let us notice that in each application of the rule only one object of the four kind zi,si,qrand pris sent out of the cell, so the number of applications correspond to the minimum of amounts of these objects. Since there are exactly cobjects of type ziand qr, the number of applications corresponds to the minimum between the multiplicities of si and pr. Let us remark that if the weight of the object si(encoded in their multiplicity) is greater than the free capacity of the r-th bin (encoded in the multiplicity of objects pr) then at least one object siwill remain in the cell after the application of these rules. R5.(1,k r,0/hc r,k r,1,0) (1,h rqr/#,0) for r∈{0,...,b−1}. These rules can be considered as cleaning rules. After the subtraction performed by the set of rules R4, the leftovers objects qr(if any) must be sent out of the cells with label 1 in order to avoid undesired interactions. This is the technical reason of the objects kr,0and kr,1. R6.(1,k r,1di/A0b0zc i+1 di+1,0) : i∈{1,...,n−1}r∈{0,...,b−1} (1,k r,1dn/f0g,0) : r∈{0,...,b−1} When the object kr,1appears in a cell with label 1, the cleaning process performed by the set of rules R5 has finished and the cell is prepared for starting the process of a new object si+1 This set of rules R6 brings the objects A0and b0for starting newly the division together with the objects zi+1 and di+1. When all the objects si,i∈{1,...,n}are processed, the objects f0and gare brought into the cells 1 which remain active. R7.(2,x i/xi+1,0) : 0 ≤i≤n∗(2m+3)−1 (2,x n∗(2m+3)/xn∗(2m+3)+1,y 0,0) The objects xiin the cell 2 act as a counter. When it reaches xn∗(2m+3)+1,a new object y0is also brought into the cell 2 for controlling the output process. R10.(1,gs i/#,0) : i∈{1,...,n} (1,f 0/f1,0) (1,f 1g/xn∗(2m+3)+1,2) (2,y 0/y1,0) (2,g,y 1/yes, 0) (2,x n∗(2m+3)+1 no, 0) These rules control the output process. Two cases must be considered: •Case 1: In all the active cells with label 1, there is at least one object si. This means that all the possible assignment of objects to bins exceed the capacity. In this case, a rule (1,gs i/#,0) is applied in such membranes and gis sent out to the environment, the rule (1,f 1g/xn∗(2m+3)+1,2) is not applied and finally, the rule (2,x n∗(2m+3)+1 no, 0) sends an object no to the cell with label 2. •Case 2: There is at least one of the cells with label 1, where there are no objects si. This means that all the assignment of objects encoded in such membrane does not exceed the capacity and it represents a solution for the problem. In this case, a rule (1,gs i/#,0) is not applied in such membrane and, in the next step of computation, the rule (1,f 1g/xn∗(2m+3)+1,2) is applied, the object gis sent to the cell with label 2 and finally, the application of (2,g,y 1/yes, 0) sends an object yes to the output cell. – Finally, the input cell has label 1, iin = 1 and the output cell has label 2, iout =2. 4.1 A Short Overview Next, we provide some hints on the computation. The initial configuration C0 contains an object A0which starts the division process, an object b0which works as an accumulator initially set to 0 and objects d1and z1, where the index a denotes that the first object in the set A={s1,...,s n}will be process at the beginning. According to the process described above, the cells with label 1 are divided and, in parallel, the counted bris increased. The configuration C2m contains an object Amand an object brencoding that the first object of the set Ais placed into the r-th bin. In the next three steps, rules from the sets R3,R4 and R5 perform the subtraction between the weight of the processed object and the free capacity of the r-th bin (represented by the multiplicity of the object pr). The first set of rules from R6 is also applied and in C2m+3 the corresponding cells 1 contain new objects A0and b0and objects d2and z2, denoting that the second object of the set Awill be processed. This sequence of 2m+ 3 steps is repeated ntimes (as many times as objects in A). In the configuration Cn∗(2m+3) all the objects in Ahave been processed and the objects f0and gappear. Only three steps later, in output stage with two possible cases described above, the halting configuration Cn∗(2m+3)+3 is reached. 4.2 Computational Resources Each tissue P system of the family described above depends on three parameters: n, the number of object to distribute among the bins; c, the capacity of the bins;