NATIONAL BUREAU OF STANDARDS REPORT

2501

COMPUTATIONAL EXPERIENCE IN SOLVING LINEAR PROGRAMS

by

A. Hoffman, M. Mannos, Do Sokolowsky and No Wiegmann

<NBS>

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
U. S. DEPARTMENT OF COMMERCE.

Sinclair Weeks, Secretary

NATIONAL BUREAU OF STANDARDS

A. V. Astin, Director THE NATIONAL BUREAU OF STANDARDS

The scope of activities of the National Bureau of Standards is suggested in the following listing of

the divisions and sections engagt i in technical work. In general, each section is engaged in specialized research, development, and engineering in the field indicated by its title. A brief description

of the activities, and of the resultant reports and publications, appears on the inside of the back

cover of this report.

Electricity. Resistance Measurements. Inductance and Capacitance. Electrical Instruments. Magnetic Measurements. Applied Electricity. Electrochemistry.

Optics and Metrology. Photometry and Colorimetry. Optical Instruments. Photographic

Technology. Length. Gage.

Heat and Power. Temperature Measurements. Thermodynamics. Cryogenics. Engines and

Lubrication. Engine Fuels. Cryogenic Engineering.

Atomic and Radiation Physics. Spectroscopy. Radiometry. Mass Spectrometry. Solid State

Physics. Electron Physics. Atomic Physics. Neutron Measurements. Infrared Spectroscopy.

Nuclear Physics. Radioactivity. X-Rays. Betatron. Nucleonic Instrumentation. Radiological Equipment. Atomic Energy Commission Instruments Branch.

Chemistry. Organic Coatings. Surface Cherpistry. Organic Chemistry. Analytical Chemistry.

Inorganic Chemistry. Electrodeposition. Gas Chemistry. Physical Chemistry. Thermochemistry. Spectrochemistry. Pure Substances.

Mechanics. Sound. Mechanical Instruments. Aerodynamics. Engineering Mechanics. Hydraulics. Mass. Capacity, Density, and Fluid Meters. Organic and Fibrous Materials. Rubber. Textiles. Paper. Leather. Testing and Specifications. Polymer Structure. Organic Plastics. Dental Research.

Metallurgy. Thermal Metallurgy. Chemical Metallurgy. Mechanical Metallurgy. Corrosion.

Mineral Products. Porcelain and Pottery. Glass. Refractories. Enameled Metals. Concreting Materials. Constitution and Microstructure. Chemistry of Mineral Products.

Building Technology. Structural Engineering. Fire Protection. Heating and Air Conditioning. Floor, Roof, and Wall Coverings. Codes and Specifications.

Applied Mathematics. Numerical Analysis. Computation. Statistical Engineering. Machine

Development.

Electronics. Engineering Electronics. Electron Tubes. Electronic Computers. Electronic

Instrumentation.

Radio Propagation. Upper Atmosphere Research. Ionospheric Research. Regular Propagation Services. Frequency Utilization Research. Tropospheric Propagation Research. High

Frequency Standards. Microwave Standards.

Ordnance Development. These three divisions are engaged in a broad program of research

Electromechanical Ordnance, and development in advanced ordnance. Activities include

Ordnance Electronics. basic and applied research, engineering, pilot production, field testing, and evaluation of a wide variety of ordnance materiel. Special skills and facilities of other

NBS divisions also contribute to this program. The activity is sponsored by the Department of

Defense.

Missile Development. Missile research and development: engineering, dynamics, intelligence,

instrumentation, evaluation. Combustion in jet engines. These activities are sponsored by the

Department of Defense. • Office of Basic Instrumentation • Office of Weights and Measures.
NATIONAL BUREAU OF STANDARDS REPORT

NBS PROJECT NBS REPORT

1102-10-1104 May 1 5 ? 1953 2501

COMPUTATIONAL EXPERIENCE IN SOLVING LINEAR PROGRAMS*

by

A, Hoffman, Mo Mannos, Do Sokolowsky and No Wiegmann

National Bureau of Standards

*This work was supported (in part) by the Office of Scientific Research, l&AFo

The publication, reprinting,

unless permission isobtalnec 25.D.C, Such permission I:

cal ly prepared If that agen

Approved for public release by the

Director of the National Institute of

Standards and Technology (NIST) on October 9, 2015

Is prohibited

Washington

been speclfiIts own use,

COMPUTATIONAL EXPERIENCE IN SOLVING LINEAR PROGRAMS*

by

Ao Hoffman, M„ Mann os , Do Sokolowsky and No Wiegraann

National Bureau of Standards

Introduction

This paper is a discussion of three methods which have been

employed to solve problems in linear programming, and a comparison of results which have been yielded by their use on the Standards Eastern Automatic Computer (SEAC) at the National Bureau of

S tandards 0 A linear program is essentially a scheme to run an organization or effect a plan efficiently, i o e 0 , it is a technique of

management which serves to minimize costs, maximize returns or

achieve other ends of a similar nature,. To illustrate the kind of

"life situation*8 to which linear programming is applicable, and

the technique of formulating the circumstances mathematically,

let us examine a particular problem,, For this purpose, we choose

a simplification of the so-called **caterer problem** of W 0 Jacobs „ A caterer knows that in connection with the meals he has

arranged to serve during the next n days, he will need r j(> 0)

fresh napkins on the j-th day, j = 1,2, 0 oo,n 0 Laundering takes

This work was supported (in part) by the Office of Scientific

Research, USAF» The coding and operation of the methods was

performed by Ro Bryce, I„ Diehm, L„ Gainen, B„ Handy, Jr„,

