TABLE OF CONTENTS Page A PROBLEM IN ESTIMATING A SAMPLE PARAMETER Richard L Patterson ooooo ooooo o o o o o..0...oooooo 2 SOME FURTHER RESULTS TO PALM'S OVER FLOW PROBLEM Kenneth R. Eaton Jr. Gary S. Beckerman... o.. 0 00....00 o 0.o 0 0 0 0 0 0 0 0 0 0 0 0 0 6 THE IMPACT OF COMPUTING SYSTEMS AND SIMULATION ON ''TOP-LEVEL MANAGEMENT' DECISION.PROCESSES J. B. Neuhardt oooooooooo oo oo oo. ooooo, ooooo o o o O oooooooo o 19 BIBLIOGRAPHY ON INTEGER LINEAR PROGRAMMING Arnoldo Hax O O O 0 e o 60 0o e e o o o o o0 o o o o o.0o o 0 o o o o o o o o o o o o 2 9 Published by the Industrial Engineering Department of The University of Michigan Mailing Address: The University of Michigan Department of Industrial Engineering 231 West Engineering Building c Professor Richard Co Wilson Ann Arbor, Michigan

"PERIODIC REPORT OF INDUSTRIAL ENGINEERING RESEARCH" at The University of Michigan This Periodic Report of Industrial Engineering Research is offered as a medium for the rapid publication of articles of industrial engineering research-in-progress and of bibliographies with potential use in such researcho The justification for this new publication is based on a number of apparent needso Faculty and students have frequently expressed concern for their difficulty in keeping informed about the current activities of their colleagueso It is hoped that they will find the report helpful in reducing this difficultyo The active researcher, it is hoped, will use the report freely as a means for inviting suggestions on work which may be still in progresso A means of easy communication should stimulate others to undertake research in areas of their own interesto The availability of a medium for publication of unfinished work should encourage preparation of progress reports and thus furnish the writer with early experience in recording his results for publicationo Initially, annual publication is plannedo More frequent publication is anticipated if reader demand and contributed articles are sufficiento Comments and suggestions about the report are invited from readers and should be sent to the attention of o The University of Michigan Industrial Engineering Department "Periodic Report of Industrial Engineering Research" Ann Arbor, - Michigan Contributors are invited to submit papers for publicationo The editors will serve as referees in accepting papers for final publicationo We will endeavor to return manuscripts if requested, but cannot assume responsibility if they are losto

A PROBLEM IN ESTIMATING A SAMPLE PARAMETER By Ro Lo Patterson Consider a denumerable population N, composed of two subpopula= tions W and BN = WuBo A set of observations are made on a sample of size N from N, which consist of "decisions" as to whether or not each element came from W or Bo The observations are subject to the following two types of errorso 1o An element drawn from N is believed to have come from B when it came from Wo 20 An element is drawn from N and is believed to have come from W when it actually came from B The problem is to make accurate statements about the fraction of the sample of size N which came from W so that further inferences may be made concerning NW,Bs The purpose of this paper is to suggest a method of describing what is known about this fraction in a way which is useful for making further inferences about the ratio of the sizes of W and Bo Sampling problems of this nature abound in the social scienceso For example, an estimate is made of the number of voters who will vote for LoBoJo in the next presidential electiono A poll is conductedo Some of the individuals who are included in the sample state that they are going to vote for LoB0Jo and then they either will not vote at all or else will vote for the opponento Some of the individuals say that they will not vote for LoBoJo and when election day rolls around, they will vote for LoBoJo Before the prediction of the percentage of the vote expected to go to LoBoJo is made, this sample must be adjusted to compensate for these two types of errorso There are various methods available for adjusting the fraction of the sample in the above example who say they will vote for LoBoJo to bring it closer to the fraction in the sample who actually do vote for LoBoJo on election dayo Some of these techniques involve selecting sets of population characteristics (Bi, o,Bk) for which (a) no mistake will be made in deciding whether or not an individual possesses characteristic Bi, and (b) each Bi is correlated to the way in which the individual will actually vote on election dayo Other examples of extracting samples which are subject to the errors (1) and (2) can easily be drawn from the fields of product merchandising, industrial quality-control, and reliability analysis To cite one more examples consider the problem of sampling batches of items to determine the fraction of the lot defectiveo On the basis of this sample, a series of decisions may be made which involves large sums of moneyo Suppose that the inspector mistakenly calls some of the good items "defective" and calls some of the defective items "good"o

The result is that the sample fraction defective is in erroro What are the likely consequences? In this example, unlike the previous one, it may be undesirable or even impossible to attempt to perform a correlation analysis between some set of "indicators" which are related to whether or not an item is defective, and which can positively be observed to be either "yes" or "no"o In facts it can be argued that almost no observation is compeletely free of erroro In practice, the accepted methodology is to (a) ignore the slight probability of "calling a spade a heart or a heart a spade" if it is low enough, or (b) estimate the fraction of the pupulation which contains property "a" by statistical techniques such as observing additional variables BiooBk for which the probability of misidentification may be ignored, and correlating the Bi with ao There are, however, a set of probability distributions which, if knownand tabulated, could aid in estimating the fraction of a population which possesses a particular set of characteristicso They might be more useful in certain situations than other statistical techniques of parameter estimationo These distributions will be identified by first hypothesizing a sampling situation and then asking a series of questions related to the sampling problemo Consider two denumerable populations W and Bo WuB = No Extract samples of size W and B from W and B, respectivelyo Let W + B = No Of the sample of size W, T are believed to come from W and W-T are believed to come from B Of the sample of size B, F are believed to come from W and B-F are believed to come from Bo Suppose theIre exist probability distributions P (T = t), t = OloooW ogo P(T = t) = P (1-P) ) and Q(F = f), f = 0,1,oooB (eogo Q(F=f) = G)Pf (1-p) B f) which describe these errors of identificationo * Let D be the number of elements which are "detected" to have come from Wo The D = T + F and D has a probability distribution R (D = d) = P (T = t) Q(F = d - t | T = t)o t+F=d * P1 is the probability that an element of W is believed to come from W, P2 is the probability that an element of B is believed to come from Bo

A series of questions may now be askedo lo How many items from W and how many from B must be drawn to make D = d? ioeo s what is the joint distribution of W and B implied by D = d? 20 How many items in all must be drawn to make D = d? ioeo if N = W + B, how large must N be to make D = d? 30 What is the difference in the conclusions if (a) a probability distribution of the proportion of B's to W's is assumedo (b) a certain proportion of B's to W's is assumedo Is it necessary to postulate (a) or (b) to answer questions 1 and 2? 4L Given a fixed sample size N= n and D = dX what is the distribution of W? 50 What fraction of N is W? (Limit of a Bernoulli sequence) For example, the answer to question (2) is that N follows the negative binominal distribution providing (a) P(T = W) = 1 (b) P(F = 0) = 1 (c) A certain proportion of the elements of are assumed to consist of elements from o The writer has recently been working on an Arms Control Verifications Requirements project in which it was necessary to estimate the number of nuclear tests which had been conducted in a time interval (OTd) which extended up to the instant that the dth "detection" occurredo A "detection" could occur in two ways: (a) a hypothetical inspection system could detect a test, if it occured, with a constant probability po (b) a stream of "false alarms" occur according to some "known" distribution, eogo, a Poisson distribution with parameter Bo The answer to this question is that, under the above assumptions, the number, k, of tests conducted up to the dth detection is distributed according to the negative binomial distribution when 6=0o If $>0, the problem becomes somewhat more difficult Dro Wyman Richardson and the writer showed that when a>0, the number of tests conducted in the interval (0,T ) was distributed according to the distribution Q(k/d) = d > Y D —ik i D = d i 0 D-k D k 1 where i=0 i Yik ki) P (1- p) and p e Bi j ' " — --

