A procedure for one-parametric linear programming

A procedure is proposed for the parametric linear programming problem where all the coefficients are linear or polynomial functions of a scalar parameter. The solution vector and the optimum value are determined explicitly as rational functions of the parameter. In addition to standard linear programming technique, only the determination of eigenvalues is required. The procedure is compared to those by Dinkelbach and Zsigmond, and a numerical example is given.     

The stochastic bottleneck linear programming problem

In this paper we consider some stochastic bottleneck linear programming problems. We overview the solution methods in the literature. In the case when the coefficients of the objective functions are simple randomized, the minimum-risk approach will be used for solving these problems. We prove that, under some positivity conditions, these stochastic problems are reduced to certain deterministic bottleneck linear problems. An application of these problems to bottleneck spanning tree problems is given. Two simple numerical examples are presented. This paper was written when I.M. Stancu-Minasian was visiting the Instituto Complutense de Análisis Económico, in the Universidad Complutensen de Madrid, from October 1, 1997 to November 15, 1997 and from October 24, 1998 to November, 9, 1998, as invited researcher. He is grateful to the Institution.     

On the bottleneck linear programming problem

In this paper, the results on primal methods for Bottleneck Linear Programming (BLP) problem are briefly surveyed, the primal method is presented and the degenerate case related to Bottleneck Transportation Problem (BTP) is explicitly considered. The algorithm is based on the idea of using auxiliary coefficients as is done by Garfinkel and Rao [6]. The modification presented for the BTP rectifies the defect in Hammer's method in the case of degenerate basic feasible solution. Illustrative numerical examples are also given.     

Nonlinear programming and nonsmooth optimization by successive linear programming

Methods are considered for solving nonlinear programming problems using an exactl ₁ penalty function. LP-like subproblems incorporating a trust region constraint are solved successively both to estimate the active set and to provide a foundation for proving global convergence. In one particular method, second order information is represented by approximating the reduced Hessian matrix, and Coleman-Conn steps are taken. A criterion for accepting these steps is given which enables the superlinear convergence properties of the Coleman-Conn method to be retained whilst preserving global convergence and avoiding the Maratos effect. The methods generalize to solve a wide range of composite nonsmooth optimization problems and the theory is presented in this general setting. A range of numerical experiments on small test problems is described.     

Nonlinear programming in normed linear spaces

Necessary conditions in the form of multiplier rules are given for a function to have a constrained minimum. First-order differentiability conditions are imposed, and various combinations of set, equality, and inequality constraints are considered in arbitrary normed linear spaces.This paper is based upon part of the author's doctoral dissertation at Ohio University, Athens, Ohio.     

A unified approach to one-parametric general quadratic programming

A method is proposed for finding local minima to the parametric general quadratic programming problem where all the coefficients are linear or polynomial functions of a scalar parameter. The local minimum vector and the local minimum value are determined explicitly as rational functions of the parameter. A numerical example is given.     

On ranking of feasible solutions of a bottleneck linear programming problem

Summary An algorithm for the ranking of the feasible solutions of a bottleneck linear programming problem in ascending order of values of a concave bottleneck objective function is developed in this paper. The “best” feasible solution for a given value of the bottleneck objective is obtained at each stage. It is established that only the extreme points of a convex polytope need to be examined for the proposed ranking. Another algorithm, involving partitioning of the nodes, to rank the feasible solutions of the bottleneck linear programming problem is proposed, and numerical illustrations for both are provided.     

A smoothing Newton algorithm based on a one-parametric class of smoothing functions for linear programming over symmetric cones

In this paper, we introduce a one-parametric class of smoothing functions which contains the Fischer–Burmeister smoothing function and the CHKS smoothing function as special cases. Based on this class of smoothing functions, a smoothing Newton algorithm is extended to solve linear programming over symmetric cones. The global and local quadratic convergence results of the algorithm are established under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool in our analysis.     

Understanding linear semi-infinite programming via linear programming over cones

