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.     

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.     

Multiobjective data envelopment analysis

Data envelopment analysis (DEA) is popularly used to evaluate relative efficiency among public or private firms. Most DEA models are established by individually maximizing each firm's efficiency according to its advantageous expectation by a ratio. Some scholars have pointed out the interesting relationship between the multiobjective linear programming (MOLP) problem and the DEA problem. They also introduced the common weight approach to DEA based on MOLP. This paper proposes a new linear programming problem for computing the efficiency of a decision-making unit (DMU). The proposed model differs from traditional and existing multiobjective DEA models in that its objective function is the difference between inputs and outputs instead of the outputs/inputs ratio. Then an MOLP problem, based on the introduced linear programming problem, is formulated for the computation of common weights for all DMUs. To be precise, the modified Chebychev distance and the ideal point of MOLP are used to generate common weights. The dual problem of this model is also investigated. Finally, this study presents an actual case study analysing R&D efficiency of 10 TFT-LCD companies in Taiwan to illustrate this new approach. Our model demonstrates better performance than the traditional DEA model as well as some of the most important existing multiobjective DEA models.     

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

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

Solution approaches for the multiobjective stochastic programming

We survey in this paper various solution approaches for multiobjective stochastic problems where random variables can be in both objectives and constraints parameters. Once a problem requires a stochastic formulation, a first step consists in transforming the problem into its deterministic formulation. We propose to classify and evaluate such transformations with regards to the many proposed concepts of efficiency. The paper addresses also some applications of the multiobjective stochastic programming models.     

Risk-control approach for bottleneck transportation problem with randomness and fuzziness

Solving transportation problems is essential in engineering and supply chain management, where profitability depends on optimal traffic flow. This study proposes risk-control approaches for two bottleneck transportation problems with random variables and preference levels to objective functions with risk parameters. Each proposed model is formulated as a multiobjective programming problem using robust-based optimization derived from stochastic chance constraints. Since it is impossible to obtain a transportation pattern that optimizes all objective functions, our proposed models are numerically solved by introducing an aggregation function for the multiobjective problem. An exact algorithm that performs deterministic equivalent transformations and introduces auxiliary problems is also developed.     

A compromise solution for the multiobjective stochastic linear programming under partial uncertainty

This paper solves the multiobjective stochastic linear program with partially known probability. We address the case where the probability distribution is defined by crisp inequalities. We propose a chance constrained approach and a compromise programming approach to transform the multiobjective stochastic linear program with linear partial information on probability distribution into its equivalent uniobjective problem. The resulting program is then solved using the modified L-shaped method. We illustrate our results by an example.     

On stability in multiobjective programming — A stochastic approach

In this paper we assume that a deterministic multiobjective programming problem is approximated by surrogate problems based on estimations for the objective functions and the constraints. Making use of a large deviations approach, we investigate the behaviour of the constraint sets, the sets of efficient points and the solution sets if the size of the underlying sample tends to infinity. The results are illustrated by applying them to stochastic programming with chance constraints, where (i) the distribution function of the random variable is estimated by the empirical distribution function, (ii) certain parameters have to be estimated.     

Constructing efficient solutions structure of multiobjective linear programming

It is not a difficult task to find a weak Pareto or Pareto solution in a multiobjective linear programming (MOLP) problem. The difficulty lies in finding all these solutions and representing their structure. This paper develops an algorithm for solving this problem. We investigate the solutions and their relationships in the objective space. The algorithm determines finite number of weights, each of which corresponds to a weighted sum problems. By solving these problems, we further obtain all weak Pareto and Pareto solutions of the MOLP and their structure in the constraint space. The algorithm avoids the degeneration problem, which is a major hurdle of previous works, and presents an easy and clear solution structure.     

Computationally Efficient Methods for Calculating the Ideal Solution for MOLP Problems

This paper presents the results of an investigation into computational considerations that are relevant to large-scale multiobjective linear programming (MOLP) problems. Four approaches to obtaining a representation of the ideal solution are compared. Statistics on the number of simplex iterations and CPU time required are analysed for a set of randomly generated multiobjective linear programming problems. Recommendations are made based on the analysis of these results which are applicable to many MOLP solution algorithms.     

Gradient projection and local region search for multiobjective optimisation

This paper presents a new method for multiobjective optimisation based on gradient projection and local region search. The gradient projection is conducted through the identification of normal vectors of an efficient frontier. The projection of the gradient of a nonlinear utility function onto the tangent plane of the efficient frontier at a given efficient solution leads to the definition of a feasible local region in a neighbourhood of the solution. Within this local region, a better efficient solution may be sought. To implement such a gradient-based local region search scheme, a new auxiliary problem is developed. If the utility function is given explicitly, this search scheme results in an iterative optimisation algorithm capable of general nonseparable multiobjective optimisation. Otherwise, an interactive decision making algorithm is developed where the decision maker (DM) is expected to provide local preference information in order to determine trade-off directions and step sizes. Optimality conditions for the algorithms are established and the convergence of the algorithms is proven. A multiobjective linear programming (MOLP) problem is taken for example to demonstrate this method both graphically and analytically. A nonlinear multiobjective water quality management problem is finally examined to show the potential application of the method to real world decision problems.     