Bo Heindish^ No Levine, Fo Meek, So Pollack, Ro Shepherd and

Oo Steiner 0
p days; that is, a soiled napkin

of the j-th day is returned in time to be used again, on the

(j+p)th day, Having no usable napkins on hand or in the laundry,

the caterer will meet his early needs by purchasing napkins at ja

cents each. Laundering costs b cents per napkin, How does he

arrange matters to meet his needs and minimize his outlays for

the n days?

Before expressing the caterer 8 ® problem algebraically, two

conventions of notation will be stated » The subscript j throughout has the range 1,2, 0 oo,n; every equation involving j is to

hold for the entire range ©f valuego Quantities with subscripts

outside this range are always zero.

Let Xj represent the napkins purchased for use on the j-th

day; the remaining requirements, if any, are supplied by laundered

naj

any other soiled napkins on hand, let y. be the number sent t<

J ie stock of soiled napkins left, Consequeni

the Tj napkins which have been used on that day plus

the laundry and s . J y- + s F

j

The stock of fresh napkins on hand on the j-th day must be

t least as great as the need. Thus

j j

(2)

j

E

i=1

X . +

1

1=1

v o > * i~p rr

r .i

i=1

The total cost to be minimized, subject to the constraints

(1) and (2) on the nonnegative variable x.,y. 5 s., is

J J J n

j=1

'a x. + b y . J <J
This is a mathematical formulation of the problem the caterer

wishes to solve.

3

If desired, the equation (1) can be changed into inequalities. For example, (1) is equivalent to the pair of inequalities

y

j

+ s

j - s j-i £ Ti -y

i ~ si + s j-i

^-r r

If we make this change, then it is clear that the problem just

described is, mathematically, a special case of the followings

Let A = be a given m x n matrix; b = (b^,...,b

m

) an 111 - dimensional vector, c = (c^,..*,c ) an n-dimensional vector.

For all vectors x = (x^,*..,x ) satisfying

(3) x

i =

0

and

(4)

a

1 1 X

1 + a1 2

x

2

+ • ° B+ a ln x

n =

b

1

a

21

X

1 + ... + ** a 2 n

b

2

o

‘ml

X

1 + + a x > b

ran n= m

(briefly, Ax ^ b)

.

minimize (c,x) = c.x.+.o.+c x„.

1 1 n n The foregoing is the mathematical statement of the general

linear programming problem. In geometric language, it is to

find a point on a convex polyhedron (the region satisfying (3)

and (*+)) at which a given linear form (c^ x^ + . .

«

+c

nx

n

) is a minimum.
The Computation Laboratory of the National Bureau o

f

Standards, with the sponsorship and close cooperation of the

Planning and Research Division of the Office of the Air Comptroller, U. S * Air Force, has been engaged in the task of discovering ane evaluating methods for computational attack on

this problem, and this paper is in a sense a progress report on

a part of this work (see also Orden [10]).

The three techniques that have received most attention so

far are (a) the MS implex” method, devised by George Dantzig,

(b) the Fictitious Play method of George Brown and (c) the

Relaxation Method of T« So Motzkin. Each will be described in

more detail in the next section, but for the present it is appropriate to remark that the simplex method is a finite algorithm

and the other two are infinite processes® Further, the other

two methods are designed to solve not the linear programming

problem per se but two related problems? fictitious play finds

a solution to a matrix game - i,e M a zero-sum 2-person game in

normalized form - and relaxation finds an x satisfying (*+) -

i e e., solves a system of linear inequalities. It is known,

however (see Gale, Kuhn and Tucker [ 6 ], Dantzig [*+], Orden [ 9 ] that the three problems (i) solving a linear program, (ii) solving a matrix game, (iii) solving a system of linear inequalities

are in general equivalent in that each of (i), (ii) and (iii)

can be so formulated that it becomes either of the other two.

For purposes of comparison, the following experiment was
undertaken. Several symmetric matrix games (i.e., games whose

matrices were skew-symmetric) were attacked by each method in

turn and the results studied with respect to the accuracy achieved

and the time required to obtain this accuracy. Many conjectures

about the relative merits of the three methods by various criteria could only be verified by actual trial. Apart from the

descriptions of the methods, the paper is concerned principally

with the results of the experiment, but some other aspects of the

comparison, revealed more strikingly by other computations, will

also be mentioned.

The games in question have as payoff matrices the submatrices

of order 5>6, 7*8,9)10 obtained from the following 10x10 array

by deleting the last five rows and columns, the last four rows

and columns, etc.

0 1 -2 -1 3 -2 -1 -4 1 -2

-1 0 -1 1 2 -2 1 1 -1 -1

2 1 0 ~3 1 1 3 -3 1 -1

1 -1 3 0 1 -1 4 2 -1 5

-3 -2 -1 -1 0 -1 -5 6 1 6

2 2 -1 1 1 0 -2 -1 -1 3

1 -1 -3 -4 5 2 0 2 1 -4

4 -1 3 -2 -6 1 -2 0 1 -1

-1 1 -1 1 -1 1 -1 -1 0 -5

2 1 1 -5 -6 -3 4 1 5 0

2. Description of the Methods

(a) The Simplex Method . The simplex method solves the problem: minimize

c lV"*+c

nxn

for all vectors x = ) satisfying
6

where A = (a. .) is an m x n matrix and b = (b^ ,.,.,bm

).

This differs slightly from the formulation of the general

linear programming problem in which Ax ]>. b, but the inequalities

can be made into equations by appending dummy nonnegative variables.

