Search

This paper studies the linear programming problem in which all coefficients (even those of the stipulations matrix) are rational functions of a single parameter t called ‘time,’ and provides an algorithm that can serve problems of the following two types: (1) Steady-state behavior [the algorithm can be used to determine the functional form x(t) of the optimal solution as a function of t, this form being valid for all ‘sufficiently large’ values of t], and (2) sensitivity analysis [if a value t0 of ‘time’ is given, the algorithm can be used to determine the two possible functional forms of the optimal solution for all values of t ‘sufficiently dose’ to t0 (the first functional form valid for t«t0, the second for t»t0)]. In addition, the paper gives certain qualitative information regarding steady-state behavior, including the following result: If for some one of the properties of consistency, boundedness, or bounded constraint set, there exists a sequence tn↗+∞ such that the linear program at tn has this property for all n, then the program has this property for all ‘sufficiently large’ values of t. [ABSTRACT FROM AUTHOR]

This paper discusses technical aspects of the Russell-Yasuda Kasai financial planning model. These include the models for the discrete distribution scenario generation processes for the uncertain parameters of the model, the mathematical approach used to develop the infinite-horizon end-effects part of the model, a comparison of algorithms used in the model's solution, and a comparison of the multistage stochastic linear programming model with the previous technology, static mean-variance analysis. Experience and benefits of the model in Yasuda-Kasai's financial planning process is also discussed. [ABSTRACT FROM AUTHOR]

This paper presents a 'one-pass' algorithm that determines an 'advanced' dual basic feasible solution for a class of capacitated generalized network problems. Special cases in this class of problems include transportation and transshipment problems. We include computational results that show that this new start substantially improves the solution performance of the dual method for transportation and transshipment problems. In fact, a dual code employing this advanced start is found to be faster (in terms of total solution time) than the fastest out-of-kilter code SUPERK on highly rectangular transportation problems. [ABSTRACT FROM AUTHOR]

This paper presents a branch-and-bound algorithm for solving fixed charge transportation problems where not all cells exist. The algorithm exploits the absence of full problem density in several ways, thus yielding a procedure which is especially applicable to solving real world problems which are normally quite sparse. Additionally, streamlined new procedures for pruning the decision tree and calculating penalties are presented. We present computational experience with both a set of large test problems and a set of dense test problems from the literature. Comparisons with other codes are uniformly favorable to the new method, which runs more than twice as fast as the best alternative. [ABSTRACT FROM AUTHOR]

We prove that a necessary and sufficient condition for the primal and dual solution sets of a solvable, finite-dimensional linear programming problem to be stable under small but arbitrary perturbations in the data of the problem is that both of these sets be bounded. The distance from any pair of solutions of the perturbed problem to the solution sets of the original problem is then bounded by a constant multiple of the norm of the perturbations. These results extend earlier work of Williams. [ABSTRACT FROM AUTHOR]

Since it is safer and less expensive to absorb delays on the ground, air traffic control management tries to limit the duration of airborne delays by holding aircraft previous to departure when congestion at the airport of destination is anticipated. The problem of assigning appropriate ground-holds to aircraft is known as the ground-holding problem. Ground-holding decisions must be implemented in real time and for multiple airports; therefore, the speed of solution for algorithms is critical. This paper tests static and dynamic optimal solutions, and a very fast heuristic for the assignment of ground-holds in air traffic control. The optimal solutions are based on stochastic linear programming. The heuristic incorporates elements of stochastic modeling by utilizing information conveyed by a probabilistic forecast of airport landing capacity, while taking into consideration the dynamic nature of the problem. In extensive computational experiments based on data for Logan airport, the heuristic performed significantly better than the optimal static solution, a deterministic solution, and the passive strategy of no-ground-holds; and within 5% of the optimal dynamic solution at a fraction of the computational time. Due to its remarkable efficiency, the stochastic-dynamic heuristic appears to be a promising building block in the development of fast ground-holding algorithms for the complete network of airports. [ABSTRACT FROM AUTHOR]

Given a complete directed graph G = (V, A), the delivery man problem (DMP) consists of determining a Hamiltonian circuit minimizing the sum of distances (along the circuit) from a given vertex v1, to every vertex of V, including v1 itself. There exists a number of applications of the DMP in the fields of distribution and machine scheduling. The DMP is NP-hard. The objective of this paper is to develop new theoretical results and an exact algorithm for the problem. A new, integer linear programming formulation is provided, and results on the matroidal structure of a class of combinatorial problems are developed. These are used to derive lower bounds for the DMP. These bounds are embedded into an enumerative algorithm. The largest problems solved to optimality with the proposed algorithm involve 60 vertices. This compares favorably with previously published methods. [ABSTRACT FROM AUTHOR]

This paper presents two versions of a method for solving large linear programs through decomposition. In both versions the problem is decomposed into subprograms as in the DANTZIG-WOLFE model, but each version uses a different type of linking program. The subprograms are first solved, and then the infeasibility of the resulting solution for the linking program is used to generate a price-adjustment process (much like a market mechanism), which gradually corrects the objective functions of the subprograms, until either some optimal solutions to the latter yield a feasible solution to the linking program (then the problem is solved), or evidence is obtained that the problem has no feasible solution. [ABSTRACT FROM AUTHOR]

The article presents information on professor Egon Balas' approach to solve linear programs. The purpose of this note is to propose additional test meant to increase the power of Balas' algorithm by reducing the number of possible solutions examined in the course of computation and to propose an application for which the algorithm appears particularly well-suited. It now includes the issue of generating and searching the solution tree. One should first note that for many problems a feasible solution is known in advance. This solution may be used to establish a starting value for other than infinity, thereby expediting convergence to the optimum. But such a solution may also be used in another way. If it is suspected that an appreciable fraction of the variables for the feasible solution coincide in value to those for some optimal solution, it may be useful to employ a two-stage algorithm that treats the 'primary' variables set at unity in the feasible solution differently from the 'secondary' variables set equal to zero.