In this article, the standard primal and dual linear semi-infinite programming (DLSIP) problems are reformulated as linear programming (LP) problems over cones. Therefore, the dual formulation via the minimal cone approach, which results in zero duality gap for the primal–dual pair for LP problems over cones, can be applied to linear semi-infinite programming (LSIP) problems. Results on the geometry of the set of the feasible solutions for the primal LSIP problem and the optimality criteria for the DLSIP problem are also discussed.     

A linear programming approach for linear multi-level programming problems

In an earlier paper, we proposed a modified fuzzy programming method to handle higher level multi-level decentralized programming problems (ML(D)PPs). Here we present a simple and practical method to solve the same. This method overcomes the subjectivity inherent in choosing the tolerance values and the membership functions. We consider a linear ML(D)PP and apply linear programming (LP) for the optimization of the system in a supervised search procedure, supervised by the higher level decision maker (DM). The higher level DM provides the preferred values of the decision variables under his control to enable the lower level DM to search for his optimum in a narrower feasible space. The basic idea is to reduce the feasible space of a decision variable at each level until a satisfactory point is sought at the last level.     

Privacy-preserving linear programming

We propose a privacy-preserving formulation of a linear program whose constraint matrix is partitioned into groups of columns where each group of columns and its corresponding cost coefficient vector are owned by a distinct entity. Each entity is unwilling to share or make public its column group or cost coefficient vector. By employing a random matrix transformation we construct a linear program based on the privately held data without revealing that data or making it public. The privacy-preserving transformed linear program has the same minimum value as the original linear program. Component groups of the solution of the transformed problem can be decoded and made public only by the original group that owns the corresponding columns of the constraint matrix and can be combined to give an exact solution vector of the original linear program.     

Bottleneck linear programming

The Bottleneck Linear Programming problem (BLP) is to maximizex ₀ = max _j c _j ,x _j > 0 subject toAx = b, x 0. A relationship between the BLP and a problem solvable by a greedy algorithm is established. Two algorithms for the BLP are developed and computational experience is reported.     

Belief linear programming

This paper proposes solution approaches to the belief linear programming (BLP). The BLP problem is an uncertain linear program where uncertainty is expressed by belief functions. The theory of belief function provides an uncertainty measure that takes into account the ignorance about the occurrence of single states of nature. This is the case of many decision situations as in medical diagnosis, mechanical design optimization and investigation problems. We extend stochastic programming approaches, namely the chance constrained approach and the recourse approach to obtain a certainty equivalent program. A generic solution strategy for the resulting certainty equivalent is presented.     

Enhanced-interval linear programming

An enhanced-interval linear programming (EILP) model and its solution algorithm have been developed that incorporate enhanced-interval uncertainty (e.g., A^±, B^± and C^±) in a linear optimization framework. As a new extension of linear programming, the EILP model has the following advantages. Its solution space is absolutely feasible compared to that of interval linear programming (ILP), which helps to achieve insight into the expected-value-oriented trade-off between system benefits and risks of constraint violations. The degree of uncertainty of its enhanced-interval objective function (EIOF) would be lower than that of ILP model when the solution space is absolutely feasible, and the EIOF’s expected value could be used as a criterion for generating the appropriate alternatives, which help decision-makers obtain non-extreme decisions. Moreover, because it can be decomposed into two submodels, EILP’s computational requirement is lower than that of stochastic and fuzzy LP models. The results of a numeric example further indicated the feasibility and effectiveness of EILP model. In addition, EI nonlinear programming models, hybrid stochastic or fuzzy EILP models as well as risk-based trade-off analysis for EI uncertainty within decision process can be further developed to improve its applicability.     

Unconstrained convex programming approach to linear programming

Recently, Fang proposed approximating a linear program in the Karmarkar standard form by adding an entropic barrier function to the objective function and derived an unconstrained dual concave program. We present in this note a necessary and sufficient condition for the existence of a dual optimal solution to the perturbed problem. In addition, a sharp upper bound of error estimation in this approximation scheme is provided.     

On possibilistic linear programming

The problem of processing and combining possibilistic information in the scope of linear programming is approached. As apparatus to cope with this problem, we use the concepts of ‘more possible value’, ‘α-possibly feasible action’ and ‘α-possibly efficient action’.Issues regarding the feasibility of the resulting deterministic programs as well as the characterization of their optimal solutions are also discussed.