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.     

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.     

Use of chance-constrained programming to account for stochastic variation in theA-matrix of large-scale linear programs: A forestry application

Linear programming (LP) is widely used to select the manner in which forest lands are managed. Because of the nature of forestry, this application has several unique characteristics. For example, the models consider many different management actions that take place over many years, thus resulting in very large LP formulations with diverse data. In addition, almost none of the data are known with certainty. The most pervasive occurrence of stochastic information is in the production coefficients, which indicate the uncertain response of the managed forest ecosystem to various management options. A chance-constrained approach to handling this uncertainty would often be appropriate in forestry applications —managers and decision makers would like to specify a probability with which uncertain constraints are met. Unfortunately, chance-constrained procedures forA-matrix uncertainty produce nonlinear programming problems, which cannot currently be solved for large-scale forestry applications. This paper utilizes a Monte Carlo simulation approach (a linear program is repeatedly solved with randomly perturbedA-matrix coefficients) to describe the distribution of total output when the individual production coefficients are random. An iterative procedure for chance-constraining feasibility is developed and demonstrated with this sort of randomA-matrix. An iterative approach is required because the mean and variance of total output are unknown functions of the randomA-matrix coefficients and the level of output required. This approach may have applications in other fields as well.     

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.     

On duality in multiple objective linear programming

In this paper we present two approaches to duality in multiple objective linear programming. The first approach is based on a duality relation between maximal elements of a set and minimal elements of its complement. It offers a general duality scheme which unifies a number of known dual constructions and improves several existing duality relations. The second approach utilizes polarity between a convex polyhedral set and the epigraph of its support function. It leads to a parametric dual problem and yields strong duality relations, including those of geometric duality.     

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.     

Calculus of convex polyhedra and polyhedral convex functions by utilizing a multiple objective linear programming solver

ABSTRACT

The article deals with operations defined on convex polyhedra or polyhedral convex functions. Given two convex polyhedra, operations like Minkowski sum, intersection and closed convex hull of the union are considered. Basic operations for one convex polyhedron are, for example, the polar, the conical hull and the image under affine transformation. The concept of a P-representation of a convex polyhedron is introduced. It is shown that many polyhedral calculus operations can be expressed explicitly in terms of P-representations. We point out that all the relevant computational effort for polyhedral calculus consists in computing projections of convex polyhedra. In order to compute projections we use a recent result saying that multiple objective linear programming (MOLP) is equivalent to the polyhedral projection problem. Based on the MOLP solver bensolve a polyhedral calculus toolbox for Matlab and GNU Octave is developed. Some numerical experiments are discussed.     

Industrial petrochemical production planning and expansion: A multi-objective linear programming approach

This paper considers a strategic model planning for the petrochemical industry. It concerns with the expansion in a firm producing multiple products in several regions of a country. The expansion of the existing facilities and the new ones are considered. It also exists a large amount of interdependencies among the firm’s products, because the output of one particular plant can be used as an input to the production of another plant in the same or different regions and to satisfy the final demand. The decision makers involved in the planning process should identify several objectives. Then, multiple objective programming is used for making trade-offs among the economic and operational factors considered. To define the interval criteria weights into the model we utilized the Analytic Hierarchy Process to bring them closer to the decision makers preferences. This work was sponsored by the Institut National Polytechnique de Toulouse, France, when the author was Associate Professor at the Département Génie des Systèmes Industriels.     

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     

Constrained optimization using multiple objective programming

In practical applications of mathematical programming it is frequently observed that the decision maker prefers apparently suboptimal solutions. A natural explanation for this phenomenon is that the applied mathematical model was not sufficiently realistic and did not fully represent all the decision makers criteria and constraints. Since multicriteria optimization approaches are specifically designed to incorporate such complex preference structures, they gain more and more importance in application areas as, for example, engineering design and capital budgeting. The aim of this paper is to analyze optimization problems both from a constrained programming and a multicriteria programming perspective. It is shown that both formulations share important properties, and that many classical solution approaches have correspondences in the respective models. The analysis naturally leads to a discussion of the applicability of some recent approximation techniques for multicriteria programming problems for the approximation of optimal solutions and of Lagrange multipliers in convex constrained programming. Convergence results are proven for convex and nonconvex problems.     

A WIN-WIN approach to multiple objective linear programming problems

