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.     

A branch and bound algorithm for mixed zero-one multiple objective linear programming

In this paper, a branch and bound algorithm for the generation of the efficient set in mixed zero-one multiple objective linear programming problems is presented. The algorithm is developed as to take account of the multiple objectives in the node fathoming procedure. In order to extend the algorithm's applicability to large sized problems from real life, an interactive procedure is introduced which systematically reduces the number of efficient points and thus saves considerable computational effort without losing essential information. The algorithm is tested in randomly generated problems along with a case study conceming the power generation sector     

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.     

An Algorithm for Solving Multicriterion Linear Programming Problems with Examples

The purpose of this paper is to develop a useful technique for solving linear programmes involving more than one objective function. Motivation for solving multicriterion linear programmes is given along with the inherent difficulty associated with obtaining a satisfactory solution set. By applying a linear programming approach for the solution of two person–zero sum games with mixed strategies, it is shown that a linear optimization problem with multiple objective functions can be formulated in this fashion in order to obtain a solution set satisfying all the requirements for an efficient solution of the problem. The solution method is then refined to take into account disparities between the magnitude of the values generated by each of the objective functions and solution preferences as determined by a decision-maker. A summary of the technique is then given along with several examples in order to demonstrate its applicability.     

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.     

Some issues in measuring and reporting solution quality of interactive multiple objective programming procedures

Issues in measuring and reporting solution quality are examined when value functions are used in computational experiments of interactive multiple objective programming procedures. They include value functions used, weights assigned to the objective functions in the value functions, the size of the efficient set, and the number of objective functions. The feasibility and existence of the ideal and nadir points are also discussed. Detailed examples are presented to demonstrate these issues. Neither the users nor, in fact, the researchers may discern these issues even though they have strong impacts on the reported solution qualities. Common practices in the computational experiments of interactive multiple objective programming procedures are reviewed.     

Efficient solution generation for multiple objective linear programming based on extreme ray generation method

In this paper we consider solution generation method for multiple objective linear programming problems. The set of efficient or Pareto optimal solutions for the problems can be regarded as global information in multiple objective decision making situation. In the past three decades as solution generation techniques various conventional algorithms based on simplex-like approach with heavy computational burden were developed. Therefore, the development of novel and useful directions in efficient solution generation method have been desired. The purpose of this paper is to develop theoretical results and computational techniques of the efficient solution generation method based on extreme ray generation method that sequentially generates efficient points and rays by adding inequality constraints of the polyhedral feasible region.     

Global maximization of UTA functions in multi-objective optimization

The UTAs (UTilité Additives) type methods for constructing nondecreasing additive utility functions were first proposed by Jacquet-Lagrèze and Siskos in 1982 for handling decision problems of multicriteria ranking. In this article, by UTA functions, we mean functions which are constructed by the UTA type methods. Our purpose is to propose an algorithm for globally maximizing UTA functions of a class of linear/convex multiple objective programming problems. The algorithm is established based on a branch and bound scheme, in which the branching procedure is performed by a so-called I-rectangular bisection in the objective (outcome) space, and the bounding procedure by some convex or linear programs. Preliminary computational experiments show that this algorithm can work well for the case where the number of objective functions in the multiple objective optimization problem under consideration is much smaller than the number of variables.     

Linear complementarity problems and multiple objective programming

An equivalence is demonstrated between solving a linear complementarity problem with general data and finding a certain subset of the efficient points of a multiple objective programming problem. A new multiple objective programming based approach to solving linear complementarity problems is presented. Results on existence, uniqueness and computational complexity are included.     

An approximation algorithm for convex multi-objective programming problems

In multi-objective convex optimization it is necessary to compute an infinite set of nondominated points. We propose a method for approximating the nondominated set of a multi-objective nonlinear programming problem, where the objective functions and the feasible set are convex. This method is an extension of Benson’s outer approximation algorithm for multi-objective linear programming problems. We prove that this method provides a set of weakly ε-nondominated points. For the case that the objectives and constraints are differentiable, we describe an efficient way to carry out the main step of the algorithm, the construction of a hyperplane separating an exterior point from the feasible set in objective space. We provide examples that show that this cannot always be done in the same way in the case of non-differentiable objectives or constraints.     