To recapitulate, assume that a population N is composed of two subpopulations W and B o A sample of size N is drawn from N, and D elements are "detected" to come from W and N - D from BS Instead of knowing the value of W, the number of elements in N which were drawn from W exactly, the number is known only to within a probability distributiono There are two approaches to the problem of making inferences about N and W. lo Make observations on the sample drawn from N for which the error of observation if "virtually" zero, and from these observations, use correlation and regression analysis to make point estimates of the fraction of the sample, which came from WO With'this point estimate in hand and its associated "confidence" level, inferences are then drawn regarding the composition of No 20 Assuming the error distributions describing the likelihood of misidentifying elements-from W and B, derive the distribution of the number of elements in the sample which came" from Wo Proceed to make inferences about the composition of N based upon this distribution0 If there is no possibility of misidentifying elements from W and B, then the distribution degenerates to a "point" distribution as in the case of an inspector drawing k "defectives" out of a sample of size N and assumes that he can always state the fraction K/N perfectlyo In this example the subpopulation B is "defectives" and W is "nondefectives" It is suggested that the distributions mentioned earlier in the paper be derived where possible and 'tables be tabulated for a variety of caseso Such information, if available, would serve to generate a complete probability distribution that a sample fraction assumes a given value in situations where it is suspected that the sample fraction may be in error The populations W and B need not necessarily be denumerableO For instance, a machine may be searching a length of wire, a sheet of metal, or a volume of space in order to discover the occurrence of a given phenomenono After it has searched a space until the dth "detection" has been made, the question is asked, "how many occurrences of the phenomenon has the machine really observed?"

SOME FURTHER RESULTS TO PALM'S OVERFLOW PROBELM* By Kenneth Ro Eaton Jro Gary So Beckerman A telephone switching network whereby an incoming call tests to determine if a line is free and, if not, switches into another line is an example of the behavior characteristic of what Palm refers to as an overflow problemo The distribution of the calls which overflow one line constitutes the distribution of the input to the next lineo Because, in a large system, the overflow behavior may be repeated for many lines, this paper will discuss the distribution in further detail More abstractly the overflow problem consists of an input to n ordered (numbered) serving stationso The input tests each station sequentially until it finds the lowest numbered free station where it may be servicedo Thereforea the input may be considered in two parts; the traffic serviced by the first m stations and the "overflow" which is the input serviced by the remaining nom stationso Obviously then the input distribution to the ith station is the same as the overflow distribution from the i-lst station0 It is this distribution that is of interest because knowing it, the mathematically difficult problem of a n-stage system may be reduced to the n single stage systems which are comparatively simple to solveo Interest developed in the overflow problem when the authors began a study of power & free conveyor systemso Here a part arrives at the first of n ordered stations and overflows if it is busyo This process continues until the part is serviced or overflows the systemo The authors were interested in describing the,input distribution to each station after the first and the distribution of parts which were lost to the system (ioeo those parts- which overflowed the last station)o Although the conveyor system.under study included storage space in front of each stations Palm9-s.:results provided an insight to a method of approach for solving the new problemo Let us assume that calls arrive to the first of m stations at the instants TlT2 ooo0Tnnooo and denote the interarrival times for the arrival distribution of this station as o 0n nT 'nl (T 1 0;o n=1,2,oo ) * This paper is an extensive revision by Mro Eaton of work originally performed by Mro Beckerman and Mro Eatono Listings of the computer programs used may be obtained by writing Mro Eaton, Department of Industrial Engineering, University of Michigan, Ann Arbor, Michigano

' 1 Also, let us assume, as Takacs does, that the 8 are identically n distributed, independent, positive random variables whose distribution function is: F(x) P {o <x} n = Denoting the Laplace-Stieltjes transform of F(x) as 0(s) we have: 0(s) = eSX dF(x) If we now define ti as the epoch of arrival of the ith demand serviced in the overflow group,' the time intervals tr i+l for i=l,2,00, are independent,-idenaically distributed random variables whose distribution function Takacs denotes as G (t)o In 1959 Takacs showed that this G r(t) can be represented by the integral recurrence relation: t F e-bu -bu (t-u) dG (u) Gr(t) J0[ebu+(1 -e ) ]Gr r-1 Furthermore$ he noted that the Laplace-Stieltjes transform: 00 ~r (s)= e SdG (t) r0 r may be represented by a recurrence relation of the form: y ( Yrls+b) r=l,200 ~ (s) = r_ r l 2 ~o r 1-Y (s)+y (s+b) r-l r-l. Continuing Takacs proved that Y r(s) could also be expressed as: r (r)J-l l_0(s+iv)) j (s =0 j i=0 (-s+-iP) rr r+l - 1 -(i) Z r+l.......... r7 i C ~0(s+iu) j=O j=iz Thus, the Laplace-Stieltjes transform of the interarrival distribution for any station can be expressed in terms involving only the LaplaceStieltjes transform of the arrival distribution to the first station0 In order then to find G r(t), one must solve for the inverse LaplaceStieltjes transform of yr (S) In most cases this is a difficult, if not impossible, problems

3 Palm has also studied the overflow problem and found an integral recurrence relation for G (t) where now G (t) P(overflow time t) = r P 1-P(overflow time <t) and G (t) = Gr (t) ft(l-e bU)[l-GrCt-u)] dGr l(u) r r-1 j r r-1L 0 However, Takacs' form for G (t) can be shown to be a reformulation of the above formula and is easier to deriveo Khintchine showss as does Palm, that if a simple stream of calls enters line L1, then there enters into any line Lr(r> 1) a stream of the type P (stationary, orderly, and with limited aftereffects) 6 Defining Gr*(s) = e Gr(t)dt Palm obtains a recurrence relation 0 for the Laplace transform of Gr(t) as: G* (S) r l G *(s) = — r 1+sG -(s) (s+l)G l(s+l) rjl r~L It can be shown that Takacs' recurrence relation follows from thiso Therefore, knowing GO*(s) [the Laplace transform of the arrival distribution to the first station] we can solve successively for the Laplace transforms of higher orders of ro In contrast to Takacs' general solution, Palm solves a special case of the overflow problem wherein the input has a negative exponential distribution0 His results followo Defining B r(s) for r= -l,0,looo as the polynomial of power r+l~ Br(S) = r+l+ (k )s(s+l)(s+2)00oo0(s+r-k)Ak -1 k=ko where z is defined as zero and, consequently, B (s)= X 0=1, Palm k=0 proves that these polynomials are related by the formula: B (s) = sB- (s+l)+ XB r(s) r r-1 r=~l If. = l S 0