Interactive decision making arose as a means to overcome the uncertainty concerning the decision maker's (DM) value function. So far the search is confined to nondominated alternatives, which assumes that a win–lose strategy is adopted. The purpose of this paper is to suggest a complementary interactive algorithm that uses an interior point method to solve multiple objective linear programming problems. As the algorithm proceeds, the DM has access to intermediate solutions. The sequence of intermediate solutions has a very interesting characteristic: all of the criteria are improved, that is, a solution Open image in new window , that follows another solution Open image in new window , has the values of all objectives greater than those of Open image in new window . This WIN-WIN feature allows the DM to reach a nondominated solution without making any trade-off among the objective functions. However, there is no impediment in proceeding with traditional multiobjective methods.     

A dual-uncertainty-based chance-constrained model for municipal solid waste management

A double-sided dual-uncertainty-based chance-constrained programming (DDCCP) model was developed for supporting municipal solid waste management under uncertainty. The model was capable of tackling left-hand- and right-hand-side variables in constraints where those variables were affected by dual uncertainties (i.e. e.g. both fuzziness and randomness); and they were expressed as fuzzy random variables (FRVs). In this study, DDCCP model were formulated and solved based on stochastic and fuzzy chance-constrained programming techniques, leading to optimal solutions under different levels of constraints violation and satisfaction reliabilities. A long-term solid waste management problem was used to demonstrate the feasibility and applicability of DDCCP model. The obtained results indicated that DDCCP was effective in handling constraints with FRVs through satisfying them at a series of allowable levels, generating various solutions that facilitated evaluation of trade-offs between system economy and reliability. The proposed model could help decision makers establish cost-effective waste-flow allocation patterns under complex uncertainties, and gain in-depth insights into the municipal solid waste management system.     

A chance-constrained programming algorithm

This paper describes a new algorithm solving the deterministic equivalents of chance-constrained problems where the random variables are normally distributed and independent of each other. In this method nonlinear chance-constraints are first replaced by uniformly tighter linear constraints. The resulting linear programming problem is solved by a standard simplex method. The linear programming problem is then revised using the solution data and solved again until the stopping rule of the algorithm terminates the process. It is proved that the algorithm converges and that the solution found is the -optimal solution of the chance-constrained programming problem.The computational experience of the algorithm is reported. The algorithm is efficient if the random variables are distributed independently of each other and if they number less than two hundred. The computing system is called CHAPS, i.e. Chance-ConstrainedProgrammingSystem.     

A dual approach to solve the fuzzy linear programming problem

A concept of fuzzy objective based on the Fuzzification Principle is presented. In accordance with this concept, the Fuzzy Linear Mathematical Programming problem is easily solved. A relationship of duality among fuzzy constraints and fuzzy objectives is given. The dual problem of a Fuzzy Linear Programming problem is also defined.     

A method for finding well-dispersed subsets of non-dominated vectors for multiple objective mixed integer linear programs

We present an algorithm for generating a subset of non-dominated vectors of multiple objective mixed integer linear programming. Starting from an initial non-dominated vector, the procedure finds at each iteration a new one that maximizes the infinity-norm distance from the set dominated by the previously found solutions. When all variables are integer, it can generate the whole set of non-dominated vectors.     

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.     

Fuzzy approaches for multiple objective linear fractional optimization

The problem of finding a solution to a multiple objective linear fractional program arises in several real world situations.In this paper we advocate that fuzzy sets theory provides a basis for solving this problem with sufficient consistency and rigorousness.After representing imprecise aspirations of the decision maker by structured linguistic variables or converting the original problem via approximations or change of variables into a multiple objective linear program, techniques of fuzzy linear programming may be used to reach a satisfactory solution.It is shown that under reasonable restrictions, this solution is efficient (Pareto optimal) for the original problem. Numerical examples are also included for illustration.     

A computer graphics-based Decision Support System for multiple objective linear programming

In this paper we propose a computer-graphics based Decision Support System for multiple objective linear programming that builds on the VIG system (Visual Interactive Goal programming). The essential part of the VIG system is Pareto Race, a dynamic and visual approach for exploring the efficient frontier of a multiple objective linear programming problem. Our objective is to extend Pareto Race to large-scale multiple objective linear programming. The approach works with any efficient solutions that are in general not extreme point solutions. Interactive use of computer graphics plays a central role. The approach, the underlying theory, and an illustrative example are described.