Hybrid Approach for Solving Multiple-Objective Linear Programs in Outcome Space

Various difficulties arise in using decision set-based vector maximization methods to solve a multiple-objective linear programming problem (MOLP). Motivated by these difficulties, some researchers in recent years have begun to develop tools for analyzing and solving problem (MOLP) in outcome space, rather than in decision space. In this article, we present and validate a new hybrid vector maximization approach for solving problem (MOLP) in outcome space. The approach systematically integrates a simplicial partitioning technique into an outer approximation procedure to yield an algorithm that generates the set of all efficient extreme points in the outcome set of problem (MOLP) in a finite number of iterations. Some key potential practical and computational advantages of the approach are indicated.     

An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem

Various difficulties have been encountered in using decision set-based vector maximization methods to solve a multiple objective linear programming problem (MOLP). Motivated by these difficulties, some researchers in recent years have suggested that outcome set-based approaches should instead be developed and used to solve problem (MOLP). In this article, we present a finite algorithm, called the Outer Approximation Algorithm, for generating the set of all efficient extreme points in the outcome set of problem (MOLP). To our knowledge, the Outer Approximation Algorithm is the first algorithm capable of generating this set. As a by-product, the algorithm also generates the weakly efficient outcome set of problem (MOLP). Because it works in the outcome set rather than in the decision set of problem (MOLP), the Outer Approximation Algorithm has several advantages over decision set-based algorithms. It is also relatively easy to implement. Preliminary computational results for a set of randomly-generated problems are reported. These results tangibly demonstrate the usefulness of using the outcome set approach of the Outer Approximation Algorithm instead of a decision set-based approach. This revised version was published online in July 2006 with corrections to the Cover Date.     

Determining maximal efficient faces in multiobjective linear programming problem

Finding an efficient or weakly efficient solution in a multiobjective linear programming (MOLP) problem is not a difficult task. The difficulty lies in finding all these solutions and representing their structures. Since there are many convenient approaches that obtain all of the (weakly) efficient extreme points and (weakly) efficient extreme rays in an MOLP, this paper develops an algorithm which effectively finds all of the (weakly) efficient maximal faces in an MOLP using all of the (weakly) efficient extreme points and extreme rays. The proposed algorithm avoids the degeneration problem, which is the major problem of the most of previous algorithms and gives an explicit structure for maximal efficient (weak efficient) faces. Consequently, it gives a convenient representation of efficient (weak efficient) set using maximal efficient (weak efficient) faces. The proposed algorithm is based on two facts. Firstly, the efficiency and weak efficiency property of a face is determined using a relative interior point of it. Secondly, the relative interior point is achieved using some affine independent points. Indeed, the affine independent property enable us to obtain an efficient relative interior point rapidly.     

Using Efficient Anchoring Points for Generating Search Directions in Interior Multiobjective Linear Programming

This paper modifies the affine-scaling primal algorithm to multiobjective linear programming (MOLP) problems. The modification is based on generating search directions in the form of projected gradients augmented by search directions pointing toward what we refer to as anchoring points. These anchoring points are located on the boundary of the feasible region and, together with the current, interior, iterate, define a cone in which we make the next step towards a solution of the MOLP problem. These anchoring points can be generated in more than one way. In this paper we present an approach that generates efficient anchoring points where the choice of termination solution available to the decision maker at each iteration consists of a set of efficient solutions. This set of efficient solutions is being updated during the iterative process so that only the most preferred solutions are retained for future considerations. Current MOLP algorithms are simplex-based and make their progress toward the optimal solution by following an exterior trajectory along the vertices of the constraints polytope. Since the proposed algorithm makes its progress through the interior of the constraints polytope, there is no need for vertex information and, therefore, the search for an acceptable solution may prove less sensitive to problem size. We refer to the resulting class of MOLP algorithms that are based on the affine-scaling primal algorithm as affine-scaling interior multiobjective linear programming (ASIMOLP) algorithms.     

Branch-and-Bound Variant of an Outcome-Based Algorithm for Optimizing over the Efficient Set of a Bicriteria Linear Programming Problem

The paper presents a finite branch-and-bound variant of an outcome-based algorithm proposed by Benson and Lee for minimizing a lower-semicontinuous function over the efficient set of a bicriteria linear programming problem. Similarly to the Benson-Lee algorithm, we work primarily in the outcome space. Dissimilarly, instead of constructing a sequence of consecutive efficient edges in the outcome space, we use the idea of generating a refining sequence of partitions covering the at most two-dimensional efficient set in the outcome space. Computational experience is also presented.     

