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.     

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.     

Further Analysis of an Outcome Set-Based Algorithm for Multiple-Objective Linear Programming

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, Benson recently developed a finite, outer-approximation algorithm for generating the set of all efficient extreme points in the outcome set, rather than in the decision set, of problem (MOLP). In this article, we show that the Benson algorithm also generates the set of all weakly efficient points in the outcome set of problem (MOLP). As a result, the usefulness of the algorithm as a decision aid in multiple objective linear programming is further enhanced.     

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.     

Adjacency based method for generating maximal efficient faces in multiobjective linear programming

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.     

A geometrical analysis of the efficient outcome set in multiple objective convex programs with linear criterion functions

This article performs a geometrical analysis of the efficient outcome setY _E of a multiple objective convex program (MLC) with linear criterion functions. The analysis elucidates the facial structure ofY _E and of its pre-image, the efficient decision setX _E . The results show thatY _E often has a significantly-simpler structure thanX _E . For instance, although both sets are generally nonconvex and their maximal efficient faces are always in one-to-one correspondence, large numbers of extreme points and faces inX _E can map into non-facial subsets of faces inY _E , but not vice versa. Simple tests for the efficiency of faces in the decision and outcome sets are derived, and certain types of faces in the decision set are studied that are immune to a common phenomenon called collapsing. The results seem to indicate that significant computational benefits may potentially be derived if algorithms for problem (MLC) were to work directly with the outcome set of the problem to find points and faces ofY _E , rather than with the decision set.     

An outcome space algorithm for optimization over the weakly efficient set of a multiple objective nonlinear programming problem

This article presents for the first time an algorithm specifically designed for globally minimizing a finite, convex function over the weakly efficient set of a multiple objective nonlinear programming problem (V1) that has both nonlinear objective functions and a convex, nonpolyhedral feasible region. The algorithm uses a branch and bound search in the outcome space of problem (V1), rather than in the decision space of the problem, to find a global optimal solution. Since the dimension of the outcome space is usually much smaller than the dimension of the decision space, often by one or more orders of magnitude, this approach can be expected to considerably shorten the search. In addition, the algorithm can be easily modified to obtain an approximate global optimal weakly efficient solution after a finite number of iterations. Furthermore, all of the subproblems that the algorithm must solve can be easily solved, since they are all convex programming problems. The key, and sometimes quite interesting, convergence properties of the algorithm are proven, and an example problem is solved.     

Finite dimensional polish spaces are extreme boundaries of convex bodies in Euclidean space

It is proved that everyn-dimensional Polish space is homeomorphic to the set of extreme points of a compact convex set inR ^18(n+1). The contribution of M. Levin to this paper is a part of his Ph.D. thesis prepared at the University of Haifa under the supervision of Y. Sternfeld.     

The biobjective travelling purchaser problem

The purpose of this article is to present and solve the Biobjective Travelling Purchaser Problem, which consists in determining a route through a subset of markets in order to collect a set of products, minimizing the travel distance and the purchasing cost simultaneously. The most convenient purchase of the product in the visited markets is easily computed once the route has been determined. Therefore, this problem contains a finite set of solutions (one for each route) and the problem belongs to the field of the Biobjective Combinatorial Optimization. It is here formulated as a Biobjective Mixed Integer Linear Programming model with an exponential number of valid inequalities, and this model is used within a cutting plane algorithm to generate the set of all supported and non-supported efficient points in the objective space. A variant of the algorithm computes only supported efficient points. For each efficient point in the objective space exactly one Pareto optimal solution in the decision space is computed by solving a single-objective problem. Each of these single-objective problems, in turn, is solved by a specific branch-and-cut approach. A heuristic improvement based on saving previously generated cuts in a common cut-pool structure has also been developed with the aim of speeding up the algorithm performance. Results based on benchmark instances from literature show that the common cut-pool heuristic is very useful, and that the proposed algorithm manages to solve instances containing up to 100 markets and 200 different products. The general procedure can be extended to address other biobjective combinatorial optimization problems whenever a branch-and-cut algorithm is available to solve a single-objective linear combination of these criteria.     

On degeneracy and collapsing in the construction of the set of objective values in a multiple objective linear program

In this paper an algorithm is developed to generate all nondominated extreme points and edges of the set of objective values of a multiple objective linear program. The approach uses simplex tableaux but avoids generating unnecessary extreme points or bases of extreme points. The procedure is based on, and improves, an algorithm Dauer and Liu developed for this problem. Essential to this approach is the work of Gal and Kruse on the neighborhood problem of determining all extreme points of a convex polytope that are adjacent to a given (degenerate) extreme point of the set. The algorithm will incorporate Gal's degeneracy graph approach to the neighborhood problem with Dauer's objective space analysis of multiple objective linear programs.     

Off-line dynamic maintenance of the width of a planar point set

