A branch and bound technique for finding the minimal solutions of the linear optimization problems subjected to Lukasiewicz

In this paper, an optimization model with a linear objective function subject to a system of fuzzy relation equations (FRE) is studied where the feasible region is defined by the Lukasiewicz t-norm. Since the finding of all minimal solutions is an NP-hard problem, designing an efficient solution procedure for solving such problems is not a trivial job. Firstly, the feasible domain is characterized and then the problem is solved with a modified branch-and-bound solution technique based on a new solution set that includes the minimal solutions. After presenting our solution procedure, a concrete example is included for illustration purposes.


I. INTRODUCTION
In this paper, we study the following linear problem in which the constraints are formed as fuzzy relational equations defined by Lukasiewicz t-norm: (1) Where , , is a fuzzy matrix such that ( and ), is a fuzzy vector such that ( ), and " " is the Lukasiewicz t-norm defined by . If is the 'th row of matrix , then problem (1) can be expressed as follows: where the constraints mean: The theory of fuzzy relational equations (FRE) was firstly proposed by Sanchez and applied in problems of the medical diagnosis [13]. Nowadays, it is well known that many issues associated with a body knowledge can be treated as FRE problems [12]. The solution set of FRE is often a non-convex set that is completely determined by one maximum solution and a finite number of minimal solutions [4]. The other bottleneck is concerned with detecting the minimal solutions that is an NP-hard problem [5,7,8,10]. The problem of optimization subject to FRE and FRI is one of the most interesting and on-going research topics among the problems related to FRE and FRI theory [1,2,[4][5][6][7][8]11,14]. Recently, many interesting generalizations of the linear programming subject to a system of fuzzy relations have been introduced and developed based on composite operations used in FRE, fuzzy relations used in the definition of the constraints, some developments on the objective function of the problems and other ideas [3,[7][8][9]11].
In this paper, after carefully study the solution set of system (1), we show that the problem can be converted to a 0-1 integer programming problem and solved by a branch-andbound method.
The rest of the paper is arranged as follows. In Section 2, a special characterization of the feasible domain of problem (1) is derived. Based on the theoretical aspects of the problem, a new solution set is obtained that includes all the minimal solutions. In Section 3, we study the effect of the cost vector c with the special characterization. A modified branch-andbound method is presented and a step-by-step algorithm for solving problem (1) is given in Section 4. Some examples are included in Section 5 to illustrate how the algorithm works. Some concluding remarks are made in Section 6.

III. LINEAR PROGRAMMING AND EFFECT OF COST VECTOR
According to the well-known schemes used for optimization of linear problems such as (1) [5,10], problem (1) is converted to the following two sub-problems: And, where and for . It is easy to prove that is the optimal solution of , and the optimal solution of is for some .

Theorem 2.
Suppose that and and are the optimal solutions for and , respectively. Then is an optimal solution of problem (1), where is defined as follows: for .

Proof.
Let . Then, from Corollary 4 we have . Therefore, for each such that , inequality implies . In addition, for each such that , inequality implies . Hence, .  As mentioned earlier, generating the maximum solution is not a problem. If we know how to find a minimum solution for , then problem (1) can be solved via Theorem 2. In the next section, we provide a branch and bound method for solving .