Approximating the nondominated set of an MOLP by approximately solving its dual problem

The geometric duality theory of Heyde and Löhne (2006) defines a dual to a multiple objective linear programme (MOLP). In objective space, the primal problem can be solved by Benson’s outer approximation method (Benson 1998a,b) while the dual problem can be solved by a dual variant of Benson’s algorithm (Ehrgott et al. 2007). Duality theory then assures that it is possible to find the (weakly) nondominated set of the primal MOLP by solving its dual. In this paper, we propose an algorithm to solve the dual MOLP approximately but within specified tolerance. This approximate solution set can be used to calculate an approximation of the weakly nondominated set of the primal. We show that this set is a weakly ε-nondominated set of the original primal MOLP and provide numerical evidence that this approach can be faster than solving the primal MOLP approximately.     

Finding DEA-efficient hyperplanes using MOLP efficient faces

This paper suggests a method for finding efficient hyperplanes with variable returns to scale the technology in data envelopment analysis (DEA) by using the multiple objective linear programming (MOLP) structure. By presenting an MOLP problem for finding the gradient of efficient hyperplanes, We characterize the efficient faces. Thus, without finding the extreme efficient points of the MOLP problem and only by identifying the efficient faces of the MOLP problem, we characterize the efficient hyperplanes which make up the DEA efficient frontier. Finally, we provide an algorithm for finding the efficient supporting hyperplanes and efficient defining hyperplanes, which uses only one linear programming problem.     

A weight set decomposition algorithm for finding all efficient extreme points in the outcome set of a multiple objective linear program

Various computational difficulties arise in using decision set-based vector maximization methods to solve multiple objective linear programming problems. As a result, several researchers have begun to explore the possibility of solving these problems by examining subsets of their outcome sets, rather than of their decision sets. In this article, we present and validate a basic weight set decomposition approach for generating the set of all efficient extreme points in the outcome set of a multiple objective linear program. Based upon this approach, we then develop an algorithm, called the Weight Set Decomposition Algorithm, for generating this set. A sample problem is solved using this algorithm, and the main potential computational and practical advantages of the algorithm are indicated.     

A modified method for constructing efficient solutions structure of MOLP

This paper deals with a recently proposed algorithm for obtaining all weak efficient and efficient solutions in a multi objective linear programming (MOLP) problem. The algorithm is based on solving some weighted sum problems, and presents an easy and clear solution structure. We first present an example to show that the algorithm may fail when at least one of these weighted sum problems has not a finite optimal solution. Then, the algorithm is modified to overcome this problem. The modified algorithm determines whether an efficient solution exists for a given MOLP and generates the solution set correctly (if exists) without any change in the complexity.     

Random problem generation and the computation of efficient extreme points in multiple objective linear programming

This paper looks at the task of computing efficient extreme points in multiple objective linear programming. Vector maximization software is reviewed and the ADBASE solver for computing all efficient extreme points of a multiple objective linear program is described. To create MOLP test problems, models for random problem generation are discussed. In the computational part of the paper, the numbers of efficient extreme points possessed by MOLPs (including multiple objective transportation problems) of different sizes are reported. In addition, the way the utility values of the efficient extreme points might be distributed over the efficient set for different types of utility functions is investigated. Not surprisingly, results show that it should be easier to find good near-optimal solutions with linear utility functions than with, for instance, Tchebycheff types of utility functions.Dedicated to Professor George B. Dantzig on the occasion of his eightieth birthday.     

Bounding MOLP objective functions: effect on efficient set size

In multiple objective linear programming (MOLP) problems the extraction of all the efficient extreme points becomes problematic as the size of the problem increases. One of the suggested actions, in order to keep the size of the efficient set to manageable limits, is the use of bounds on the values of the objective functions by the decision maker. The unacceptable efficient solutions are screened out from further investigation and the size of the efficient set is reduced. Although the bounding of the objective functions is widely used in practice, the effect of this action on the size of the efficient set has not been investigated. In this paper, we study the effect of individual and simultaneous bounding of the objective functions on the number of the generated efficient points. In order to estimate the underlying relationships, a computational experiment is designed, in which randomly generated multiple objective linear programming problems of various sizes are systematically examined.     

An MOLP based procedure for finding efficient units in DEA models

