On Sensitivity in Linear Multiobjective Programming

In this paper, we prove that, if the data of a linear multiobjectiveprogramming problem are smooth functions of a parameter, then in theparameter space there is an open dense subset where the efficient solutionset of the problem can be locally represented as a union of some faces whosevertices and directions are smooth functions of the parameter.     

On Approximate Efficiency in Multiobjective Programming

This paper is focused on approximate ( -efficient) solutions of multiobjective mathematical programs. We introduce a new -efficiency concept which extends and unifies different notions of approximate solution defined in the literature. We characterize these -efficient solutions in convex multiobjective programs through approximate solutions of linear scalarizations, which allow us to obtain parametric representations of different -efficiency sets. Several classical -efficiency notions are considered in order to show the concepts introduced and the results obtained.This research was partially supported by Ministerio de Ciencia y Tecnología (Spain), project BFM2003-02194.     

多目标规划的αk-较多有效性

本文先讨论带两个参数的αk-较多锥的几个性质,借助它们研究了多目标规划问题的αk-较多有效解和αk-较多最优解之间以及它们与Pareto有效解之间的关系.同时,还各自给出这两类解存在的两个充要条件.     

A Semidefinite Programming approach for solving Multiobjective Linear Programming

Several algorithms are available in the literature for finding the entire set of Pareto-optimal solutions of Multiobjective Linear Programmes (MOLPs). However, all of them are based on active-set methods (simplex-like approaches). We present a different method, based on a transformation of any MOLP into a unique lifted Semidefinite Program (SDP), the solutions of which encode the entire set of Pareto-optimal extreme point solutions of any MOLP. This SDP problem can be solved, among other algorithms, by interior point methods; thus unlike an active set-method, our method provides a new approach to find the set of Pareto-optimal solutions of MOLP.     

Primal-Dual Simplex Method for Multiobjective Linear Programming

We develop a primal-dual simplex algorithm for multicriteria linear programming. It is based on the scalarization theorem of Pareto optimal solutions of multicriteria linear programs and the single objective primal-dual simplex algorithm. We illustrate the algorithm by an example, present some numerical results, give some further details on special cases and point out future research. The paper was written during a visit of the first author to the University of Sevilla financed by a grant of the Andalusian Consejería de Educación. The research of the first author was partially supported by University of Auckland Grant 3602178/9275. The research of the second and third authors was partially financed by Spanish Grants BFM2001-2378, BFM2001-4028, MTM2004-0909 and HA2003-0121. We thank Anthony Przybylski for the implementation and making his results available. We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper.     

Bounds in Multistage Linear Stochastic Programming

Multistage stochastic programs, which involve sequences of decisions over time, are usually hard to solve in realistically sized problems. Providing bounds for optimal solution may help in evaluating whether it is worth the additional computations for the stochastic program vs. simplified approaches. In this paper we generalize measures from the two-stage case, based on different levels of available information, to the multistage stochastic programming problems. A set of theorems providing chains of inequalities among the new quantities are proved. Numerical results on a case study related to a simple transportation problem illustrate the described relationships.     

Robust Solutions in Stochastic Linear Programming

The recent developments in stochastic linear programming are reviewed here broadly in their applied aspects. They include non-parametric methods which are applicable in situations of incomplete knowledge and partial uncertainty. This framework is shown to be most suitable for developing robust optimal solutions. For instance, a class of non-parametric methods based on the minimax principle and the criteria of stochastic dominance is developed here to illustrate its wide scope of application. It is shown that this class of methods provides a measure of robustness through the adoption of a cautious policy. Some examples are discussed using the recent field of data envelopment analysis.     

Efficient Solution Concepts and Their Relations in Stochastic Multiobjective Programming

In this work, different concepts of efficient solutions to problems of stochastic multiple-objective programming are analyzed. We center our interest on problems in which some of the objective functions depend on random parameters. The existence of different concepts of efficiency for one single stochastic problem, such as expected-value efficiency, minimum-risk efficiency, etc., raises the question of their quality. Starting from this idea, we establish some relationships between the different concepts. Our study enables us to determine what type of efficient solutions are obtained by each of these concepts.     

多目标线性生产规划的模糊联盟对策

研究多目标生产规划的模糊联盟对策的求解问题,提出了求解多目标模糊联盟对策的Shapley值方法.通过建立多目标线性生产规划的模糊联盟对策模型,提出了多目标对策转化为多个单目标对策的权重分析法.结合多目标线性生产规划问题的实例,给出不同权重系数下局中人合作的利益分配策略.     

Stackelberg Solutions to Multiobjective Two-Level Linear Programming Problems