An algebraic description of the process* is given in Dantzig

[ 5 ] and Orden [ 9 ]» and will not be repeated here. While it is

not excessively complicated it is somewhat lengthy, and we merely

remark now that it very much resembles elimination methods for

solving equations. Even for those familiar with the algebra, however, (as well as for novices), the following geometric interpretation is illuminating. First, to state the problem in geometric

language; if A-.,..., A are the m-dimensional column vectors of

A, let A^ 1 , • . • ,A 1 be the (m+1 )-dimensional vectors obtained

f rom A^ , . .

.

,A

n by appending c

1 ,...,cq

respectively as the (m+1)th

coordinate. Let C be the cone in (m+1 )-space spanned by these

vectors. Let B be the line in (m+1 )-space consisting of all

points whose first m coordinates are b^,...,b

iQ

. The object of

the computation is to find the lowest point of B which is also

in C, i.e., the point of B whose (m+1)th coordinate is a minimum.

The computation proceeds in the following way; assume that

m of the vectors A^ ' , . . . ,A

n

1 , say A ’ , • • • »A./ are given which

*1

are linearly independent and have the property that the mdimensional cone D they span contains a point of B. (Such a set

^Interesting variations suggested by Charnes [33 and Wolfe [12]

have not yet been tested.
7

of vectors may have to be given initially by an artificial device

which we shall not describe here). Of all the remaining vectors

A^’, let us look at the subset of those which are on the side of

the hyperplane containing D that does not contain the positive

(m+1)th coordinate axis. These vectors are all "lower** than D.

Each of these vectors can be joined to the hyperplane containing

D by a line segment parallel to the (m+1)th coordinate axis. Let

A^ 8 be the vector with the property that this line segment has

maximal length - i.e., A^ 8 is the "lowest" of the low vectors.

Then A. 8 and a certain set of m-1 of the vectors A .

8 , . . . ,A .

8 1 V1 - vmhave the property that the m-dimensional cone they span contains

a point of B, and this point will be lower than the intersection

of D with B. We replace the discarded vector of the set

A^ Ay 8 with A. 8 and proceed. This replacement process is

i vm

1

an iteration in the simplex method) and clearly the computation

must stop after a finite number of iterations with the desired

lowest point of the intersection of C and B.

The symmetric games were formulated for the simplex method as follows

§

Let A = (a. .) be the n x n game matrix. We wish to find an

x = (x^,.o.,x ) such that

Ax <_ 0

Xi^O

= 1 This is equivalent to
8

(a^ + 1 ) x.j + (fi-j2 + 1) x

2+

n + w

n

1

x± > 0 (i = 1

w, >^0 (i = 1

n)

n);

maximize

(thus minimize -Xg-***-* ) which is suitable lor simplex computation. We omit the proof of the equivalence as well as the

justification for choosing this particular way of formulating

the game as a simplex computation, since both depend on technical

reasons irrelevant to the main purpose of the paper.

(b) Fictitious Play „

tional scheme that will solve symmetric games can be adapted to

the solution of linear programming problems. The fictitious play

method, devised by G. Brown [2] and proved valid by J. Robinson

the computation is simpler (particularly from the standpoint of

storage) if the game is symmetric. And since our primary interest is in linear programs rather than games per se, we have

confined our attention to the symmetric case.

If A = (a- •) is skew-symmetric, our object is to solve the

J system of linear inequalities

It is well known (see Dantzig [*+]), that a computa-

[11], is a procedure for solving an arbitrary matrix game, but
9

( 5)

a

11

X

1 + a 21 x2+000+an1 % = 0

a

1 2 X

1 + a 22 x

2

+0 ° 0+a n2 X

r i

0

X, 3 X o o 0^3 X ^ 0 Ini 2n 2 nn n =

subject to the conditions x. > 0 (i = 1 , 2 ,...,n),

n

i=1 x . = 1

The fictitious play method consists of forming two sequences

of n-dimensional vectors, V(0), V(1), V(2),..., and T(0), T(1),

T(2),..., with V(0) = T(0) = 0<> V(N) (N=1,2,...) is obtained

by adding the r-th row of A to V(N-1), where the r-th coordinate

of V(N-1) is the minimum of the coordinates of V(N-1 ) and of smallest index among all the coordinates equal to the minimum. The

smallest index criterion is used in order to be specific but is

in no way essential.* T(N) is the same as T(N-1) except for the

r-th coordinate which is larger by 1 . In effect, the j-th component T.(N) of T(N) represents the number of times the j-th row

of the matrix A has been selected by the above criterion in forming V(N). Hence, if V.(N) denotes the j-th component of V(N),

J* we have

V . (N) = a,, T,(N) + a~. T„(N)+ . . .+a„ . T.(N) =

J il 1 2 j 2 nj j

N

i=1

a. . T. (N) ij i

To (N)

Upon setting x^(N) = — this is equivalent to

V . (N) N

(6) ^

— a^

j

x,j (N) + 82

j

X

2

( N)+ o o .+

a

j

x^(N) — ^ a^jX^(N)

*This procedure is followed in the illustrative example on page

12 but not in the SEAC code.
10

Since T^ (N) >. 0, and T, (N) + T? (N)+ . . .+T

n (N) = N, it follows that

x.(N) >0 and x 1 (N) + x 0 (N)+ • • .+x„ (N) = 1. If the first player

follows the strategy (x^ (N) , XgCN) , » o • »x n (N) ) his expectation

is the least of the expressions (6), and except in the trivial

case that the first row of A consists of nonnegative elements

,

V. (N)