Agarwal, P.K. and M. Sharir, Off-line dynamic maintenance of the width of a planar point set, Computational Geometry: Theory and Applications 1 (1990) 65-78. In this paper we present an efficient algorithm for the off-line dynamic maintenance of the width of a planar point set in the following restricted case: We are given a real parameter W and a sequence Σ=(σ₁,...,σ_n) of n insert and delete operations on a set S of points in ², initially consisting of n points, and we want to determine whether there is an i such that the width of S the ith operation is less than or equal to W. Our algorithm runs in time O(nlog³n) and uses O(n) space.     

The role of non-Archimedean epsilon in finding the most efficient unit: With an application of professional tennis players

The determination of a single efficient decision making unit (DMU) as the most efficient unit has been attracted by decision makers in some situations. Some integrated mixed integer linear programming (MILP) and mixed integer nonlinear programming (MINLP) data envelopment analysis (DEA) models have been proposed to find a single efficient unit by the optimal common set of weights. In conventional DEA models, the non-Archimedean infinitesimal epsilon, which forestalls weights from being zero, is useless if one utilizes the well-known two-phase method. Nevertheless, this approach is inapplicable to integrated DEA models. Unfortunately, in some proposed integrated DEA models, the epsilon is neither considered nor determined. More importantly, based on this lack some approaches have been developed which will raise this drawback.In this paper, first of all some drawbacks of these models are discussed. Indeed, it is shown that, if the non-Archimedean epsilon is ignored, then these models can neither find the most efficient unit nor rank the extreme efficient units. Next, we formulate some new models to capture these drawbacks and hence attain assurance regions. Finally, a real data set of 53 professional tennis players is applied to illustrate the applicability of the suggested models.     

Biorthogonal decompositions of the Radon transform by multivariate interpolation

The concept of biorthogonal and singular value decompositions is a valuable tool in the examination of ill-posed inverse problems such as the inversion of the Radon transform. By application of the theory of multivariate interpolation, e. g. the set of Lagrange polynomials with respect to the space of homogeneous spherical polynomials, we determine new biorthogonal decompositions of the Radon transform. We consider the case of functions with support in the unit ball and the case of functions with support ?^r. In both cases we assume that the functions are square integrable with respect to some weight functions. In the important special case of square integrable functions with respect to the unit ball the structure of the biorthogonal decompositions is easier in comparison with the known singular and biorthogonal decompositions. Especially the calculation of the unknown expansion coefficients can be done by using arbitrary fundamental systems (μ-resolving data set in terms of tomography with a minimum number of nodes) and simplifies essentially. The decompositions are based on a system of zonal (ridge) Gegenbauer (ultraspherical) polynomials which are used in the theory of the Radon transform and in the field of numerical algorithms for the inversion of the transform.     

A new strategy for the undirected two-commodity maximum flow problem

We address the two-commodity maximum flow problem on undirected networks. As a result of a change of variables, we introduce a new formulation that solves the problem through classical maximum flow techniques with only one-commodity. Therefore, a general strategy, based on this change of variables, is defined to deal with other undirected multi-commodity problems. Finally, we extend the single objective problem to a bicriteria environment. We show that the set of efficient solutions of the biobjective undirected two-commodity maximum flow problem is the set of alternative optimum solutions of the undirected two-commodity maximum flow problem. In addition, we prove that the set of efficient extreme points in the objective space has, at most, cardinality two.     

Extreme 2-homogeneous polynomials on Hilbert spaces

Let H be a (real or complex) Hilbert space. We characterize the extreme points of the unit ball of the space of 2-homogeneous polynomials on H. We find the exact value of the λ-function for P(² H) and thus we show that its unit ball is the norm closed convex hull of its extreme points. We also describe topological properties of the set of extreme points, making connections between the set of extreme points and Grassmanian manifolds.     

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.     

An interactive approach for multiobjective decision making

We develop an interactive approach for multiobjective decision-making problems, where the solution space is defined by a set of constraints. We first reduce the solution space by eliminating some undesirable regions. We generate solutions (partition ideals) that dominate portions of the efficient frontier and the decision maker (DM) compares these with feasible solutions. Whenever the decision maker prefers a feasible solution, we eliminate the region dominated by the partition ideal. We then employ an interactive search method on the reduced solution space to help the DM further converge toward a highly preferred solution. We demonstrate our approach and discuss some variations.     

Copositivity detection by difference-of-convex decomposition and ω-subdivision

We present three new copositivity tests based upon difference-of-convex (d.c.) decompositions, and combine them to a branch-and-bound algorithm of ω-subdivision type. The tests employ LP or convex QP techniques, but also can be used heuristically using appropriate test points. We also discuss the selection of efficient d.c. decompositions and propose some preprocessing ideas based on the spectral d.c. decomposition. We report on first numerical experience with this procedure which are very promising.     

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.