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 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.     

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.     

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.     

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.     

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).     

Sensitivity analysis in linear semi-infinite programming: Perturbing cost and right-hand-side coefficients

This paper analyzes the effect on the optimal value of a given linear semi-infinite programming problem of the kind of perturbations which more frequently arise in practical applications: those which affect the objective function and the right-hand-side coefficients of the constraints. In particular, we give formulae which express the exact value of a perturbed problem as a linear function of the perturbation.     

Implementing proximal point methods for linear programming

We describe the application of proximal point methods to the linear programming problem. Two basic methods are discussed. The first, which has been investigated by Mangasarian and others, is essentially the well-known method of multipliers. This approach gives rise at each iteration to a weakly convex quadratic program which may be solved inexactly using a point-SOR technique. The second approach is based on the proximal method of multipliers, originally proposed by Rockafellar, for which the quadratic program at each iteration is strongly convex. A number of techniques are used to solve this subproblem, the most promising of which appears to be a two-metric gradient-projection approach. Convergence results are given, and some numerical experience is reported.This research was supported by National Science Foundation, Grant Nos. ASC-87-14009 and DMS-86-19903, and by Air Force Office of Scientific Research, Grant No. AFOSR-ISSA-87-0092. Part of this work was performed at Argonne National Laboratory. Computation was partly performed at the Pittsburgh Supercomputer Center under NSF Grant No. DMS-88-0033P and at the Argonne Advanced Computing Research Facility, whose support is gratefully acknowledged. The author thanks Olvi Mangasarian and Renato DeLeone for helpful discussions, and Jorge Moré for his valuable advice on the algorithms discussed in Section 3. The contributions of a referee, who provided helpful comments on an earlier version of this paper, are also acknowledged.     

Primal—dual methods for linear programming

Many interior-point methods for linear programming are based on the properties of the logarithmic barrier function. After a preliminary discussion of the convergence of the (primal) projected Newton barrier method, three types of barrier method are analyzed. These methods may be categorized as primal, dual and primal—dual, and may be derived from the application of Newton's method to different variants of the same system of nonlinear equations. A fourth variant of the same equations leads to a new primal—dual method.In each of the methods discussed, convergence is demonstrated without the need for a nondegeneracy assumption or a transformation that makes the provision of a feasible point trivial. In particular, convergence is established for a primal—dual algorithm that allows a different step in the primal and dual variables and does not require primal and dual feasibility.Finally, a new method for treating free variables is proposed.Presented at the Second Asilomar Workshop on Progress in Mathematical Programming, February 1990, Asilomar, CA, United StatesThe material contained in this paper is based upon research supported by the National Science Foundation Grant DDM-9204208 and the Office of Naval Research Grant N00014-90-J-1242.     

A class of methods for linear programming

A class of methods is presented for solving standard linear programming problems. Like the simplex method, these methods move from one feasible solution to another at each iteration, improving the objective function as they go. Each such feasible solution is also associated with a basis. However, this feasible solution need not be an extreme point and the basic solution corresponding to the associated basis need not be feasible. Nevertheless, an optimal solution, if one exists, is found in a finite number of iterations (under nondegeneracy). An important example of a method in the class is the reduced gradient method with a slight modification regarding selection of the entering variable.