Insoluble multicriteria linear programming problems

This note concerns a method for analyzing insoluble multicriteria linear programming problems.     

Sensitivity analysis of an agricultural linear programming model

The paper presents a method of sensitivity analysis for linear systems and its practical application, allowing directs interpretation of results. The subject of analysis is a set of large regional agricultural LP models meant for rationalization of regional agricultural policies in Polish conditions. Sensitivity analysis is performed with regard to perturbations in values of elements of the LP basis matrix for a given LP solution. Software developed makes it possible to analyze solutions obtained with MPS 360 or MPSX 370. Structural approach was applied consisting in block-triangularization of the matrix defining the set of equations corresponding to the optimum vertex. The approach lowers computational burden and yields qualitative sensitivity assessment, i.e. enables exclusion of influences of certain parameters on some variables.     

Some perturbation theory for linear programming

Mathematical Programming -     

Bicriteria linear fractional programming

As a step toward the investigation of the multicriteria linear fractional program, this paper provides a thorough analysis of the bicriteria case. It is shown that the set of efficient points is a finite union of linearly constrained sets and the efficient frontier is the image of a finite number of connected line segments of efficient points. A simple algorithm using only one-dimensional parametric linear programming techniques is developed to evaluate the efficient frontier.This research was partially supported by NRC Research Grant No. A4743. The authors wish to thank two anonymous referees for their helpful comments on an earlier draft of this paper.     

An approximate solution of linear multicriteria control problems through the multicriteria simplex method

This paper deals with multicriteria, linear, continuous optimal control problems through the application of the multicriteria simplex method. Since the system is linear, the state variables at a given time can be expressed in terms of definite integrals. Upon using standard numerical integration formulas, the definite integrals are approximately expressed by means of weighted sums of the integrands. Then, after introducing some suitable auxiliary variables, approximate linear multicriteria programming problems are formulated. Illustrative numerical examples are provided to indicate the efficiency of the proposed method.The author is indebted to Professor Y. Sawaragi of Kyoto University for his constant encouragement. The author also wishes to thank T. Suwa for his cooperation in preparing the programming for the digital computer.     

MCS—A new algorithm for multicriteria optimisation in constraint programming

In this paper we propose a new algorithm called MCS for the search for solutions to multicriteria combinatorial optimisation problems. To quickly produce a solution that offers a good trade-off between criteria, the MCS algorithm alternates several Branch & Bound searches following diversified search strategies. It is implemented in CP in a dedicated framework and can be specialised for either complete or partial search.     

Maximal and supremal tolerances in multiobjective linear programming

Let a multiobjective linear programming problem and any efficient solution be given. Tolerance analysis aims to compute interval tolerances for (possibly all) objective function coefficients such that the efficient solution remains efficient for any perturbation of the coefficients within the computed intervals. The known methods either yield tolerances that are not the maximal possible ones, or they consider perturbations of weights of the weighted sum scalarization only. We focus directly on perturbations of the objective function coefficients, which makes the approach independent on a scalarization technique used. In this paper, we propose a method for calculating the supremal tolerance (the maximal one need not exist). The main disadvantage of the method is the exponential running time in the worst case. Nevertheless, we show that the problem of determining the maximal/supremal tolerance is NP-hard, so an efficient (polynomial time) procedure is not likely to exist. We illustrate our approach on examples and present an application in transportation problems. Since the maximal tolerance may be small, we extend the notion to individual lower and upper tolerances for each objective function coefficient. An algorithm for computing maximal individual tolerances is proposed.     

Additive and multiplicative tolerance in multiobjective linear programming

We consider a multiobjective linear program. We propose a procedure for computing an additive and multiplicative (percentage) tolerance in which all the objective function coefficients may simultaneously and independently vary while preserving the efficiency of a given solution. For a nondegenerate basic solution, the procedure runs in polynomial time.     

Vector linear programming in zero-sum multicriteria matrix games

In this paper, a multiple-objective linear problem is derived from a zero-sum multicriteria matrix game. It is shown that the set of efficient solutions of this problem coincides with the set of Paretooptimal security strategies (POSS) for one of the players in the original game. This approach emphasizes the existing similarities between the scalar and multicriteria matrix games, because in both cases linear programming can be used to solve the problems. It also leads to different scalarizations which are alternative ways to obtain the set of all POSS. The concept of ideal strategy for a player is introduced, and it is established that a pair of Pareto saddle-point strategies exists if both players have ideal strategies. Several examples are included to illustrate the results in the paper.     

Stability and accuracy functions in multicriteria linear combinatorial optimization problems

We consider a vector linear combinatorial optimization problem in which initial coefficients of objective functions are subject to perturbations. For Pareto and lexicographic principles of efficiency we introduce appropriate measures of the quality of a given feasible solution. These measures correspond to so-called stability and accuracy functions defined earlier for scalar optimization problems. Then we study properties of such functions and calculate the maximum norms of perturbations for which an efficient solution preserves the efficiency. This work was partially supported through NATO Science Fellowship grant.     

Generalized linear fractional programming under interval uncertainty

