NATIONAL BUREAU OF STANDARDS REPORT

2971

ON THE SOLUTION OF THE CATERER PROBLEM

by

J. W. Gadd urn

A, J. Hoffman^ D. Sokolowsky

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
U. S. DEPARTMENT OF COMMERCE

Sinclair WsekSj, Secratary

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 engaged in technical work. In general, each section is engaged in specialised 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 hack

cover of this report.

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

Optics aiffld 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 Cheipistry. 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 STANPARBiS REPORT

MBS PROJECT MBS REPORT

1102-10-1104 December 1 6, 195b 2971

ON THE SOLUTION OF THE CATERER PROBLEM

by

Jerry Gaddum

A. J. Hoffman , D. Sokolovsky

U.S. Air Force

National Bureau of Standards

This work vas sponsored (in part) by the Office

of Scientific Research, USAF

<NBS>

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS

The publication, re)

unless permission is

25, 0. C, Such perr

cal iy prepared If th

Approved for public release by the

Director of the National Institute of

Standards and Technology (NIST) on October 9, 2015

n part, Is prohibited

indards, Washington

tort has been speclflport for Its own use,
.
ON THE SOLUTION OF THE CATERER PROBLEM

by

J 0 W„ Gaddom*

A 0 J 0 Hoffman, D 0 Sokolowsky**

Introduciloji

This paper continues the investigation of the Caterer

problem formulated and partially solved by Walter Jacobs in

[ 1 ] o We shall describe and justify an algorithm for solving

the problem, indeed for solving a problem that is slightly

more general than the original one, A knowledge of [l] is

desirable for an interpretation of the abstractly formulated

linear program discussed here, but is not necessary for a reading of this paper 0 We believe^ however, that the reader

who is interested in the "life cycle" of a linear program -

(a) formulation, (b) simplification, (e) development of an

algorithm for solution - will learn from the discussion of

the caterer problem contained in [ 1 ] (which treats (a), (b)

and a special case of ( e ) ) and this article an instructive,

and in some ways, typical example,,

We now introduce the problem to be attacked?

Let be given constants, r^, 0 , ? Pn given nonnegative constants, let X be a variable, z = (z^,,o ? z

n

) be

a variable vector lying in the rectangular parallelepiped

*U 0 S 0 Air Force,

**National Bureau of Standards

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

Research, USAF,
- 2-

(1) 0 < z

i (i = 1 , . . . ,n)

Let A-j,...,Am

9 iven vectors in n-spaee, the coordinates

of each consisting of I's and 0

f s such that:

(2) The I's in each A^ are consecutive, and

(3) If the coordinates in A^ which are 1 are a, a + 1,...,b,

and the coordinates in A. which are 1 are c, c+1,...,d, and if

a < c, then bid. We assume tacitly that each A^ contains

at least one 1

.

The problem is: for any number A ^ 0, to find values for

X and z, subject to (l) and

(4) (

A

±

, z ) > t

± - X (i = 1 , . . . ,m)

which minimize the linear form

(5) >x+ Z z

i

i1

A comparison of our problem ivith the transformed caterer

problem given in (4.3) of [l] will show that (4.3) is a special case of the above.

2. The solution if X is specified . Since our object is

to study the behavior of X and Z, it is not unnatural to ask

what the solution of our problem would be if X were specified;

i.e., if X were a given constant. If we set = t^ - X

(i = 1,...,m), then our problem becomes: for all z = (z^,...,z

n

) subject to (1) and
-3-

(4*)

minimize

(5 ! )

(Apz) £

Z

^ + o o o + Z

^

(i = 1 ? o o ° ? m) 9

Before solving the problem, one should cheek to see that

the inequalities (1) and (4") ape consistent,, Set r =

Then it is clear that the inequalities are c©n~

sistent if and only if (A^ 9 p) > (i = 1 90 oo 9 m ) 9 which can

be easily ascertained,,

Assume now that (l) and (h- 5 ) are consistent,. Let S. be

the set of all indices i such that the j-th coordinate of

A. is 1, Define = (0, r 0? r-,,„ 6 o S r ), and

i d J n

(6) z, (X) = max ^O; max [ - (A^, ) ]}

i e s,