-9 - He then proves that these polynomials describe the Laplace transform of G (t): r B (s+l) G *(s) = --------------- B (s) r It follows from the definition then, that the polynomial B r(t) of order r+l has positive coefficients and the coefficient of r+l s is lo Therefore$ all real roots, sri' of this polynomial are negative and can be written: Br(s) (s+a )(s+a r).o(s+ar) where ari -sri and ari >0 Consequently, the denominator of G r*(s) can be factored into the form: B 1 (s+1) C C G *(s) =.. ro. + rl + o0+ rr B (s) s+a s+a s+a rS) ro0 rl rr Now knowing that: L(Ve Pt) = V s+p and r Crk. G *(s) = _.____ k= s+ark Palm shows that: r -(ark )t G (t) = Crk e r k=0 rk Essentially then Palm has solved the overflow problem under the assumption that the input is negative exponentially distributedo He then derives a polynomial which simplifies the computation for inverting the Laplace transforms of the interarrival distributionso The remainder of this paper is devoted to two different approaches to solving a simple two station overflow problemo First, Palm's results are solved with the successful application of the University of Michigan Computing Center's programs for finding the roots of polynomial equations and the coefficients of partial fraction expansions0 And secondly, a simulation is developed and tested against the known resultso

Solution of two station case usi'n'gi:Palm's resultso It was assumed for this case that the input stream or arrival process was governed by the negative exponential distributiono Therefore, G (t) = e t -0 and B (s) = X+s Now, the polynomial of degree 1 can be determined to be: Bl(s) = s2+(2X +l)s+X2 which yields the Laplace transform of Gl(t)o Sn _ _ 1 ss +(2X+I)Ps+A s +(2X+l)s+ A In order to obtain the partial fraction expansion, the denominator of G *(s) is factored to give: s= -(X+2.) + Letting all equal the root with positive coefficient we find: a =A + 1 1a2 X + 1 +\f Therefore, by partial fraction expansion: G *(s) = 1)s+(x+) (s+a1) ( s+al 2) s+a + 12 s+a12 Where Cll and C12 can be found by equating coefficientso Solving we find: 1 cll ~ 7+ 0 1 C12 =- 7 - 1 4\+ 1

-11 - Finally then: 1 1 7 + s ^ 4^ __ A. -...... _~...... ' 1 + ~ 1,41\Wi G1*(s) = S+X+T. + \ + 1 to Because both of these expressions contain only first order powers of s, the inverse Laplace transform is of the form~ -allt al2t Gl(t) = Cle 11 +C1e 12 or 1 + G (t) =(~ + 1 --- )e + 1 ( x + + 4\E+ This then is the overflow distribution from the first stationo Although the mathematical manipulations performed in obtaining the final values were not difficult, they were lengthyo For this reason the authors decided to use the computer facilities at the University to find the roots of the denominator and the partial fraction expansion of G2*(s)o For the second station we have as before: B2(s) = s3+(3X+3)s2+(3X2+3X+2)s+X3 and B (s+l) G2*(s)= = B (s) s2+.(2X+3)s+( 2+2A+2) s +(3X+3)s +(3X +3X+2)s+X3 At this time various subroutines from the Computing Center Library were used to compute the roots of the denominator and the partial fraction expansion of G2*(s) To find the cube roots of the denominator of G *(s) the subroutine 2 M = ZER2o (NA,R) was used where: N = the degree of the polynomial in integer mode A = a vector containing the real and imaginary coefficients of X1 (i = nnl,oo0001)

R = a vector containing the real and imaginary roots of the equation MU an error indicator such that m=l means execution OK and m 2,3,4 means an error has occuredo For the particular example in this paper:o ACO)= 1 A(2) 3X+3- A (4) 3X 2+3X+2 A(6) A3 A(l) = A(3) A(S) A(7) Q Next, a subroutine which solves simultaneous equations was used to find the partial fraction expansion. For this particular problem we wish to determine roots r1,r2r which are negative0 Letting a -r 1a -r -a 1 2~ 2 3 3 we desire that:A B C 52.PS -+ -...+ sp s+a1 s+a2 s+a3 (S:+a~)(s+a )(s+a) where p 2X+3 and q = A +2X Now finding a common denominator and equating coefficients we obtain:, A+B+C= 1 (a2 +a3)A + (a1+a 3)B + (a 1+a2 )C p a~a3A + a a3B + a a2Cq which can be expressed in matrix notation as:, a 2a3 a1+a 3 a1+a. a al a3 ala C To-solve the simultaneous equations, the subroutine, X =GJRDTO, (N,14,A9D) was used, where: N= the number of rows M = the number of columns including the right had side A= the first element of the matrix of coefficients (A(l,l)) X = an erros return-where X=1 means execution OK and X=2,3,,00 indicates an error, D = the value of the determinent

The input format required 'is of the form: N = 3 1 a.. p J-J -q M=~4=N+l and the output is of the form: N (ai Ic M-=N+l1 Thus, a simple program incorporating the two subroutines solved for both the roots of the denominator an h ata rato xaso ofG*(s). inverting the final-form ofOG *(s) we obtain: -a~t -a~t -a~t G Ct) Ae 1+ Be 2+ Ce 2 The following pages contain listings of the coefficients of G1(t) and G 2(t) for different values-!of~ — with ji = 1 Values of G1(t) f or. Various X's -lo 312t -o.; 021t X= 1/6 G1(t).123e +.887e -1. 37t -. 029t X: 1/5 G 1(t) X = 1/4 G1I(t) X= 1/ 3 G 1(t) X =2/ 5 G 1(t).127e.1 46e 9q1 7 3e -104 6t -10 G0t +.827e + 0.8 53 e. + 08 27 e +.810e + -M, O43t -.~o0070t - 009'4t - 1 3 4 t )X= 1/2 G1(t) X= 3/5 G1 (t) X= 2/3 G1(t) -10o 71t. 190Oe -, 86t.211e - 2 0 02t 2 2 9e -20o12t +.78'4e +.771e M, 17 8t -, 209t.239e +.761e

