Exact and stable least squares solution to the linear programming problem

A linear programming problem is transformed to the finding an element of polyhedron with the minimal norm. According to A. Cline [6], the problem is equivalent to the least squares problem on positive ortant. An orthogonal method for solving the problem is used. This method was presented earlier by the author and it is based on the highly developed least squares technique. First of all, the method is meant for solving unstable and degenerate problems. A new version of the artifical basis method (M-method) is presented. Also, the solving of linear inequality systems is considered.     

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.     

Exact solutions to linear programming problems

The use of floating-point calculations limits the accuracy of solutions obtained by standard LP software. We present a simplex-based algorithm that returns exact rational solutions, taking advantage of the speed of floating-point calculations and attempting to minimize the operations performed in rational arithmetic. Extensive computational results are presented.     

A stabilization method for solution of a parametric multicriteria equilibrium programming problem

A multicriteria equilibrium programming problem comprising a mathematical programming problem as a particular case, a multicriteria Pareto-point search problem, a minimization problem with equilibrium selection of the feasible set, etc., is considered. It is assumed that the initial data are known only approximately. In view of the fact that the considered problem is generally unstable with respect to the input data, a regularization method, which is a generalization of the Tikhonov stabilization method, is proposed. Conditions for matching the method parameters to the error in the input data are presented. The convergence of this method is analyzed.     

A concept of a robust solution of a multicriterial linear programming problem

A new concept of a robust solution of a multicriterial linear programming problem is proposed. The robust solution is understood here as the best starting point, prepared while the preferences of the decision maker with respect to the criteria are still unknown, for the adaptation of the solution to the preferences of the decision maker, once they are finally known. The objective is the total cost of the initial preparation and of the later potential adaptation of the solution. In the starting robust solution the decision variables may have interval values. The problem can be solved by means of the simplex algorithm. A numerical example illustrates the approach.     

Exact solution of a particular problem of oscillations of a system with random parametric excitation

A second order system with external and parametric perturbations of the white noise type is considered. An exact analytic solution of the steady Fokker—Plank —Kolmogorov equation is obtained for this system at some special relation between the coefficients of modulation intensity with respect to the coordinate and velocity. The solution determines the power relationship for the combined probability density of the coordinate and velocity.     

Least-norm linear programming solution as an unconstrained minimization problem

It is shown that the dual of the problem of minimizing the 2-norm of the primal and dual optimal variables and slacks of a linear program can be transformed into an unconstrained minimization of a convex parameter-free globally differentiable piecewise quadratic function with a Lipschitz continuous gradient. If the slacks are not included in the norm minimization, one obtains a minimization problem with a convex parameter-free quadratic objective function subject to nonnegativity constraints only.     

Numerical solution of positive control problem via linear programming

The reachability problem for linear time-invariant discrete-time control systems with sign-restricted input is considered. The time-optimal control is constructed by an iterative procedure. Each step of the iteration is defined as a linear programming problem. This problem is solved by the simplex algorithm. The initial feasible solution for the simplex algorithm is provided by the preceding step of the iteration. The inversion of the basis matrix is reduced to a bordering procedure. The structural stability of the solution is investigated.     

An explicit linear solution for the quadratic dynamic programming problem

For a given vectorx ₀, the sequence {x _t} which optimizes the sum of discounted rewardsr(x _t, x_t+1), wherer is a quadratic function, is shown to be generated by a linear decision rulex _t+1=Sx _t +R. Moreover, the coefficientsR,S are given by explicit formulas in terms of the coefficients of the reward functionr. A unique steady-state is shown to exist (except for a degenerate case), and its stability is discussed.     

Finiteε-subgradient algorithm for approximate solution of the parametric programming problem

Translated from Vychislitel'nye Kompleksy i Modelirovanie Slozhnykh Sistem, pp. 111–117, Moscow State University, 1989.     

Range sets for weak efficiency in multiobjective linear programming and a parametric polytopes intersection problem

ABSTRACT

