روش مبتنی بر مجاورت برای ایجاد چهره های کارآمد حداکثر در برنامه ریزی خطی چندهدفه

Multiobjective linear optimization problems (MOLPs) arise when several linear objective functions have to be optimized over a convex polyhedron. In this paper, we propose a new method for generating the entire efficient set for MOLPs in the outcome space. This method is based on the concept of adjacencies between efficient extreme points. It uses a local exploration approach to generate simultaneously efficient extreme points and maximal efficient faces. We therefore define an efficient face as the combination of adjacent efficient extreme points that define its border. We propose to use an iterative simplex pivoting algorithm to find adjacent efficient extreme points. Concurrently, maximal efficient faces are generated by testing relative interior points. The proposed method is constructive such that each extreme point, while searching for incident faces, can transmit some local informations to its adjacent efficient extreme points in order to complete the faces’ construction. The performance of our method is reported and the computational results based on randomly generated MOLPs are discussed.

Many real optimization problems can be modeled as a multiobjective linear programming (MOLP) problem, such as transportation [1] and inventory planning [2]. MOLPs are characterized by the simultaneous maximization of a set of objectives under a system of constraints, where both objective functions and constraints are linear, within continuous decision variables. Solving MOLPs yields to a set of efficient solutions belonging to a connected set of efficient faces. The set of all efficient solutions is the union of all maximal efficient faces. Several approaches for solving such problems have been proposed in the literature [3], [4] and [5]. These methods employ different schemes for exploring the efficient set, and different ways of characterizing and locating the maximal efficient faces. Recently, much more attention has been given to solving MOLPs in objective space. The earlier works of Dauer and Gallagher [6] and Benson [7] provided a new view for studying efficient solutions set in outcome space. Comparing to the decision based approaches, the outcome based search methods seem to give promissive computational results [8]. Yan et al. [9] presented a method for generating maximal efficient faces in combined decision-outcome space using the weight decomposition and with an easy and clear solution structure, they defined the set of efficient faces as a finite combination of extreme points and rays. This representation was called the sum form. More details might be found is Section 3. Most of exiting outcome based methods, operate in two steps: generating efficient extreme points then locating efficient faces. In this paper, we propose a new method for solving MOLPs in objective space, by combining the sum form approach with the adjacency information of efficient extreme points. The proposed method performs the neighborhood approach defined by Benson and Sun [10] in order to generate efficient extreme points. Simultaneously, the efficiency of certain combinations of these extreme points are tested by investigating relative interior points in order to find maximal efficient faces. The main idea is to design a local and constructive method. We associate to each extreme point x a list L(x) to keep in memory the faces containing this point. At each iteration, we investigate a new extreme point. We start by exploring its adjacent efficient vertices. If a new efficient point x′ is generated, then we test the efficiency of the convex hull defined by combining this new point x′ with preexisting faces in L(x). To do so, a relative interior point is tested. If a new face is encountered, we update the list L(x′) by adding this face. This procedure iterates until exploring all efficient extreme points. The paper is structured as follows. In the next section, we present the multiobjective linear programming problem and some theoretical background. In Section 3, we review related literature. In Section 4, we present the proposed method for generating maximal efficient faces in outcome space. We provide empirical results in Section 5. A comparison with an existing method [5], as well as a computational analysis for medium and large sized problems are also discussed in the same section. The conclusion is presented in Section 6.

This paper propose an adjacency based method for generating maximal efficient faces for solving MOLPs in the objective (outcome) space called efficient solutions adjacency based method (ESAM). ESAM is based on the simplex pivoting method [10] in order to generate efficient extreme points, and then it constructs simultaneously efficient faces by testing selected relative interior points. It exploits the properties of convex faces in order to verify its efficiency. Since the mapping from the decision space to the objective space generally reduces the number of dimensions, ESAM generally performs better than the decision based search methods. This paper presents empirical comparison of ESAM to an existing method [5] for solving MOLPs based on randomly generated problems. These results show that for small size problems (p = 3, m = 3, n < 5), Sayin’s method has better CPU time even though that ESAM CPU time is very reasonable. However, as soon as the size of the problem increases (p = 3, m = 3, n > 5), ESAM outperforms the Sayins method. Moreover, Sayin’s method does not generate efficient faces for problem larger than where (p = 3, m = 10, n = 9). We continued testing the ESAM method on larger MOLPs instances. It continues to generate efficient faces. The proposed method could be improved by considering improvements to the pivoting simplex method, use of meta-heuristics and better computation algorithms (for example combining with solvers like CPlex or other powerful engines). We are considering examining other properties of efficient faces in order to reduce the computation complexity of the method.