-14+ - 2,, 2 5t,250t X~= 3/4+ G1(t) = X= 4/5 G1(t) = X = 5/6 G1(t)= 0 250e. 2 56 e o, 260e -2, 32t -2, 37t +. 750e + 07441e + 0774Oe -0.2 9 5t -. 2 92 t Values of G 2(t) for Various x'Is X= 1/6 G 2(t) x= 1/5 G 2(t) X= 1/4+ G 2(t) X= 1/3 G 2(t) X= 2 /5 G 2(t) X= 1/ 2 G 2(t) X= 3/ 5 G2 Ct) X= 2 /3 G 2(t) X= 3 /1+ G 2Ct) X= 1+/S G 2Ct) X= 5 /6 G 2(t).0 S5 e 0 061+e o 072e o 0 8 4e.0 09 5e 0 106e 1 16 e o, 122e 1 2 8e o 1 32 e 0,131+e -2. 4t -2.5 2t -20 61+t -2 0 82t -2. 97t - 3.1 7 t -3 37t - 3" SOt -30 66t - 30 7 5t -30 81t + 0028e + 0 037e +.005 0e + 0071e + 008 6 e + 0 107e + 0 126e + 0 137 e + 014+9e + 1 56 e + 0 160e -l. O5t -l. 07t -l0 lit -lois6t -1. 22t -l1 3 0t -l. 38t +. 916e + 0 900e + 8 7 8e +.8441e + 8 19 e + 7 86 e + 0758e + 074+le + 0 722e + 0 712e +.706e =, 002t -.0 003 t Qos00t -. oolt -. 018t -M. 030t -.o0046t -W 059t - o007 6t -.087t. 095t -l. 51t -l. 56t - 1.59 t After the successful compilation of the constants for G C(t) and G2(),the authors could accurately evaluate a conveyor simulator which was to be used for further research. The simulator was designed to include storage before each service station0 However, it had to be validated before any results could be accepted0 Setting the storage at zero level, the simulator provided a model of the two.station nostorage case0 Consequently its results for the overflow distribution could be validated against the known distribution through suitable statistical tests0 The simulation was used to study the particular case where the values of X 1/2 and 1 P'2= 1 were used0 In order to obtain what the authors considered to be statistical equilibrium, a run of 16,000 time units was simulated0 Actually four different runs of '4000 time units were made0 However, because the starting point for each run was chosen "at random" by the IBM 7090, the results could be combined and considered as one run0 Approximately 18 minutes were required to simulate 16,000 time units0

The 16,000 simulationed time units gave rise to 5393 trials for station 1 and 1280 trials for station 2o These number of trials were considered to be sufficiently large to meaningfully apply any statistical testo The results from the computer simulation were used to determine the cumulative frequency of the interarrival distributiono. In other words, the number of trials for-which a success occurred in -t, time, was divided by the total number of trialso These values and those obtained from the solution of -the analytic equations for stations 1 and 2 are given in tables 1 and 2 (Pagesl6 and 17) o Also, the difference between the two values is giveno The Kolomogorov-Smirnov goodness of fit statistical test was made. This statistic compares the maximum deviation between the actual and theoretical curves with a tabulated maximumo Acceptance of the hypothesis that both curves come from the same distribution occurs if and only if the calculated maximum deviation is less than the tabulated maximum According to the Kolomogorov-Smirnov statistic we then 1) reject the hypothesis that the sample came from the theoretical population if~ 5393 max IF n(x) - F(x)> -. = o02218 x n at the o01 level for station lo 2) reject the hypothesis that the sample came from the theoretical population if: 1 o63 D1 8 = ax IF(x) - F (x)> Q = o04557 at the 01 level for station 20 The maximum deviations which occurred can be read from tables 1 and 20 They are o0045 and.0227 for station 1 and station 2 respectivelyo Therefore, the hypothesis that the values from the simulation results came from the same distribution as the theoretical results is not rejected at the o01l levelo This paper has presented the results of an analytic solution to Palm's overflow problem using an electronic computer to calculate the necessary coefficients of the overflow distribution and of a simulation of the same problemo Because a statistical test showed that the simulations results accurately portrayed the system under study, further research could now be performed on systems which do not yield to analytic solutions attemptso

TABLE I TIME BETWEEN OVERFLOWS - STATION 1 _ I -- Pa G(t) Simulatio |I E | Palm I Simulation __.I.,,, I G (t) _-.1 I E I Palm Simulation............ I 1 -w o0016 72290 o7245 0002 o00829 0081 00024.60863 o6062 oOO0l o00725 o0074 o0025 o 52862. 5311 o 0002 o00634 o 0065 o0011 46176.4637 o0002.00554 o0057 o0002 o 40376 o 4040 o 000l o 00485 o 0050 o0013 o35311.3544 o 0004 00424 o 046 o0027 o 30882 o 3115 0003.00371 o 0040 o0003 o27009.2698 00005 o00324 o0037 o0003. 23622 o2359 o0002 000284 00026 *00045.20650.2021.0003 o00248.0022 o0022.18069.1785.0019 o15803.1561 o0025 o13821 o1357.0020.12088 o1189 *. '0045 o10572 o 1012.0032.09246 o 0892 00015 o08086.0794 o 0002 o 07072 o 0709 o0004 06185 o0623 00028 o05410 o 0569.0015 o04731.0488 o0016 o04138.0430.0013 03619 00375 o0006 o03165 o0323 -o0001 OOOl 02768.0278.0007 o 02421 o 0235 o0006 o 02117.0206.0009.01852.0176 o0016 o 01620 0146.0005.01416 o0137 o0004 o01239 o0119.0000.01083.0108 o0001 000948.0096 16 NA

