1962 05_#21 05 #21

1962-05_#21 1962-05_%2321

User Manual: 1962-05_#21

Open the PDF directly: View PDF PDF.
Page Count: 408

Download1962-05_#21 1962-05 #21
Open PDF In BrowserView PDF
AMERICAN FEDERATION OF INFORMATION PROCESSING SOCIETIES

1962

PROCEEDINGS
SPRING JOINT COMPUTER CON FERENCE
SAN

FRANCISCO,

CALIFORNIA. MAY

1-3,

1962. VOL.

21

ADDITIONAL COPIES
Additional copies of the Proceedings maybe purchased
from the printer at $6.00 per copy and will be sent postpaid
if order is accompanied by remittance.
Orders should be sent to:
The National Press
850 Hansen Way
Palo Alto, California

Copyright 1962 by
American Federation of Information Processing Societies

DISCLAIMER
The ideas and opinions expressed herein are solely those of
the authors, and are not necessarily representative of, or
endorsed by, the 1962 Spring Joint Computer Conference
Committee or the American Federation of Information
Processing Societies.

Manufactured in the U.S.A. by The National Press, Palo Alto, California

PREFACE

This volume embodies the substance of technical presentations made
at the first of two major computer conferences to be held this year. Taking
a name which designates when it took place, rather than its geographic
location, the 1962 Spring Joint Computer Conference heralds recognition
that these meetings are nationwide in scope, no longer mere regional conventions. AFIPS continues the tradition of the former Western Joint Computer Conferences by bringing together from all parts of the country men
of talent who can provoke and inspire us to meet the challenges which
face our industry today.
Each paper presented has been selected for the unique contribution
which its author can make toward satisfying our industry's appetite for
new ideas. Rather than catering to anyone specific theme, this program
touches the highlights of new developments, points out trends, summarizes
progress, and orients the computer field with other disciplines.
We trust that this book will meet the need for which it was designed:
to serve as a valuable source of reference to a collection of technical literature for the computer industry.

G. A. Barnard, 3rd
Chairman
1962 Spring Joint Computer Conference
iii

AMERICAN FEDERATION OF INFORMATION PROCESSING SOCIETIES
AFIPS came into being as an unincorporated society of societies on May 10, 1961. AFIPS is a
direct outgrowth of the National Joint Computer Committee (NJCC). The latter organization was
formed in 1951 for the sole purpose of sponsoring and coordinating the Joint Computer Conferences, Eastern and Western. The same organizations which comprised the NJCC are the founding
societies of AFIPS:

The American Institute of Electrical Engineers (AlEE)
The Association for Computing Machinery (ACM)
The Institute of Radio Engineers (IRE)
Officers, Directors, and Committee Chairmen of AFIPS are:
CHAIRMAN GOVERNING BOARD: Dr. Willis H. Ware, The RAND Corporation, 1700 Main Street,
Santa Monica, California
EXECUTIVE DIRECTORS: R. A. Imm-AIEE; Dr. H. D. Huskey-ACM; Dr. A. A. Cohen-IRE
SECRETARY: Miss Margaret R. Fox, National Bureau of Standards, Data Processing Systems Div.,
Washington 25, D.C.
TREASURER: Frank E. Heart, Lincoln Laboratory, Room B-283, P.O. Box 73, Lexington 73, Massachusetts

AlEE DIRECTORS

ACM DIRECTORS

IRE DIRECTORS

R.A.lmm

Walter M. Carlson

Dr. Werner Buchholz
IBM Corporation
South Road Laboratory
Poughkeepsie, New York

IBM Corporation
Dept. 550, Bldg., 006-1
3605 Highway 52 North
Rochester, Minnesota

Mechanical Research Laboratory
E. I. duPont DeNemours & Co.
101 Beech Street
Wilmington 98, Delaware

Dr. Arnold A. Cohen
R. S. Gardner

American Institute of
Electrical Engineers
345 East 47th Street
New York 17, New York

Dr. Bruce Gilchrist
IBM Corporation
590 Madison Avenue
New York 22, New York
Dr. Harry D. Huskey

Claude A. R. Kagan
Western Electric Company
P.O. Box 900
Princeton, New Jersey

Dept. of Mathematics
University of California
Berkeley 4, California

517 Anthwyn Road
Merion Station, Pennsylvania

Frank E. Heart
Lincoln Laboratory, Room B-283
P.O. Box 73
Lexington 73, Massachusetts
Harry T. Larson

J. D. Madden
Dr. Morris Rubinoff

Remington Rand Univac
Univac Park
St. Paul 16, Minnesota

System Development
Corporation
2500 Colorado Avenue
Santa Monica, California
v

Aeronutronic, Division of
Ford Motor Company
P.O. Box 486
Newport Beach, California

AMERICAN FEDERATION OF INFORMATION PROCESSING SOCIETIES (Continued)
ADMISSIONS COMMITTEE

FINANCE COMMITTEE

PUBLICATIONS COMMITTEE

Dr. Bruce Gilchrist
IBM Corporation
590 Madison Avenue
New York 22, New York

Dr. Morton M. Astrahan

Dr. 'Verner Buchholz

IBM Research Laboratory
Monterey and Cottle Roads
San Jose 14, California

IBM Corporation
South Road Laboratory
Poughkeepsie, New York

AWARDS AND PRIZES
COMMITTEE
Claude A. R. Kagan
Western Electric Company
P.O. Box 900
Princeton, New Jersey
BY-LAWS AND
CONSTITUTION COMM..lTTEE

COMMITTEE ON
NEW ACTIVITIES
Dr. Morris Rubinoff
517 Anthwyn Road
Merion Station, Pennsylvania

SOCIAL IMPLICATIONS OF
INFORMATION PROCESSING
TECHNOLOGY COMMITTEE
Harry T. Larson
Aeronutronic, Division of
Ford Motor Company
P.O. Box 486
Newport Beach, California

Walter M. Carlson
Mechanical Research Laboratory
E. I. duPont deNemours & Co.
101 Beech Street
Wilmington 98, Delaware

PUBLIC RELATIONS
COMMITTEE

AFIPS REPRESENTATIVE
TO IFIPS

CONFERENCE COMMITTEE

J. D. Madden

I. L. Auerbach

Keith W. Uncapher
The RAND Corporation
1700 Main Street
Santa Monica, California

System Development
Corporation
2500 Colorado Avenue
Santa Monica, California

vi

Auerbach Electronics
Corporation
1634 Arch Street
Philadelphia 3, Pennsylvania

1962 SPRING JOINT COMPUTER CONFERENCE COMMITTEE
CHAIRMAN: G. A. Barnard, Philco WDL, Palo Alto, Calif.
VICE CHAIRM..4.N: Dr. H. D. Crane, SRI, Menlo Park, Calif.
SECRETARY-TREASURER: R. A. Isaacs, Philco WDL, Palo Alto, Calif.
L. J. Borrego, Philco WDL, Palo Alto, Calif.

TECHNICAL PROGRAM

REGISTRATION

Chairman: Dr. R. I. Tanaka, Lockheed, Palo Alto, Calif.
Vice Chairman: R. C. Minnick, SRI, Menlo Park, Calif.
Assoc. Chairman: J. E. Sherman, Lockheed, Palo Alto,
Calif.

Chairman: D. E. Eliezer, IBM, San Jose, Calif.
Vice Chairman: Leo Rinsler, IBM, San Jose, Calif.
R. A. Shaw, IBM, San Jose, Calif.
PRINTING AND MAILING
Chairman: W. O. Hamlin, Fairchild, Mountain View,
Calif.
Vice Chairman: R. J. Johnston, Fairchild, Mountain
View, Calif.

SESSION CHAIRMEN:
F. M. Tonge, Stanford University, Calif.
R. A. Kirsch, Nat'l Bureau of Standards, Wash., D.C.
J. I. Raffel, Lincoln Laboratory, Lexington, Mass.
D. C. Engelbart, SRI, Menlo Park, Calif.
B. G. Farley, Lincoln Laboratory, Lexington, Mass.
J. H. Pomerene, IBM, Yorktown Heights, N.Y.
V. L. Larrowe, University of Michigan
Jack Goldberg, SRI, Menlo Park, Calif.
B. A. Galler, University of Michigan
Louis Fein, Consultant, Palo Alto, Calif.
H. K. Skramstad, Naval Ordnance Lab, Corona, Calif.
R. M. Bennett, IBM, San Jose, Calif.
J. P. Runyon, Bell Telephone Lab, Murray Hill, N.J.

PUBLICATIONS
Chairman: E. T. Lincoln, IBM, San Jose, Calif.
Vice Chairman: J. J. McNulty, IBM, San Jose, Calif.
PUBLIC RELATIONS
Chairman: N. S. Jones, Friden, San Leandro, Calif.
Vice Chairman: R. D. Painter, Fairchild, Mountain
View, Calif.
EXHIBITORS' PROGRAM
Chairman: D. C. Lincicome, SRI, Menlo Park, Calif.
LADIES' ACTIVITIES
Chairman: Margaret G. Conley, IBM, San Francisco,
Calif.
Vice Chairman: Anne Niemi, IBM, San Francisco, Calif.
Joy Gallagher, IBM, San Francisco, Calif.
Barbara Taylor, IBM, San Francisco, Calif.

EXHIBITS
Chairman: J. W. Ball, Pacific Telephone, Sacramento,
Calif.
Vice Chairman: Art Scholar; Pacific Telephone, San
Francisco, Calif.