min — will be negative , which , by (6), implies that the inJ equalities (5) will not be satisfied.. It is however, the main

result of J, Robinson's paper that

rain V.(N)

lira i ^ = 0

N~^oo N

This implies (See Hoffman [7], McKinsey [8]), that the vector

x(N) = (x.,(N),...,x (N)) approaches the convex set of all solutions to (5) as N increases indefinitely, though it does not imply

(indeed, it is not true) that x(N) converges* Of course, if the

first player is willing to follow a strategy such that his expected loss is no greater than € , he may follow the strategy

V. (N)

x(N) , where min - ^ >_ - 6 . j N -

These considerations suggest that the speed of convergence

of the fictitious play method should be determined by deciding

how "long” it takes for the process to arrive at a vector x(N)

such that the corresponding expected loss is no greater than ^

for a given decreasing sequence of positive numbers & . At least two criteria are relevant in measuring ? boW^long”

it takes to attain an & $ the size of N and the time consumed on

the computer. Both are given in the table of results, A third
11

criterion is suggested by the manner in which the procedure was

codedo It is apparent from J e Robinson’s proof and readily verifiable by experience that as the computation proceeds the same

row vector of A will be added to V(N) for a large stretch of

successive values of No Hence, the code picks out, not only the

row to be added to V(N), say A , but decides how many times A

r is to be added to V(N) before some other row is added; i.e,

it determines a number S(N) such that

V (N+1 ) - V(N) o=V(N+S (N) ) - V ( N+S ( N ) - 1 ) = A

r but

V(N+S (N) + 1) - V(N + S (N)

A

The number S(N) is the least positive integer not less than

r?J

a XO r J

V r (N) - Vj(N)

rj

if Mb . is not an integer (i 0 e o S(N) = [ M .]) and S(N) =

J J [M_ .] + 1 if H. . is an integer 0 In the latter case ties

r ? J r 9 J resulting between the j-th and k-th components with k > j are

resolved in favor of the k-th componento

Then V(N+S(N)) = V(N) + S(N)*A

r

, T(N+S(N)) = T(N) + S(N)*6

r

, (where 6

p

is the r-th unit vector,,)

The foregoing computation and subsequent changes in V(N) and

T(N) are essentially computational ’’steps” in the SEAC code

and therefore the number of such steps it takes to attain a given £ is a third proper criterion by which to measure the

convergence rate of the process.

Before listing the experimental data and the conclusions,

let us illustrate j except for a slight modification, the preceding descriptions of the process by an example»
12

The modification consists of letting S(N)-[M .] if either M . r 9 J r 9 J is not an integer or is an integer with j<r and S (N)=[M„ .]+1

r » 3 if M .is an integer with j>r„

r, j

Let G be the payoff matrix

0 0 2 -1 -2100 0 0-12

1-200

which is the same as the illustrative matrix in J, Robinson's

papero The first component of V(0) guides the choice of the row

of G added to V(0), Hence the first row of G is added to V(0) in

order to obtain V(1)o In the next step the fourth component is

taken as the minimum and so the fourth row of G is added to V(1 )

yielding V(2), In the next five steps the second component is

the minimum and 5 times the second row of G is added to V(2),

giving V(7)« In the next two steps one observes that the third

component is the minimum and so adds 2 times the third row of G

to V(7) to get V(9)o It is the first, fourth, second and third

components in that order which give rise to the minimum component

Due to the simplicity of the payoff matrix which has but one negfi

tive element in each row the minimum component keeps passing

through the same cycle as above, For example, in the next cycle

the first component is a minimum 13 successive times, the fourth

component 2 times, the second component 28 times, and the third

component 2 times , That is, S (9) = 13? S (22) = 2, 5(24) = 28,

and S(52) = 2, Similarly, in the next cycle one may verify

that S (54) = 58, 5(112) = 2, 5 ( 1 1 4) = 1 1 8 , S (232) = 2 C It is

then observed that for any of the following cycles the first

component appears as a minimum 4 times as many plus 6 as it does

in the previous cycle. The second component follows this pattern
13

whereas, the third and fourth components appear as a minimum,

twice in each of the succeeding cycles» In the first cycle then,

the first component appears once as the minimum component and in

the n-th cycle (n 2 2) the first component appears as the minimum

in 13c 1*

11 ”2

+ 6(4n"3+1+n"lf+o 0 e +4+i ) = 1

3

A

n“' 2+2o I+n“2-2 = l5.4n“2

- 2 successive steps Q In the first cycle the second component

appears 5 times as the minimum component and in the n-th cycle

(n > 2) the second eomponent appears as a minimum in

28,4n “2+6(4n"3+4n"^+, , ,+4+1 ) = 28,4n “2+2,4n ”2-2 - 30 o 4

n“2-2

successive steps. The third component enters twice as the minimum component in each cycle; whereas, the fourth component is a minimum one time in the first cycle and 2 times in each cycle

thereafter. It is quite clear that x^(N) and xj+ (N)-^-0

as N—>oo. If one computes the x(N) for each N at the end of

each cycle, it is seen that x 1 = 1/3 and x

2 = 2/3® However, by

computing x(N) for various other sequence of N's it may be observed that x^ (N) and x

2

(N) come close to any value between 1/3

and 2/3 provided their sum is 1, While the sequencesof x^ (N)

and x

2

(N) oscillate as N —*-oo , one may pick out a subsequence

of the N 8 s such that the corresponding subsequence of the x(N) ! s converges to any given optimal strategy,

(c) Relaxation Method • There have been several proposed versions of the

relaxation method and what we call the relaxation method here

might more properly be termed the "furthest hyperplane” method.
The object of the computation is to 1 a point which satisfies a finite system of linear inequalities

n

"'S' a 4

• x • + b» 0 (i — 1,2,ooo,ra) Aj J -* —

j = 1 The set of points which satisfy one of these m inequalities is

called a half-space and the set of points which satisfy the

corresponding equation is called the bounding hyperplane of the

half-space,, A point satisfies the entire system of inequalities

(i„e 0 is a solution) if and only if it lies at the intersection

of the m half-spaces,,

The procedure is indue tive, producing an infinite sequence

of points x

0

,x

12

,x ,o„o)which converge to a solution (see Agmoe

[l])j provided one exists „ x^ is arbitrary,. Assuming we Slave