-17 -TABLE II TIME BETWEEN OVERFLOWS -. STATION 2 G2(t) | I Palm [Simulation I G2(t) I I Palm Simulation.I. 00082 0 0061 00022 0031 00009 o 0004 00035 o0019 0 o00034 00057 00031 00002 o0016 o0059 o0036 o00040 00057 o0114 o0 0111 o0061 00085 o0122 0146 o0158 0173 0 0161 0 0151 0 0191 o0173 o0156 o 0143 o0147 o 0147 079638 o 7483,6 o72052 o69771 o67668 o65657 o63713 o61829 o60002 o58228 o56507 o54837 o53217 51644 o50118 o48636 o47199 o45804 044450 o43137 o41862 o40625 039424 o38259 o37128 036031 o34966 o33932 o32930 o31956 o 31012 o30095 029206 o28343 o7891 o7422 o7227 o7008 06758 o6562,6406 o6164 6000 o5789.5594 05453 5320 5148 04953 4828 04680 4523 04359 04203 4125 o 3977 3820 o3680 03555 o3430 3336 03242 o3102 03023 2945 02867 o2773 o2687 -1 00142 00130 o 0129 o 0139 o0182 o 0172 *00227 0o 207 o0204 0 0212.0171 0172 00200 00206 00205 00176,0155 00183 0181 o0188 o 0918 0176 *00227 o 0216 o0214,0190 00183 00177 00203.0184 0 0181 o0163 o 0147 o 0139 I 027505 026692 025903 0 25138 024395 023674 22974 022295 021636 020997 20376,19774 10180,18623 018072 017538 17020 016517 016029,15555.15095.14649 o 14216 013796 1l3388.12992,12609 1l2236,11874 11523 011183.10852.10532 o10220 I 02609 02539 02461 2375 2258 o2195 0 2070 02023 o 1960 1898 01867 01805 1719 o1656 o1602 01578 01547 01469 o 1422 1367,1312 01289.1195 01164 01125,1109,1078 01047 o0984 00969 o0937 o0922 o0906 00883 06 Pe

-1 8 - TABLE IIl (con't) C 2(t) JEj Palm simulation. 0l14 0 099l8.0852 0l5 8 0 9 6 2 5.080 5.0161.0934l 00773.0l48.09065 p 0758 FO'OT' 'N`0T' REFERENCE l 1 Takacs, pp 174-188 20 Riordan, ppo, 37-38 3. Khintchine, pp. 82-89 4e Khintchine, pp. 89-95 5. Khintchine, pp, 11-12 6o Khintchine, pp 44-48 31B'ILI O'GRAPHY 2.. Khintchine, A, Y, Mathemati~cal' Method's, '.in the Theory of Qu~eueing No. 7 in Griffin's Statistical Monographs Courses, Haffner Publi11shing Company, New York, l19'6 0 2o Riordan, J., Stochasti'c' 'S'er~v~i"c'e Sy~s'tems, John Wiley and Sons, Inc. New York, 1962. 3, Siegel,. S., Nonparametric, Statis'tic's For The Behavioral Sciences, McGraw-H1ill Bo Company, Inco, 1956. I 4. Takacs, L,, Introduction 'to 'the' TheorX of Queues, Oxford University Press, New York — 1962

THE IMPACT OF COMPUTING SYSTEMS AND SIMULATION ON TOP-LEVEL MANAGEMENT DECISION PROCESSES By Jo Bo Neuhardt (I) Introduction Originally, this paper was to have been a study of the impact of the 1975 computer system on administration control systems, with special emphasis on multivariate sequential samplingo As it became apparent that the latter could never be practical without computers, a simple control system was modelledo One approach to optimization of the system would have been to set partial derivatives equal to zero, and search for minimization of expected costso This analytical approach was not taken, but instead the expected cost model was explored on a digital computer0 The relative ease with which the pseudo-optimum conditions became apparent was rather startling (as opposed to the straight analytical approach)0 The idea of replacing analytical studies with simulation is certainly not new0 Many authors, including G. Morgenthaler (Refe 2), note that simulation is one possible alternative when analytical models become unwieldy0 The basis direction of this paper then changed toward answering. What types of simulation languages and computer systems would increase the use of such tools by top management directly? Would this direct use partially solve the problems of insufficient support of top management in 00 Ro studies? (II) Past Problems in Achieving Results from Operations Research StudiesOne Partial Answera It has been written that some of the reasons that operations research studies fail to materialize into significant results include.(1) Inability of the OoRo team members to obtain clear statements of the problems to be solved, leading eventually to the study of the wrong variables, (2) Less than full indorsement of top management due to poor communications, or simply to management change0 In addition, future Operations Research efforts may falter in many organizations simply because there are not enough specialists in this area to go aroundo One suggestion seems obvious: give top management a tool which it can use directly; a tool which gives the ability to deal with complex situations, arrives at answers relatively quickly, and requires no extensive background in refined Operations Research techniques to use0

-20 - (III) Future Computing Systems-Present Simulation Language No attempt will be made to extrapolate speeds, memory sizes, etco 9 of future generation computerso It is merely noted that the future management simulation language would probably require the following type of computing system' (a) Parallel processing, to insure access of perhaps several management inquiries in addition to fulfilling lower priority daily data processing requirements (b) input devices located- near the inquirer to facilitate processing, (c) high processing speeds relative to in-out speeds (characteristicly scientific rather than commercial which stresses mass in-out data processing) for large scale simulationo These elements represent a minimum consideration, and are unfortunately geared to present state-of-the-art computing techniqueso The only system simulation language known to the writer is the "General Purpose Systems Simulation Program", written by Go Gordono Time did not permit becoming operationally acquainted with this language, but it is interesting that Mro Gordon, in discussing the program's application, states "the program involves compromises and it seldom meets exactly the requirements of the userso" This would undoubtedly be true of any general purpose program, but would not deter an avid operations "researcher" in its use However, difficulty in the use might discourage top management in direct utilization of the program, (if the reader has ever tried to operate a program by simply following directions in a general program write-up, imagine a company president being given such an item for immediate use)o The answer lies partially in specific rather than general programs, written possibly by company personnel for use by that company s top management, rather than a general program written by a computer organization for all its userso The use of such specific programs might only require a basic knowledge in probability theory, descriptive statistics and possibly inferential statisticso A specific problem is now consideredo (IV) Example of Problem, Suggested Extensions (A) Problem Statement (Figure 1) Suppose "na" units of a given -product are sold each period, and this product is under continual use after it is soldo Let P.. be the probability that any product sold in the "ith" period will fail in the,jth,, period of useo For simplicity, it is assumed that Pij is not dependent on i, the period of saleso It is assumed that the failures are independent in the statistical sense o Upon failing, this fact is reported to

FIGURE 1 FLOW DIAGRAM OF WARRANTY PROBLEM FOR H0 TRUE (ACCEPTABLE P, FAILURE PROBABILITY PER PERIOD): SALES (n/PERIOD) FAILURES - (COST, 1 UNIT.-. ---- PER FAILURE) T1 REPORT LAG DATA PROCESSING COST, D UNITS PER PERIOD I I SUCCESS FUL REDESIGN Hi TRUE (UNACCEPTABLE p + 6 FAILURE PROBABILITY): SALES 1/. J EXPECTED FAILURE COST PER PERIOD = np EXPECTED FAILURE COST PER PERIOD BEFORE REDESIGN ' n(p+6)

data processing and analysis, with a — 1 period lago It is assumed that all failures occuring in a period have the same lag time in data processingo The data processing and analysis section tests the following hypothesis, H0, with the associated alternate, H1, upon receipt of failure data: ^ H0: Pj = P H1: pj = p +6 (6>0 ) where p is a tolerable failure probability, and p + 6 is considered excessive. Let a, 8 be the associated type I, II errors, respectively, of the testo It is assumed that sales, n, is constant from period to period, If H0 is accepted, data processing continues to monitor failures, performing independent tests from period to periodo If H0 is rejected, it is assumed that an engineering redesign is necessaryo It is further assumed that the probability that engineering redesign will result in success (with the new failure probability, p) in one period is PR, and this probability is constant from period to period while redesign efforts are in progress (a most unrealistic assumption)o It is assumed that PR is fixed whether H0 is true or noto Let: D = cost of data processing per period, C = cost of engineering redesign per period, 1 = cost of one product failingo Figure 1 is a flow diagram of the possible states under H0 and H1, and transition probabilities are notedo For instance, under H1, the probability of remaining 'in state "A", data processing, upon receipt of failure data is 0, the probability of accepting a false hypothesis0 (B) Analytical Model of Expected Costs Leto: = expected number of periods in making the transition from state A to BoT=X = + ' = E ack+l)(l-a) k+ ) (m+l) (lpmp) k=0 m=0 R PR = l/a + 1/pR For H0 true: E0 = Expected Cost per period = D + 1/T (C/PR T For H1 trues E1 = 1/T[DT + C/PR + n6Z j] = D+C + n6 (T+l) 1 1 jR =l pT -- Further assumptions on cost relations: -X D ax D -X C B e a= e a = e, ( AS $,X Constants) $'-PR = 'ap

This is the assumed relationship of data processing costs, D, and the errors a, B, while larger expenditures in redesign per period, C, increases the chances of successful redesign, The above cost assumptions result in the following expected cost functions: E0 eD --- l [ Ile P 2 E _ D+ n S(T+l) Where: T=Tj-l-e + [l-ePJ It is desired to minimize the expected cost, E, where: E = E0 (probability that H0 is true) + E1 (probability that H1 is true) Actually, it was found that E0 and E1 differed considerably, and for practical purposes E1 was the variable to concentrate ono (C) Computer Solution After spending some time studying the analytical expression for expected cost, and contemplating that model for more complicated models, it was decided to analyze the model on a digital computero A "one variable at-a-time" method to seek an optimum was usedo In a matter of two man hours and $20 computer costs, relationships of the variables seemed evident with respect to cost, and a "flat" region of expected cost was apparent (Figure 2)o The computer program, written in basic machine language, was simple, yet the relative ease with which the expected cost region was studied seemed remarkable to the writero Several items were of immediate interest in the computer runs (Figure 2)o A relatively constant expected cost region existed over rather considerable ranges in expenditures, C and D. (Figure 2)o It is far better to overspend rather than underspend, due to the slope of E1 above and below the apparent optimum, It is noted that data processing and analysis costs are about 6 to 1 relative to redesign costs D, in the area of optimum Elo One other run was made, increasing the time lag to data processingo This quantity seemed rather insignificant relative to C and D expenditureso (D) Remarks Many of the assumptions made, point to the impracticality of this specific model0 The practical aspect is the inexpensive study via computer runs, which might have implications in more complex modelso An extremely valuable piece of information would be obtained if the expected cost curves were relatively flat in even complex modelso

)6 )0 EXPECTED COST UNDER H0, 100 UNITS (A) 4:r U1 ~~.~,.~......,.-......."... c ~.'n.. ~ \...1 \. S~ ~ \.-^ ~ g --—................ '~ \. o ~ C \ I V 00. _ _ _ _ _. -_I r 'l ' \ - ' ': '.:. ' ' '...'Z \ '...' *" ".... ' I " ' 'i / \.. -I _ _ k\ _ _...... *..-......... '....... o 4 0 1._,,__......._. _................... --- —--------------------- _I _.. I -. I. 0 ~ 0 (J* (

Practical extensions of this model might include the probability of failure changing with time, several products tested simultaneously with a restriction on redesign expenditure (above and below), sequential and multivariate sequential testing of failure rates, and inclusion of more than one possibility of product improvement (production, material etc )o (V) Problem Extension Through Simulation Language When a special purpose simulation language is considered to enable the study of the warranty problem with most of the elements included, and the simulation is mere parameter study, top management has not played a part in model constructiono For instance, with reference to the warrantcy problem as stated above, a simulation program could be written which would select failures randomly, and with given alpha, beta and PR values, simulate the problem and log costs per periodO The executive could study costs as the expenditures and even the functional relationships of errors with expenditures were changed0 However, in this role, the executive is not utilizing his experience in fundamental relationships of certain variables or, as previously stated, he is not playing an active role in the construction of the model, How, then, can this role be made easier, so that it does not consume a prohibitive amount of the executive's time? A general purpose simulator is probhl.v too complicated and unwieldy to use,9 while a specific simulator relegates the executive to studying parameter effects in a given modelo It is suggested that a compromise might exist in a language written specifically for company executives which would be flexible enough to allow the executive the study of many problems by constructing his own simulation models, yet operationally simpleo This task is obviously a formidable one, and the following represents a first attempt Given the four types of activities: (A) Random function generator; For random variables xl,x2soooooX and associated distribution functions Fl,F2,Ioooo Fn, generate A A sample Fl,F2oo e oFn, possibly in independent periods in time, with associated costs C(F1)9, ooo C(Fn)o (B) Storage Activity; Ability to store quantities for time Trat cost C(T) o (C) Decision Activity; (D) Action activity; Function, which hopefully affects the Fi, with associated costs per periodo Transition probabilities from activity are needed, which may be fixed, or functions of costs, or expenditures in specific activities o

-26 With these building blocks, an extension of the warranty problem is indicated in figure 3e The random variable is the failure probability at time t, possibly multivariate, with associated cost to the company, This is followed by a time lag and then to a decision activity which tests the typothesis that the failure level is below some preassigned amount. With probabilities p00 or p.01 the problem is considered not significant or it warrants further analysis, respectivelyo Under further analysis, the decision is made to refer the problem to one or more action activities, which in turn have costs associated with them, and certain probabilities of achieving results0 It is conceivable that this model could be read automatically in its flow diagram form, by a computer^ The problems facing an executive might involve questioned elimination of the decision process for instance, and submit the problem to all action groups, or it might be desired to investigate the effects of spending more money in decreasing the time lag of failure reporting~ Perhaps raw data could be fed to the action groups, and allow them to perform their own analyses. These are all questions that involve more than parameter study, and questions of this type could lead to basic model changes quickly and efficiently by the executiveo It is hoped that a similar language could be applied to, say, a production control problem or similar inventory and distribution systemso The above suggestions concerning a simulation language certainly in no way exhaust possibilities, but the complex flow diagram resulting from just four elements might indicate that further language complication would render the approach useless as an active tool for top managemento Nothing has been said about data displayo Experience has shown that graphic outputs are invaluable as aids in rapid digestion of gross effectso Provision should be made for such displays to the executiveo (VI) Summary As a result of this investigation, it appears more evident to the writer that computer simulation should play a bigger role in future management decision processes0 It is suggested that the effectiveness of this approach to top level management will depend on how active a role the executive plays in the model construction, which in turn will depend greatly on how much effort is demanded in such a tasko It would appear that a general simulation program would demand too much time for direct use in many situations, while a specific program might not be flexible enough to handle the variety of problems facing the executiveo An attempt to consider elements of a compromise language resulted in only four building blocks, but the flow diagram model was still quite unwieldy,, It is evident that the task of writing a flexible yet easily manipulated language is not a small one, but it would seem necessary if the benefits in allowing top management to play active roles in simulation model construction are to be realized0

FIGURE 3 = RANDOM FUNCTION GENERATOR = DECISION ACTIVITY L~II cIIID= ACTION = STORAGE WARRANTY PROBLEM A0 p=J~ P0 0 N /I 4, p12 1 A 2 P30 CONSTANTS: F(t),9 Pi5 s COSTSI DECISI-ON RULE FOR HYPOTHESIS

RE FE REN CE S (1) G. Gordon, General Purpos Syste ms Simulator, IBM Publication,, (2) Re Ackoff Ced.) Progre's's in' Oper~ations Research, John Wiley and Sons, 1961. 1-W! — "m-m

Bibliogra hy on Integer Linear Programming Arnoldo Hax 1o Balinsky, Ho Lo, "Notes on Integer Linear Programming o Foundations and Tools for Operations Research'an the Management Sciences The University of Michigan~ Summer 19620 This paper represents, as far as our knowledge is concerned, the only attempt made up to now to provide a general discussion of all the methods available in the field of integer linear programmingo Gomory's work is analyzed in detail a list of uses of integer programming is given, and the necessary background and notation concerning linear programming and the simplex method is presentedo We strongly recommend this paper for anybody interested in gaining a rapid and general insight in the field0 -2o Balinsky, Ho Lo, "Fixed Cost Transportation Problem" Naval Research Logistic Quarterly oVolo 8 (1961).i ppo 41lh54 This paper formulates a, fixed-cost transportation problem as an integer program, describes some of its special properties and suggests an approximate method of solutiono Examples are given to demonstrate the approximation technique 3, Berge, Co, "The Theory.of Grah"o John Wiley and Sons, 1962o This book gives a general survey of the theory of graphs and its applicationso It provides an analysis of p-coloring map problem in terms of integer linear programmingo (ppo 27-34) 4o Charnes, Ao and Wo Wo Cooper 9Management Models and Industrial Applications of Linear Programming (2 volumes), John Wiley and Sons, 1961 These volumes illustrate all aspects of underlying theory of linear programming with concrete numerical examples accompanied by explanationso In volume2, ppo 695-712, a discussion of Gomory s algorithms for Integer and Mixed Integer programming problems is giveno The methods are illustrated by examples, nevertheless the presentation is far from complete 5 0 Charnes, Ao and Co Eo Lenke, Optimization of Non-Linear Separables Convex Functionals" oNaval Research Quarterly, Vol0o 1, N4 (195), ppo 3OiZsr2o Programming problems may arise in which the variables

are subjected to linear equations and inequalities9 but the objective function may not be a linear function of the variableo This paper shows how the methods of linear programming may be extended to cover any objective function which is the sum of convex functions of each of the variablesG The technique consists of constructing a large linear program whose solution yields the solution to a polygonal approximation of the convex orogramming problemo An efficient computational algorithm for solving the auxiliary linear program is also presentedo 60 Dantzig, Go Bo I "Discrete -Variable Extremum Problems"o JOoRoSA 0o 1957), p, 266O-2ROSOA This paper presents an outline of the use of linear programming methods for the solution of discrete variable extremum problemso Three types of these problems are dis= cussed, a) the assignment problem, b) the problem of the shortest route in a network c) the knapsack problemO Certain techniques on solving these problems are provided by the author, although no foolproof technique is offered, and no guarantee is given that they will work in all caseso Nevertheless the paper is interesting primarily because it brings a good discussion of several applications of integer linear programming to certain classes of problems that are combinatorial in nature and easy to formulateO 7 Dantzig, Go Bo "Note on Solving Linear Programs in Integers Naval Research Logistic Quarterly0o'o 0 9 9 pp75 76 0 The paper considers the method presented by Gomory (ref 0 13) for solving linear program in integerso Gomory showed how to add linear inequality constraints to a linear programming problem automatically in such a way that the extreme points of the resulting convex contain only integral solutions in the neighborhood of the minimum0o In this paper an alternative method is given for generating these additional contraintso Dantzigts idea is based on the following theorem~ If a linear programming problem in variables xlx200oooo0xn has a basic feasible solution for basic variables X1,x2000ooxm say, which is inadmissible for any reason, then the partial sum condition xm+xm++ 000 OOxn > 1 is satisfied for all admissible solutions with integral values and not the basic solution In general suppose the convex of solutions in the n-dimensional space of lx2 0 oooooXn is defined by K linear inequalities o j=n o(X) = oo Xo > no i=l 2%ooooK 1 j~l 13 -- I

=31 - where noj and ni are positive and negative integerso An extreme point of the convex would be defined by the intersection of some n of the hyperplanes no(x) =no for i=i i i000 1 12'oo no If the extreme point is inadmissible for any reasons then at least one of the conditions w7o(x))no must be violated for an admissible integral solution, hence for at least one 1i2-11 9o 0 9in ri.(x)>n.+ 1 because n o and no are integers and therefore Z or(X) > 1+ no i 1 i,i2 oin i 0 is a linear inequality not satisfied by the extreme point but satisfied by all admissible integral solutionso Gomory and Hoffman (refo '19) and Balinsky (ref 0 1) have shown that this is a deficient algorithm which cannot obtain the optimal integer solution unde4 certain circumstanceso The reason for us to present Dantzig s idea is due to the fact that it represents a new approach to the problem9 and it is considered in almost all the literature in the fieldo 80 Dantzig, Go Bo, "On the Signifiance of Solving Linear Programming Problems witF some Integr ariaes conometrica o o 8 (1960)t "pp 3044o Keeping in mind Gomory s methods for solving linear programs involving integer-valued variables 9 Dantzig reviews and classifies problems that can be reduced to this class and thereby solvedo After considering the general principles of the cutting plane method 9 the author analyzes problems involving multiple dichotomies and k-fold alternatives which include problems with discrete variables nonlinear seperable minimizing functions9 conditional constraints9 global minimum of general concave functions and combinatorial problems such as the fixed charge problem9 traveling salesman problem orthogonal latin square problem9 and map coloring problemo The paper gives one of the most complete discussions on uses of integer programmingo 9 Dantzig, Go Bo, "Solution of a Large-Scale Traveling-Salesman Problem"o (et alo Fulkerson R- and So Johnson) J.OORoS.A. Vol. 2 (1954) pp, 393-410o The paper gives a complete analysis of the traveling salesman problem, a classic one in the fieldo The authors present some examples and the way in which it is possible to make a mathematical statement of the problem putting it into a linear programming formo An estimation procedure for solving the problem is consideredo It is shown that a certain tour of 49 cities, one in each of the 48 states and Washington, Do CO 0 has the shortest road distanceo In connection with integer programming, the paper is important because the cutting plane approach was proposed in this paper for the first time0

10o Dorn, Wo S9o "Non-Linear Programming0 A Survey" RC 707o IBM Research entero June 2 2 Some of the more recent theoretical and computational developments in non-linear programming are surveyedo The notion of Lagrange multipliers and duality are discussed together with applications of these ideas to scientific and business problemso Moreover, several algorithms for solving quadrate programming problems are reviewedo Explicit rules are-given for two of these algorithms, and a simple example is solved by both methodso A large step gradient method for the solution of convex programs is given and the all-integer integer programming Gomory s algorithm is describedo Simple examples are solved using both of these techniqueso Linear fractional programming is also discussed brieflyo 11o Eisemann, Ko, Management Scienceso Volo 3 (1957), ppo 279-284 "The Trim Problem" A problem of primary significance to a variety of industries is the suppression of trim losses in cutting rolls of paper, textiles cellophane, metallic foil, or other material,9 for the execution of business orderso The trim problem then consists in fitting orders to rolls and machines in such a way as to reduce trim losses to an absolute minimumo The authors illustrate the general treatment of such a problem by a numerical exampleo The problemof course, falls into the category of integer linear programmingo 12 Gilmore, Po Co and Ro E.o GCmory, "A Linear Programming Approach to the Cutting Stock Problem" Pr Ro7R-A" Vol- 9o Dec. 1961 The cutting-stock problem is the problem of filling an order at minimum cost for specified quanitity of material to be cut from given stock lengths of given costo When expressed as an integer programming problem the large number of variables involved generally makes computation infeasibleo This same difficulty persists when only an approximate solution is being sought by linear programming In this paper) a technique is described for overcoming the difficulty in the linear programming formulation of the problemo The technique enables one to compute with a matrix which has no more columns than it has rowso 13 Gomory, Ro E o "An Algorithm for Integer Solutions to Linear Programs"0 Princeton-IBM0 Mathematics Research Pro t Tecnica Report N~lo Novo 17, 19580 This report describes a method, based on Go Bo Dantzig's simplex algorithm, for solving linear programming problems in integero The paper is, perhaps, the most important one written in the field of integer programmingo '~

-33 - The paper is divided into ten sections A general description of the method is given in section lo In section 2 the main class of inequalities used in the method is derived and shown to form a groupO Section 3 gives a geometrical interpretation of the inequalitieso In section 4 some properties of the inequality group are derivedo Section 5 discusses briefly, ways of choosing particularly effective inequalities In section 6 a variant of the basic inequalities is discussedo Section 7 contains a description of the lexicographical dual simplex method used in the finiteness proofso Section 8 gives two versions of the method and shows that they obtain the integer answer in a finite number of stepso Section 9 contains miscellaneous comments including remarks on possible extensions, programming experience, etCo Section 10 contains a summary of the procedure and small worked out problems illustrating some of the results of the preceding sectionso 14 Gomory, Ro Eo, "Outlilne of an Algorlthm for Integer Solutions to Linear P rams" Bulletin of the American Mathematical Society,, Vo 64, (1958), ppo 275-2780 This article is a short presentation of refo 13o Here Gomory only describes the algorithm, without going into deep theoretical considerationso 15o Gomory, Ro Eo "Solving Linear Programming Problems in Integers 0 Proceedings of Symposia in Applied Mathematicso Vol0 X0 American Mathematical Societyo (1960)9 ppo 211-2160 Same as in refo 14, this article gives a short presentation of refo 130 An example is also presentedo The paper offers a good analysis of Gomory~s algorithm for those who do not like to go into all the mathematical background of the methodo 16 Gomory, Ro Eo, "An Algorithm for the Mixed Integer Problem" RM-2597 Rand Corporationo July.7 196o0 An algorithm is given for the numerical solution of the "mixed integer" linear programming problem, the problem of maximizing a linear form in finitely many variables constrained both by linear equalities and the requirement that a proper subset of variables assume only integral valueso The algorithm is an extension of the cutting plane technique for the solution of the "pure integer" problem, given in refo 13o 17o Gomory, Ro Eo "All -nteger Integer Programming A.lgorithmllo RC 198 IMB Research Centero Jano 29, i 96 6 The purpose of this paper is to describe a new method of integer programming which differs from its predecessors in two main points It is an all-integer method, that is, if the coefficients in the original matrix are integers all coefficients remain integer during the whole calculationo

It is a uniform procedure closely resembling the ordinary dual simplex method with the difference that the pivot element is always a-lo The cycle of maximizing by adding an inequality, etCo characteristic of refo 12 has been eliminated 18 Gomory, Ro E and Jo Wo Banmol, "Integer Programming and Pricing o Econometricao Volo 28 (1960) pp 52 550o In this article Gomory's method of solution of integer linear programming problems (based on refo 13 and refo 14) is described briefly, with an example of the method of solutiono The bulk of the paper is devoted to a discussion of the dual prices and their relationship to the marginal yields of scarce indivisible resources and their efficient allocationo The article also gives a geometrical interpretation of the integer programming algorithm, and explains the dual simplex calculations necessary for the applications of Gomory's methodo 19 o Gomory, Ro Eo and Ao J0 Hoffman, "On the Convergsnce of an IntegerProgramming Process RC-650 IBM Research Center Mar 3 192 The purpose of this paper is to analyze the finiteness of a procedure for integer programming described by Go B o Dantzig in refo 7 which left the finitness question openo The result given here shows that the process will not be finite or even converge to the optimal integer answer x~ unless certain necessary conditions are satisfiedo In particular, the procedure will not be finite unless xo already lies on at least nl1 of the faces of the polynedron cut out by the inequalities of the linear programming problemo 20o Land$, Ao Ho and Ao Go Doig, "An Automatic Method of Solving Discrete Programming Problems", Econometrica VOTEto 28 (1960) ppo4971=520o This paper presents a simple numerical algorithm for the solution of programming problems in which some or all of the variables can take only discrete valueso The algorithm requires no special technique beyond those used in ordinary linear programming, and lends itself to automatic computingo Its use is illustrated on two numerical exampleso The algorithm was completed by the authors at the same time that Gomory published his first paper (refo 14)o It had the advantage that the method could work in the mixed case (ioeo in which not all the variables are required to be discrete)o Further work made by Gomory (refo 16), also solved this problem in a more efficient wayo 210 Manne, Alan So, "On the Job=Shop Scheduling Problem"' JoO0oRSoAo VOlq 8 (1960), o 2l2 The article is a proposal for the application of discrete linear programming to the typical job shop scheduling problem, one that involves both sequencing

restriction and also noninterference constraints for individual pieces of equipmento Thus far no attempt has been made to establish the computational feasibility of the approach- in the case of large-scale realistic problemso This formulation seems, however, to involve considerably fewer variables than two other proposals~ a) Eo Ho Bowman "The Schedule-Sequencing Problem", JO0 RoS OA Volo 17 (1960) ppo 621-624, b) Ho Wagner, "An Integer Linear-Programming Model for Machine Scheduling"0 Naval Research Logistic Quarterlyo June 1959o 220 Markowitz. Ho Mo, and Ao So Manne, "On the Solution of Discrete Programming Problems" o Econometrica, Volo 25 - (1957)" ppo 84 -l10o This paper considers optimization problems in which some or all variables must take on integral valueso The authors do not present an automatic algorithm for solving such problemso Rather they present a general approach susceptible to individual variations, depending upon the problem and the judgment of the user0 -Two moderate size and interesting examples are presented to illustrate the methodO The paper is often cited as having suggested the general line of attack employed by Gomoryo 23 Miller, C. Eo Ao W0 Tucker and Ro Ao Zemlin, "Integer Programming Formulation of Traveling Salesman Problems0'0 Journalof the Association for Computing Machineryo Vol0 7 (1960 ), ppo 326-329o The paper provides yet another example of the versatility of integer programming as a mathematical modeling device by representing a generalization of the well-known "Traveling Salesman Problem" in integer programming termso After formulating the problem in analytical form, the authors give the results of five machine experimentso The solution procedure used was the All-Integer Algorithm of Ro E o Gomoryo The answers obtained were sufficiently irregular in their behaviour to cast doubt on the heuristic value of machine experiments with the modelo It seems hopeful that more efficient programming procedures now under development will yield a satisfactory algorithmic solution to the traveling salesman problemo In any case, the models served to illustrate how problems of this sort may be succinctly formulated in integer programming termso 24 Thrall, Ro Mo, "Linear Algebra with Applications to Linear Programming, Game Theoryand other Models" Foundations and Tools for Operations Research an~d The Management Scienceso The University of Michigan, Summer, 1962o This set of notes provides a general analysis of linear programming and its applicationso The theory underlying the several linear programming techniques is very well covered, and many examples are giveno

25o Vadja, So "Mathematical Programming"~ Addison-Wesley Publishing Company, Inco chapter iscrete Linear Programming" o ppo 191-205o The chapter starts with a discussion of certain classical applications of integer linear programming, such as the traveling salesman problem, the allocation problem, the introduction of logical relations and the fixed charge problem0 The problems are formulated in analytical form and some examples are giveno As far as the formulation of algorithms to solve the integer linear programming- problem, the author presents two approacheso First, the method proposed by Ro Eo Gomory (refo 14), and, second, the method presented by AoH.o Land and A. Doig (ref0 20) for the mixed case. Examples are given to illustrate the use of algorithmso Although the general discussion is far from being complete, and no attempt is made to provide the theoretical background of the methods proposed, we consider that the chapter gives a nice introduction to the topic, for those who want to get a general view of the subject.