The aim of this paper is to obtain the range set for a given multiobjective linear programming problem and a weakly efficient solution. The range set is the set of all values of a parameter such that a given weakly efficient solution remains efficient when the objective coefficients vary in a given direction. The problem was originally formulated by Benson in 1985 and left to be solved. We formulate an algorithm for determining the range set, based on some hard optimization problems. Due to toughness of these optimization problems, we propose also lower and upper bound approximation techniques. In the second part, we focus on topological properties of the range set. In particular, we prove that a range set is formed by a finite union of intervals and we propose upper bounds on the number of intervals. Our approach to tackle the range set problem is via the intersection problem of parametric polytopes. Thus, our results have much wider area of applicability since the intersection (and separability) problem of convex polyhedra is important in many fields of optimization.     

Computational complexity of parametric linear programming

We establish that in the worst case, the computational effort required for solving a parametric linear program is not bounded above by a polynomial in the size of the problem.This research is partially supported by Air Force Office of Scientific Research, Air Force Number AFOSR-78-3646.     

Finding an efficient solution to linear bilevel programming problem: An effective approach

Multilevel programming is developed to solve the decentralized problem in which decision makers (DMs) are often arranged within a hierarchical administrative structure. The linear bilevel programming (BLP) problem, i.e., a special case of multilevel programming problems with a two level structure, is a set of nested linear optimization problems over polyhedral set of constraints. Two DMs are located at the different hierarchical levels, both controlling one set of decision variables independently, with different and perhaps conflicting objective functions. One of the interesting features of the linear BLP problem is that its solution may not be Paretooptimal. There may exist a feasible solution where one or both levels may increase their objective values without decreasing the objective value of any level. The result from such a system may be economically inadmissible. If the decision makers of the two levels are willing to find an efficient compromise solution, we propose a solution procedure which can generate effcient solutions, without finding the optimal solution in advance. When the near-optimal solution of the BLP problem is used as the reference point for finding the efficient solution, the result can be easily found during the decision process.     

On the parametric linear complementarity problem: A generalized solution procedure

This paper presents a solution procedure for the parametric linear complementarity problemIw–Mz=q+sp,w ^T z=0,w0, andz0, whereM is a positive semidefinite matrix or aP-matrix. This procedure is different from existing ones in the way it handles initialization. By exploiting special relationships between the vectorsq andp, it can reduce computational effort. Sinceq is an arbitrary vector, the procedure can be used for the ordinary linear complementarity problem. In that case, it produces pivots exactly analogous to those of Lemke's algorithm.This paper is based on the author's doctoral dissertation at Johns Hopkins University, 1977. The author wishes to thank her advisors, Professors C. S. ReVelle and D. J. Elzinga. During the last year of her graduate studies, the author held an AAUW-IBM dissertation fellowship.     

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.     

Exact solution to the periodic boundary value problem for a first-order linear fuzzy differential equation with impulses

Using the expression of the exact solution to a periodic boundary value problem for an impulsive first-order linear differential equation, we consider an extension to the fuzzy case and prove the existence and uniqueness of solution for a first-order linear fuzzy differential equation with impulses subject to boundary value conditions. We obtain the explicit solution by calculating the solutions on each level set and justify that the parametric functions obtained define a proper fuzzy function. Our results prove that the solution of the fuzzy differential equation of interest is determined, under the appropriate conditions, by the same Green’s function obtained for the real case. Thus, the results proved extend some theorems given for ordinary differential equations.     

One way to solve the parametric quadratic programming problem

A method is presented for the solution of the parametric quadratic programming problem by the use of conjugate directions. It is based on the method for quadratic programming proposed by the author in [1].While engaged in this research the author had a part-time post with the Manpower Services Commission.     

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

Solving special nonlinear fractional programming problems via parametric linear programming

A new procedure is developed to solve a generalized linear fractional programming problem. We find the optimal solutions in two steps. First we solve a parametric linear programming problem. Using the results of this step we then define a simple optimization problem in the second step. This yields an optimal value which together with the results of the parametric analysis provides the optimal solutions of the considered fractional programming problem.