Two-stage stochastic linear programs with incomplete information on uncertainty

Two-stage stochastic linear programming is a classical model in operations research. The usual approach to this model requires detailed information on distribution of the random variables involved. In this paper, we only assume the availability of the first and second moments information of the random variables. By using duality of semi-infinite programming and adopting a linear decision rule, we show that a deterministic equivalence of the two-stage problem can be reformulated as a second-order cone optimization problem. Preliminary numerical experiments are presented to demonstrate the computational advantage of this approach.     

随机多目标规划区间交互过程及其应用

针对随机多目标规划问题中目标函数含有连续型随机变量的情形,设计一种基于概率有效性意义下的区间交互过程,将概率有效性与多目标问题理想点进行有机结合,有效辅助决策者寻求愿意承受的风险水平,并进行决策,简化了随机多目标优化问题。最后通过实例说明该交互过程的作用。     

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.     

Multiobjective transportation problem with interval cost,source and destination parameters

In this paper, we focus on the solution procedure of the multiobjective transportation problem (MOTP) where the cost coefficients of the objective functions, and the source and destination parameters have been expressed as interval values by the decision maker. This problem has been transformed into a classical MOTP where to minimize the interval objective function, the order relations that represent the decision maker's preference between interval profits have been defined by the right limit, left limit, centre, and half-width of an interval. The constraints with interval source and destination parameters have been converted into deterministic ones. Finally, the equivalent transformed problem has been solved by fuzzy programming technique. Numerical examples have been provided to illustrate the solution procedure for three possible cases of the original problem.     

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.     

A Chance Constrained Approach to Fractional Programming with Random Numerator

This paper presents a chance constrained programming approach to the problem of maximizing the ratio of two linear functions of decision variables which are subject to linear inequality constraints. The coefficient parameters of the numerator of the objective function are assumed to be random variables with a known multivariate normal probability distribution. A deterministic equivalent of the stochastic linear fractional programming formulation has been obtained and a subsidiary convex program is given to solve the deterministic problem.     

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.     

Solving the multiobjective possibilistic linear programming problem

In conventional multiobjective decision making problems, the estimation of the parameters of the model is often a problematic task. Normally they are either given by the decision maker (DM), who has imprecise information and/or expresses his considerations subjectively, or by statistical inference from past data and their stability is doubtful. Therefore, it is reasonable to construct a model reflecting imprecise data or ambiguity in terms of fuzzy sets for which a lot of fuzzy approaches to multiobjective programming have been developed. In this paper we propose a method to solve a multiobjective linear programming problem involving fuzzy parameters (FP-MOLP), whose possibility distributions are given by fuzzy numbers, estimated from the information provided by the DM. As the parameters, intervening in the model, are fuzzy the solutions will be also fuzzy. We propose a new Pareto Optimal Solution concept for fuzzy multiobjective programming problems. It is based on the extension principle and the joint possibility distribution of the fuzzy parameters of the problem. The method relies on α-cuts of the fuzzy solution to generate its possibility distributions. These ideas are illustrated with a numerical example.     

A Deterministic Approach To Stochastic Optimal Control With Application To Anticipative Control

Using the decomposition of solution of SDE, we consider the stochastic optimal control problem with anticipative controls as a family of deterministic control problems parametrized by the paths of the driving Wiener process and of a newly introduced Lagrange multiplier stochastic process (nonanticipativity equality constraint). It is shown that the value function of these problems is the unique global solution of a robust equation (random partial differential equation) associated to a linear backward Hamilton-Jacobi-Bellman stochastic partial differential equation (HJB SPDE). This appears as limiting SPDE for a sequence of random HJB PDE's when linear interpolation approximation of the Wiener process is used. Our approach extends the Wong-Zakai type results [20] from SDE to the stochastic dynamic programming equation by showing how this arises as average of the limit of a sequence of deterministic dynamic programming equations. The stochastic characteristics method of Kunita [13] is used to represent the value function. By choosing the Lagrange multiplier equal to its nonanticipative constraint value the usual stochastic (nonanticipative) optimal control and optimal cost are recovered. This suggests a method for solving the anticipative control problems by almost sure deterministic optimal control. We obtain a PDE for the “cost of perfect information” the difference between the cost function of the nonanticipative control problem and the cost of the anticipative problem which satisfies a nonlinear backward HJB SPDE. Poisson bracket conditions are found ensuring this has a global solution. The cost of perfect information is shown to be zero when a Lagrangian submanifold is invariant for the stochastic characteristics. The LQG problem and a nonlinear anticipative control problem are considered as examples in this framework