A compromise procedure for the multiple objective linear fractional programming problem

A generalization of a well-known multiple objective linear fractional programming (MOLFP) problem, the multiple objective fractional programming (MOFP) problem, is formulated. A concept of multiple objective programming (MOP) problem corresponding to MOFP is introduced and some relations between those problems are examined. Based on these results, a compromise procedure for MOLFP problem is proposed. A numerical example is given to show how the procedure works.     

Selecting tolerances in chance-constrained programming: A multiple objective linear programming approach

An importance issue concerning the practical application of chance-constrained programming is the lack of a rational method for choosing risk levels or tolerances on the chance constraints. While there has also been much recent debate on the relationship, equivalence, usefulness, and other characteristics of chance-constrained programming relative to stochastic programming with recourse, this paper focuses on the problem of improving the selection of tolerances within the chance-constrained framework. An approach is presented, based on multiple objective linear programming, which allows the decision maker to be more involved in the tolerance selection process, but does not demand a priori decisions on appropriate tolerances. An example is presented which illustrates the approach.     

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.     

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.     

PROMISE: A DSS for multiple objective stochastic linear programming problems

Most of the multiple objective linear programming (MOLP) methods which have been proposed in the last fifteen years suppose deterministic contexts, but because many real problems imply uncertainty, some methods have been recently developed to deal with MOLP problems in stochastic contexts. In order to help the decision maker (DM) who is placed before such stochastic MOLP problems, we have built a Decision Support System called PROMISE. On the one hand, our DSS enables the DM to identify many current stochastic contexts: risky situations and also situations of partial uncertainty. On the other hand, according to the nature of the uncertainty, our DSS enables the DM to choose the most appropriate interactive stochastic MOLP method among the available methods, if such a method exists, and to solve his problem via the chosen method.     

An exact method for computing the nadir values in multiple objective linear programming

In this paper we propose a new method to determine the exact nadir (minimum) criterion values over the efficient set in multiple objective linear programming (MOLP). The basic idea of the method is to determine, for each criterion, the region of the weight space associated with the efficient solutions that have a value in that criterion below the minimum already known (by default, the minimum in the payoff table). If this region is empty, the nadir value has been found. Otherwise, a new efficient solution is computed using a weight vector picked from the delimited region and a new iteration is performed. The method is able to find the nadir values in MOLP problems with any number of objective functions, although the computational effort increases significantly with the number of objectives. Computational experiments are described and discussed, comparing two slightly different versions of the method.     

Smooth representation of a parametric polyhedral convex set with application to sensitivity in optimization

We show in this paper that if a polyhedral convex set is defined by a parametric linear system with smooth entries, then it possesses local smooth representation almost everywhere. This result is then applied to study the differentiability of the solutions and the marginal functions of several classes of parametric optimization problems.

     

Duality-based regularization in a linear convex mathematical programming problem

For a linear convex mathematical programming (MP) problem with equality and inequality constraints in a Hilbert space, a dual-type algorithm is constructed that is stable with respect to input data errors. In the algorithm, the dual of the original optimization problem is solved directly on the basis of Tikhonov regularization. It is shown that the necessary optimality conditions in the original MP problem are derived in a natural manner by using dual regularization in conjunction with the constructive generation of a minimizing sequence. An iterative regularization of the dual algorithm is considered. A stopping rule for the iteration process is presented in the case of a finite fixed error in the input data.     

Robust aspects of solutions in deterministic multiple objective linear programming

We study questions of robustness of linear multiple objective problems in the sense of post-optimal analysis, that is, we study conditions under which a given efficient solution remains efficient when the criteria/objective matrix undergoes some alterations. We consider addition or removal of certain criteria, convex combination with another criteria matrix, or small perturbations of its entries. We provide a necessary and sufficient condition for robustness in a verifiable form and give two formulae to compute the radius of robustness.     

Sensitivity analysis on the priority of the objective functions in lexicographic multiple objective linear programs

This paper deals with a class of multiple objective linear programs (MOLP) called lexicographic multiple objective linear programs (LMOLP). In this paper, by providing an efficient algorithm which employs the preceding computations as well, it is shown how we can solve the LMOLP problem if the priority of the objective functions is changed. In fact, the proposed algorithm is a kind of sensitivity analysis on the priority of the objective functions in the LMOLP problems.     

Approximation of convex bodies by multiple objective optimization and an application in reachable sets

In this paper, we focus on approximating convex compact bodies. For a convex body described as the feasible set in objective space of a multiple objective programme, we show that finding it is equivalent to finding the non-dominated set of a multiple objective programme. This equivalence implies that convex bodies can be approximated using multiple objective optimization algorithms. Therefore, we propose a revised outer approximation algorithm for convex multiple objective programming problems to approximate convex bodies. Finally, we apply the algorithm to solve reachable sets of control systems and use numerical examples to show the effectiveness of the algorithm.     

A note on linear complementarity problems and multiple objective programming

Kostreva and Wiecek [3] introduced a problem called LCP-related weighted problem in connection with a multiple objective programming problem, and suggested that a given linear complementarity problem (LCP) can be solved by solving the LCP-related weighted problem associated with it. In this note we provide several clarifications of the claims made in [3]. Finally, we feel that solving any LCP by the approach given in [3] may not be as useful as it is claimed.Mathematics Subject Classification (2000): 90C33Received: October 1998 / Revised version: August 2003     

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.     

Asymptotic sign-solvability, multiple objective linear programming, and the nonsubstitution theorem

In this paper we investigate the asymptotic stability of dynamic, multiple-objective linear programs. In particular, we show that a generalization of the optimal partition stabilizes for a large class of data functions. This result is based on a new theorem about asymptotic sign-solvable systems. The stability properties of the generalized optimal partition are used to address a dynamic version of the nonsubstitution theorem.All research was conducted at Trinity University and was supported by NSF Grant 0097366.     

Geometry of optimal value functions with applications to redundancy in linear programming

In 1967, Wets and Witzgall (Ref. 1) made, in passing, a connection between frames of polyhedral cones and redundancy in linear programming. The present work elaborates and formalizes the theoretical details needed to establish this relation. We study the properties of optimal value functions in order to derive the correspondence between problems in redundancy and the frame of a polyhedral cone. The insights obtained lead to schemes to improve the efficiency of procedures to detect redundancy in the areas of linear programming, stochastic programming, and computational geometry.The author is indebted to G. Dewan for his review and discussions.     

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.     

Generalization of Murty's direct algorithm to linear and convex quadratic programming

Murty's algorithm for the linear complementarity problem is generalized to solve the optimality conditions for linear and convex quadratic programming problems with both equality and inequality constraints. An implementation is suggested which provides both efficiency and tight error control. Numerical experiments as well as field tests in various applications show favorable results.The author thanks K. G. Murty for his encouragement and helpful comments.     

多目标数学规划有效集的参数表示

研究了p-维多目标数学规划问题有效集的参数表示. 通过研究相关的单目标优化问题和相关的(p-1)-维多目标优化问题, 提出了几个新的关于p-维多目标规划有效集的表示定理.