Data in many real-life engineering and economical problems suffer from inexactness. Herein we assume that we are given some intervals in which the data can simultaneously and independently perturb. We consider a generalized linear fractional programming problem with interval data and present an efficient method for computing the range of optimal values. The method reduces the problem to solving from two to four real-valued generalized linear fractional programs, which can be computed in polynomial time using an appropriate interior point method solver.     

Minimax linear programming problem

In this paper, we consider the following minimax linear programming problem: min z = max_{1 ≤ j ≤ n}{C_jX_j}, subject to Ax = g, x ≥ 0. It is well known that this problem can be transformed into a linear program by introducing n additional constraints. We note that these additional constraints can be considered implicitly by treating them as parametric upper bounds. Based on this approach we develop two algorithms: a parametric algorithm and a primal—dual algorithm. The parametric algorithm solves a linear programming problem with parametric upper bounds and the primal—dual algorithm solves a sequence of related dual feasible linear programming problems. Computation results are also presented, which indicate that both the algorithms are substantially faster than the simplex algorithm applied to the enlarged linear programming problem.     

Sensitivity analysis in geometric programming

A unified approach to computing first, second, or higher-order derivatives of any of the primal and dual variables or multipliers of a geometric programming problem, with respect to any of the problem parameters (term coefficients, exponents, and constraint right-hand sides) is presented. Conditions under which the sensitivity equations possess a unique solution are developed, and ranging results are also derived. The analysis for approximating second and higher-order sensitivity generalizes to any sufficiently smooth nonlinear program.     

Sensitivity analysis in interval-valued trapezoidal fuzzy number linear programming problems

The aim of this article is to introduce a formulation of fuzzy linear programming problems involving the level (h^L,h^U)$(h^L\text{,}{h}^U)$-interval-valued trapezoidal fuzzy numbers as parameters. Indeed, such a formulation is the general form of trapezoidal fuzzy number linear programming problems. Then, it is demonstrated that study of the sensitivity analysis for the level (h^L,h^U)$(h^L\text{,}{h}^U)$-interval-valued trapezoidal fuzzy number linear programming problems gives rise to the same expected results as those obtained for trapezoidal fuzzy number linear programming problems.     

Identifying the anchor points in DEA using sensitivity analysis in linear programming

In this paper, the anchor points in DEA, as an important subset of the set of extreme efficient points of the production possibility set (PPS), are studied. A basic definition, utilizing the multiplier DEA models, is given. Then, two theorems are proved which provide necessary and sufficient conditions for characterization of these points. The main results of the paper lead to a new interesting connection between DEA and sensitivity analysis in linear programming theory. By utilizing the established theoretical results, a successful procedure for identification of the anchor points is presented.     

Sensitivity analysis in posynomial geometric programming

Sensitivity analysis results for general parametric posynomial geometric programs are obtained by utilizing recent results from nonlinear programming. Duality theory of geometric programming is exploited to relate the sensitivity results derived for primal and dual geometric programs. The computational aspects of sensitivity calculations are also considered.This work was part of the doctoral dissertation completed in the Department of Operations Research, George Washington University, Washington, DC. The author would like to express his gratitude to the thesis advisor, Prof. A. V. Fiacco, for overall guidance and stimulating discussions which inspired the development of this research work.     

Graphical analysis of duality and the Kuhn-Tucker conditions in linear programming

Careful inspection of the geometry of the primal linear programming problem reveals the Kuhn-Tucker conditions as well as the dual. Many of the well-known special cases in duality are also seen from the geometry, as well as the complementary slackness conditions and shadow prices. The latter at demonstrated to differ from the dual variables in situations involving primal degeneracy. Virtually all the special relationships between linear programming and duality theory can be seen from the geometry of the primal and an elementary application of vector analysis.     

Developments in fuzzy multicriteria analysis

Selecting or ranking available alternatives (observations/objects) with respect to multiple, often conflicting criteria in a fuzzy environment usually referred to as fuzzy multicriteria analysis is a problem of a major interest in information and engineering. Methodologies for addressing this problem have been developed from a variety of research disciplines, including statistics, econometrics, artificial intelligent, and operations research. This paper presents an overview of the developments in fuzzy multicriteria analysis. It discusses the complexity of fuzzy multicriteria analysis and analyses the existing approaches from four different perspectives for facilitating a better understanding of the recent development in this domain. Finally, the paper elaborates on the future research areas in fuzzy multicriteria analysis.     

Sensitivity analysis in linear programming and semidefinite programming using interior-point methods

We analyze perturbations of the right-hand side and the cost parameters in linear programming (LP) and semidefinite programming (SDP). We obtain tight bounds on the perturbations that allow interior-point methods to recover feasible and near-optimal solutions in a single interior-point iteration. For the unique, nondegenerate solution case in LP, we show that the bounds obtained using interior-point methods compare nicely with the bounds arising from using the optimal basis. We also present explicit bounds for SDP using the Monteiro-Zhang family of search directions and specialize them to the AHO, H..K..M, and NT directions. Received: December 1999 / Accepted: January 2001?Published online March 22, 2001