In this paper, we consider a multiobjective two-level linear programming problem in which the decision maker at each level has multiple-objective functions conflicting with each other. The decision maker at the upper level must take account of multiple or infinite rational responses of the decision maker at the lower level in the problem. We examine three kinds of situations based on anticipation of the decision maker at the upper level: optimistic anticipation, pessimistic anticipation, and anticipation arising from the past behavior of the decision maker at the lower level. Mathematical programming problems for obtaining the Stackelberg solutions based on the three kinds of anticipation are formulated and algorithms for solving the problems are presented. Illustrative numerical examples are provided to understand the geometrical properties of the solutions and demonstrate the feasibility of the proposed methods.     

Deviation Measures in Linear Two-Stage Stochastic Programming

We consider a linear two-stage stochastic program. Whereas optimization in the traditional setting is based solely on expectation, we include risk measures reflecting dispersions of the random objective. Presenting the mean-risk models, we aim to extend existing results for the expectation-based model. In particular, we discuss structural properties such as continuity, differentiability and convexity and address stability issues. Furthermore, we propose algorithmic treatment with a slight variation of the L-shaped method     

不确定信息多目标线性优化的鲁棒方法

研究不确定信息的多目标线性优化问题,其数据不能精确给出但是属于一个给定的集合.首先,采用鲁棒方法把该问题转化为一个确定的多目标优化问题.然后,给出此问题解存在的充分条件.最后,通过实例验证了用鲁棒方法解决不确定信息的多目标线性优化问题的有效性.     

Stochastic Optimal Control and Linear Programming Approach

We study a classical stochastic optimal control problem with constraints and discounted payoff in an infinite horizon setting. The main result of the present paper lies in the fact that this optimal control problem is shown to have the same value as a linear optimization problem stated on some appropriate space of probability measures. This enables one to derive a dual formulation that appears to be strongly connected to the notion of (viscosity sub) solution to a suitable Hamilton-Jacobi-Bellman equation. We also discuss relation with long-time average problems.     

应用模糊目标规划方法求解多目标线性分式规划问题

针对多目标分式线性规划问题,提出利用上(下)界表示目标期望水平及允许上(下)限,且利用一阶泰勒公式逼近隶属函数,将多目标分式规划转化为线性规划问题,并用单纯形法求解,通过实验算例说明了所提出的方法的有效性.     

Anchoring Points and Cones of Opportunities in Interior Multiobjective Linear Programming

This paper presents a modification of one variant of Karmarkar's interior-point linear programming algorithm to Multiobjective Linear Programming (MOLP) problems. We show that by taking the variant known as the affine-scaling primal algorithm, generating locally-relevant scaling coefficients and applying them to the projected gradients produced by it, we can define what we refer to as anchoring points that then define cones in which we search for an optimal solution through interaction with the decision maker. Currently existing MOLP algorithms are simplex-based and make their progress toward the optimal solution by following 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 optimal solution may prove less sensitive to problem size. We refer to the class of MOLP algorithms resulting from this variant as Affine-Scaling Interior Multiobjective Linear Programming (ASIMOLP) algorithms.     

An Interval-Parameter Fuzzy Approach for Multiobjective Linear Programming Under Uncertainty

An interval-parameter fuzzy linear programming method (IFMOLP) is proposed in this study for multiple objective decision-making under uncertainty. As a hybrid of interval-parameter and fuzzy methodologies, the IFMOLP incorporates interval-parameter linear programming and fuzzy multiobjective programming approaches to form an integrated optimization system. The method inherits advantages of interval-parameter programming, and allows uncertainties and decision-makers’ aspirations to be effectively communicated into its programming processes and resulting solutions. Membership functions for both objectives and constraints are formulated to reflect uncertainties in different system components and their interrelationships. An interactive solution procedure has been developed based on solution approaches of the interval-parameter and fuzzy programming techniques, plus necessary measures for handling the multiobjective feature. A didactic example is provided in the paper to illustrate the detailed solution process. Possibilities of further improvements by seeking Pareto optimum and incorporating flexible preference within constraints are also discussed.     

线性约束多目标规划的非单调信赖域算法

本文对线性约束多规划问题提出了一类非单调信赖域算法 ,该方法是可行点法与信赖域技巧的结合 .在一定的条件下证明了算法的全局收敛性 .并进行了数值试验 .     

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.     

Satisfactory solution concepts and their relations for Stochastic Multiobjective Programming problems

This work deals with the concept of satisfactory solution for Stochastic Multiobjective Programming (SMP) problems. Based on previous literature, we will introduce different concepts of satisfactory solutions for SMP problems, define a new concept of solution (where the decision maker (DM) sets his/her preferences in terms of two aspiration levels for the stochastic objective and two probabilities to reach those levels), and establish some relationship between these concepts. The results will aim at featuring these concepts and determine the differences between them. Moreover, the paper proposes a new step by step procedure to exchange information between the analyst and DM prior to solving the problem. Thus, the DM will be able to choose the transformation criterion for each stochastic objective and the aspiration level.     

集值映射多目标半定规划的Benson真有效性

将多目标半定规划问题推广到集值映射,在广义锥-次类凸条件下,在Benson真有效性意义下研究了问题的标量化,Lagrange函数与无约束化,真鞍点条件和对偶性.