An extension of the entropic perturbation method of linear programming

In this paper, an extended form of the entropic perturbation method of linear programming is given, which can overcome the weakness of the original method - being easy of overflow in computing. Moreover, the global convergence of the gradient algorithm for the method is discussed.     

On the entropic perturbation and exponential penalty methods for linear programming

This note points out that the recently proposed exponential penalty approach to linear programming is identical to the well-known entropic perturbation approach. The primal and dual trajectories provided by these two approaches are shown to be equivalent.The work of the first author was supported partially by the North Carolina Supercomputing Center and 1995 Cray Research Grant.     

Linear programming with matrix variables

Linear programming is formulated with the vector variable replaced by a matrix variable, with the inner product defined using trace of a matrix. The theorems of Motzkin, Farkas (both homogeneous and inhomogeneous forms), and linear programming duality thus extend to matrix variables. Duality theorems for linear programming over complex spaces, and over quaternion spaces, follow as special cases.     

Linear programming with estimatable parameters

Problems of estimating parameters in a linear programming model and using it in production planning are discussed here. An empirical application illustrates the various aspects of the estimation problem. © 1997 by John Wiley & Sons, Ltd.     

Linear programming with interval coefficients

In order to solve a linear programme, the model coefficients must be fixed at specific values, which implies that the coefficients are perfectly accurate. In practice, however, the coefficients are generally estimates. The only way to deal with uncertain coefficients is to test the sensitivity of the model to changes in their values, either singly or in very small groups. We propose a new approach in which some or all of the coefficients of the LP are specified as intervals. We then find the best optimum and the worst optimum for the model, and the point settings of the interval coefficients that yield these two extremes. This provides the range of the optimised objective function, and the coefficient settings give some insight into the likelihood of these extremes.     

Linear programming with online learning

We propose online decision strategies for time-dependent sequences of linear programs which use no distributional and minimal geometric assumptions about the data. These strategies are obtained through Vovk's aggregating algorithm which combines recommendations from a given strategy pool. We establish an average-performance bound for the resulting solution sequence.     

Linear programming with partial information

We study a particular class of linear programming problems in which only ordinal information concerning the objective function coefficients is known. Specifically, we assume the decision maker(s) can place partial orders (possibly incomplete) on the components of the contribution vector. The concept of tangent and polar cones forms the basis for the analytical and solution technique. An example problem is included.     

Linear bilevel programming with interval coefficients

In this paper, we address linear bilevel programs when the coefficients of both objective functions are interval numbers. The focus is on the optimal value range problem which consists of computing the best and worst optimal objective function values and determining the settings of the interval coefficients which provide these values. We prove by examples that, in general, there is no precise way of systematizing the specific values of the interval coefficients that can be used to compute the best and worst possible optimal solutions. Taking into account the properties of linear bilevel problems, we prove that these two optimal solutions occur at extreme points of the polyhedron defined by the common constraints. Moreover, we develop two algorithms based on ranking extreme points that allow us to compute them as well as determining settings of the interval coefficients which provide the optimal value range.     

Linear programming with variable matrix entries

We consider linear programming (continuous or integer) where some matrix entries are decision parameters. If the variables are nonnegative the problem can be easily solved in two phases. It is shown that direct costs on the matrix entries make the problem NP-hard. Finally, a strong duality result is provided.     

Linear programming with multiple fuzzy goals

This paper describes the use of fuzzy set theory in goal programming (GP) problems. In particular, it is demonstrated how fuzzy or imprecise aspirations of the decision maker (DM) can be quantified through the use of piecewise linear and continuous functions. Models are then presented for the use of fuzzy goal programming with preemptive priorities, with Archimedean weights, and with the maximization of the membership function corresponding to the minimum goal. Examples are also provided.     

Linear multiplicative programming

An algorithm for solving a linear multiplicative programming problem (referred to as LMP) is proposed. LMP minimizes the product of two linear functions subject to general linear constraints. The product of two linear functions is a typical non-convex function, so that it can have multiple local minima. It is shown, however, that LMP can be solved efficiently by the combination of the parametric simplex method and any standard convex minimization procedure. The computational results indicate that the amount of computation is not much different from that of solving linear programs of the same size. In addition, the method proposed for LMP can be extended to a convex multiplicative programming problem (CMP), which minimizes the product of two convex functions under convex constraints.     

Linear max-min programming

Theoretical aspects of the programming problem of maximizing the minimum value of a set of linear functionals subject to linear constraints are explored. Solution strategies are discussed and an optimality condition is developed. An algorithm is also presented.This research was partially supported by the Management Research Center of the University of Wisconsin—Milwaukee.     

Some perturbation theory for linear programming

Mathematical Programming -     

