MACROBUTTON MTEditEquationSection2 Equation Chapter 1 Section 1 SEQ MTEqn \r \h \* MERGEFORMAT  SEQ MTSec \r 1 \h \* MERGEFORMAT  SEQ MTChap \r 1 \h \* MERGEFORMAT Most real life optimization problems are typically multiobjective in nature. However, often these objectives are conflicting, i.e. improvement in one objective is obtained at the cost of deterioration in other objectives. For such cases, the trade-offs between these conflicting objectives can be evaluated using a pareto-frontcomprising of non-dominated solutions. A solution is said to be non-dominated if it is feasible and there is no other feasible solution which has better values for all the objectives. Some typical combinatorial optimization based design problems from sensor network design area are considered to demonstrate the utility of the proposed general-approach. Hence, the discussion in this work is tailored towards sensor network design problems.

The optimal placement of sensors involves the selection of variables that need to be measured in the process. This optimality can be either with respect to the objectives of cost, flexibility, reliability, variance, observability, or robustness of the network [1]. In sensor network design multiobjective optimization literature, some of the traditional methods that have been used include - constraint method and Genetic Algorithms. The -constraint method [2, 3] involves the conversion of multi-objective problem into a single objective problem by considering only one objective and imposing constraints on threshold values for other objectives. However, this method suffers various drawbacks: (i) The optimality of pareto-front critically depends on the method that handles the underlying single-objective optimization problem which often are combinatorial and nonlinear in nature. (ii) To generate the pareto-front, several such problems with different thresholds need to be solved. Additionally, systematic methods for choosing different thresholds that will enable generation of all points on the pareto front are not available in general. (iii) Sometimes, a single point on the pareto front may correspond to several realizations (solutions with same objective function values but different decision variables). Generation of such multiple realizations is not straightforward in the  -constraint method. (iv) This method can lead to sub-optimal solutions if the underlying single-objective optimization problems have multiple solutions. In contrast, while Genetic algorithms [4] are free from some of these drawbacks since they don't require threshold specifications, are suitable for pareto-front generation as they work with a population and not a single solution, and don't even require the problem specification in an explicit form (can deal with constructive constraints). However, they involve the specification of tuning parameters such as crossover and mutation probabilities which can affect the results. A more severe drawback is that optimality of Genetic algorithms is not guaranteed even for well structured problems (such as linear).

A recent approach [5,6] for solving sensor network design problems involves the use of Constraint Programming for the determination of globally optimal pareto-front.

Multi-objective problem: The rest of the discussion will use the following representative problem to aid in discussion.

P1:                                                                                         MACROBUTTON MTPlaceRef \* MERGEFORMAT  SEQ MTEqn \h \* MERGEFORMAT (1)

The problem P1 consists of three objective functions and four decision variables subject to the set of constraints denoted by . It may be noted that this set of constraints can include (but not restricted to) constraints that involve the product of decision variables, disjunctive constraints, implication constraints and constraints involving the operator since these can be directly incorporated (without any additional modifications/transformations) in the CP modeling framework.

Existing Method: The existing method [5,6] perceives the problem to be composed of two separate entities, viz (i) the set of constraints and (ii) the set of objectives with no interaction between them. The set of constraints is used to generate all feasible solutions (from P2) and the set of objectives are used to filter the pareto points from the set of feasible solutions.

P2:                                                                                                    MACROBUTTON MTPlaceRef \* MERGEFORMAT  SEQ MTEqn \h \* MERGEFORMAT (2)

Though sophisticated algorithms like Kung's Method [2] can be used for the sorting of pareto points, it is more time consuming to generate all the feasible solutions of P2 even with a CP algorithm. This algorithm can be summarized as shown in Figure 1

Figure 1: Algorithm of the Existing Approach

 SHAPE  \* MERGEFORMAT

Step 1: Determine the set of all feasible solutions for the constraint set Step 2: Evaluate the objective functions at all feasible solutions obtained in the above step. Step 3: Apply any standard algorithm to sort the set of non dominated solutions.

Proposed Approach: The approach proposed in this article does not perceive the problem to be composed of two independent entities but uses the objective function values at a feasible point to prune the search space for the generation of a subsequent better feasible point as shown in the problem (P3) below:

P3:                                                                                        MACROBUTTON MTPlaceRef \* MERGEFORMAT  SEQ MTEqn \h \* MERGEFORMAT (3)

Before presenting the algorithm, we explain the two types of cuts that have been used in this work.

Type I cuts: These cuts are added sequentially to ensure that the subsequent feasible solution (at step ) has atleast one better objective than the solutions obtained in the previous steps (i.e. it is not dominated by any solution obtained earlier). A Type I cut is added as soon as a feasible solution is generated. For problem P1, after generation of k feasible solutions, these cuts can be written as

                                                                    MACROBUTTON MTPlaceRef \* MERGEFORMAT  SEQ MTEqn \h \* MERGEFORMAT (4)

where k denotes the step-number and  is the value of  jth objective function for the ith feasible solution. The above cut has three components separated by a OR function and is satisfied if atleast one of the three components are evaluated to be true. This procedure stops once the problem becomes infeasible. Let the number of feasible solutions generated by this procedure be K.

Type II cuts: This cut is constructed based on the definition of pareto-points as defined earlier. For P1, these cuts can be written as

                          MACROBUTTON MTPlaceRef \* MERGEFORMAT  SEQ MTEqn \h \* MERGEFORMAT (5)

It can be seen that the above cut consists of 4 parts. The last three parts are similar to Type I cuts whereas the first cut helps in the determination of realizations. As a result, all feasible solutions of P1 which satisfy constraint (5) are pareto-optimal solutions. These feasible solutions are easily generated by CP using its intelligent search approach. The proposed approach is given in Figure 2.

Figure 2: Algorithm of the Proposed Approach

 SHAPE  \* MERGEFORMAT

Step 1: Transform P1 to P3. Initialize k = 0; Step 2: Set k = k+1; Solve P3.             If P3 is Infeasible, go to Step 6 if k=1             If P3 is Infeasible, go to Step 4 if k > 1             Determine one feasible solution to P3. Let the solution be Step 3: Add a cut of Type 1 to P3. Go to Step 2 Step 4: Solve P3 with K cuts of Type II and determine all feasible solutions. Step 5: Pareto-points (with realizations) obtained. End Step 6: Problem Infeasible. End

Case Studies: The proposed approach has been applied to five problems from sensor network design literature taken from [5,6]. Table 1 presents the comparative results of both the methods on the 5 case studies on the same machine with ILOG Solver 6.1.

 

From Table 1, it is obvious that the proposed method performs better than the existing method. Additionally, it does not require sorting for pareto points. Moreover, the number of pareto-points and realizations in both cases are same thereby validating the proposed approach. Hence, the proposed approach can be a useful tool for solving multiobjective optimization problems.

References:

(1)   Mani Bhushan, Narasimhan, S.; and Rengaswamy, R. Robust Sensor network design for fault Diagnosis, Submitted to Comput Chem. Eng. Sept. 2006.

(2)   Deb, K. Multiobjective Optimization Using Evolutionary Algorithms; John Wiley & Sons Ltd. :Chichester, U.K., 2001.

(3)   Kotecha, P. R, Mani Bhushan, Gudi R. D.; Keshari M. K.; A duality based framework for integrating reliability and precision for sensor network design, Submitted to Journal of Process Control, Dec 2006.

(4)   S. Sen, S. Narasimhan, K. Deb, Sensor Network Design of Linear processes Using Genetic Algorithms. Comput Chem. Eng. 22 (1998) 385-390.

(5)   Kotecha, P. R, Mani Bhushan, Gudi R. D.; Constraint Programming Based Robust Sensor Network Design, Submitted to Industrial & Engineering Chemistry Research, Dec 2006.

(6)   Kotecha, P. R, Mani Bhushan, Gudi R. D.; Constraint Programming based multi-objective sensor network design for fault diagnosis, Paper ID: T3_404, To be presented at the 17^th European Symposium on Computer Aided Process  – ESCAPE17 Bucharest, Romania; V. Plesu and P.S. Agachi (Editors) © 2007 Elsevier B.V./Ltd.