In this paper a multiple objective linear programming (MOLP) problem whose feasible region is the production possibility set with variable returns to scale is proposed. By solving this MOLP problem by multicriterion simplex method, the extreme efficient Pareto points can be obtained. Then the extreme efficient units in data envelopment analysis (DEA) with variable returns to scale, considering the specified theorems and conditions, can be obtained. Therefore, by solving the proposed MOLP problem, the non-dominant units in DEA can be found. Finally, a numerical example is provided.     

Outcome-based algorithm for optimizing over the efficient set of a bicriteria linear programming problem

This article presents a finite, outcome-based algorithm for optimizing a lower semicontinuous function over the efficient set of a bicriteria linear programming problem. The algorithm searches the efficient faces of the outcome set of the bicriteria linear programming problem. It exploits the fact that the dimension of the outcome set of the bicriteria problem is at most two. As a result, in comparison to decisionbased approaches, the number of efficient faces that need to be found is markedly reduced. Furthermore, the dimensions of the efficient faces found are always at most one. The algorithm can be implemented for a wide variety of lower semicontinuous objective functions.     

Outcome Space Partition of the Weight Set in Multiobjective Linear Programming

Approaches for generating the set of efficient extreme points of the decision set of a multiple-objective linear program (P) that are based upon decompositions of the weight set W⁰ suffer from one of two special drawbacks. Either the required computations are redundant, or not all of the efficient extreme point set is found. This article shows that the weight set for problem (P) can be decomposed into a partition based upon the outcome set Y of the problem, where the elements of the partition are in one-to-one correspondence with the efficient extreme points of Y. As a result, the drawbacks of the decompositions of W⁰ based upon the decision set of problem (P) disappear. The article explains also how this new partition offers the potential to construct algorithms for solving large-scale applications of problem (P) in the outcome space, rather than in the decision space.     

Parametric LP for sensitivity analysis of efficiency in MOLP problems

This paper describes sensitivity analysis in multiple objective linear programming (MOLP) with one of the criteria function coefficients parameterized. The parametric linear programming (LP) is used for analyzing a range set—the parameters set for which a given feasible solution is efficient for MOLP. The main theoretical result is a presentation of convexity of the range set. Moreover, an algorithm based on some of LP problems is presented for generating the range set.     

Range sets for weak efficiency in multiobjective linear programming and a parametric polytopes intersection problem

ABSTRACT

The aim of this paper is to obtain the range set for a given multiobjective linear programming problem and a weakly efficient solution. The range set is the set of all values of a parameter such that a given weakly efficient solution remains efficient when the objective coefficients vary in a given direction. The problem was originally formulated by Benson in 1985 and left to be solved. We formulate an algorithm for determining the range set, based on some hard optimization problems. Due to toughness of these optimization problems, we propose also lower and upper bound approximation techniques. In the second part, we focus on topological properties of the range set. In particular, we prove that a range set is formed by a finite union of intervals and we propose upper bounds on the number of intervals. Our approach to tackle the range set problem is via the intersection problem of parametric polytopes. Thus, our results have much wider area of applicability since the intersection (and separability) problem of convex polyhedra is important in many fields of optimization.     

A finite,nonadjacent extreme-point search algorithm for optimization over the efficient set

The problem (P) of optimizing a linear function over the efficient set of a multiple-objective linear program serves many useful purposes in multiple-criteria decision making. Mathematically, problem (P) can be classified as a global optimization problem. Such problems are much more difficult to solve than convex programming problems. In this paper, a nonadjacent extreme-point search algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact extreme-point optimal solution for the problem after a finite number of iterations. It can be implemented using only linear programming methods. Convergence of the algorithm is proven, and a discussion is included of its main advantages and disadvantages.The author owes thanks to two anonymous referees for their helpful comments.     

An all-linear programming relaxation algorithm for optimizing over the efficient set

The problem (P) of optimizing a linear function over the efficient set of a multiple objective linear program has many important applications in multiple criteria decision making. Since the efficient set is in general a nonconvex set, problem (P) can be classified as a global optimization problem. Perhaps due to its inherent difficulty, it appears that no precisely-delineated implementable algorithm exists for solving problem (P) globally. In this paper a relaxation algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact optimal solution to the problem after a finite number of iterations. A detailed discussion is included of how to implement the algorithm using only linear programming methods. Convergence of the algorithm is proven, and a sample problem is solved.Research supported by a grant from the College of Business Administration, University of Florida, Gainesville, Florida, U.S.A.