If z.j (X) ? o e 0 9 %^ (X) have been defined (1 n ) 9 let

( k

)

r = (z^ (X) , o „

9 z

k (X) , 0, r ^+ 25 ° ° °

?

Then define

(7) z k+ -j(X) = max

[

0 9 max C ^ i ~ r^)]j

i 6 S

k+1

We contend that the vector z(X) = (z 1 (X), oeo ,z (X)) de~

1 n fined inductively above solves the problem of this section,,

It is clear that our prescription states that z^ (X) is the

smallest value of z ? consistent with (l) and (4"); and that,

assuming z

} = z^(X) ?ooe? z^ = z^CX), z^-j (X) is the smallest

value of z^ + .j consistent with ( 1 ) and (4 ' ) ®
We shell prove our contention by showing that

Lemma Is For every k (k = 1 , . . . ,n) , z(X) minimizes z^+ . • .+7 : , subject to (1) and (4').

Proof by induction: We have already seen that lemma 1 holds if k = 1. Assume it holds for k - 1, we wish to show it

holds for k. If z f/.(X) = 0, this is obvious from the induction

hypothesis. If z h (X) ^ 0, then by (7), there exists a vector

A. such that

i

(8) z (X) + (A. 1 ^ ) = u., i6 S, 1

7 .1

7 K

Let us write out the inequality

(9) (A^,z) >

as

(9') z

k-ot t# * * + 2

kl

+ z

k

+z k+1

+ * * * + z k+6^

(Recall (2)). Of course « or or both may be 0). Then (8)

says that

(1°) z k-czX>) + •••+ z k^ + ^k+l + # ** + r

k+/3 = M i

Now (9 1 ) is one of the inequalities (4'). Hence, by (10)

and (1), z

k_^(X) + . . .+ z v (X) - min z z,r , for all z subject to ( 1 ) and (

4

1 )

.

But by the induction hypothesis,

z^ (X) + ...+ z

k_af _ 1 (X) = min Zj + ...+ z k-^_i • Combining these

last two statements proves the induction step.
- 5-

Note that our proof uses (2), but not (3) 0 The theorem is

false if (2) does not hold

Now ? it is clear from (h) that the set of X for which the

inequalities (1) and (*+) of our main problem are consistent

form a closed half-line^ containing arbitrarily large positive numbers „ Let e be the end point of^ » For each X > @ 9 let S(X) = min (z, + 0 oo+ z ) 9 subject to (l) and (*+)„ We have

i n just seen how to compute S(X) and we now prove

3o For X 2. s, S(X) is a .convex non-increa s ing function of X c Proofs Let then the convex region which is the

intersection of the half-spaces corresponding to X=X^ in (*+)

contains the convex region corresponding to X=X^; hence S(X,

)

1 SCX^)*, To prove S(X) is convex, we first prove a more general lemma 0 Let A and B be two real linear spaces 9 and let K be a convex set in A® B„ Let V be the projection of K on A; i 0 e<, 9 V = { v| v e. A 9 3 w £, B such that v <3> w & K; let W be the projection of K on B„ It is easy to see that V and W are convex

setSo Let f be a convex function bounded from below defined

on V 0Lemma 3° The function

(11) g(w) = inf f(v)

v <a w €. K

is a convex function on W„

Proof a We must show that w,

{ W 9 ^ W 9 ct o, ^2. 0 9

(3 = 1 , imply
-6-

(12) g(°^w^ +/3 w

2

) < ag(w^) + (l g(w

2

).

Let C be any positive number. Then by (11), there exist

v.j , v

2

such that

(13) v

1 ® w

1 € K, v

2 ® w2 € K, and

(14) f(v^) < g(w

1 ) + £ , f(v2

) 1 g(w

2

) + £- .

Since K is convex, it follows from (13) that ^(v-j® )

+ |£> (v2 d w

2

) = ( * v.j + 0> v

2

) & ( <* + ft w

2

) € K. Therefore, since f is convex, g( « + (l w

2

) 1 f(ocvj +/3 v

2

)

£ o:f(v

1 ) + /3f(v2

) £ org( Wl ) + (3g(w

2

) + <£.

, by 04).

Since this inequality holds for every £ > 0, we have (12).

Apply lemma 3 to the present situation as follows: Let

z = v, z, +...+z„ = f(v), X = w, S(X) - g(w). This completes

the proof of 3*

4. Summary of the s±iiiation_to_ date . Let us assume, temporarily that S(X) is explicitly

known. Now it is manifest from (6) and (7) that z . (X) is a n polygonal curve. Hence S(X) - £2 z.(X) is a polygonal

j=1

curve. Since S(X) is convex, the half-line will break up

into intervals (e - e Q ,e^), (e^ ,

©

2

) ,...,(

©

d

, 00 )

,

such that

the slope of S(X) is -m. in (e o ,e^), -m

2

in (e^ ,

e

2

) ,"j-rad

in

(e

(j _ 1 ,e

(j), 0 in (e d ,oo), m1 > m

2 >...>m

d > 0. It is obvious
-7-

that = max t ^ and that in (e^oo), S(X) = 0, It is also

clear that e = max [t. - (A^,r)j „ Assuming that all @

o

JL and m were known, it is obvious that the minimum of (5)

(which, as the sum of two convex polygonal functions of X,

is also a convex polygonal function of X) could be obtained

as follows?

if A > m. , the minimum of (5) is attained at X = e

if > A £ m^, the minimum of (5) is attained at X =

(ip) if £ A >_ ra^ ? the minimum of (5) is attained at

X = e d-n

if m^ > A > 0 , the minimum of (5) is attained at X = e^

)

if 0 > A ? (5) has no minimum,,

Since we have already seen in paragraph 2 how to obtain

the z . which minimize (5) once the correct X is known, forj

mulas (15) solve our problem once the numbers e rt ,e 1?000 ,e

and ,ooo,m, are determined

,

o'-1 ?oos?v d

m n !ia A >41 jr\ * /tb. m m, >41

^

' d

We already know e Q

„ We shall show below how, given

one may obtain and m^ by a reasonably efficient procedure.

Since is also known, this procedure, in view of 0 5)? will

solve our problem,

5, The algorithm . Recall now the procedure described in paragraph 2,

particularly formulas (6) and (7),
- 8-

An inequality (A^,z) > - X is said to be bounding for

z • at X if i € S. and z.(X) = M- - (A.,r^ J ^). Let B. be

j J J i 1 J the set of all indices i such that (A.,z) > t.-X is bounding

1 "l

for z B at X = e. 1 . Note that k o-l

(16) z

j

(8 o-1 ) > 0

implies that Bj is not empty. Let be the set of all indices j such that the j-th coordinate of A^ is 1 . Then

(17) i £ k > j, k € T

± imply i £ B

R

, z

k (e6_ 1 ) = r R

We now divide all indices i = l,...,n into two classes M

(moving) and S (stationary) as follows: if z^(e

0_^) - 0,

assign 1 to S; if z^(e^_^) > 0, assign 1 to M; if 1,2, ...,k

have been assigned, and 2 k+ -j ^ e o-l ^ = assign k+1 to S; if

z R+ i(e^>0, and no index in U (recall ( 16 )) has been

* ^ B k+1

assigned to M, we assign k+1 to M, but if an index in U T.

i € B

k+1

has been assigned to M, we put k+1 in S.

It will turn out that rk is the number of indices assigned to M, but before we show this, we first prove

Lemma *+. (a) If i € fj B . , then there is at most one

j

3 index in the intersection of T . and M; (b) for any i, there

are at most two indices in the intersection of and M.

P roof of (a): Assume i €. B.; k,£ £ T., £ M, k </.

J If j? then (17) and the definition of M contradict i £ M.
-9-

Therefore, we may assume k < £ < j 0

Let i

Q £ B^ (we know from (16) that i € M implies B^ is

not empty) o Then since k £ M, k < d , it follows that

k £T. o But k, H , j £. T.; hence by (2) and (3), p >£ , 2. "

p £ T.^ imply p ^ T. , But by (17)? p € T. , p > l imply

z n (e, 1 ) = r t p o- 1 p

Together with i £ B., these facts imply

J i e o We know, however, that k £ M, k £ T

d £ T., we have a contradiction of d€ Mo

Combined with

Proof of Assume j < k < J? ; j, 6 T. 5 j, k,i? £ M<

Let p € B^o Then j ^

T^, and also, by (17)? ft T^„ A comparison of T . and T exhibits a violation of (2) and (3)»

** r 6 8 Going from e

Q._i to Resuming our main discussion,

let K be the set of all i such that the intersection of T. and

i

M consists of two indices (K may be empty)* Let ft> = min

. x i£ K

)(A. ,z(e^ J) - t. + e. J if K is not empty, ft = + oo otherwise* Then ft> 0 o For if ft ~ 0 , i 0 e 0 , there is an i G K

such that (A. ,z(e A ,))=!„- 6 ,, then if k is the largest i

Q

o-l i p-1 J index in T . , clearly i G. B, OK, and we would have a violation

O

of lemma 4(a)*

Let t= min z.(e. -,)* By the definition of M, > 0,

iSU 1 0-1

Jbmaliy, let = min (/3, if) > 0„ We contend

Lemma 5» For all X, e ^_-j < X < 0£ + and each j = 1,

ooofti, we have
- 10-

(13) z • (X) = z . (X) = ) j b 1 J J /

if j 6 S

z

j

(8 o-1 ) {x-e

d-1 ) if j e M

Before proving the lemma, let us informally state its

content. If X lies in the prescribed range, then: if j € S,

moves by precisely the amount by which X differs from e^_^

.

Proof : Obviously the lemma holds for z^(X). Assuming it

holds for z.j , . . . jz^-j (X) , we shall show it holds for z^CX).

By virtue of lemma 1, we must show that if z^ = z^ (X) , . . . ,z^_^

- z

Jt _ 1 (X) satisfy ( 1 3) , z

fc+1 = r,;+1 ,

. . . ,z R = r , then (i) if

we set Zj,t = z^(X) according to (l3), the vector z satisfies

(1) and (*+); but (ii) if we set z^ < z^(X) th© vector z will

not satisfy (l) and (4-).

Suppose k M. We first prove (i). For each i £. S f^, TV

may contain no indices in the range 1,...,k-1 in M or 1 index

in the range in M (lemma h(b)). It is clear from

the induction hypothesis that; in the former case, (A^,z) t^

- X. In the latter case, again from the induction hypothesis,

we have

But, by the definition of o( and ft , for this range of X,

(19) (A

i? z) > (A

i ,z(e

& _ 1 )) - 2(x - e^))

( 20 )
Combining (19) and (20), we obtain again (A,,z) 2_ t, - X.

Next, let i £ B , Then clearly (A 4 ,z) = t. - X, which proves

iia. -a- X

(ii) •Suppose k €. S. The proof of (i) involves no new ideas,

ar^d is omitted. To prove 1 (ii), if z., (e. ,) = 0, (ii) is

il 0“ i immediate; hence, assume z,(eA ,) > 0, which, by ( 16 ) , (17),

and the construction of S, implies that there exists an i € B

j & S , j < k such that j £ M. It follows from (17) and (7)

that (A.; ,z) = - X, which proves (ii).

We observe the following immediate consequences of lemma

r'J 9 Corollary i. The funetio.'- z > (X) is a mocotonie, nonJ increasing function of X.

This implies that in coinc from 3.- , to e. « w- may substitnte for (i) the inequalities

(s') 0 < z .(X) < z .(a- , ) = j ” J o—l

Corollary 2. The slope m.. is equal to the number of

indices in M.

To complete our algorithm, when we arrive at X = 0( + e

^ we replace ©, , by , + oc and repeat our construction of 0“ i o—

the new M and S , say M* and S’. By virtue of the convexity

of S(X), the number of indices in M* is less than or equal

to the number of indices in M. Ii it is less than, then

+ 8: 1 = e x . If it is equal, we proceed in the same mosme Q— | Q

a 7
- 12-

It is clear, from the fact that each Zj(x) is a polygonal

function of X with a finite number of vertices, and (from the

definition of « ) that each step takes us from an X corresponding to a vertex of some ?.(X) to the next largest X cor-

•I responding to a vertex of (possibly some other) z.(X), that

J we arrive at in a finite number of steps.

BIBLIOGRAPHY

[l] The Caterer Problem, by W. Jacobs, to appear.
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.
))J)