Posynomial geometric programming as a special case of semi-infinite linear programming

This paper develops a wholly linear formulation of the posynomial geometric programming problem. It is shown that the primal geometric programming problem is equivalent to a semi-infinite linear program, and the dual problem is equivalent to a generalized linear program. Furthermore, the duality results that are available for the traditionally defined primal-dual pair are readily obtained from the duality theory for semi-infinite linear programs. It is also shown that two efficient algorithms (one primal based and the other dual based) for geometric programming actually operate on the semi-infinite linear program and its dual.     

Generalized fractional programming: Algorithms and numerical experimentation

Several algorithms to solve the generalized fractional program are summarized and compared numerically in the linear case. These algorithms are iterative procedures requiring the solution of a linear programming problem at each iteration in the linear case. The most efficient algorithm is obtained by marrying the Newton approach within the Dinkelbach approach for fractional programming.     

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.     

Modelling a product-mix determination problem

This study presents a combined linear programming package and a user-oriented program for its data input employed in product-mix determination. An optimal product-mix is to be determined for a rapidly changing manufacturing environment. The study consists of developing an interactive computer program for the solution of a product-mix problem. The user-oriented program has been developed so that a person familiar with the plant can determine the ‘best’ mix which should be produced. This study provides a quantitative tool to aid in the decision-making process when time is limited and the production process dynamic.     

A Hybrid Approach to Scheduling with Earliness and Tardiness Costs

A hybrid technique using constraint programming and linear programming is applied to the problem of scheduling with earliness and tardiness costs. The linear model maintains a set of relaxed optimal start times which are used to guide the constraint programming search heuristic. In addition, the constraint programming problem model employs the strong constraint propagation techniques responsible for many of the advances in constraint programming for scheduling in the past few years. Empirical results validate our approach and show, in particular, that creating and solving a subproblem containing only the activities with direct impact on the cost function and then using this solution in the main search, significantly increases the number of problems that can be solved to optimality while significantly decreasing the search time.     

A linear programming-based optimization algorithm for solving nonlinear programming problems

In this paper a linear programming-based optimization algorithm called the Sequential Cutting Plane algorithm is presented. The main features of the algorithm are described, convergence to a Karush–Kuhn–Tucker stationary point is proved and numerical experience on some well-known test sets is showed. The algorithm is based on an earlier version for convex inequality constrained problems, but here the algorithm is extended to general continuously differentiable nonlinear programming problems containing both nonlinear inequality and equality constraints. A comparison with some existing solvers shows that the algorithm is competitive with these solvers. Thus, this new method based on solving linear programming subproblems is a good alternative method for solving nonlinear programming problems efficiently. The algorithm has been used as a subsolver in a mixed integer nonlinear programming algorithm where the linear problems provide lower bounds on the optimal solutions of the nonlinear programming subproblems in the branch and bound tree for convex, inequality constrained problems.     

Possibility linear programming with trapezoidal fuzzy numbers

Fuzzy linear programming with trapezoidal fuzzy numbers (TrFNs) is considered and a new method is developed to solve it. In this method, TrFNs are used to capture imprecise or uncertain information for the imprecise objective coefficients and/or the imprecise technological coefficients and/or available resources. The auxiliary multi-objective programming is constructed to solve the corresponding possibility linear programming with TrFNs. The auxiliary multi-objective programming involves four objectives: minimizing the left spread, maximizing the right spread, maximizing the left endpoint of the mode and maximizing the middle point of the mode. Three approaches are proposed to solve the constructed auxiliary multi-objective programming, including optimistic approach, pessimistic approach and linear sum approach based on membership function. An investment example and a transportation problem are presented to demonstrate the implementation process of this method. The comparison analysis shows that the fuzzy linear programming with TrFNs developed in this paper generalizes the possibility linear programming with triangular fuzzy numbers.     

A multi-objective facility location model for closed-loop supply chain network under uncertain demand and return

A closed-loop supply chain (CLSC) network consists of both forward and reverse supply chains. In this paper, a CLSC network is investigated which includes multiple plants, collection centres, demand markets, and products. To this aim, a mixed-integer linear programming model is proposed that minimizes the total cost. Besides, two test problems are examined. The model is extended to consider environmental factors by weighed sums and ε-constraint methods. In addition, we investigate the impact of demand and return uncertainties on the network configuration by stochastic programming (scenario-based). Computational results show that the model can handle demand and return uncertainties, simultaneously.     

A compromise procedure for the multiple objective linear fractional programming problem

A generalization of a well-known multiple objective linear fractional programming (MOLFP) problem, the multiple objective fractional programming (MOFP) problem, is formulated. A concept of multiple objective programming (MOP) problem corresponding to MOFP is introduced and some relations between those problems are examined. Based on these results, a compromise procedure for MOLFP problem is proposed. A numerical example is given to show how the procedure works.     

一类线性规划问题的快速解法

研究了在组合投资和多属性决策指标权重确定中有着重要应用的一类线性规划问题,得到了该类线性规划问题有可行解的充要条件,以及在有可行解的情况下寻求最优解的快速解法.     

