A hybrid approach to discrete mathematical programming

The dynamic programming and branch-and-bound approaches are combined to produce a hybrid algorithm for separable discrete mathematical programs. Linear programming is used in a novel way to compute bounds. Every simplex pivot permits a bounding test to be made on every active node in the search tree. Computational experience is reported.     

线性规划流动等值面算法

对于线性规划问题，本文给出了基于流动等值面的等价模型，提出了一种不可行流动等值面算法．新算法保留了传统单纯形算法的优点并克服了它的不足。初步数值结果表明新算法比传统方法更为有效．     

Comparison of Four Goal Programming Algorithms

A major limitation in the use of goal programming has been the lack of an efficient algorithm for model solution. Schniederjans and Kwak recently published a proposal for more efficient solution of goal programming models utilizing dual simplex procedures. A goal programming algorithm based upon that method has been coded, as well as a revised, simplex-based algorithm. These algorithms are compared in terms of accuracy and time requirements with algorithms previously presented by Lee and by Arthur and Ravindran. Solution times for a series of 12 goal programming models are presented. The dual simplex method appears to have superior computational times for models with a large proportion of positive deviational variables in the solution. The revised simplex algorithm appears more consistent in time and accuracy for general goal programming models.     

A simplex algorithm for piecewise-linear programming I: Derivation and proof

The simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. This three-part paper develops and analyzes a general, computationally practical simplex algorithm for piecewiselinear programming.Part I derives and justifies the essential steps of the algorithm, by extension from the simplex method for linear programming in bounded variables. The proof employs familiar finite-termination arguments and established piecewise-linear duality theory.Part II considers the relaxation of technical assumptions pertaining to finiteness, feasibility and nondegeneracy of piecewise-linear programs. Degeneracy is found to have broader consequences than in the linear case, and the standard techniques for prevention of cycling are extended accordingly.Part III analyzes the computational requirements of piecewise-linear programming. The direct approach embodied in the piecewise-linear simplex algorithm is shown to be inherently more efficient than indirect approaches that rely on transformation of piecewise-linear programs to equivalent linear programs. A concluding section surveys the many applications of piecewise-linear programming in linear programming,l ₁ estimation, goal programming, interval programming, and nonlinear optimization.This research has been supported in part by the National Science Foundation under grant MCS-8217261.     

燃气输配的数学模型

研究了某天然气公司向市民供应优质燃气的输配问题 ,建立了寻求合理的配产方案的非线性数学模型 ,运用拉格朗日乘子法、最速下降法、修正牛顿法、动态规划方法、化二次规划为线性规划的单纯形法和罚函数法等不同方法给出了各气井的合理的配产方案 .对于实际应用与大学生数学建模训练有一定的指导意义 .     

George Dantzig’s impact on the theory of computation

George Dantzig created the simplex algorithm for linear programming, perhaps the most important algorithm developed in the 20th century. This paper traces a single historical thread: Dantzig’s work on linear programming and its application and extension to combinatorial optimization, and the investigations it has stimulated about the performance of the simplex algorithm and the intrinsic complexity of linear programming and combinatorial optimization.     

A simplex algorithm for piecewise-linear programming II: Finiteness,feasibility and degeneracy

The simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. Part I of this paper has developed a general and direct simplex algorithm for piecewise-linear programming, under convenient assumptions that guarantee a finite number of basic solutions, existence of basic feasible solutions, and nondegeneracy of all such solutions. Part II now shows how these assumptions can be weakened so that they pose no obstacle to effective use of the piecewise-linear simplex algorithm. The theory of piecewise-linear programming is thereby extended, and numerous features of linear programming are generalized or are seen in a new light. An analysis of the algorithm's computational requirements and a survey of applications will be presented in Part III.This research has been supported in part by the National Science Foundation under grant DMS-8217261.     

A simplex algorithm for piecewise-linear fractional programming problems

Generalizations of the well-known simplex method for linear programming are available to solve the piecewise linear programming problem and the linear fractional programming problem. In this paper we consider a further generalization of the simplex method to solve piecewise linear fractional programming problems unifying the simplex method for linear programs, piecewise linear programs, and the linear fractional programs. Computational results are presented to obtain further insights into the behavior of the algorithm on random test problems.     

A linear programming embedded genetic algorithm for an integrated cell formation and lot sizing considering product quality

Production lot sizing models are often used to decide the best lot size to minimize operation cost, inventory cost, and setup cost. Cellular manufacturing analyses mainly address how machines should be grouped and parts be produced. In this paper, a mathematical programming model is developed following an integrated approach for cell configuration and lot sizing in a dynamic manufacturing environment. The model development also considers the impact of lot sizes on product quality. Solution of the mathematical model is to minimize both production and quality related costs. The proposed model, with nonlinear terms and integer variables, cannot be solved for real size problems efficiently due to its NP-complexity. To solve the model for practical purposes, a linear programming embedded genetic algorithm was developed. The algorithm searches over the integer variables and for each integer solution visited the corresponding values of the continuous variables are determined by solving a linear programming subproblem using the simplex algorithm. Numerical examples showed that the proposed method is efficient and effective in searching for near optimal solutions.     

Using complementary slackness property to solve linear programming with fuzzy parameters

The most popular approach to handle the challenge of solving fuzzy linear programming problems is to convert the fuzzy linear programming into the corresponding deterministic linear programming. Mahdavi-Amiri and Nasseri [15,16] developed the fuzzy dual simplex algorithm to fuzzy linear programming with fuzzy parameters. In this paper, we use the complementary slackness to solve it without the need of a simplex tableau.     

A bump triangular dynamic factorization algorithm for the simplex method

