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     

Sensitivity analysis in fuzzy linear programming

In this paper we propose a certain interpretation of a partially fuzzy LP-Problem. This LP-is dualized and the corresponding variables of the Dual are analyzed and an economic interpretation is given.     

Sensitivity analysis for nonlinear programming using penalty methods

In this paper we establish a theoretical basis for utilizing a penalty-function method to estimate sensitivity information (i.e., the partial derivatives) of a localsolution and its associated Lagrange multipliers of a large class of nonlinear programming problems with respect to a general parametric variation in the problem functions. The local solution is assumed to satisfy the second order sufficient conditions for a strict minimum. Although theoretically valid for higher order derivatives, the analysis concentrates on the estimation of the first order (first partial derivative) sensitivity information, which can be explicitly expressed in terms of the problem functions. For greater clarity, the results are given in terms of the mixed logarithmic-barrier quadratic-loss function. However, the approach is clearly applicable toany algorithm that generates a once differentiable solution trajectory.Supported by the U.S. Army Research Office, Durham.     

Sensitivity analysis in fuzzy number linear programming problems

In this paper, we generalize the concept of sensitivity analysis in fuzzy number linear programming (FLNP) problems by applying fuzzy simplex algorithms and using the general linear ranking functions on fuzzy numbers. The purpose of sensitivity analysis is to determine changes in the optimal solution of FNLP problem resulting from changes in the data. If the change affects the optimality of the basis, we perform primal pivots to achieve optimality by use of the fuzzy primal simplex method. Whenever the change destroys the feasibility of the optimal basis, we perform dual pivots to achieve feasibility by use of the fuzzy dual simplex method.     

A linear programming problem in harmonic analysis

For a given subset E of the natural numbers it is desired to maximize Σ_n?Ea_n subject to a_n?0, 1+Σ_n?Ea_n cosnθ?0 for θ?[0,π]. A dual program is defined, and a duality principle is established. Extensions to other series of functions are given, and these include the motivating example of P. Delsarte [Philips Res. Repts.27 (1972), 272–289].     

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.     

An application of sensitivity analysis to a linear programming problem

Summary In an ordinary linear programming problem with a given set of statistical data, it is not known generally how reliable is the optimal basic solution. Our object here is to indicate a general method of reliability analysis for testing the sensitivity of the optimal basic solution and other basic solutions, in terms of expectation and variance when sample observations are available. For empirical illustration the time series data on input-output coefficients of a single farm producing three crops with three resources is used. The distributions of the first, second, and third best solutions are estimated assuming the vectors of net prices and resources to be constant and the coefficient matrix to be stochastic. Our method of statistical estimation is a combination of the Pearsonian method of moments and the maximum likelihood method.In our illustrative example we observe that the skewness of the distribution of the first best solution exceeds that of the distributions of the second and third best solution. We have also analyzed the time paths for the three ordered solutions to see how far one could apply the idea of a regression model based on inequality constraints. A sensitivity index for a particular sample is suggested based on the spread of the maximum and minimum values of the solutions.

---

Zusammenfassung Im allgemeinen ist bei Linear-Programming-Problemen mit statistischen Einflüssen die Zuverlässigkeit der optimalen Basislösung nicht bekannt. Unser Ziel ist es, eine allgemeine Methode anzugeben, um die Empfindlichkeit der optimalen Basislösung und anderer Basislösungen durch den Erwartungswert und die Varianz bei gegebener Stichprobe zu testen. Zur Illustration wird eine Zeitreihe der input-output-Koeffizienten einer einzigen Farm benutzt, die drei Getreidesorten erzeugt, wobei drei Ressourcen benützt werden. Es werden die Verteilungen der ersten drei besten Lösungen geschätzt bei vorausgesetzten konstanten Nettopreisen und Ressourcen und stochastischer Koeffizientenmatrix. Die verwendete Methode der statistischen Schätzung ist eine Kombination der Pearsonschen Momentenmethode und der Maximum-Likelihood-Methode.In unserem Beispiel stellen wir fest, daß die Schiefe der Verteilung der besten Lösung größer ist als die der Verteilung der zweit- und drittbesten Lösungen. Ferner wurden die Zeitläufe der ersten drei geordneten Lösungen analysiert, um festzustellen, wie weit sich die Idee eines Regressionsmodells, das auf Ungleichungsrestriktionen basiert, anwenden läßt. Für eine Stichprobe wird ein Empfindlichkeitsindex empfohlen, der sich aus der Spannweite der maximalen und minimalen Werte der Lösungen ableitet.