SPECIAL EDUCATION PROGRAM
Chairman: R. J. Andrews, IBM, San Jose, Calif.
Vice Chairman: William Gerkin, Rem. Rand, San Francisco, Calif.
Bryce Ells, IBM, San Jose, Calif.
A. J. Bodine, IBM, San Jose, Calif.
E. W. Means, Rem. Rand, San Francisco, Calif.

LOCAL ARRANGEMENTS
Chairman: R. G. Glaser, McKinsey & Co., San Francisco, Calif.
Vice Chairman: R. D. Smith, Smith-Corona Marchant,
Oakland, Calif.
G. W. Mills, Burroughs, San Francisco, Calif.
H. G. Asmus, General Electric, Phoenix, Ariz.
D. C. Hays, General Electric, San Francisco, Calif.

CONSULTANTS
Exhibits: J. L. Whitlock Associates, Oakton, Va.
Public Relations: W. C. Estler, Palo Alto, Calif.
vii

REVIEWERS
AFIPS and the Conference sincerely appreciate the excellent job done by
the Reviewers. Their careful study and comments have been vital to maintaining the high standards of quality for this collection of papers.
S. Amarel
W. L. Anderson
M. M. Astrahan
D. C. Augustin
J. A. Baker
R. M. Barnett
R. C. Baron
D. E. Beecher
G. A. Bekey
R. M. Bennett
D. F. Berg
J. E. Bertram
E. Bloch
E. K. Blum
E. V. Bohn
A. Bridgman
W. Buchholz
T. H. Bullock
F. Carr
A. B. Clymer
M. Cohn
L. J. Craig
T. H. Crowley
E. C. DeLand
J. F. Dirac
C. B. Dowling
J. Earle
R. D. Elboum
G. F. Emch
D. C. Engelbart
G. W. Evans
B. G. Farley
I. Flores
S. Frankel
W. S. Fujitsubo
B. A. Galler
H. L. Gamer

R. A. Kudlich
V. L. Larrowe
R. S. Ledley
C. y, Lee
C. T. Leondes
B. M. Levin
M. H. Lewin
J. D. Little
B. Loveman
J. Lyman
O. L. MacSorley
J. Macy, Jr.
J. Mangnall
W. Marggraf
F. N. Marzocco
M. S. Mason
M. S. Mayzner
E. J. McCluskey
M. E. McCoy
R. M. Meade
R. Meagher
R. E. Miller
R. C. Minnick
M. Morgan
T. H. Mott, Jr.
P. G. Neumann
L. W. Neustadt
C. J. Nisson
H. Nonken
A. B. N ovikoff
M. Paskman
G. T. Paul
A. Pohm
J. H. Pomerene
C. R. Porter
T.F.Potts

J. P. Gibbons
B. Gilchrist
M. C. Gilliland
E. L. Glaser
R. C. Gold
E. A. Goldberg
J. Goldberg
M. H. Goldstein
E. Goto
G. R. Grado
D. Greenberg
J. Griffith
D. Haagens
D. W. Hagelbarger
J. K. Hawkins
L. D. Healy
P. J. Hermann
T. R. Herndon
T. Higgins
W. H. Highleyman
M. E. Homan
R. D. Horwitz
R. M. Howe
K. Iverson
A. S. Jackson
G. T. Jacobi
S. Jamison
D. B. Jordan
J. A. Joseph
L. Kanal
W. J. Karplus
W. Kindle
R. A. Kirsch
R. H. Kohr
G.A.Kom
L. D. Kovach

This list was compiled of all reviewers registered as of the date this book went to press.

ix

J. I. Raffel
M. J. Relis
S. Rogers
H. Rosenberg
A. I. Rubin
M. Rubinoff
B. W. Rudin
J. P. Runyon
T. T. Sandel
C. M. Schoenberg
N. R. Scott
F. F. Sellers
W. L. Semon
N. Z. Shapiro
Q. W. Simkins
H. K. Skramstad
W. R. Slack
A. Slade
K. H. Speierman
R. I. Tanaka
H. M. Teager
D. Teichroew
L. E. Thibodeau
R. B. Thomas
R. M. Tillman
F. M. Tonge
K. B. Tuttle
G. Vandling
R. L. Van Hom
H. R. Van Zoeren
L. M. vVarshawsky
G. P. Weeg
R. R. Wheeler
H. K. Wild
R. O. Winder
C. H. Wolff

EXHIBITORS
This list was compiled as of the date this book went to press.
Aeronutronic Division of Ford Motor Co.
Newport Beach, Calif.

Consolidated Electrodynamics Corp.
Pasadena, Calif.

AMP, Inc.
Harrisburg, Penna.

Control Data Corp.
Minneapolis, Minn.

Ampex Corp.
Redwood City, Calif.

Datamation
New York, N.Y.
Data Products Corp.
Beverly Hills, Calif.

ANelex Corp.
Boston, Mass.

Datapulse, Inc.
Inglewood, Calif.

Applied Dynamics, Inc.
Ann Arbor, Mich.

DI/AN Controls, Inc.
Dorchester, Mass.

Automatic Electric Sales Corp.
Northlake, Ill.

Digital Equipment Corp.
Maynard, Mass.

Bell Telephone System, Pac. Tel. Co. and
Long Lines Dept.
San Francisco, Calif.

Digitronics Corp.
New York, N.Y.

The Bendix Corp., Bendix Computer Div.
Los Angeles, Calif.

DYMEC Div. of Hewlett-Packard Co.
Palo Alto, Calif.

Berkeley Div. of Beckman Instruments
Richmond, Calif.

Electro Instruments, Inc.
Sunnyvale, Calif.

Brush Instruments Div. of Clevite Corp.
Cleveland, Ohio

Electronic Associates, Inc.
Long Branch, N.J.

Bryant Computer Products
Walled Lake, Mich.

Electronic Engineering Co. of Calif.
Santa Ana, Calif.

The Bureau of National Affairs, Inc.
Washington, D.C.

Electronic Memories, Inc.
Los Angeles, Calif.

Burroughs Corp.
Detroit, Mich.

Engineered Electronics Co.
Santa Ana, Calif.

California Computer Products, Inc.
r!l Hf
-nnumP"
_ ..

Epsco, Inc.

C-E-I-R, Inc.
New York, N.Y.

Fabri-Tek, Inc.
Amery, Wis.

Collins Radio Co.
Dallas, Texas

Fairchild Semiconductor
Mountain View, Calif.

Comcor, Inc.
Denver, Colo.

Ferranti Electric, Inc.
Plainview, L.I., N.Y.

Computer Control Co., Inc.
Los Angeles, Calif.

Friden, Inc.
San Leandro, Calif.

Computer Systems, Inc.
Monmouth Junction, N.J.

Gen. Dynamics/Electronics Information Tech. Div.
San Diego, Calif.

--~.l'

""~~1..._!.l~~

~----'

~, and-E..~!f!r~-where-3.y.!y.!~ may form, will
be underlined. The description may begin as a
catalog of observations.
Books in the return bin are
In-the stacks-:-'-'-' -.-

In conducting this type of modeling:

by

~~~~~~

~2k~ from the r~~~ E..f~ are ~ by Yf~~~~~~

and placed in the
The basic modeling concepts are those of
activity, activity performer, transient information record, and queue. A caricature of the
system drawn upon these concepts places the system
in an information-processing context. Activities
may be defined as series of arithmetic-logical
operations--algorithms. Activity performers may
be identified by quantitative and logical descriptors, and transient information records contain
like descriptors by definition. Such a model is
relatable to the phenomena under study and conveniently translated to computer code.

~

r~1~ E..~~.

Yf~f~~~~ generate re3.u!s1s_f2r_b20~s
1h~ in the r~3.~~~1 E,~~.

and

place

H1>~~~~~~ examine re3.u~s1s_f2r_b20!S from
r~3.~~~1 E,~~ and place 1h~m in the !~~
E,~~.

the

9~E;:rf~ ~ r e,g,U!!S1s against :!?,o2k! in ~~!:~!~
and either ~ E,02k in !.~~~.E..~!! or ~
!e3.u~s1s in 2~1.E,~~.

A flow chart may be constructed at this point
which fixes the relationships of the components
thus far identified (see figure 1).

Potential queues are identified,

Transient information in the system is
identified,
Activities are separated from the people
or machines who perform them,

Thus far, the flow chart shows no control
activities, that is no activities directing the
flow of information, modifying queue disciplines,
or allocating performers among activities. A twodimensional flow chart is limited in application
to fairly stable component relationships. At same
point in modeling, the transient information flow

TOWARD A GENERAL SIMULATION CAPABILITY

chart becomes incapable of rendering component
relationships intelligibly, although flow charts
continue to be of value where relationships are
relatively stable; e. g., in the internal functions
of an activity.
The transient information flow chart must be
read as consisting of the routes of information
intersecting the processes performed upon the
information, and the buffers where the information
reposes when not being acted upon. The fact that
performance of a process is contingent upon allocation of activity performers and availability
of required information must be borne in mind. If
the routing of information is not fixed, the transient information flow chart may become burdened
with contingencies to the extent that its utility
disappears.
The following control activity might be one
added to the library model:

Hl>::lH'f*

aSSigns £l~.r!!.s to ~t~.ri~ E,o£k~ if

.9.~~ in_r~t:!:!I'!! E,i,!! is longer than .9.~~ in
~ !i,!!d_bin, or to !!!B-!c!!i~_r~<@e~t~ if
.9.u~u~ !n_f!n~ ~i,!! is longer than .9.u~u~ in