IV. MODIFIED BRANCH AND BOUND METHOD
A branch-and-bound method implicitly enumerates all possible solutions to a programming problem. For our application, in the beginning, we choose one constraint to branch the original problem into several sub-problems. Each sub-problem is represented by one node. Then branching at each node is done by adding one additional constraint. New sub-problems are created and represented by new nodes. Note that the more constraints added to a sub-problem, the smaller feasible domain it has and, consequently, the larger optimal objective value Z it achieves. Therefore, solving one subproblem could provide the possibility to eliminate many possible solutions from consideration. In other words, once a current candidate solution is obtained, we judge other nodes for further consideration. If the best potential solution of one particular node is no better than the current candidate solution, then there is no need to branch on this node. Otherwise, branching is needed to yield a new bound. In this section, we use one concrete example to illustrate how this method works.
Based on the theory we built in previous sections, here we propose an algorithm for finding an optimal solution of problem (1).
Step 1: Find the maximum solution of system (1). Compute according to relation (2).
Step 4: Arrange cost vector. Define and for and define sub-problems and .
Step 5: Use the branch-and-bound concept based on to solve .
Step 3: We compute , , and . So, the cardinality of and is equal to 60. However, in this example we have also , , and . Therefore, the cardinality of and is equal to 8.
Step 4: The main problem is converted to the following two sub-problems: Step 5: Our branch-and-bound method begins by choosing from . Hence, each feasible solution must satisfy either or . This yields two branches denoted by nodes 1 and 2 in Fig. 1. We then obtain a lower bound on the Z-value associated with each node. For example, when , we know , therefore, any choice with results in . So we write for node 1 of Fig. 1. Similarly, any choice with results in . Since at this moment we have no reason to exclude any one of nodes 1 and 2 from consideration, both nodes have to be further investigated. By using the jump-tracking technique, we branch on the node with a lower bound on Z. In this ease, we choose node 2. Since , any choice associated with node 2 must satisfy either or . Branching on node 2 yields nodes 3 and 4 in Fig. 1. For each new node, we need to evaluate a lower bound for the objective value Z. For example, at node 3, we compute Z . Hence, any choice associated with node 3 must have Z . Similar reasoning shows that Z for node 4. Again, we do not have any reason to exclude any of nodes 3 and 4 from consideration, so we need to branch on one node. The jumptracking technique directs us to branch node 3. Any choice associated with node 3 must satisfy either or , since . This yields nodes 5 and 6 in Fig. 1. By the same reasoning as before, any choice associated with node 5 must have Z and any choice associated with node 6 must have Z . Of course, we are interested in node 5. To branch further on node 5, any choice associated with node 5 must have , since . This yields node 7 in Fig. 1. Note that node 7 corresponds to the sequence . This sequence leads to a value of Z . Therefore, node 7 is a feasible sequence which may be viewed as a candidate solution with Z . Because the Z value for nodes 4 and 6 cannot be lower than 2.75, these nodes can be eliminated from further consideration. However, node 1 cannot be eliminated yet, because it is still possible for node 1 to yield a sequence having Z . Hence, we now branch on node 1. Since , any sequence associated with node 1 must have either or . Correspondingly, we create nodes 8 and 9, respectively. For node 9, we calculate Z . Since any sequence associated with node 9 must have Z , this node is eliminated from consideration. For node 8, we have Z . So it cannot be eliminated yet. We branch on node 8. Since , any sequence associated with node 8 must have either or . This creates nodes 10 and 11 in Fig. 1. For node 10, since Z , we eliminate it. Similarly, for node 11 with Z , it can be eliminated too. Now, with the exception of node 7, every node in Fig. 1 has been eliminated from consideration. Node 7 yields the sequence that generates solution . Thus, we should choose the sequence and solution with Z as an optimal solution for .
Step 6: According to formula (5), we can find the optimal value of the original problem as with optimal objective value .

V. NUMERICAL EXAMPLES
In this section, we present the experimental results for evaluating the performance of our algorithm. For this purpose, we apply our algorithm to the following eight test problems. The test problems have been randomly generated in different sizes.

Test Problem 1:
[-9.3708 , 6.7080 , 6.        Table 1 shows the cardinality of and , the cardinality of and , the number of nodes that the algorithm visits and the number of complete paths visited by the algorithm. Moreover, for each test problem , the best path , the optimal solution and the optimal value is listed as follows: In this paper, we have studied a linear optimization problem subjected to a system of Lukasiewicz fuzzy relation equations and presented a procedure to find an optimal solution. Due to the non-convexity nature of its feasible domain, we tend to believe that there is no polynomial-time algorithm for this problem. The best we can do here is that, after analyzing the properties of its feasible domain, we find a solution set that include all the minimal solutions of the main feasible region, then apply a modified branch-and-bound method to find one solution. The question of how to generate the whole optimal solution set is yet to be investigated. From the analysis of Theorem 2, it is clearly seen that if all minimum solutions of a given system of fuzzy relation equations can be found, then an optimal solution of the optimization problem defined by (5) can be constructed. Therefore, solving this optimization problem is no harder than solving a system of fuzzy relation equations for all minimum solution. Although it is not known whether these two problems are essentially equivalent or not, the basic concepts introduced in Section 2 have been further developed for solving fuzzy relation equations. Extension to other types of objective functions is under investigation.