---

---

Research partly supported by the NSF project No. 420-04-70 at the Department of Economics, Iowa State University, Ames.The results of this paper are closely related in some theoretical aspects to the following papers. Sengupta, J. K., G. Tintner andC. Millham. On some theorems of stochastic linear programming with applications, Management Science, vol. 10, October 1963, pp. 143–159. Sengupta, J. K., G. Tintner andB. Morrison. Stochastic linear programming with applications to economic models, Economica, August 1963, pp. 262–276. Sengupta, J. K.: On the stability of truncated solutions of stochastic linear programming (to be published in Econometrica, October, 1965).     

Sensitivity analysis in linear programming: just be careful!

In this paper we review the topic of sensitivity analysis in linear programming. We describe the problems that may occur when using standard software and advocate a framework for performing complete sensitivity analysis. Three approaches can be incorporated within it: one using bases, an approach using the optimal partition and one using optimal values. We elucidate problems and solutions with an academic example and give results from an implementation of these approaches to a large practical linear programming model of an oil refinery. This shows that the approaches are viable and useful in practice.     

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.     

Sensitivity theorems in integer linear programming

We consider integer linear programming problems with a fixed coefficient matrix and varying objective function and right-hand-side vector. Among our results, we show that, for any optimal solution to a linear program max{wx: Axb}, the distance to the nearest optimal solution to the corresponding integer program is at most the dimension of the problem multiplied by the largest subdeterminant of the integral matrixA. Using this, we strengthen several integer programming proximity results of Blair and Jeroslow; Graver; and Wolsey. We also show that the Chvátal rank of a polyhedron {x: Axb} can be bounded above by a function of the matrixA, independent of the vectorb, a result which, as Blair observed, is equivalent to Blair and Jeroslow's theorem that each integer programming value function is a Gomory function.Supported by a grant from the Alexander von Humboldt Stiftung.Since September 1985: Department of Operations Research, Upson Hall, Cornell University, Ithaca, NY 14853, USA.Partially supported by the Sonderforschungbereich 21 (DFG), Institut für Ökonometrie und Operations Research of the University of Bonn, FR Germany.     

Interior-point methods for linear programming: a review

The paper reviews some recent advances in interior-point methods for linear programming and indicates directions in which future progress can be made. Most of the interior-point methods belong to any of three categories: affine-scaling methods, potential reduction methods and central path methods. These methods are discussed together with infeasible interior methods and homogeneous self-dual methods for linear programming. Also discussed are some theoretical issues in interior-point methods like dependence of complexity bounds on some non-traditional measures different from the input length L of the problem. Finally, the paper concludes with remarks on the comparison of interior-point methods with the simplex method based on their performance on NITLIB suite, a standard collection of test problems.     

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.     

Integer linear programming models for a cement delivery problem

We consider a cement delivery problem with an heterogeneous fleet of vehicles and several depots. The demands of the customers are typically larger than the capacity of the vehicles which means that most customers are visited several times. This is a split delivery vehicle routing problem with additional constraints. We first propose a two phase solution method that assigns deliveries to the vehicles, and then builds vehicle routes. Both subproblems are formulated as integer linear programming problems. We then show how to combine the two phases in a single integer linear program. Experiments on real life instances are performed to compare the performance of the two solution methods.     

Parametric linear programming techniques for the indefnite quadratic programming problem