Linear programming with a possibilistic objective function

This paper proposes some ways for dealing with a linear program when the coefficients of the objective function are subject to possibilistic imprecision, i.e. they are characterized by fuzzy restrictions. Emphasis is placed upon a passive approach that yields a satisfying solution via an appropriate semi-infinite program, and an active one that allows to reach a solution with a high possibility level of optimality. Extensions to the possibilistic constraints case and to the case of multiple-objective programming problems with possibilistic coefficients are also hinted. We end up with some concluding remarks and indicate axes for further developments.     

Linear bilevel multi-follower programming with independent followers

This paper considers a particular case of linear bilevel programming problems with one leader and multiple followers. In this model, the followers are independent, meaning that the objective function and the set of constraints of each follower only include the leader’s variables and his own variables. We prove that this problem can be reformulated into a linear bilevel problem with one leader and one follower by defining an adequate second level objective function and constraint region. In the second part of the paper we show that the results on the optimality of the linear bilevel problem with multiple independent followers presented in Shi et al. [The kth-best approach for linear bilevel multi-follower programming, J. Global Optim. 33, 563–578 (2005)] are based on a misconstruction of the inducible region.     

Linear programming system identification

We define a version of the Inverse Linear Programming problem that we call Linear Programming System Identification. This version of the problem seeks to identify both the objective function coefficient vector and the constraint matrix of a linear programming problem that best fits a set of observed vector pairs. One vector is that of actual decisions that we call outputs. These are regarded as approximations of optimal decision vectors. The other vector consists of the inputs or resources actually used to produce the corresponding outputs. We propose an algorithm for approximating the maximum likelihood solution. The major limitation of the method is the computation of exact volumes of convex polytopes. A numerical illustration is given for simulated data.     

Operator splitting for nonlinear reaction-diffusion systems with an entropic structure : singular perturbation and order reduction

Summary. In this paper, we perform the numerical analysis of operator splitting techniques for nonlinear reaction-diffusion systems with an entropic structure in the presence of fast scales in the reaction term. We consider both linear diagonal and quasi-linear non-diagonal diffusion; the entropic structure implies the well-posedness and stability of the system as well as a Tikhonov normal form for the nonlinear reaction term [23]. It allows to perform a singular perturbation analysis and to obtain a reduced and well-posed system of equations on a partial equilibrium manifold as well as an asymptotic expansion of the solution. We then conduct an error analysis in this particular framework where the time scale associated to the fast part of the reaction term is much shorter that the splitting time step t thus leading to the failure of the usual splitting analysis techniques. We define the conditions on diffusion and reaction for the order of the local error associated with the time splitting to be reduced or to be preserved in the presence of fast scales. All the results obtained theoretically on local error estimates are then illustrated on a numerical test case where the global error clearly reproduces the scenarios foreseen at the local level. We finally investigate the discretization of the corresponding problems and its influence on the splitting error in terms of the previously conducted numerical analysis.Mathematics Subject Classification (2000): 65M12, 35K57, 35B25, 35Q80, 34E15, 80A32, 92E20     

Homotopy perturbation method for linear programming problems

In this paper, He’s homotopy perturbation method (HPM) is applied for solving linear programming (LP) problems. This paper shows that some recent findings about this topic cannot be applied for all cases. Furthermore, we provide the correct application of HPM for LP problems. The proposed method has a simple and graceful structure. Finally, a numerical example is displayed to illustrate the proposed method.     

A dual perturbation view of linear programming

Solving standard-form linear prograrns via perturbation of the primal objective function has received much attention recently. In this paper, we investigate a new perturbation scheme which obtains a dual optimal solution by perturbing the dual feasible domain under different norms. A dual-to-primal conversion formula is also provided. We show that this new perturbation scheme actually generalizes the primal entropic perturbation approach to linear programming.Partially sponsored by the North Carolina Supercomputing Center 1994 Cray Research Grant and the National Textile Center Research Grant.     

Linear programming in measure spaces

This paper studies a linear programming problem in measure spaces (LPM). Several results are obtained. First, the optimal value of LPM can be equal to the optimal value of the dual problem (DLPM), but the solution of DLPM may be not exist in its feasible region. Sccond, :he relations between the optimal solution of LPM and the extreme point of the feasible region of LPM are discussed. In order to investigate the conditions under which a feasible solution becomes an extremal point, the inequality constraint of LPM is transformed to an equality constraint. Third, the LPM can be reformulated to be a general capacity problem (GCAP) or a linear semi-infinite programming problem (LSIP = SIP), and under appropriate restrictioiis, the algorithm developed by the authors in [7] and [8] are applicable for developing an approximation scheme for the optimal solution of LPM