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.     

An operator theory of parametric programming for the transportation problem-II

This paper investigates the effect on the optimum solution of a (capacitated) transportation problem when the data of the problem (the rim conditions-i. e., the warehouse supplies and market demands-, the per unit transportation costs and the upper bounds) are continuously varied as a (linear) function of a single parameter. Operators that effect the transformation of optimum solution associated with such data changes, are shown to be a product of basis preserving operators (described in the earlier paper) that operate on a sequence of adjacent basis structures. Algorithms are provided for both rim and cost operators. The paper concludes with a discussion of the economic and managerial interpretations of the operators.     

Control variable methods in the simulation of a model of a multiprogrammed computer system

One approach to the evaluation of the performance of multiprogranmed computer systems includes the development of Monte Carlo simulations of transitions of programs within such systems, and their strengthening by control variable and concomitant variable methods. An application of such a combination of analytical, numerical, and Monte Carlo approaches to a model of system overhead in a paging machine is presented.     

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.     

An operator theory of parametric programming for the generalized transportation problem: II Rim,cost and bound operators

This paper investigates the effect on the optimum solution of a capacitated generalized transportation problem when certain data of the problem are continuously varied as a linear function of a single parameter. First the rim conditions, then the cost coefficients, and finally the cell upper bounds are varied parametrically and the effect on the optimal solution, the associated change in costs and the dual changes are derived. Finally the effect of simultaneous changes in both cost coefficients and rim conditions are investigated. Bound operators that effect changes in upper bounds are shown to be equivalent to rim operators. The discussion in this paper is limited to basis preserving operators for which the changes in the data are such that the optimum bases are preserved.     

Adjacent vertices on transportation polytopes

To solve linear fixed charge problems with Murty's vertex ranking algorithm, one uses a simplex algorithm and a procedure to determine the vertices adjacent to a given vertex. In solving fixed charge transportation problems, the simplex algorithm simplifies to the stepping-stone algorithm. To find adjacent vertices on transportation polytopes, we present a procedure which is a simplification of a more general procedure for arbitrary polytopes.     

An operator theory of parametric programming for the generalized transportation problem-III-weight operators

This paper investigates the effect on the optimum solution of a capacitated generalized transportation problem when any coefficient of any row constraint is continuously varied as a linear function of a single parameter. The entire analysis is divided into three parts. Results are derived relative to the cases when the coefficient under consideration is associated, to a cell where the optimal solution in that cell attains its lower bound or its upper bound. The discussion relative to the case when the coefficient under consideration is associated to a cell in the optimal basis is given in two parts. The first part deals with the primal changes of the optimal solution while the second part is concerned with the dual changes. It is shown that the optimal cost varies in a nonlinear fashion when the coefficient changes linearly in certain cases. The discussion in this paper is limited to basis-preserving operators for which the changes in the data are such that the optimum bases are preserved. Relevant algorithms and illustrations are provided throughout the paper.     

A cost analysis of sampling inspection under Military Standard 105D

Military Standard 105D has been almost universally adopted by government and private consumers for the lot-by-lot sampling inspection of product which may be inspected on a dichotomoun basis The plan specifies, for each lot size, a random sample size and set of acceptance numbers (maximum allowable number of defectives in each sample). The acceptance numbers are based upon the binomial distribution and depend upon the quality required by the purchaser. Where several consecutive lots are submitted, a shift to less severe (“reduced”) inspection or more severe (“tightened”) inspection is specified when the ongoing quality is very high or low. Further experience permits a return to normal sampling from either of these states This paper examines the long range costs of such a sampling scheme. The three inspection types are considered as three distinct Markov chains, with periodic transitions from chain to chain. The expected sample size and the expected proportion of rejected product are determined as a function of the two parameters under control of the manufacturer, lot size and product quality. Some numerical examples are given which illustrate how to compute the overall cost of sampling inspection. Suggestions are made concerning the choice of parameters to minimize this cost.     

An empirical bayes estimator for the scale parameter of the two-parameter weibull distribution

An empirical Bayes estimator is given for the scale parameter in the two-parameter Weibull distribution. The scale parameter is assumed to vary randomly throughout a sequence of experiments according to a common, but unknown, prior distribution. The shape parameter is assumed to be known, however, it may be different in each experiment. The estimator is obtained by means of a continuous approximation to the unknown prior density function. Results from Monte Carlo simulation are reported which show that the estimator has smaller mean-squared errors than the usual maximum-likelihood estimator.