A dynamic factorization algorithm is developed which algebraically partitions the basis inverse in such a manner so that the simplex method can be executed from a series of small inverses and the basis itself. This partition is maintained dynamically so that the additional memory required to represent the basis inverse reduces to this series of small inverses for in-core implementations.The algorithm is intended for use in solving general large-scale linear programming problems. This new method of basis representation should permit rather large problems to be solved completely in-core.Preliminary computational experience is presented and comparisons are made with Reid's sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases. The computational experience indicated that a significant reduction in memory requirements can usually be obtained using the dynamic factorization approach with only a slight (up to about 20%) degradation of execution time.This research was supported in part by the Air Force Office of Scientific Research, Air Force System Command, USAF, under AFOSR Contract/Grant Number AFOSR-74-2715.     

On the Equivalence of the Simplex Methods and a Multiplier-Alike Method for Linear Programming

In linear programming, the simplex method has been viewed for a long time as an efficient tool. Interior methods have attracted a lot of attention since they were proposed recently. It seems plausible intuitively that there is no reason why a good linear programming algorithm should not be allowed to cross the boundary of the feasible region when necessary. However, such an algorithm is seldom studied. In this paper, we will develop first a framework of a multiplier-alike algorithm for linear programming which allows its trajectory to move across the boundary of the feasible region. Second, we illustrate that such a framework has the potential to perform as well as the simplex method by showing that these methods are equivalent in a well-defined sense, even though they look so different.     

An algorithm for the solution of ill-posed linear systems arising from the discretization of Fredholm integral equation of the first kind

An algorithm for obtaining approximate solutions of ill-posed systems of linear equations arising from the discretization of Fredholm integral equation of the first kind is described. The ill-posed system is first replaced by an equivalent consistent system of linear equations. The method calculates the minimum length least squares solution of the consistent system. Starting from rank = 1 of the consistent system, the rank is increased by one in succession and a new solution is calculated. This is repeated until a certain simple criterion is satisfied. Linear programming techniques are used for which successive solutions are the basic solutions in the successive simplex tableaux. The algorithm is numerically stable. Numerical results show that this method compares favorably with other direct methods.     

A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines

This paper deals with a scheduling problem of independent tasks with common due date where the objective is to minimize the total weighted tardiness. The problem is known to be ordinary NP-hard in the case of a single machine and a dynamic programming algorithm was presented in the seminal work of Lawler and Moore [E.L. Lawler, J.M. Moore, A functional equation and its application to resource allocation and sequencing problems, Management Science 16 (1969) 77–84]. In this paper, this algorithm is described and discussed. Then, a new dynamic programming algorithm is proposed for solving the single machine case. These methods are extended for solving the identical and uniform parallel-machine scheduling problems.     

Algorithmic improvements on dynamic programming for the bi-objective {0,1} knapsack problem

This paper presents several methodological and algorithmic improvements over a state-of-the-art dynamic programming algorithm for solving the bi-objective {0,1} knapsack problem. The variants proposed make use of new definitions of lower and upper bounds, which allow a large number of states to be discarded. The computation of these bounds are based on the application of dichotomic search, definition of new bound sets, and bi-objective simplex algorithms to solve the relaxed problem. Although these new techniques are not of a common application for dynamic programming, we show that the best variants tested in this work can lead to an average improvement of 10 to 30 % in CPU-time and significant less memory usage than the original approach in a wide benchmark set of instances, even for the most difficult ones in the literature.     

A Simplex-Type Algorithm for General Transportation Problems: An Alternative to Stepping-Stone

This paper re-examines use of the linear programming (LP) formulation to solve the transportation problem (TP). The proposed method is a general-purpose algorithm which uses only one operation, the Gauss Jordan pivoting used in the simplex method. The final tableau can be used for post-optimality analysis of TP. This algorithm appears to be faster than simplex, more general than stepping-stone and simpler than both in solving general TP. A numerical example illustrates the methodology. It is assumed the reader is familiar with simplex terminology.     

Approximation of optimal feedback control: a dynamic programming approach

We consider the general continuous time finite-dimensional deterministic system under a finite horizon cost functional. Our aim is to calculate approximate solutions to the optimal feedback control. First we apply the dynamic programming principle to obtain the evolutive Hamilton–Jacobi–Bellman (HJB) equation satisfied by the value function of the optimal control problem. We then propose two schemes to solve the equation numerically. One is in terms of the time difference approximation and the other the time-space approximation. For each scheme, we prove that (a) the algorithm is convergent, that is, the solution of the discrete scheme converges to the viscosity solution of the HJB equation, and (b) the optimal control of the discrete system determined by the corresponding dynamic programming is a minimizing sequence of the optimal feedback control of the continuous counterpart. An example is presented for the time-space algorithm; the results illustrate that the scheme is effective.     

A comparison of interval linear programming with the simplex method

A detailed comparison of the simplex method for linear programming with a recent interval linear programming algorithm reveals that the methods are identical in the sense that the same sequence of extreme points can be generated by either algorithm.     

On the Existence of Fixed Points for Approximate Value Iteration and Temporal-Difference Learning

Approximate value iteration is a simple algorithm that combats the curse of dimensionality in dynamic programs by approximating iterates of the classical value iteration algorithm in a spirit reminiscent of statistical regression. Each iteration of this algorithm can be viewed as an application of a modified dynamic programming operator to the current iterate. The hope is that the iterates converge to a fixed point of this operator, which will then serve as a useful approximation of the optimal value function. In this paper, we show that, in general, the modified dynamic programming operator need not possess a fixed point; therefore, approximate value iteration should not be expected to converge. We then propose a variant of approximate value iteration for which the associated operator is guaranteed to possess at least one fixed point. This variant is motivated by studies of temporal-difference (TD) learning, and existence of fixed points implies here existence of stationary points for the ordinary differential equation approximated by a version of TD that incorporates exploration.