return bin.
----Note that here activities and activity performers, as well as queue content are treated as
transient information.
A number of additional control activities are
necessary to move the librarian from activity to
activity, get her and the clerks to work in the
morning, etc.
Each of the activities must be described by
an algorithm. The compOSition of the algorithm
will identify information exchanged with other
activities which must be contained in the records
passed between them. Information used in control
activities may be obtained from control blocks
associated with the various activities, activity
performers, and queues (buffers).
The modeling of a system with SIMPAC requires
the unambiguous statement of much information.
Consider the activity, "Generate requests for
books." How long does it take a viSitor to generate a request? Is this time constant or is there
a distribution of such times? Does each visitor
generate one request, or more?
The model of generation activity may include
sampling from Poisson, normal, or rectangular distributions for determining the number of requests
to generate during any time period, or the content
of any of the fields in the transient records
generated; e.g., what book.
Very likely the process will be stochastic,
but it need not be. The particular requests might
be input to the model as exogenous events, if so,
actual history might be utilized in defining these
events.
There are no simple rules for going about

5

this. Each of the activities is a highly aggregated representation of a portion of the system.
The completed model is a caricature of the system,
and each component of the model a caricaturistic
sum of myriad phenomena. Modeling serves to
clarify understanding of the system and indicate
areas of insufficient knowledge. It is the purpose of SIMPAC to provide building blocks for
expressing the model and a framework on which to
rest them.
Translation of the Model to COsPuter Code
Once a model has been specified in terms of
activities, performers, transient information records, and queues (or buffers), it is necessary to
translate the model to machine language--instructions and data.
SIMPAC provides, in the form of macro definitions, a simulation-oriented extension of the
normal symbolic instruction set. ExpreSSions for
entities like queues, and for operations upon them,
form this extension. For example, 'QTAKD A,B' is
an expression for: 'select a record from queue B
in accordance with the queue discipline found at
A'. 'GETBL A' for: 'secure a free block of storage from list A'. 'MCNRN A,B' for: 'generate a
sample drawn from a normal distribution, mean A,
standard deviation B'. 'X ACMAC A,B,C,D,E' for:
'there is an activity X, which services transient
information records in queue A, selecting them
according to the prevailing discipline found at B,
and requiring the expenditure of an amount of service time equal to C times the content of record
field D before placing the record in queue E'.
All activities are modeled as pairs of
algorithms: A set-up phase in which information
necessary for performance is gathered and a
resource time of performance computed, and a completion phase in which the activity itself is performed. The activity is considered "in process"
between the performance of set-up and completion,
and the time between is a function of activity
performer allocation.
Control Blocks.
has a control block.

Each component of the model

The activity control block contains:
The addresses of the set-up and completion
phases of the algorithm expressing the
activity.
Variables which indicate the performer
time necessary for the current performance
and the performer time thus far spent upon
performance.
A busy:not-busy indicator to show an inprocess state of the activity.
The minimum, maximum, and current performer allocations.

STUDY OF BUSINESS INFORMATION SYSTEMS

6

Counters of the number of times the activity has been performed, of the amount of
performer time expended upon performance,
and of the amount of performer time spent
on idle for lack of fulfillment of necessary conditions.

Each cycle the time increment is multiplied
by the performer allocation of the activity to
produce an amount of performer-time. Performertime is then applied to the activity, resulting in
partial or multiple performances, or accumulation
of idle performer-time.

The addresses of the activity's input and
output queues.

The computer code necessary to perform certain common operations is contained in a coherent
group of over sixty subroutines. The performance
of a given service may require the operation of
several subroutines.

The activity performer control block contains:
A count of currently available performers.
The unit of this count is a function of
their separability.
A count of the number of activities to
which these performers are assignable.
A list of assignable activities wherein a
block for each activity indicates its
activity control block address, the
address of an algorithm for determining
the effective value of assigned performers,
and the current allocation.
A count of performers assigned to 'other'
activities than those in the list.
Transient information records may represent
bearers of information or physical entities. The
record is made up of a number of logical fields
sufficient to identify the entity in the context
of the system. A particular format may serve for
many records, and occasionally the same record may
appear in several queues. The control block identifies the format of the record.
The queue control block indicates:
The current count of waiting records.
A list of these records.

An indication of the order

in which the

records are held.
The ordered mix of SIMPAC macro expressions
and symbolic expressions is merged with the body
of the SIMPAC program and compiled by a generalpurpose compiler. The program produced is the
SIMPAC program supplemented by the particular
model. See figure 2.
Moving the Model Through Time
The basic SIMPAC program contains modules for
effecting operations called out by various macro
expressions and routines which handle the
mechanics of moving the model through time and
recordir~ its performance.
The model is moved through time by a cycling
routine which steps each activity by a fixed increment of time. The inc,rement is variable from
one rlli~ to another, however, and the scheme is
adaptable to varying the increment from cycle to
cycle as a function of predicted events.

Each of the SIMPAC subroutines performs some
particular service in one of the following areas:
initialization and production of exogenous events;
clock and calendar timekeeping; delayed transmission of records; queue manipulation; associative
storage control; raw data recording; data analysis
and output presentation; distribution sampling;
miscellaneous, including table-look-up, square
root, etc.
Familiarity with the routines is not required
of the user, merely familiarity with the macro
instructions and their usage.
(Each subroutine in the SIMPAC program is
consistent with conventions of modularity so that
portions of the program, and the associated macro
expressions, may be useful in the implementation
of information-processing systems unrelated to
simulation: e.g., the associative storage
mechanisms.
It is conceivable that the simulation of a
planned information-processing system might result
in the development in the model of activity algori thms directly transferable to the actual system.)
SIMPAC Associative Storage. The queue control block contains the addresses of the first and
last queue words, each of which contains a referent address of a transient record and the
address of the following queue word. Records
contain no link to other records in the same
queue. This indirect catenation permits multiple
concatenations of records without incurring redundancy of the information contained and avoids the
physical movement of records (see figure 3).
Queue words are each one word of computer
storage. Transient information records vary in
length with the number and size of logical fields
contained and are conjunctive.
SIMPAC contains a device to enable the sharing of available storage by queue words and
transaction records, thus eliminating arbitrary
limits upon queue lengths. The device is as
follCtllS:

An initial associative allocation of 1, 2,
3, ... n word blocks is made to push-dmm/
pop-up lists; n is a multiple of all
smaller blocks, and most available stor~~e
is allocated to n word blocks.

TOWARD A GENERAL SI\1ULATION CAPABILITY

Free blocks are made available and returned by macro instructions.
Automatic communication with a storage
banker routine is established "'Then a control word of a push-down/pop-up list
indicates no more blocks are available.
The storage banker diverts n word blocks
to 1, 2, 3, ... word blocks as needed, or,
in a second mode (when n word blocks are
exhausted) builds larger blocks from
available conjunctive smaller blocks.
This operation consumes little computer time
(with the exception of mode 2 of the storage
banker which involves tape movement) and provides
great flexibility of storage utilization.
Although records in a queue are not conjunctive, they are recorded on tape as a continuous
record.

7

This is a fairly general flworld view" and, as
a result, SIMPAC is a fairly general simulation
tool.
Muse is the name given to the project of
developing a simulation capability more general
and more efficient than SIMPAC. The name is appropriate in that simulation is a blend of art and
science, and several - if not nine - simulation
systems may be developed. These systems will be
developed with more regard for pure theoretical
considerations than was SIMPAC, whose development
was greatly influenced by immediate, practical
considerations. This is not to say that practical
considerations will be ignored; they will be
weighed, but the practical considerations will be
tomorrow's rather than today's.
Before introducing the special II world Vie1-1"
upon which Muse is based, several terms which have
been used throughout this paper are defined.
'Model' - 'A representation of an aggregate
of phenomena'

Output Presentation

'Symbol' - 'A representation of a phenomenon'

Before a simulation run is made, data recording parameters are fixed, which determine the raw
data which will be recorded as the model is moved
through time.
Available outputs are limited by the fund of
raw data made available by the recording routines.
The data which may be recorded are the content of
the three control blocks (queue, performer, and
activity) and the content of the transient records
in the queues.
After the simulation run, output listings are
produced in accordance with list requests phrased
with a small vocabulary of macro expressions. The
output phase of the program may be rerun as often
as desired, producing whatever listings might be
of interest.
Sample listings are shown in figure 4. 1 Time
series listings of selected variables, functions
of the series, and, as in the case of the listings
illustrated the particular contents of queues the discrete records, or summaries of the contents,
may be obtained.
Part 3: Muse

SIMPAC is prea1cated upon a Weltansicht which
recognizes systems as complexes of transient information, queues formed in the system's buffers
by transient information records, algorithms which
generate, use and destroy this information, and
performers of these algorithms.

~rom tests of
Mark I model.
put phase (SDC
Calif.: System
1961. 18 pp.

the Management Control Systems
See Patricia McKeever, SIMPAC outdocument FN-5256). Santa Monica,
Development Corporation, April 20,

'Simulation' -

'~JUamic representation of
dynamic phenomena'