x

1 , (k = 0,1

,

2,000 x is obtained as follows^

k k+1 k

If x is a solution, x = x

k If x is not a solution, there are one or more of the given

half spaces which do not contain it„ Among the bounding hyperplanes of these half-spaces, let o»C be one at a maximum distance

k k from x and let p be the point of <* nearest x

1 „ Then

x

k+1 = xi<L + t(p-x k

) where 0 < t < 2„

Three values of t were tried, namely t = 3/4- (undershoot),

i t = 1 (normal -here x

w = p), and t = 3/2 (overshoot)

„

We now describe the process algebraically along with a summary of the machine procedure,. The code does not use the

algebraic formulation which would yield the fastest computational
15

procedure (the reader can easily concoct such a procedure using

T

the matrix AA ), for the naive method followed required less internal storage,,

n Let the set of inequalities be normalized, a. . =1,

n (i = 1,2,...,m). Let y^ = '>__J a^j x^ + b^, choose an initial

J=1-

set of values for x? x^ C0) ,...,x^nd obtain a corresponding

set of ys y.j

^ . ,y n ^

If all the y^ are nonnegative, the

(0)

x.

v y form a solution® If not choose the largest (in absolute

value.) of the negative y^^ , call this y^^ , and form new

t*a ( 0 ) kj values x. according to x.^ where 0 < t < 2,

y = x

J J J Substitute the x. ^ into the system and obtain a new system of

ys y

( 1 )

i

.

U) 90009 X

Continue in this way to form a sequence x^

(i)

(i)

n for i = 1 ,2 000 o The machine procedure has

been as follows? Given the m x n matrix A - (a..), the problem

J is scaled so that J max a° .j < 1, Each inequality is multiplied

_L|.

by 10 so that the b^ are properly scaled. This scaling is to

be kept in mind in interpreting the final results. Next conversion is made from the decimal to the binary system and the

system is normalized. The matrix A and the b^‘s are stored in

the machine,

in all the problem work

The initial choice is x^^ = 0 for i - 1,2,...,n

In order to measure convergence, it is reasonable to comfit)

pare the size of the negative y^ relative to k itself. In

this case the following procedure was adopted? an €. > 0 was

chosen and a solution was considered as obtained when the minimum
1

6

y^ > - 6 . The <= was made progressively smaller and, on the basis

of previous experience was taken successively as 2”

, 2 , 2

J

, —11 —12 —22

2 ? 2 ,...,2 ® The time required to satisfy a given 6 was

also noted in each instance.

The game problem was transformed into a pure inequality

problem in the following manners If the m x n game matrix is

A = (a. .), the expected payoff for player one 9 if he engages in a

^ n mixed strategy x^ ^x^ > • » <> ,x

r

, is given by M = min a ^j

x^9 where

^x. - 1, x. > Oo Since the game is symmetric, the value is

zero so that the problem reduces to solving

m

-Ax > 0, x >. 0 and x. = 1 , *

i=1 1

or to solving the (2m+2)x m system of inequalities

m \ m

-Ax >. 0 , x > 0,

^ x^ - 1 , - x^ >_ -1 .

3 » Numerical Results

(a) Simplex Method - Table I gives the answers obtained, the number

of iterations required and the time consumed on the machine by

the computation.
17

£*2 6x6 22k

1

8x8 2*1 10x10

X

1 0,00000 0,00000 0,00000 0,00000 0,12341 0,03690

x

2 0.59999 0,00000 0,00000 0,00000 0,00000 0,00000

x

3 0,19999 0,20000 0,19999 0,04761 0,00000 0,08487

x4 0,19999 0,20000 0,20000 0,26190 0,25949 0,22509

x

5

0,00000 0,00000 0,00000 0,00000 0,06012 0,10332

x

6 0,60000 0.59999 0,57142 0,02531 0.12915

x

7 0,00000 0,09523 0,03481 0,00000

x

8 0,02380 0,06645 0,00000

x

9 0.43037 0.39483

x

10 0.02582

No, of

item- 6

tions

5 6 7 11

A, Time

(mins) 10 8 si 9 12 15

Note that the number of iterations is about n for each of

these n x 2n linear programming problems. This is in accord with

our general experience using the simplex method on m x n problems

that a solution takes approximately m iterations unless the

artificial device mentioned in the description of the simplex

method given in 2(a) is needed. In that case it takes about 2n

iterations to reach a solution. These estimates are completely

heuristic, but they are based on over fifty simplex computations

of various sizes and are probably the right order of magnitude.

The success that the simplex method has enjoyed is based largely

on the fact that the number of iterations required has not been

larger.
18

(b) The Fictitious Play Method o For each of the problems many answers were printed as

different 6 *s were attained,.

Let us look in detail at the results of the 6x6 game, which

illustrate the typical properties of the convergence rates „ In