On the structure and properties of a linear multilevel programming problem

Many decision-making situations involve multiple planners with different, and sometimes conflicting, objective functions. One type of model that has been suggested to represent such situations is the linear multilevel programming problem. However, it appears that theoretical and algorithmic results for linear multilevel programming have been limited, to date, to the bounded case or the case of when only two levels exist. In this paper, we investigate the structure and properties of a linear multilevel programming problem that may be unbounded. We study the geometry of the problem and its feasible region. We also give necessary and sufficient conditions for the problem to be unbounded, and we show how the problem is related to a certain parametric concave minimization problem. The algorithmic implications of the results are also discussed.This research was supported by National Science Foundation Grant No. ECS-85-15231.     

A procedure for parameterizing a constraint in linear programming

A post-optimal procedure for parameterizing a constraint in linear programming is proposed. In the derivation of the procedure, the technique of pivotal operations (Jordan eliminations) is applied. The procedure is compared to another by Orchard-Hays [2], and a numerical example of the procedure is provided.     

Analyzing the potential of a firm: an operations research approach

An approach to analyzing the potential of a firm, which is understood as the firm's ability to provide goods or (and) services to be supplied to a marketplace under restrictions imposed by a business environment in which the firm functions, is proposed. The approach is based on using linear inequalities and, generally, mixed variables in modelling this ability for a broad spectrum of industrial, transportation, agricultural, and other types of firms and allows one to formulate problems of analyzing the potential of a firm as linear programming problems or mixed programming problems with linear constraints. This approach generalizes the one proposed by the author earlier for a more narrow class of models and allows one to effectively employ a widely available software for solving practical problems of the considered kind, especially for firms described by large scale models of mathematical programming.     

正态随机规划的确定性规划及其灵敏度分析

在大量的管理决策问题中,经常会遇到目标函数的系数和右端常数为相互独立的正态随机变量的随机线性规划模型.利用对偶规划将正态随机规划化为具有α可靠度的线性规划,给出了解决该正态随机规划的一个有效方法,并对正态随机变量的参数进行了灵敏度分析,避免了由于参数估计偏差给决策带来的风险,保证了最优方案的α可靠度.     

线性多级规划的最优性条件和基本性质

本文研究的线性多级规划模型比较一般化，容许集可以是无界的，每级的目标函数可以与各下级控制的决策变量有关．我们得到了这类多级规划的一组最优性充要条件，利用这组条件推导了各级可行集的弱拟凸性、连通性等几何性质．作为应用订正了Bard的一个例题．     

Solving a full fuzzy linear programming using lexicography method and fuzzy approximate solution

This paper discusses full fuzzy linear programming (FFLP) problems of which all parameters and variable are triangular fuzzy numbers. We use the concept of the symmetric triangular fuzzy number and introduce an approach to defuzzify a general fuzzy quantity. For such a problem, first, the fuzzy triangular number is approximated to its nearest symmetric triangular number, with the assumption that all decision variables are symmetric triangular. An optimal solution to the above-mentioned problem is a symmetric fuzzy solution. Every FLP models turned into two crisp complex linear problems; first a problem is designed in which the center objective value will be calculated and since the center of a fuzzy number is preferred to (its) margin. With a special ranking on fuzzy numbers, the FFLP transform to multi objective linear programming (MOLP) where all variables and parameters are crisp.     

NP-hardness of linear multiplicative programming and related problems

The linear multiplicative programming problem minimizes a product of two (positive) variables subject to linear inequality constraints. In this paper, we show NP-hardness of linear multiplicative programming problems and related problems.     

Solving Difficult Multicommodity Problems with a Specialized Interior-Point Algorithm

A scheduling problem with piecewise linear (PL) optimization extends conventional scheduling by imposing a conjunction of combinatorial PL constraints involving the objective function variables. To solve this problem, this paper presents a hybrid algorithm where Constraint Programming (CP) search is supported and driven by a (integer) linear programming solver running on a well-controlled subproblem which is dynamically tightened. The paper discusses and compares different ways of decomposing the problem constraints between the CP search and the solver. We show how the subproblem structure and the piecewise linearity are exploited by the search.     

On geometric programming and complementary slackness

When the terms in a convex primal geometric programming (GP) problem are multiplied by slack variables whose values must be at least unity, the invariance conditions may be solved as constraints in a linear programming (LP) problem in logarithmically transformed variables. The number of transformed slack variables included in the optimal LP basis equals the degree of difficulty of the GP problem, and complementary slackness conditions indicate required changes in associated GP dual variables. A simple, efficient search procedure is used to generate a sequence of improving primal feasible solutions without requiring the use of the GP dual objective function. The solution procedure appears particularly advantageous when solving very large geometric programming problems, because only the right-hand constants in a system of linear equations change at each iteration.The influence of J. G. Ecker, the writer's teacher, is present throughout this paper. Two anonymous referees and the Associate Editor made very helpful suggestions. Dean Richard W. Barsness provided generous support for this work.