'System' - 'A body of phenomena'
'Object system' - 'A system to be modeled;
the system under study'
A symbol is a representation of a unity, a
whole. A model is a representation of an entirety,
an aggregate whole. A sLuulation model is a
representation in time of an aggregate whole, a
representation of a dynamic, aggregate whole.
Mere aggregations of phenomena need not be systems
but may be modeled. An aggregation of phenomena
is a system if it forms an organic whole.
Weltansicht: there are things, and every
thing may be from time to time, in several logical
states. A logical situation is a particular
pattern of certain things in certain states. Multiple occurrences of similar things in similar
states may give rise to multiple occurrences of
similar logical patterns and thus multiplicities
of similar logical situations. Certain logical
situations invite the exertion of forces which
affect those things in the logical si t.uat.iorI,s;
destroying the situations. Thus things are
created, destroyed, and placed in different states.
this

The following definitions are adopted from
II wor ld view. II
'Logical situation' - 'A logical pattern
formed of certain things in certain
states'
'Total logical situation' - 'The logical
pattern formed of all things'
'Event' - 'A change in a logical situation'

STUDY OF BUSINESS INFORMATION SYSTEMS

8

1.3 FYlQ

'tvenement' - 'A change in total logical
situation'

=¢

QrlT = ¢
1.5 T()F s¢

1.4
'Unstable logical situation' - 'A l.s. which
invites the exertion of a force'
'Stable logical situation' - 'A l.s. which
does not invite the exertion of a
force'

1. 6

This definition of 'evenement,l does not
admit of simultaneous evenements. There may be
simultaneous events, but they produce but one
change in total logical situation.

1.7

'Q' - 'The class of logical situations'

Several simulation systems will be developed,
based upon these concepts. In all models constructed within these systems, things and thing/
states are represented by symbols, forces are
represented by algorithms, and logical situations
are represented by patterns of thing/state
symbols.

=

2'-

A thing is, or it is not.

cp~X

Explanation: The number of forces corresponds to the number of unstable total
logical situations and the number of
possible evenements, at most equal to
the number of total logical situations.

'F' - 'The class of forces'

'T' - 'The class of things'

X

Explanation:

Abbreviation:

For 'object system nt, IO,S'n'

An object system must be stated in simple
terms in Sl, due to 1.6.
Example.

In 0.8'1 there are 4 things, and 3

unstable logical situations.

(Recall there are no

thing/states in Sl.)

X = 16

Sl

1.6

A loose description of the first, and basic
system follows. The system, Sl, is predicated on
a simplified interpretation of the Weltansicht,
and is inchoate at this writing.

A number from a to 15 may be assigned to each
possible logical situation; thus:

Sl does not contemplate thing/states, only
things. Furthenmore, multiple occurrences of
similar things are precluded. A thing is, or is
not.

There are 3 unstable logical Situations, and
so three forces:

In later systems, multiple occurrences,
thing/states, and individual characteristics of
similar things will be contemplated.
In Sl, the following rules and definitions
hold for any object system.

1.0

F

= ff l ,

f 2 , f3, ••• ,f~)

Q

F

= r~,

= ff l ,

ql,···,q15 J

f2' f3}

Since the antecedent (unstable) and consequent (stable or unstable) logical situation for
each fi completely define each f , it is conveni
of