table II are given the approximate solutions x^(N) corresponding

to the various values of £ „ The step in going from V(N) to

V(N+S(N)) is called an S“Step 0 The time is counted from the

beginning of the computation excluding the time taken to print

out the answers 0

6 = 2"2

TABLE II

6 = 2~6

6 ~ 2

10

X*| “ OoOl 69491 525 x

i = 0o0002732987 X

1 = 0 o 0000013102

0

11

OJ X x

2

= 0 x

2

= 0

X

3 = 0o1016949152 x

3 = Ool 866630226 x3 = Ool 9903201 37

x^ = Ool 864406779 x4

= Oo19978l36lO X4

= Ool 99998951 8

x^ = 0 x

5 = 0 x5 = 0

x

6 = Oo6949l5l542 x

6 = 0.6132823175 x6 = Oc 6009677241

TIME = Os 02

S=steps = 7

N = 59

TIME = Os 12

S-steps = 52

N = 3659

TIME = 2 s 0

1 S-steps = 742

N = 763,234

e = 2

-11 6 = 2

' -12

x

1 = 0 0 0000003290

= 0

x^ = Ool 995141064

= 0 o 1 999997367

x 0 0000000824

%2 = 0

x

^ = 0o1997565760

= 0

x

6 = 0 o 6004858277

TIME = 3050“

S-steps = 1480

N = 3,039,349

x^ = Ool 999999340

x^ = 0

x

6 = Oo 6002434074

fmT~= 6s 40 — S-steps = 2956

N = 12,130,279
19

Observe that for £ sufficiently small the number of S-steps

required to "attain the £

" doubled as 6 was halved, while N

quadrupled,, This phenomenan held for all the games solved as

part of the experiment and for others not part of the experiment

that were solved by the Brown method

„

No arithmetic relationship between the computing time (required to attain a given £ ) and the size of the matrix could

be determinedo

(c) The Relaxation Method , For the same reasons as given above for the fictitious

play method, we present below (table III) the results of the

6x6 game obtained using the three methods of relaxation,,

(N - number of iterations „

)
20

TABLE III

—2

€ =2 Undershoot Normal Overshoot X 1 = Oo 125000 0.015152 -=0e034309 x 2 = 0 el 25000 0o015152 0.217439 x3 = 0 el 25000 0 0 242424 0.225306 xk = 0.1 25000 Oe 090909 0.262019 x 5 = 0.1 25000 0o090909 0.136145 x6 = 0 . 1 25000 0 0 1 66667 0.558348 N 2 3 5 T 0 §02 08 03 Tro

=2“6 Undershoot Normal Overshoot

x i = -o.oi4o57 Oo 000000 =0.014191 x 2 = 0.054008 0.043413 .=0.004277 x 3 = 0 o 21 71 43 0.210530 0.203763 x4 = 0 . 1 74677 0. 177211 0.203559 x 5 = 0.010341 -Oo 002738 0.029268 x 6 = o. 545075 0.546727 0.585016 N 50 33. 12 T 0 § 56 0§37 0§13 £ =2“ Undershoot Normal Overshoot X 1 = -0. 000697 -Oe 000 9 23 -0.000269 x 2 = 0.003456 0o002975 -0.000320 x 3 = Oe 201 573 0 0201360 0.198920 xk = Oe 198840 0.198293 0.200325 x 5 = ~0e 000877 Oo 000000 -0.000 288 x 6 = 0.596372 0.596994- 0.599880 N ' T9B 121 37 T 3s42 28 15 ' 0s4i
21

—1 1 € = 2 Undershoot Normal Overshoot X 1 = -0.000372 -0,000251 -0, 000412 x2 = O0OOI661 0,001701 -0,000462 x3 = 0 0200672 0,200691 0,199648 x4 = 0.199325 0,199442 0,200473 x 5 = ”0 <>000408 -0,000238 -0,0001 40 x 6 = 0»598l02 0,598654 0,600318 N = 236 144 39 T = o§o4 2s4l o?44 £ = 2~^ Undershoot No rmal Overshoot X 1 = -0,000179 -0,000216 -0,000219 x 2 = 0 ,000920 0,000866 -0,000194 x3 = 0,200323 0,200202 0,199861 x4 = 0,199665 0.199755 0,200260 x 5 = -0,000067 -0,000172 0,000176 x6 = 0,598970 0.59935^ 0,600318 N = 271 168 T = 5 §03 3T0B 0§48 6 = 2”^ Undershoot No rraal Overshoot X 1 = -0,000099 -0,000093 0,000110 x 2 = 0,000436 0,000399 -0,000034 x 3 = 0,200179 0,200086 0.199827 x4 = 0,199822 0,199877 0.200029 x 5 = -0,000104 -0,000070 -0.000055 x6 = 0.599505 0,599696 0.600185 N = 310 193 “W T = 5§47 3T36 Os 54 e =

—1 4 2 Undershoot No rmal Overshoot

x i = -0,000023 0,000000 -0.000041 x 2 = 0,000226 0,000177 0.000036 x3 = 0,200085 0, 200040 0.199914 x4 = 0,199904 0,199916 0.200052 x 5 = -0,000033 -0, 000041 -0.000035

*6“ 0,599760 0.599772 0.600149 N = 212 55 T = 6s31 3; 57 00 0 C\J
22 e = 2'“ 1 ^ Undershoot Normal Overshoot

x i = “0 o 0000 26 -Oo 0000 17 -0o 000027 x2 = 0 oOOOl 1 6

OoOOOIIO 0o000017