Saddle Points and Pareto Points in Multiple Objective Programming

In this paper relationships between Pareto points and saddle points are studied in convex and nonconvex multiple objective programming. The analysis is based on partitioning the index sets of objectives and constraints and splitting the original problem into subproblems having a special structure. The results are based on scalarizations of multiple objective programs and related linear and augmented Lagrangian functions. In the nonconvex case, a saddle point characterization of Pareto points is possible under assumptions that guarantee existence of Pareto points and stability conditions of single objective problems. Essentially, these conditions are not stronger than those in analogous results for single objective programming.This research was partially supported by ONR Grant N00014-97-1-784AMS Subject Classification: 90C29, 90C26     

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.     

Fuzzy programming and linear programming with several objective functions

In the recent past numerous models and methods have been suggested to solve the vectormaximum problem. Most of these approaches center their attention on linear programming problems with several objective functions. Apart from these approaches the theory of fuzzy sets has been employed to formulate and solve fuzzy linear programming problems. This paper presents the application of fuzzy linear programming approaches to the linear vectormaximum problem. It shows that solutions obtained by fuzzy linear programming are always efficient solutions. It also shows the consequences of using different ways of combining individual objective functions in order to determine an “optimal” compromise solution.     

Using modified maximum regret for finding a necessarily efficient solution in an interval MOLP problem

The current research concerns multiobjective linear programming problems with interval objective functions coefficients. It is known that the most credible solutions to these problems are necessarily efficient ones. To solve the problems, this paper attempts to propose a new model with interesting properties by considering the minimax regret criterion. The most important property of the new model is attaining a necessarily efficient solution as an optimal one whenever the set of necessarily efficient solutions is nonempty. In order to obtain an optimal solution of the new model, an algorithm is suggested. To show the performance of the proposed algorithm, numerical examples are given. Finally, some special cases are considered and their characteristic features are highlighted.     

A continuous approch for globally solving linearly constrained quadratic

In a continuous approach we propose an efficient method for globally solving linearly constrained quadratic zero-one programming considered as a d.c. (difference of onvex functions) program. A combination of the d.c. optimization algorithm (DCA) which has a finite convergence, and the branch-and-bound scheme was studied. We use rectangular bisection in the branching procedure while the bounding one proceeded by applying d.c.algorithms from a current best feasible point (for the upper bound) and by minimizing a well tightened convex underestimation of the objective function on the current subdivided domain (for the lower bound). DCA generates a sequence of points in the vertex set of a new polytope containing the feasible domain of the problem being considered. Moreover if an iterate is integral then all following iterates are integral too.Our combined algorithm converges so quite often to an integer approximate solution.Finally, we present computational results of several test problems with up to 1800

variables which prove the efficiency of our method, in particular, for linear zero-one programming     

On multiple objective programming problems with set functions

The convexity of a subset of a σ-algebra and the convexity of a set function on a convex subset are defined. Related properties are also examined. A Farkas-Minkowski theorem for set functions is then proved. These results are used to characterize properly efficient solutions for multiple objective programming problems with set functions by associated scalar problems.     

研究国际证券投资及其有效集的多目标线性规划方法

本文给出国际证券组合投资决策的多目标线性规划模型，以及求解有效国际证券组合的偏好系数加权法．在此基础上，应用线性多数规划技术研究有效国际证券组合集的几何特征，并给出相应结论和简单算例．     

Linear bilevel programs with multiple objectives at the upper level

Bilevel programming has been proposed for dealing with decision processes involving two decision makers with a hierarchical structure. They are characterized by the existence of two optimization problems in which the constraint region of the upper level problem is implicitly determined by the lower level optimization problem. Focus of the paper is on general bilevel optimization problems with multiple objectives at the upper level of decision making. When all objective functions are linear and constraints at both levels define polyhedra, it is proved that the set of efficient solutions is non-empty. Taking into account the properties of the feasible region of the bilevel problem, some methods of computing efficient solutions are given based on both weighted sum scalarization and scalarization techniques. All the methods result in solving linear bilevel problems with a single objective function at each level.