Suboptimal algorithms for the quadratic assignment problem

The idea of combining relatively simple continuous methods with discrete procedures is used for the construction of suboptimal algorithms for quadratic assignment problems. Depending on the nature of the special problem these steps may vary in complexity. The simplest procedures require minimum storage space and result in tolerable computation times. Different choices of parameters and random variations may be used in order to obtain statistical distributions of suboptimal solutions. Computational results for sample problems indicate improvements on results of Steinberg, Gilmore, and Hillier and Connors.     

A chance-constrained distribution problem

The transportation model with supplies (S_i) and demands (D_i) treated as bounded variables developed by Charnes and Klingman is extended to the case where the S_i and D_i are independently and uniformly distributed random variables. Chance constraints which require that demand at the jth destination will be satisfied with probability at least β_i and that stockout at the ith origin will occur with probability less than α_i are imposed. Conversion of the chance constraints to their linear equivalents results in a transportation problem with one more row and column than the original with some of the new arcs capacitated. The chance-constrained formulation is extended to the transshipment problem.     

A priori error bounds for procurement commodity aggregation in logistics planning models

A complete logistical planning model of a firm or public system should include activities having to do with the procurement of supplies. Not infrequently, however, procurement aspects are difficult to model because of their relatively complex and evanescent nature. This raises the issue of how to build an overall logistics model in spite of such difficulties. This paper offers some suggestions toward this end which enable the procurement side of a model to be simplified via commodity aggregation in a “controlled” way, that is, in such a manner that the modeler can know and control in advance of solving his model how much loss of accuracy will be incurred for the solutions to the (aggregated) overall model.     

An analytical minefield evaluation model without space averages

The paper describes an approach to the evaluation of the effectiveness of a minefield in terms of the number of mines that are detonated by a convoy of sweepers and ships and the corresponding number of vessels that are immobilized. The positions of the mines and the tracks of the vessels are assumed to be known, which means that the evaluation measures are dependent on a large number of disjoint events, each event being the immobilization of particular vessels by particular mines. This may render combinatorial methods computationally infeasible, but by introducing approximations in the assumptions, the difficulty can be overcome, specifically by modelling the arrival of each individual vessel in the neighborhood of a mine by an inhomogeneous Poisson stream for which the arrival rate is nonzero only over a short time interval. The plausibility of the approach is supported by results of a critical-event simulation model.     

A finiteness proof for modified dantzig cuts in integer programming

Let be a basic solution to the linear programming problem subject to: where R is the index set associated with the nonbasic variables. If all of the variables are constrained to be nonnegative integers and x_u is not an integer in the basic solution, the linear constraint is implied. We prove that including these “cuts” in a specified way yields a finite dual simplex algorithm for the pure integer programming problem. The relation of these modified Dantzig cuts to Gomory cuts is discussed.     

Stochastic linear programs with simple recourse: The equivalent deterministic convex program for the normal,exponential, and erlang cases

We consider here stochastic linear programs with simple recourse when all the elements of the technology matrix and the resource vector have certain specific distributions. The distributions considered are the Normal, Exponential and Erlang. For the first two instances we extend the equivalent deterministic program to include the variance of the recourse. Finally, a simple example is given to illustrate the application of the formulas for the Erlang case.     

Analysis of data from life-test experiments under an exponential model

This paper discusses situations in which the distribution of a lifetime response variable T is taken to depend upon a vector x of regressor variables. We specifically consider the case in which T, given x , has an exponential distribution, and in which x represents levels of fixed factors in an experimental design. Methods of analyzing data under this type of model are discussed, with maximum likelihood and least squares methods being presented and compared.     

Auxiliary procedures for solving long transportation problems

An efficient auxiliary algorithm for solving transportation problems, based on a necessary but not sufficient condition for optimum, is presented.     

On the distribution of the optimal value for a class of stochastic geometric programs

An approach is presented for obtaining the moments and distribution of the optimal value for a class of prototype stochastic geometric programs with log-normally distributed cost coefficients. It is assumed for each set of values taken on by the cost coefficients that the resulting deterministic primal program is superconsistent and soluble. It is also required that the corresponding dual program has a unique optimal point with all positive components. It is indicated how one can apply the results obtained under the above assumptions to stochastic programs whose corresponding deterministic dual programs need not satisfy the above-mentioned uniqueness and positivity requirements.