x3 = 0 0 20004-7 Oo 200055 Ool 99932 x4 = 0,199953 0.199957 Oo 200003 x 5 = ^0o 000028 -Oo 0000 17 0o000021 x6 = Oo 599867 0.599912 Oo 600099 N = 383 233 6§ T = 7 §09 4s 21 1814” 6 = 2"1 6 Undershoot N© rnaal Overshoot X 1

”” =0o 000004 -Oo 00001 5

-Oo 000012

%2 ~ Oo 0000 56 0o000058 Oo 000003 x 3 = Oo 200025 Oo 200011 0.199957 x4 = Ool 99974 Ool 99981 Oo 200028

*5 - -Q 0 00001 4

-Oo 00000? -0o000015

x6 = 0,5999*+6 0.599953 Oo 600060 N = 427 ’ 256 T " 7 §58 T74? 1 §27

6- = 2-17 Undershoot W© rmal Overshoot X1 = =Oo 000007 -Oo 000002

-0o000003

x 2 = Oo 000030 0o000025 -Oo 00000 8 x3 s Oo 20001 3

Oo 20000 5

Ool 99984

x4 = Ool 99988 0.199989 Oo 200010 x 5 = -Oo 000007 -Oo 000006 -Oo 000003 x6 = 0.599965 0.599980 Oo 600023 N = *+57 '283 105 T = 8 §31 VJ1 00 cai 1 § 58

fe= 2”18 Undershoot No rmal Overshoot

X1 = -Oo 000003 -0o 00000 2

-Oo 000001

x2 “ O0OOOOI6 0o000013 Oo 000002 x3 = 0 0 200006 0o 200004 Ool 99993 x4 = 0.19999'+ 0.199995 Oo 20000 5 x 5 - -Oo 000003 -0o 000001 -Oo 000003

*6 = 0.599986 0 . 599990 Oo 60001 3 N = 1+99 - "W “

12T*

T = 9s19 ^742 fO 00 ro0
23

€. =2 19 Undershoot No rraal Overshoot X 1 = -0. 000001 -0.000002 -0.000001 x 2 = 0.000007 0,000006 0.000000 x 3

0.200003 0.200003 0.199996

X4 = 0.199998 0.199998 0.200003 x 5 = -0.000002 -0.000002 -0.000001 x6 = 0.599993 0.599993 0.600005 N = Wi 322 ftf7 T = 10s05 6s0i 2s45

vi; II CM !CMo Undershoot No rmal Overshoot

x i = -0.000001 0.000000 -0.000001

ii

oo

X 0.000003 0.000003 0.000000 x 3 = 0.200001 0.200001 0.199999 x4 = 0.199999 0.199999 0 . 200000 x 5 = -0.000001 -0.000001 0.000001 4 = 0.599996 0.599998 0.600004 N = ~ ?79 355 163 T = 10 s 48 6 s 38 3*03 n ro i ro Undershoot No rraal Overshoot X 1 = 0.000000 0.000000 0.000000 n • X c\ 0.000002 0.000002 0.000000 x 3 = 0.200001 0.200001 0.199999 x4 = 0.199999 0 . 200000 0.200001 x 5 = 0.000000 0.000000 0.000000 x6 = 0.599998 0.599998 0.600001 N = 6i4 W ' 1 64 T = 1 1 s 28 6 s 52 3:26

<6 = 2~22 Undershoot Normal Overshoot X 1 = 0.000000 0.000000 0.000000 x 2 = 0.000001 0.000001 0.000000 x 3 = 0.200000 0 . 200000 0 . 200000 x4 = 0 . 200000 0 . 200000 0.200000 x 5 = 0.000000 0.000000 0.000000 4 = 0.599999 0.599999 0.600001 N = 553 35s 201 T = 1 2 § 1 1

7:15
Observe that overshoot converged faster than normal ? which

in turn converged faster than undershoot. This held consistently for all the games.

Further ? for Q sufficiently small? there is an approximately uniform increase in the number of iterations required

to ’'attain a given G

n as is halved. For the 6x6 game? for

example? from 6 = to 6 = 3 the additional iterations

required to go from 6= 2” x to 6= were approximately

38 (for undershoot), 2h (for normal)? 12 (for overshoot).

The experiment did not reveal any arithmetic relationship

between the size of the matrix and the computing time.

Conclusions

Any relative evaluation of proposed computation schemes

requires specification of the size of the problem considered?

the accuracy demanded and the amount of computation time reasonable to invest in obtaining this accuracy. Let us assume

(in accordance with the requirements of most of the practical

problems that have so far arisen in our work) that four or

five decimal digits are required in the answer? and that the

size of the matrix A< is say? 7^7 or greater „ Then the simplex method is outstanding among the three.

In the large size games considered in the experiment? the

simplex method achieved answers to this precision in a third

or a fourth of the time required by the most favorable of the

others. This occurred despite the fact that simplex was
25

to use magnetic tapes for storage of most of the numbers arising

in the computation, whereas the other methods stored all the

numbers within the high speed memory,, It is estimated that

about 4/5 of the machine time required for simplex on these

games was spent in bringing the needed numbers from the tape

to the high speed memory and taking the numbers from the

memory to the tape. (Improvements in tape performance subsequent to these computations have reduced this ratio to about

^)„ The other methods would be completely impractical if tape

had to be used, and that is why only the simplex method has

solved moderately large problems (where the matrix A is about

50x70) o Even assuming a very large memory so that, for instance, a large problem could be coded for relaxation in the

most efficient way, then the fact that simplex could be done

internally would favor it even more. It is true, however,

that because simplex is more complicated algebraically, it is