""""+ +,...

... - .........'"

of,:l 0 .... + of of',. of'
... ""' ................. J

of'
-1' -2'

of'
~.T"I +'h ,...., ..... .,. ... "1 r>
.."'" -3
..
..--..-.... -

0"",:1
~

-~

c:",'h_
~~~-

cripts identical to their respective antecedent
and consequent logical Situations; thus:

'~' - 'the number of forces; the
cardinal of F'

1.1

Q = (ql' ~, q3""'~}

'X' - 'the possible number of total
logical Situations; the cardinal of
Q'
1.2

T

= (tl ,

t 2 , t3, ••• ,tTl

'the number of thingsj the
cardinal of T'
ITI

-

Inspection of this statement of F makes
possible identification of a set of sequences of
total logical Situations, or states, of O,S'l'

{(l, 3, 8), (4, 6)}
It is clear that if O,S'l is ever in state 1
it will proceed to state

state other than 1, 3, or

~'Evenement"

French for 'event', is used to
connote something more comprehensive than an
event.

8 and remain there; and

it is equally clear that if O,S'l is ever in a

4, it will remain there.

Sl, upon examination, is a very simple system,
AnalYSis of an object system is an almost trivial
task.

TOWARD A GENERAL SIMULATION CAPABILITY

9

This simplicity is its virtue. For if more
sophisticated systems (Sn) are developed whose
statement may be transformed to Sl statement, the
problem of system analysis will be greatly simplified. Algori tbms can be programmed which perform
model analysis.
The eventual scheme of operation might be as
follows:
1.

Statements concerning O,S'i in Sn.
modeler.

By a

2.

Synthesis of a model of O,S'i in Sn.

3.

Transformation of the Sn model to an Sl
model.

4.

Analysis of the Sl model.

5.

Translation of the Sl model analysis to
statements about the Sn model.

6.

Presentation of the analysis to the
modeler.

7. Possible revision of the Sn model and
repetition of steps 1 through 6.
8.

Simulation runs of the Sn model.

9.

Presentation of simulation results to the
modeler.

Figure 5 is an example of what a simulation
model in S2 or S3 might look like. upon transformation to Sl, ambiguities and inconsistencies
in such a model become identifiable. The possible
terminal states, as functions of initial states,
may be deducible.
Within the syntax exe~lified in figure 5,
quite co~lex statements may be written. These
statements may refer to individual characteristics
of things, states, and logical situations. For
example, duration time may be determined by a
formula containing occurrences of variables which
are functions of individual characteristics of
things occurring in the antecedent logical situation formula.
Summary. Muse is intended to provide a
system of analysis, modeling, and simulation which
will reserve to the student of systems the functions he alone may fulfill and which will delegate
as much as possible to machine. By delegating
deduction to machines and reserving premise and
hypothesis statement to humans, we expect to be
able to study the simulated behavior of very large,
very complex systems.

I-'

o

Place in
Stack

Return Bin

Read Book

HB
Visitors

Clerk

1,J

Genera te
Requests
for Books
---Visitors

J

..
RF B

r

Examine
Requests

oF

~;----------~

Find
Requested
Book in Stack
B

Found Bir=:>

UB
Out Bin

Clerk

Librarian

U 0 B

Transient Information Reeords

Activity Performers

oF

Clerks
Librarian
Visitors

R
R
S
U
U

B
F
B
B
0

B Order for Book
Read Book
B Request for Book
Stacked Book
Unread Book
B Unfilled Order fcr' Book

tr.I

t-i

c:::

~
o>-:rj
~

c:::
tr.I

Z

LIBRARY SYSTEM

I:'%j
tr.I
tr.I

....Z
>-:rj

FIGURE 1

o

::0
~

>

t-i

6
z

tr.I

-<

tr.I

t-i

I:'%j

~

tr.I

>-l

~
~

ij

>

otrl

,Z

trl

~

L'

~

....

~

c::::

~

>-l

Exogenous
Events

o

New or Changed
Model Components,
Cycler and
Recording Controls

%

Output
Requests

&?

~

to

r::

S

Initializatio

Simulation

Data Analysis

Time
Series
and
Functions

OPERATION OF THE SIMPAC FROGRAM
FIGURE 2

~
~

.....

t-o

:First
Count

,

Discipline

,,'"

Last

.,~

Queue Control Block

en
....,
c::

/~

I

I

t:l
~

o"'!j

4'

t:P

c::
en

Link Word

Z
t-t1
en
en

Z
>:tj

o~
~

>
....,

Transient Information Record

oz
en
~
en
....,

FIGURE 3

SIMPAC Associative Storage

t-t1
~
en

13

TOWARD A GENERAL SIMULATION CAPABILITY

~'\

c c::

·;~E

Cl.

~!

F!'. E

REFERENCE

FR:9CD
-1
1

~~~~'_T~ME~.~SE~G~~~f~N~C:E__________________----~L~I;S~T--~~~~.~----I_'_"~

~

--....~

~ :~::".'" ............0:: ............... ~:W........\ ~;.:~.=-~~=.=.:~~~.~=. :. . . . . ~. .:~. ~. '~)

.,...,)'1"

or ~ I'F
2?:?C,r,0
2?56.r.r:r:.

?:?SC·.('(O
?7C_· J',r,}

?"?SJ:<:-G

? 7"? . cer:.
?:.76.(·CO

?".J:.I~CC;
?S~,:.r,rO

'Z:..C?

'Z-l? . (,C'r,
2=7(.Cr:O

:::~!N; cr

VARI!1l.ES SJ'PRESSED. rucrlOlS au.

.,
.000,

::~

::i:
::i:

I

.orJC

184 7 .15f
46.594
139.781
139.781
139.'81
.000
.000

14

lR~
18.428
ZO.OOO
1.222

U lRN&CTICNS
11.000

!t.UJ
2J.000

1.192
U~IOCS

19.000
2J..l.
24.000

1.974

.001

~

,.".

1!:i:
!:i:
1::i:

38.000

25.000

~:u4
30.321
7.73'
... INTERVAI.. SrD !lEV

.000
.000

ZO.OOO

~:i:

23.000
23.000

1880.000
.000
.000

.000
.000
.000
.000

~~If'S5597.'750
roo

0001

YM

,

J

~

.000
.000

:~~

1376.000
137f,.000
1376.000
137f,.000
.000
.000
1032.000
.OOG
.000

.000
.000
.000
.000
.000
.000
.000
.000
344.000
1376.000
1376.000

1465.000

.000

137 6.orJO

1881.875

.000
.000
.000
.000

1376.000
.000
000
2752.000
2752.000
2752.000
2752.000

H65.000

• .).).)
!672.0n

4364.000

m.m
1465.000
nO'."7
5236.000
1184.987

5236.000
1150.190

•

/____~.ooo 'IOTAl..104IiERcrTIIANSACTIOISINQ.£\E.

PAIiE.
QTY

::~

::~

4.000

4.000
0.000

,000
52f ... ,Yk), the magnitude
is defined by /'YI = (Y1 2 + y22 +... + Yk 2}1/2.
Norm. A measure which is not strictly the
vector magnitude as defined above, but is ordinarily easier to calculate. In the case of vector

== l'il

(Yl' Y2"'" Yk) the norm is defined by {V}
/Yk\' In any case, 1~ {YV/yI~k1

+ IY2 1 +... +

.

Unitize. To change the magnitude of a
vector to unity without changing the ratios of
components. If vector magnitude is used for
this purpose, the unitized components are defined by ~ == Yu/
If the vector norm is
used, the unitized components are defined by

IYI.

Yu=Y u

={y}.

Some Methods of Nonlinear Programming
With the help of the foregoing nomenclature, we
are in a position to describe some methods used
in nonlinear programming. Allusions to some of
these techniques are already in the literature
of optimization, and useful bases for the development of general nonlinear methods have long been
available. However, only two basic methods
have been developed sufficiently for wide use
in systems that have nonlinear constraints as well
as nonlinear objective functions.
In order not to lengthen this paper, we offer only
a brief description of these methods. The literature references should be useful to those desiring more information about particular techniques.

17

Analytical Method
Use elementary calculus and algebra to determine all proper maxima possessed by the objective function. The highest of these maxima
may be the solution, if feasible. Next determine
constrained local maxima subject to each of the
constraints and bounds (Lagrange's method of indeterminate multipliers is convenient for this).
The highest of these may be the solution, if
feasible and not surpassed in the earlier calculations. Next, do the same for local maxima
subject to pairs of constraints or bounds. Note
that there are (2K + q). (2K + q-l)/2 such pairs.
Continue in this way until all local maxima on
groups of constraints or bounds have been isolated. Then select the .global maximum. Some of
the mathematics required in this method may be
found in the literature. 9, 11
Grid Method
Space Yu values at reasonable intervals for each
variable (e. g., divide the entire range of each
variable into ten parts). Calculate F at each
feasible member of the (j1 + 1) (j2 + 1) ... (jk + I)
resulting grid points (where ju is the number of
intervals for variable yu)' Designate the point
with the highe st F value as the "fir st solution. "
If more precision is required, explore the vicinity of the first solution on a finer mesh than
before (or else apply some interpolation device,
such as a second-degree I!hypersurface"). Continue this until satisfactory precision is obtained.
Check the solution by making gradient or gradient-projection excursions. To reduce computing
time when using this method, eliminate protions
of the grid whenever possible by considering
analytical properties of the constraints. This is
sometimes called the "case study" method in
design work.
Monte Carlo Methods
Use a random number table (or generator) to
select a point in the bounded region. Retain this
point if feasible, and calculate its F. Repeat for
another random point. Retain the new point if
its F is higher than that of the old point. Continue in this way for a predetermined number of
points (calculated from statistical considerations
to give a preset confidence level). The last retained point is taken as an approximate solution.
Check this solution by making gradient or gradient-projection excur sions.
A variation of this method use s the retained
point as a start for the next move. Then the
direction of the move is determined at random,
but the magnitude is fixed. If a certain number
of moves does not produce an improvement, the
magnitude of the move is decreased. Brooks2

18

discusses some of the possibilities of these
methods.
Cross-Section or Univariate Method
With fixed starting values of Y2' Y3"'" YR'
vary Yl by preselected steps, spanning its range.
At each point, calculate F if feasible. Select the
best F so far and set the corresponding value of
YI' Then vary Y2 in the same way, and set Y2
according to the best feasible point so far. Continue in this way until a complete cycle produce s
no further change in F. As with the grid method,
a finer mesh may be introduced after the final
approximation is achieved. As usual, the solution must be checked by making eradient or
gradient-projection excur sions.
Blocking Methods
Consider the pos sibility of reducing the region
to be examined, in a systematic rather than a
random manner (d. Monte Carlo Methods). The
general idea is to eliminate about half of the
bounded region of coordinate space at each step.
These methods may be satisfactory for a small
number of variables, but they become unmanageable for a large number of variables because the
procedure requires a knowledge of the objective
function and of the constraint functions for at
least the "corners" of the region to be eliminated.
In a region with k major variables, there are 2k
such corners. For k = 20, this number is more
than one million.
Gradient Projection Method
From a feasible starting point, follow the gradient until stopped by a constraint. Follow this
constraint, via gradient projections on tangent
hyperplanes, until stopped by another constraint.
Then follow the two constraints, via gradient
projections on intersections of tangent hyperplanes, until stopped by a constraint. Follow
this constraint, via gradient projections on tangent hyperplanes, until stopped by another constraint. Continue in this way until "cornered"
(at a constrained maximum) or stopped by a zero
gradient or gradient projection (at a proper maximum or partially constrained maximum). Check
the final calculated point to see whether it is a
solution. Due to the use of tangents to approximate constraints, it will sometimes be necessary
to return to the feasible region when a calculated
step has led to a nonfeasible point. This is done
by an interpolation procedure. 8
Probe Methods
With preselected step sizes for all variables,
make excursions from a feasible point, in directions of increasing and decreasing Yu' The first
successful excursion (feasible point with improved F) determines the next point on the course,

STUDY OF BUSINESS INFORMATION SYSTEMS

and this point becomes a nucleus for further
probing. Continue the course until no improved
feasible point is achieved, due perhaps to approaching a constraint. A technique for following constraints is described in the section on
Subprogram EDGE, later in this paper.' When
a course terminates away from all bounds and
constraints, a nearby solution is indicated.
When the appropriate procedures have failed to
produce any advance, it is time to decrease the
step size and repeat the entire procedure. Mter
repeated reductions, the step size falls below
some tolerance, and the calculation stops, indicating a solution. The calculated solution is to
be checked via gradient or gradient-projection
calculations, provided that it is possible and
practical to calculate derivatives of the objective
and constraint functions.
A number of practical variations of the method
just outlined are possible. One of these involves
resetting the probe point to a bound whenever
such a bound is crossed in probing. Another
involves persisting with probes in a favorable
direction, once such a direction is established.
Another consists in designating certain variables
as "discrete, It in which case their increments
will be integer multiples of specified values
(usually unity), and the variables themselves
will take on only specified values {usually
integers}.
Figure 1 illustrates the general operations involved in a Probe program. The details are
discussed later.
Other Methods
Of course we should not, and do not, claim that
all methods of nonlinear programming have been
included in this summary. However, some
published methods l5 , 17 are so closely related
to linear programming that it is better to treat
them in publications on that subject. Other
methods 16 relate more specifically to special
classes of problems, for which the ultimate
solution depends on such methods as we have
already considered.
Comparisons. Experience with actual
programming and problem solving, using the
methods described above, has indicated that
either the Gradient Projection method or the
Probe method, or special combinations of these,
will prove most effective in attacking optimization problems which relate to evaluation, design,
or control of large systems.
Note at this point that, although some analogie s
do exist between Gradient methods and Probe
methods, essential differences also exist. For

A ~ONLINEAR DIGITAL OPTIMIZING PROGRAM FOR PROCESS CO:'lJ'TROL SYSTEMS

example, if the calculation of a derivative is not
possible or practical, the Gradient Projection
method cannot be used. On the other hand, if a
situation arises which demands only the most
rapid feasible advance, the Probe method is
ruled out.
Analytical procedures are rejected because of
the complications which would be encountered in
the usual control problem. Grid methods require
examination of too many !!cases!!; e. g., a rnillion
cases might be examined in solving a three-variable problem with a solution tolerance of 1% of
the range. Blocking methods are similarly
cumbersome. Monte Carlo methods may be useful for finding a solution, but in the usual form
they do not give information about the nature of
conditions close to the solution: such conditions
may be of considerable interest in a control
problem. Cross-section methods and variations
of Gradient Projection, now under study by
others, 8, 12 may be found to be interchangeable
with the methods that we have stressed.
In this paper, details of structure and program
are presented for Probe methods only.
Optimizing Subprograms
In the preceding section, general features of
Probe techniques were outlined. We shall now
describe in detail the principal subroutines which
are incorporated in the final program to be considered later. This program is simple in concept and application, but gives indication of being
suitable for use with large and complicated problems. In the sections that follow, the entire
program will be elaborated in enough detail to
guide coding for a stored-program computer.
Subprogram PROBE, shown in flow form in Figure 2, contains the basic logic of the "probe"
and is operative as long as special local conditions (e. g., regions where the gradient changes
sharply within one step, or regions near constraints) do not intervene. The basic procedure
is as follows:

19

with a fixed step size, this operation is under the
control of Subprogram ORDER. But if the return
to Subprogram PROBE from RIDGE or EDGE
shows no improvement, it is time to halve the
step size. When the step size falls below some
preassigned tolerance, the calculation will be
halted under direction of the main program.
In Figure 3, which shows a simple two-dimensional (schematic) problem with two constraints, thi::> subprogram is illustrated by the
course SABDEF. Note that for this course the
preferred direction is changed at B (under control of Subprogram ORDER), where it is not
necessary to go into Subprogram EDGE; and
again at F, where it is necessary to go into
EDGE.
The use of a flag, Key 23, for this branching, is
illustrated in Figure 2. Another function of
Subprogram PROBE is to select the critical
points (high and low feasible and nonfeasible
alternates) to be used in Subprograms RIDGE
and EDGE if needed.
Subprogram RIDGE, shown in flow form in Figure 4, is designed to maintain progre s s with
large steps even in regions where the gradient
changes sharply within one step. Suppose that
probes from the nucleus (at full step size) have
failed to indicate an impending constraint, yet
have also failed to yield an improved point.
Then before reducing the step size, proceed
as follows: between the two highest-valued probe
points, evaluate the midpoint. Break out of the
subprogram if the midpoint is nonfeasible
(failure) or if it is feasible and higher than the
nucleus (success). Otherwise, use the evaluation toge'ther with a quadratic approximation to
estimate the maximum F between the critical
probe points. The equations for this estimate
are:
Y IR = (I - r) y IA

+ ry IB

y 2R = (I - r) y 2A + ry 2B
r = (FA - F B) /2 (2FM - FA - F B)'

With preselected step-sizes for all variables,
probe, in a preset order, from a feasible point
(nucleus) in the (positive and negative) directions
of the basic variables. Desist as soon as a higher-valued feasible point is found; use this point
as a new nucleus. When the probes on all variables fail to produce an improvement, go into
Subprogram RIDGE, unless some probe point
was nonfeasible; in that case go into Subprogram
EDGE. Subprograms RIDGE and EDGE are discus sed later.
If progress is made for several (e. g., 4) steps

Here y I and Y2 repre sent the variable s involved
in probes that produce the highest feasible point
(A) and the next-highest feasible point (B); F is
the objective function; M represents the midpoint
between A and B; and r is a parameter used in
calculating the approximate maximum or "ridge"
point between A and B. This calculation is in
part based on a quadratic approximation of the
objective function on the ridge.
Figure 5 illustrates a course in which Subprogram
RIDGE is effective in using the midpoint for

20
several steps (SCFJ), then fails at the midpoint
(N) but succeeds at the quadratic approximation
(P).

Subprograni EDGE, shown in flow form in Figure
6, directs procedure after a constraint (or a
confluence of constraints) is sensed (Key 23 = 3).
It directs the course of computation so as to
"follow" the "nearest" constraint, unless improvement can be made in a direction away from
the constraint. An outline of procedure follows.
Since at least one of the probe points is nonfeasible and all probe points one step-size away have
been evaluated (otherwise we would not be in
EDGE), information is available to classify
highest-valued and lowest-valued feasible and
nonfeasible points. The classification may be
represented as follows:
Nonfeasible
Feasible
HN
Highest
HF
LF
LN
Lowest
Now, first test the midpoint between HF and HN.
If feasible, evaluate. If not better than the
nucleus, replace HF by the new point. Then
proceed similarly with LF and LN. Repeat the
procedure using HF and HN, as well as the procedure using LF and LN, at least four times before concluding that a revised choice of critical
points is required. Then combine the first- and
second-choice points according to the schedule
shown at the upper right in Figure 6, under control of flag K3. As usual, break out of the subprogram as soon as a point better than the nucleus is discovered.
In Figure 3, the combined use of Subprograms
PROBE and EDGE is illustrated by the course
FKLPWX. In this schematic example, the need
fur ::;tep-:;;iz.e reductiun due::. nut uccur until the
last step (which also involves resetting to a
bound).
For a single nearly linear constraint, as in the
diagram at the right of Figure 6, this procedure
must produce a point (such as L or H) which is
better than the nucleus and feasible, provided
that the value function is also nearly linear and
that we are not already at the optimum. (As a
matter of theoretical interest, this statement can
be proved for a number of variables and for more
general conditions than those implied here. )
Although these conditions may seem very restrictive, they commonly occur in practice, with
the result that Subprogram EDGE is very useful.
The approximation to linearity, of course, improves at sma11 step-size.
Subprogram ORDER, shown in flow form in

STUDY OF BUSINESS INFORMATION SYSTEMS

Figure 7, reorders the probe array JORD and the
constraint-calculating order array JCON when
needed in the interests of efficiency. The procedure used in probing is to bring the successful probe to the head of the list, and to remo"~"e
its complement to the end. For example, if the
probe order has been-3, +2, +1, -1, -2, +3,
and a successful probe is made on the fourth
trial (-I), the new probe order becomes -1, -3,
+2, -2, + 3, + 1. The array JCON is adjusted
according to a tally of the number of times that
individual constraints have been calculated negative during the course of a major cycle. The
largest frequency NC(K) determines the first
C(K) to be calculated in sequence, the next largest
NC(K) determines the next C(K}, and so on. This
eliminates superfluous calculations of constraints
likely to be positive, when a negative one is
sought. For a feasible point, the complete set
of constraints must be calculated in any case;
then the order is unimportant and will be left
unchanged.
Main Probe Program and Subroutines
The main program is shown in flow form in Figure 8. In addition to connecting the subprograms
and doing the necessary initializing, finalizing,
and branching, the main program also calls the
subroutines which define the problem. Such subroutines are defined in the following paragraphs.
General restrictions on formulation of problems
are also presented following the description of
the subprograms.
Problem Subroutines. The subroutines
that define the problem are briefly described as
follows:
1. ENTER. The optimization program will call
ENTER only at the start of the calculation. Accurdingly, Lhi::; ::;uuruuiine ::;huuld include all the
one-time operations required to set up the calculation. It will set the values of KY, Y, YL,
YH, and KC, normally by means of a data-load.
It may set an initial value for STEP, and values
for STEND and D. Although these are not essential (being calculable as fixed fractions of the
ranges of variables), a proper selection may
shorten the program running time. If discrete
variables are to be used, ENTER must set the
MQD values accordingly. ENTER can also be
used to load other data or parameters, perform
initial calculations, or provide an initial
printout.
2. SAVE. This subroutine is the fir st one called by the optimization program after it changes
the Y(I) values. To eliminate duplicate programs, calculations should be included here that
are common to several constraint functions, or

21

A NONLINEAR DIGITAL OPTIMIZING PROGRAM FOR PROCESS CONTROL SYSTEMS

common to the objective function and to some
constraint functions. Calculations which pertain
to the objective function alone, or to only one or
two constraint functions, ordinarily are omitted
from SAVE.
3. OBJECT. This subroutine sets VAL equal
to the value of the objective function at the specified set of Y(I). The subroutine can as sume that
SAVE results are consistent with the assigned
Y(I)' s, but must not use any results from FENCE,
since they may be inconsistent. Results reported
as VAL at successive points should represent a
single-valued function of the variables, and
should not vary randomly because of convergence
and roundoff errors. If such variations occur
in the last few digits of a calculated objective
function, they should be dropped before reporting
the value as VAL.
4. FENCE. This subroutine must set C(JC)
equal to the value of the constraint function for
the stored index JC, at the specified set of Y(I).
The subroutine can assume that SAVE results
are consistent with the assigned Y(I)' s, but must
not use any results from OBJECT, nor those
from FENCE for any other value of JC.
5. FOUL. If all C(I) values are positive or zero
at the initial set of Y(I) values, this subroutine
will not be used. However, if any C(I) is negative
at the start, it is recognized as nonfeasible.
The optimization program will attempt to find
a feasible start, without regard to the objective
function. After each unsuccessful try, it will
call FOUL. If the programmer wishes to follow
the results of these trials, he can program FOUL
to print out pertinent re suIts calculated by SAVE
and FENCE. Once a feasible point is reached,
OBJECT will be called. Thereafter, nonfeasible
points are treated as intermediate results with
no special provision for publishing. If the optimization program concludes without finding a
feasible point, it will set KERR = -1 and call
FINISH to terminate the calculations.
6. FAIR. This subroutine is called each time
a ne"\T/ nucleus is established. Thus the program=
mer can use FAIR to publish results of interest
for moves (points along the path to the optimum).
When de sired, FAIR can include machine options
to bypass the publication. Moreover, a short
testing routine at the start of FAIR can limit the
points published to insure that each published
VAL exceeds the previously published VAL by
some specified increment. Since FAIR may be
called several hundred times in a typical optimization, some limitation on either the points
published or the length of publication per point
is desirable.

In some calculations, the desired optimum may
actually be set in advance. For example, in
using an optimization technique to solve simultaneous nonlinear equations, the objective
function starts as a large negative number and
gradually approaches zero. In such calculations,
the programmer may wish to conclude the run
as soon as VAL approaches the known optimum
closely enough.

7. FINISH. This subroutine is called at the
conclusion of the optimization, for any of the
following reasons:
a. The optimization program or one of its subroutines declares an answer;
b. an error is indicated;
c. no feasible start is found; or
d. the machine is required for another problem.
The programmer
final calculations
detailed results.
be used to switch
FINISH.

can use FINISH to perform any
at the optimum and to publish
If desired, the error flag can
to a diagnostic routine within

General Restrictions. The programmer
should keep in mind the following restrictions.
1. The objective function, all constraint functions' and any intermediate variables used in
their calculations should be single-valued, real,
and calculable for any set of Y's with YL(I) ~ Y(I)
~YH(I) for all 1.
Discontinuous functions are not
ruled out, but should be subject to careful scrutiny during the course of the calculation. In some
case s it will be advisable to introduce an arbitrary function for the slope of a, discontinuous
variable, or to provide arbitrary (negative)
values for constraint functions and an arbitrary
(large negative) value for the objective function
at the discontinuity.

2. The subroutines must provide easy access to
the values of Y, YL, YH, C, KY, KC, JC, VAL,
KERR, STEP,STEND, D, MQD. (In FORTRAN
coding, this can be done by carrying these in the
+!_.-.+

rr\7.,K'?tJfr\1\T

,....1..-..1.. _ _ _ _ _ "'-

-L.L.1. O\..

V\.../.lVJ.J.V.l\...l.i.'1

OI,a.L..Cl..llt=:l.lL..

3. Subroutines SAVE, OBJECT, FENCE, FOUL,
and FAIR must not alter any of the above listed
values, except that OBJECT must set VAL,
FENCE must set C(JC), and any subroutine may
set KERR to an appropriate value if an error is
detected.
4. Adequate permanent storage must be provided for all of the above quanti tie s so that they are
always present, even though the subroutines may
be moved about or altered. (In FORTRAN coding,

22
this can be achieved with suitable COMMON and
DIMENSION statements. )
5. Limitations of the Probe Method. As indicated before, this Probe method does not pm"port
to be a "univer sal" optimizer, although it has
important advantages. As is true of all optimization programs known to the author, it is possible
to construct problems which will defeat the program. It is even expected that such problems
will arise in a practical setting, although none
such has yet come to our attention. For this
reason, a careful examination of calculated results is always required, from a mathematical
as well as an engineering standpoint.
In case the result obtained is a local maximum
and not a global maximum, even the careful
terminal examination is of no avail. As Rosen 8
indicates, no better way of achieving the global
maximum is yet known than that of proceeding
from several different starting points. These
starting points may be selected by a Monte Carlo
procedure, or by more rational means if the
problem is familiar to the programmer.
We note that there may be "pathological" features
of value functions and constraint functions capable
of defeating optimizer s. Analysis of such
feature s is outside the scope of this report.
They are generally associated with discontinuities
in derivatives of the value function or constraint
functions. These give rise to "essential nonlinearities" which render the reduction of stepsize futile as a mode of escaping from an unsatisfactory point in the calculation. An important exception is the case of a discrete independent variable; even though such a variable
introduces essential nonlinearities, it does not
defeat the Probe method.

STUDY OF BUSINESS INFORMATION SYSTEMS

not test for a global maximum but only for a local
maximum. In a problem which cannot be solved
analytically, the probability of achieving a global
optimum might be increased by solving the problem a number of times, using a different starting point each time.
A satisfactory criterion of "efficient" solution is
not so easily established. However, in order
to have some kind of indication, we suggest that
a solution be judged inefficient, if, in the cour se
of it, some constraint, or the objective function,
is calculated more than n e = k S log2 R max times,
where 15 is the number of major variables, Ru is
the range of a basic variable divided by the final
tolerance on that variable and Rmax is the greatest of the Ru'
Study of Tables 1, 2, and 3 sho,",vs that the pro~
gram achieved "successful" solutions of each
problem. Except in two extreme cases (B-2 and
B-3), the method is "efficient" by our criterion
(with s = 3, an arbitrary but probably reasonable
value). Of course, these results are merely
illustrative of the possibilities of the PROBE
program. Peculiarities of a given problem,
selection of a starting point, and choice of initial
step sizes and final tolerances may alter the
efficiency even on the same problem. Nevertheless, the PROBE program has performed well on
a wide variety of nonlinear problems, including
a "refinery simulationt! with ten variable sand
seventeen constraints 10. Therefore, this method
is recommended for further application to nonlinear problems (including control problems),
especially when complicated nonlinear constraints
are present.

6. Examples and Criteria for Numerical Testing.
Problems of different degrees of complexity have
been used to test the Probe program. The list
includes synthetic test problems, practical design problems, and the solution of algebraic
systems (simultaneous equations, curve fitting,
and rational approximation).
For the pre sent report, three te st problems are
selected and tabulated (Tables 1, 2, and 3) merely
to give the reader some indication of the relations
between problem data and program parameters.
A satisfactory criterion of "successful" solution
is easily established. The criterion (as suggested
earlier) is as follows: Within the preset tolerance, an excur sion along the gradient or gradient
projection should produce no better solution than
that already obtained. This, of course, does

Summary of Problem A

O~Yi~3(i=l,

l, 3,4)

C 1 = 3-YI-Y2-Y3-Y4~ 0

i

I

I

!

Test,

Yo

Starting
Values
Fo ! (0

i
Ye

Solution
Fe
I

Se

!EfrtcienCY i
Criterion Tallies
R I ne ! ne1 nf

A-l

0.50
0.50
0.50
0.50

3.125

0.10
0.10
0.10
0.10

0.6586
1.6703
0.0000
0.0000

5.433 10.00211500
i 0 • 002 I l500

A-2

0.5?

3.750

0.10

?~5~
.. ov7v,.,l

5.433

"

, "

0.0000
0.0000

0.6586
1.6703
0.0000
0.0000

I g:gg~ I

~~gg

i 675

("I,

0 002
1 •
5.433 : 0.002
i 0.002
1 0 . 002
i 0.002

C
.,.,00
1500
1500

."'\

1500
1500
1500
1500

360

320
460

360

~65

i

i,0.002 I 1500!I 675
"" .002
0.002

318

A NONLINEAR DIGITAL OPTIMIZING PROGRAM FOR PROCESS CONTROL SYSTEMS

23
Nomenclature, Part 1

Note: The first part of this table defines symbols used in the descriptive
part of the text. The second part defines FORTRAN expressions
which have been used on the flow charts and also in coding the
program.

Summary of Problem B

B
CI

=

I - YI - Y2 /I 00 ~ 0

C

=

1- [(Y2- 1)/100]2-

C

2

I

3

B-1

0. 540

?o

Fe

7e

i'e

0."01 21192.5
".85 I 10.01
o.S9981 >.26'" 0.0002
0.02
t

go.oo

17477.5

0.60
30.00

0.540

i

199.15

0.06

I 211 .85 0.9Ooo! 1.2608
I 727.5
242.5 I 10.00
199.18

i

go.OO

R

0.10
0.8999 1.2605 0 .• 0002 5000
10.01
0.02
3.00
4250
0.06
2500
9.00 I 199.15

1

i

0.60
30.00

B_3 b

Eft'1c1ency
Cr1ter1on

Solut1on

I

Fo

00.60
30.00
90.00

B_2 a

(Y3/200)2~0

Starting
Valuell

-Yo

Test

B

u

Upper and lower bound functions, y': -Yu and Yu- Yu-

C.

Constraint function.

F

Objective or value function.

HF, LF,
HN, LN

Designations of highest, lowest, feasible, nonfeasible
points in !!cunst:ralnt ' ! subprogram.

K'

Proportionality constant.

k

Number of basic variables.

1

Y3/200~0

= -I + Y +

+
u

~()OOOO

Tallies

ne

net

nf

332

358
212
212

219

6110
330
413

323!

734
380
435

3971

511

74000
332500

0.0002 500000
0.0020 1170000
0.0059 330500

511

n.

Tally on constraint function calculations.

n

Efficiency criterion, k

Cl

s

i

I

n

e
f

log2 Rmax'

Tally on value function calculations.

p

Gradient projection vector.

q

Number of constraint functions.
Parameter used in subprogram RIDGE.

a

Upper bound of each variable increased IOO-fold for this test

Ratio of range of y u to tolerance on y u'
b Upper bound of YI increased 100-fold; Y2 and Y3 increased 10-fold

R

max

Largest Ru'
Upper bound for y u'
Lower bound for y u'
Independent or basic variable"

Summary of Problem C
y
F =

52.909653- (YI- 0.5 Y2- 1. 0)2 -

2 (Y2- 2.04 YI

+

2. 072) 2_

ou

3(Y3- 2 YI + 2.2)2_.4 (Y - 0.13 Y3- 1.618)2_ 5(Y - 1.5 Y3
I
2

O::!Oy.~2
1

C
C

(i = 1,2,3).
2
2
+ Y2
I

=

z

= (Y I

5.80- (Y

Test! Yo
C_O c 0.00
0.00
0.00

Fo
10.00

C_l d

10.00

C-2

e

t

I
1

C-3

r

1.6)2 + (Y 2

g:gg

10.00

3

0 • 00

10.00
0.00
0.00

10.00

)~O.

Subscripts

I. 5)2_

0.07~O.

0.10
0.10
0.10

Ye
1.800
1.600
1.400

Fe
52.910

0.10
0.10
0.10

1.673
1.246
1.200

0.10
0.10
0.10
0.10
0.10
0.10

o

Initial conditions.

e

Final conditions.

Efficiency
Criterion Tall1es

Solution

fo

I

2

+Y

Start1ng
Values

0.00
0.00
0.00

u

2

Tolerance on first basic variable.

I

!

Basic step length for y u'
Set of all 6 •

+ 0.5)2 - 6 (Y - 0.196 Y - I. 0864)2
3

Operating vector (y I' Y2' ... 'Yk)'

,fe

Xorr.l'nclatur...:, Part 2

R

ne
296

0.001
0.001
0.001

2000
2000
2000

52.725

0.001
0.001
0.001

2000
2000
2000

296

1.675
1.246
1.200

52.724

0.001
0.001
0.001

2000
2000
2000

296

1.677
1.247
1.196

52.723

0.001
0.001
0.001

2000
2000
2000

290

nc1

--

BIG

o

325

C(K)
D(K)
DIN(K)
DORD(K)
EDGE

2 0
5
220

207

ENTER

264

FAIR
FENCE
FINISH

i'i
I

nf
230

1

con~trd.intl:i.

-

290
280
260

FOUL
No constraints in effect.

Constraint C I in effect.
Constraints C

and C in effect.
I
2
All constraints in effect.

Number beyond expected range of any variable (as 1030).
Constraint (bnction of Y).
Initial increments for Y(K).
Array for history of step sizes.
Signed probe length, K ranging from I to KY2.
Subroutine for 11follov.ri.ng tl a constraint or confluence of

JA
JAR(K)
JC
JCON(K)
JORD(K)

Subroutine for pablishing problem data and making initial
calculations.
Subroutine for pllblishing feasible advance.
Subroutine for calculating constraints.
Subroutine for publishing solution and making terminal
calculations.
Subroutine for publishing nonfeasible advance when seeking
a feasible point.
Index number of basic variable y(I).
JORD(I).
Variable affected in present probe.
Array of the eight subscripts for Y AR.
Number of specified constraint.
Order array for constraint calculations.
Order array for probes.

STUDY OF BUSINESS INFORMAnON SYSTEMS

24

Nomenclature, Part 2

KC
KERR
KEYC
KEY23
KORD
KVIOL
KY
KY2
MQD(K)
NC(K)
NCT(K)
NLIST
NP
NVAL
NVALT
OBJECT
ORDER
PROBE
RIDGE
SAVE
STEND
VAL
VALHFI,
etc.
VALS
Y(K)
YA
YAR(K)
YH(K)
YL(K)
YS

Number of constraints.
Error flag, numbered for statement which detects error,
or for selected types of errors.
I when seeking feasible point, otherwise 2.
2 to select Subprogram RIDGE, 3 to select Subprogram EDGE.
J, 200 or 300 in Subprogram PROBE, RIDGE, or EDGE on
SUCCEssful probe (other-.;..tisc 0).
I for nonfeasible, 2 for feasible point.
Number of basic variables.
KY + KY = range of JORD.
Array for discrete variables (MQD(K) = 0 if y(K) is a
continuous variable).
Tallies of constraint violations during major cycle.
Tallies of calculations for individual constraints.
Tally of listings (one per feasible advance).
Problem identification number.
Tally of VAL calculations during major cycle.
Tally of VAL calculations during complete problem.
Subroutine for calculating VAL.
Subprogram to set orders of probes and constraint calculations.
Principal probing subprogram.
Subprogram for "following" a "ridge".
Subroutine for calculating and storing quantities which will
be needed for VAL and/or C(K).
Final tolerance on step size for first variable.
Value function or objective function.
VAL at Y(JAR(I», etc.
Reference value of VAL
Basic variable.
Y(JA).
Array of the eight probes Y(JAR (1) ), etc.
for classification of critical probes.
Upper limit for Y(K).
Lower limit for Y(K).
Reference value of Y(JA).

See Figure 2

References

1.

2.
3.
4.
5.
6.
7.
8.

9.
.Lv.

II.
12.
13.
14.
15.

16.
17.

N. R. Amundson, American Institute of Chemical Engineers, Tenth
Annual Institute Lecture, Cincinnati, December, 1958.
S. H. Brooks, "A Discussion of Random Methods for Seeking Maxima, "
Operations Research, vol. 6, p. 244; 1958.
R. Dorfman, P. A. Samuelson, R. M. Solow, "Linear Programming
and Economic Analysis," McGraw-Hill, New York; 1958.
R. O. Ferguson, L. F. Sargent, "Linear Programming Fundamentals
and Applications," McGraw-Hill, New York; 1958.
S. I. Gass, "Linear Programming Methods and Applications," McGrawHill, New York; 1958.
Clifford Hildreth, "A Quadratic Programming Procedure, " Naval
Research Logistics Quarterly, vol. 4, p. 79; 1957.
A. S. Manne, "Scheduling of Petroleum Refinery Operations,"
Harv:..rd University Press, Cambridge; 1956.
J. B. Rosen, "The Gradient Projection Method for Nonlinear
Programming; Part I, Linear Constraints, " J. Soc. Industrial and
Applied Math, vol. 8, p. 181, March, 1960; "Part II, Nonlinear
Constraints, " to be published.
T. L. Saaty, "Mathematical Methods of Operations Research,"
McGraw-Hill, New York; 1959 .
E. Si.t"l.gt:1, "Si.fllulatlu(l a.nd Optl:l;'-l~ .... a.tiO.r, uf Oil Refinery Dcsi g i"'l, II
Shell Development Co., Publication P-839, Emeryville; 1959
I. S. Sokolinkoff, and E. S. Sokolinkoff, "Higher Mathematics for
Engineers and Physicists" (Second Ed.), McGraw-Hill, New York; 1941.
Henry Stone, Per sonal communication.
Philip Wolfe, "Computational Techniques for Nonlinear Programs, "
Princeton Conference on Linear Programming, March 13-15, 1957.
W. S. Dorn, "Non-Linear Programming," Research Report RC-266,
IBM Corp., Yorktown Heights, N. Y., May 24, 1960.
R. E. Gomory, "Outline of an Algorithm for Integer Solutions to
Linear Programs," Bulletin of the American Mathematical Society,
vol. 64, p, 275; 1958,
R. Bellman, "Dynamic Programming," Princeton University Press; 1957.
R. E. Griffith, R. A. Stewart, "A Non-linear Programming Technique
for the Optimization of Continuous Processing Sy-stems," Management
Science, vol. 7, p. 379; 1961.

A NONLINEAR DIGITAL OPTIMIZING PROGRAM FOR PROCESS CONTROL SYSTEMS

STARt

READ AND
CHECK DATA

25

MAKE PRELIMINARY
IF NEEDED, FIND
CALCULATIONS.
~----DI A FEASIBLE POINT
LI ST RESULTS
AN 0 PROCE ED
AND PROCEED

STORE Hi-LO,
FEASI BLENONFEASIBLE 1 0 - - - - - - 1
POINTS AND
ALTERNATIVES

GO TO PROBE ,SEEK
IMPROVED FEASIBLE
POINT WITHOUT
REDUCING STEP
SIZE

\
\

I
I

\

\
SOME
NONFEASIBLE

GO TO RIDGE,
SEEK I MPROVED
FEASIBLE POI NT,
USING HIGH AND
ALTERNATE
FEASIBLE POINTS

~

\
\

RESET TO
BOUNDS WHEN
REQUIRED

GO TO EDGE, SEEK
I MPROVED FEASIBLE
POINT, USING HI -LO
FEASIBLE NONFEASIBLE
POINTS AND
ALTERNATIVES

LIST POINT
AND PROCEED

GO TO ORDER,
REORDER PROBES
AND CONSTRAINTS;
PROCEED

NOT BELOW
TOLERANCE

LIST
RESULTS

Fig. 1 Probe method for nonlinear
constrained optimization

t----........j;)(

I NTERUPT,
STOP, OR
RELOAD

26

STUDY OF BUSINESS INFORMATION SYSTEMS

START

INITIALIZE
VALH'S AT-co
VALL'S AT+co
KEY 23 2,
I =I

SUBSCRIPTS FOR
CRITI CAL PROBES

=

I
2
3
4

SELECT AND
SAVE VARIABLE
OF PRESENT
PROBE Y(J).
INCREASE OR
DECREASE AS
REQUIRED.

5
6
7
8

* SPECIAL
PROCEDURE FOR
DISCRETE VARIABLE IS

*

ACTIVATED BY MQD

TEST BOUND
RESET TO
BOUND IF NEEDED

~

,----------It>!

I

UPGRADE
HF2 , t!£.J;
IF VALLF I
OR VALLF2=co
UPGRADE
LFI OR LF2

COMPUTE
CONSTRAI NTS
AND TEST.

SET
KEY 23

~

HFI
HF2
LFI
LF2
HN I
HN2
LN I
LN2

UPGRADE
HF2, HFI ;
IF VALLN I
OR VALLN 2 =00,
UPGRADE
b!:!.1 OR ~

Fig. 2 Subprogram PROBE

RESTORE

~

I
I

A NONLINEAR DIGITAL OPTIMIZING PROGRAM FOR PROCESS

CO~TROL

, F=4
I
I
Q,

SYSTEMS

,
\

\
I

CONSTRAINT
C2 (YIIY2)=O

27

BOUND
Vt- Y1=O

,

----+-----------------------~~--+----BOUND

Y2- V2-=O

Fig. 3 Operation of subprograms
PROBE and EDGE

28

STUDY OF BUSINESS INFORMATION SYSTEMS

START

COMPUTE
MIDPOINT

COMPUTE ALL
CONSTRAINTS

I
COMPUTE

VAL=
LEAST C(K)

IQ------\

INITIALIZE
KSW 2=0

1-----01

COMPUTE
CONSTRAINTS.
TEST

CALL
OBJECT.
CALCULATE

VAL.

SET
KSW2
~

SET
KORD

= 200

1---------+----01

l
Fig. 4 Subprogram RIDGE

APPROXIMATE TO
PARABOLIC MAXIMUM.
Y(JAI)= (I.O-RISE)
Y(JAI) + RISE
YAR (I).
ETC_
.

*

*

I

A NONLINEAR DIGITAL OPTIMIZING PROGRAM FOR PROCESS CONTROL SYSTEMS

29

Y(2)

F=3
F=4

--+-------------------~

Fig. 5

Operation of subprograms
PROBE and RIDGE

YO

,

/

LN
(D)

/

C=O
/C

Navigation menu