In this paper, we discuss a multiparametric technique for findinga global minimum for an indefinite quadratic programming problembased on the spectral decomposition of the matrix of the quadraticform. Special attention is given to the case where this matrixhas only rank 1, where the multiparametric linear program turnsout to be a single-parameter linear program. An extension ofthe traditional linear parametric procedure is introduced whichin general solves this problem efficiently. However, an exampleis presented showing that this technique may take an exponentialnumber of steps.     

Common set of weights in data envelopment analysis: a linear programming problem

Data Envelopment Analysis is used to determine the relative efficiency of Decision Making Units as the ratio of weighted sum of outputs by weighted sum of inputs. To accomplish the purpose, a DEA model calculates the weights of inputs and outputs of each DMU individually so that the highest efficiency can be estimated. Thus, the present study suggests an innovative method using a common set of weights leading to solving a linear programming problem. The method determines the efficiency score of all DMUs and rank them too.     

Discrete linear bilevel programming problem

In this paper, we analyze some properties of the discrete linear bilevel program for different discretizations of the set of variables. We study the geometry of the feasible set and discuss the existence of an optimal solution. We also establish equivalences between different classes of discrete linear bilevel programs and particular linear multilevel programming problems. These equivalences are based on concave penalty functions and can be used to design penalty function methods for the solution of discrete linear bilevel programs.Support of this work has been provided by the INIC (Portugal) under Contract 89/EXA/5, by INVOTAN, FLAD, and CCLA (Portugal), and by FCAR (Québec), NSERC, and DND-ARP (Canada).     

Exact algorithm for solving a special fixed-charge linear programming problem

A branch-and-bound algorithm (A) for solving a fixed-charge linear programming problem (P) involving identical fixed charges, one equality constraint, and explicit bounds on the variables is presented. Problem (P) can serve as a mathematical model for profit optimization in sawn timber production. Some theoretical considerations upon a fixed-charge problem (P), arising from (P) by permitting the fixed charges to be different for each variable, are carried out. A basic algorithm (A₀) is stated, and it is proved that Algorithm (A₀) finds an optimal solution of Problem (P) [resp., (P)] within a finite number of steps. Algorithm (A₀), combined with bounds developed with regard to Problem (P), yields Algorithm (A), which operates on a subset of all vertices of the feasible region. Finally, computational results concerning the numerical solution of Problem (P) by Algorithm (A) are stated.A part of this work was carried out in connection with the project Optimierung der Schnittholzproducktion auf Zerspaneranlagen, which was done at the Institute of Mathematics of the University of Klagenfurt in cooperation with the firm J. Offner, Holzindustrie GmbH, Wolfsberg. This project was partially supported by Forschungsförderungsfonds für die gewerbliche Wirtschaft. The author would like to thank Professor H. Stettner, C. Nowak, and H. Woschitz for their support and G. Stoiser for his help in achieving the numerical results.     

Direct newton method for a linear problem of semidefinite programming

We consider a linear problem of semidefinite programming. To solve this problem, we propose a direct Newton method, which is a generalization of the direct barrier-Newton method for problems of linear programming. We study properties of the method and prove its local convergence.     

The balanced linear programming problem

The Balanced Linear Programming Problem (BLPP) arises in situations which require equitable distribution of a scarce resource. The BLPP can be transformed to the standard form of the linear programming problem by introducing 2∥N∥ + 2 additional variables and 2∥N∥ additional constraints. This transformation is not desirable from the computational point of view for larger values of ∥N∥ as it increases the problem size substantially. It is also undesirable from a theoretical perspective as it might affect the special structure of the constraint matrix. In this paper, we develop an algorithm for the BLPP which does not require problem enlargement. The algorithm is based on the relationship between the BLPP and the minimax linear programming problem, and solving the latter problem parametrically. Our algorithm, in essence, performs steps that are similar to those performed in the parametric simplex method with parametric right hand side. We then adapt our algorithm for the network flow problem and this specialized algorithm can be applied on the network directly without maintaining the simplex tableau.     

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.