possible by clever coding to fit some problems into the high

speed memory when using fictitious play or relaxation that

could not be so accommodated if simplex were employed. One

such large problem arose in our works the computation matrix

was 48x71 for the simplex method, but formulated as a symmetric

game and using ingenious coding devices, it could be done

within the high speed memory by fictitious play. Nevertheless, simplex was completed in half the time that fictitious

play required to obtain the same accuracy.
26

Is there then an area of usefulness for the infinite methods?

The answer is yes, for problems satisfying the following conditions; They are small enough to be done entirely within the

memory, and the precision demanded is very slight ©r very great,,

Two objections to the simplex method ares (i) in general,

there is no reason to believe that an answer from an early

iteration has any meaning at all, so there is no provision

for doing less work if one is content with small accuracy?

and (ii) when the answers are finally obtained, there is no

way to improve them to obtain greater precision,, (Wolfe's

proposed variation [12] of the .simplex method will help (ii) , but it is questionable that it would involve less work than

the procedure suggested below)

,

If the purposes of the computation require only one or

two decimals in the answer, then one is perhaps better off

using the infinite methods „ This is verified in the 6x6 problem, which, indeed, favors fictitious play over relaxation

for this purpose (which favorable position held in general)

.

If the purposes of the computation demand greater precision

than the simplex answers yield, then it is reasonable to use

the simplex answers as a starting point for one of the other

methods. And here, the more favorable convergence rate for

relaxation (see the comments in 3(b) and 3(c) over fictitious play favors the use of the former.
27

References

Several of the references (indicated with *) are taken

from Activity Analysis of Production and Allocation ^ edited

by T. Co Koopmans, New York, 195l»

[1] So Agmon, The Relaxation Method for Linear Inequalities , to appear in Annals of Mathematics 0 *[2] Go Wo Brown, Iterative Solution of Games by Fictitious

Plays P» 379o

[3] Ao Charnes, Optimality and Degeneracy in Linear Programming ^ Econometric a 9 vol 0 20, No 0 2(l 952) , p„ l60o

*[4] Go Bo Dantzig, A Proof of the Equivalence of the Program- ming Problem and the Game Problem 9 p » 330

„

*[ 5] Go Bo Dantzig, Maximization of a Linear Function of Variables Subject to Linear Inequalities , p<, 339°

*[6] Do Gale , Ho W Q Kuhn, Ao Wo Tucker, Linear Programming and

the Theory of Games , p 0 317°

[7] Ao Jo Hoffman , On Approximate Solutions of Systems of

Linear Inequalities 9 Journal of Research of the

National Bureau of Standards , volo 49, No, 4

(1952)9 p 0 263o

[8] Jo Co Co Me Kinsey , Introduction to the Theory of Games 9 New York,~T952o

[9] Ao Orden, Application of the Simplex Method to a Variety

of Matrix Problems 9 in Symposium on Linear Inequalities and Programming, edited by Ao Orden

and Lo Goldstein, Washington, 1952, p 3 28 0

[10] Ao Orden, Solution of Systems of Linear Inequalities on

a Digital Computer , Proceedings of the Association for Computing Machinery, May 1952, Pittsburgh, Pa,

[11] Jo Robinson, An Iterative Method of Solving a Game , Annals

of Mathematics, vol 0 54(1 951 ), p» 2980

[12] Po Wolfe, The Epsilon-Technique and the Artificial Basis

in the Simplex Solution of the Linear Program- ming Problem s Planning Research Division, Office of Air Comptroller, United States Air

Force, 1951 (mimeographed)

»

THE NATIONAL BUREAU OF STANDARDS

Functions and Activities

The functions of the National Bureau of Standards are set forth in the Act of Congress, March

3, 1901, as amended by Congress in Public Law 619, 1950. These include the development and

maintenance of the national standards of measurement and the provision of means and methods

for making measurements consistent with these standards; the determination of physical constants and properties of materials; the development of methods and instruments for testing materials,

devices, and structures; advisory services to Government Agencies on scientific and technical

problems; invention and development of devices to serve special needs of the Government; and the

development of standard practices, codes, and specifications. The work includes basic and applied

research, development, engineering, instrumentation, testing, evaluation, calibration services, and

various consultation and information services. A major portion of the Bureau’s work is performed

for other Government Agencies, particularly the Department of Defense and the Atomic Energy

Commission. The scope of activities is suggested by the listing of divisions and sections on the

inside of the front cover.

Reports and Publications

The results of the Bureau’s work take the form of either actual equipment and devices or published papers and reports. Reports are issued to the sponsoring agency of a particular project or program. Published papers appear either in the Bureau’s own series of publications or in the

journals of professional and scientific societies. The Bureau itself publishes three monthly periodicals, available from the Government Printing Office: The Journal of Research, which presents

complete papers reporting technical investigations; the Technical News Bulletin, which presents

summary and preliminary reports on work in progress; and Basic Radio Propagation Predictions,

which provides data for determining the best frequencies to use for radio communications throughout

the world. There are also five series of nonperiodical publications: The Applied Mathematics

Series, Circulars, Handbooks, Building Materials and Structures Reports, and Miscellaneous

Publications.

Information on the Bureau’s publications can be found in NBS Circular 460, Publications of

the National Bureau of Standards ($1.00). Information on calibration services and fees can be

found in NBS Circular 483, Testing by the National Bureau of Standards (25 cents). Both are

available from the Government Printing Office. Inquiries regarding the Bureau’s reports and

publications should be addressed to the Office of Scientific Publications, National Bureau of Standards, Washington 25, D. C.