This book made available by the Internet Archive.

ABSTRACT

XML is a language for describing linear-programming models to computer systems. Parts I and II of this report together comprise a full syntactic and semantic specification of XML. Several extended examples of XML models are given in Part III.

XML's purpose and structure are also set forth in general terms in

"A Modern Approach to Computer Systems for Linear Programming" by Fourer

and Harrison (MIT Sloan School Working Paper 988-78).

?*s r-^ A- cS Cj c^-^

6.1 Definition 31

6.2 JndQ.XA.ng-aniXs 32

6.3 lnde.xA.ng-e,xpfLU6lons 33

6.A Determining the index set 33

6.5 Representing index items by IndCK-ncuvzs 35

6.6 Evaluation with respect to an index 37

6.7 Scopes of -tndex-names 38

PART II: XML LANGUAGE FORMS FOR PARTICULAR COMPONENTS AND ELEMENTS

SET DECLARATIONS 41

A.l Name element Al

A.2 Attribute element 41

A. 3 Indexing element 42

A.4 Specification element 42

A.5 Alias element 43

A.6 Comment element 43

PARAMETER DECLARATIONS 45

B.l Name element 45

B.2 Attribute element 45

B.3 Indexing element 46

B.4 Specification element 46

B.5 Alias element 47

B.6 Comment element 47

VARIABLE DECLARATIONS 49

C.l Name element 49

C.2 Attribute element 49

C.3 Indexing element 50

C.4 Specification element 51

C.5 Alias element 51

C.6 Comment element 52

CONSTRAINT DECLARATIONS 53

D.l Name element 53

D.2 Attribute element 53

D. 3 Indexing element 54

D.4 Specification element 54

D.5 Alias element 56

D.6 Comment element 56

E.l Name element 57

E.2 Attribute elemenl; 57

E.3 Indexing element 58

E.4 Specification element 58

E.5 Alias element 59

E.6 Commen'_ element 59

PART III: EXAMPLES OF XML MODELS

EXAMPLE 1: A MULTIPLE-PERIOD INPUT-OUTPUT MODEL 63

Original formulation 64

XML representation 67

EXAMPLE 2: A MODEL FOR ALLOCATING TRAIN CARS 71

Original formulation 72

XML representation 76

EXAMPLE 3: MODELING ALTERNATIVE ENERGY SOURCES 79

Original formulation 80

XML representation 85

REFERENCES 91

^

INTRODUCTION

This report is a specification of XML, a language for describing linear-programming models to computer systems. Parts I and II together comprise a full syntactic and semantic specification of an initial version of XML. Several extended examples of XML models are given in Part III.

This arrangement is intended to serve two purposes* First, it should make clear in detail what an LP modeling language may be like, thereby making a case that such a language is practical and desirable. Second, it should be sufficiently precise to serve as a basis for a first implementation of XML. These goals are sometimes in conflict — one cannot always be both clear and precise — and so examples have been added to Part I where the specifications are especially complicated.

This report is not intended to give a formal grammar for parsing XML. There are many ways in which such a grammar might be devised, but the choice is properly a matter of implementation rather than specification,

On the other hand, this report also is not organized to serve as a user's manual or primer for XML. Readers unfamiliar with the idea of a modeling language are urged to look first at "A Modern Approach to Computer Systems for Linear Programming" [2] which offers a general justification and summary of XML.

Syntactic conventions

XML syntactic forms are written in itaJLLci) throughout this report.

XML employs the full ASCII character set. No distinction is made, however, between the lower-case and upper-case forms of a letter; they may be used interchangeably in any XMI. expression.

The lexical tokens of XML are -XCJits (defined in section §2.1), 6tAA.ngs (§3.1), nnines (§5.1), and the following special characters:

+ -*/< = >-()[]{}'",:

Appearance of a space or special character indicates the beginning of

a new token.

The following notation is used in defining syntactic forms:

-> The syntactic form to the left of the arrow is defined to represent any of the syntactic expressions listed after the arrow.

[] In syntactic expressions, anything within brackets is

optional (except where, in §5.2, the brackets are part of the XML language). Section numbers in brackets (for example, [§3.4]) refer to syntactic definitions in other sections. Bracketed numbers to the right of syntactic expressions are line numbers referred to in the ensuing discussion.

... The preceding syntactic form may be repeated any number of times.

Different appearances of the same syricactic form are sometimes distinguished by numbers following the form's name (for example, OAQiMnzntl and ciAgumtntl) . Numbered forms are referred to collectively by writing i for the number iajigmyrnvti).

•-. '

PART I

GENERAL XML LANGUAGE FORMS

„ t^tJCi»«m*

-3-1 STRUCTURE OF A MODEL

§1.1 Model components

An XML model is a representation of a class of linear programming problems.

Every model is composed of units called components . There are five types of components, each describing a different aspect of the model;

Set components describe collections of objects, over which parts of the model are indexed.

Parameter components describe numerical data required by the model.

Variable components describe the model's structural variables.

Constraint components describe equations and inequalities that restrict the activities of the variables.

Objective components describe functions of the variables to be computed or optimized.

§1.2 Declarations of components

A model is represented by a collection of declarations that describe its components.

A declaration may describe just one component separately from all others declared in the model. Such a component is said to be single .

Alternatively, a declaration may describe a group having any number of related components, all of the same type. Every group is indexed by a specified set value (§3.2): there is exactly one component of the group corresponding to each set .L_^'.,^r.

A declaration's name is a unique identifier used throughout the model to refer to the component or components that the declaration represents. Its alias is an alternative to the name provided for use in printed output that refers to the model.

s <

-4-

The type of a declaration is the type of component that it declares.

§1.3 E lements of a declaration

Each declaration comprises one or more parts called elements , which are written by use of the XKL syntactic forms described in succeeding sections.

There are six types of elements, each pertaining to a different

aspect of the component or components being declared:

A name element gives the declaration's name (§1.2).

An attribute element specifies simple and fundamental properties of a component or group of components.

An indexing element specifies a set value by which a group of components is indexed.

A specification element gives an explicit or symbolic expression for a component or group of components.

An alias element gives the declaration's alias (§1.2).

A comment element is a string of explanatory text that accompanies the declaration.

A declaration contains at most one element of each type.

Each of the five declaration types uses these elements in a somewhat different way. Thus, the precise syntactic form and meaning of an element depend to some extent on the type of declaration in which it is employed. Further, not all types of elements need appear in a declaration. A name element is required, and a specification element is required in constraint and objective declarations; but otherwise all elements are optional. Omission of an optional element is interpreted according to a default convention for that element.

The syntax, meaning, and default for each element type are given separately for each component type in Part II of this specification.

-5-

2 REPRESENTATION OF NUMERICAL VALUES

§2.1 Nunierical constants

Numerical constants of the forms ^ntZQQA. and fitcUL are employed to represent literal numerical values.

An AJ'VizgiZA is any sequence of digits, optionally preceded by a sign (+ or -). liVtZQiAs represent integral numerical values in cVuXhr\QJU.C.-(ixpAZ66A.ons (§§2.2-2.4), and stand for numerical values contained in sets (§3.2).

A Kexit is any sequence of digits, optionally: (a) preceded by a sign (+ or -); (b) including a decimal point before, among, or after the digits; or (c) followed by the letter E and an X.ntzgeA exponent. Rea£s represent rational approximations to real numerical values. Every AjntZQQA is also a ^iZaZ.

Two rational approximations •'i^ and A- to real numerical values are equal when their difference is within a sufficiently small tolerance of zero. If fi, and -'i„ are not equal. A., is greater than or less than A„ in the usual sense. (XML incorporates no definition of "sufficiently small". Choice of a tolerance is left to the solution algorithms.)

A (rational approximation to a) real numerical value is, in certain contexts, rounded to yield the nearest integral numerical value. Formally, a positive real value K is rounded to the greatest integer value X. such that -i < H. + 1/2; -H. is rounded to --L.

-6-

§2.2 NumeAU.cs

A numOJLLC. represents a single (rational approximation to a) real numerical value. Humzxics are the basic building blocks of OAAjtimoXi-C-e.Kpn.e^6AX)n3 (§2.4). Their general form is:

numeXcc -»■

Kzal [§2.1]

paAa!n\ttQA-lz{i2AQ.ncz [§5.2] \jaAloibtz-fiz{i<Lfi<inc<i [§5.2] objtcitivt-fiziQAznta [§5.2] indax-name. [§6.2]

A fiZjCdi may serve as a nvufnOAX-C, anywhere in a model.

A paAamztOA-KZiftfKincz may serve as a nLm2AX.C anywhere in a model, subject to certain exceptions to prevent circular definitions (§5.3). The numerical value that a paAwneXeA-^e.^eAe.ncz represents may be determined from the parameter's declaration (§B.4).

A vaAAJlbZe.-n.2.{iQAZnce. may serve as a niomAA.c only in a specification element of a constraint or objective declaration. It represents the activity of the referenced variable.

An obje.(ltLvQ.-\.zi2AQ.nc.Z may serve as a numwic only in a specification element of an objective declaration. It represents the value computed for the referenced objective.

An -cndex-mzwie may serve as a numeAUc only within its scope of definition (§6.7). It represents integral numerical values chosen from a specified index set, according to the rules given in §§6.4-6.6. An AjridZK-ncmz serving as a nu/neAcc is invalid if these rules assign it a character-string value (§3.1) rather than an integral value.

-7-

§2.3 AAxXivmttlc.- f^anctions

An oAAXhnzt-ic- {jUncCCon represents a numerical value computed from one or more other values. Its general form is:

qfUXhmeXic- <(u>tcXt.on ->

function-name.ioAgutmnt [, cUiQumZYit] ...)

{^unction-namz -* ABS CEIL FLOOR MAX MIN ROUND TRUNC

oAgumznt -> aAAXhm^tic-e.Kpfiej,6^on [§2.A]

Each {^uncXwn-name, imposes certain additional requirements upon the number of OAgumen^ts, and indicates a particular method of computing a value. Particulars are given in §§2.3.1-2.3.3 below.

§2.3.1 Absolute value: ABS

ABS iaAJXhme,tlc- e-xpiui^on)

aAiXhmeXA.c-(ixpfiQJi&lon -> [§2.4]

The computed value is the magnitude (absolute value) of the value represented by the aAAJJn3r\eJU.c-(LXp12^i)ion.

-8-

§2.3.2 Integer functions: CEIL, FLOOR, ROUND, and TRUNC

CEIL (oAlthmeXlc- expAe44-<lon) FLOOR (o/iXt/iweXcc-expA&44-con) ROUND (oA^une^c-exp-^e64-con) TRL^NC (oAAXhmdtic- Q.xpAHi^ion)

a/uXlvm&Zcc-ZKp^z66-con -> [§2.4]

The a/uXhneXic-Zxpfieyi6-Lon is evaluated to yield a numerical value A., from which the OAAMmeJU-C-(^anCJtions compute the following: CEIL: the smallest integer not less than h.. FLOOR: the largest integer not greater than fi. ROUND: the integer that results from rounding '"i (§2.1). TRUNC: the integer part of K.

§2.3.3 Greatest or least: MAX and MIN

W^iaXQumdwty oAQumznt [, ajiguim^nt] ...) MlN(aAguiiien^, (ViQuxmnt [, oAQumzYVt] ...)

oAQumzYit -^ aAAMmQXX.c-<Lxph.(iAi>lon [§2.4]

MAX computes the greatest amont the values represented by the oAQumtiits.

MIN computes the least among the values represented by the OAQUimriLS.

-9-

§2. A A^uMmttXc- expA.gA.5 ions

An aAAXhtr&t-ic-Zxp\2A6^on is the most general form for representation of (rational approximations to) real numerical values. It is written:

aAAXiimdJtic- exp^e^-6 lo n ^

tznm [1]

(Vujthmz^tLc- e.xpfl^^^lon + ttnm [2]

cvUXlrar\(iXA.<i--zxpfiU^iilon - tzAm [3]

ttnm ->- ^acXoA. [Al]

teAm * (^acXofi [A2]

tojm I iacXofi [A3]

tdAxn DIV iactofi [A4]

XeAm MOD iacZoK. [A5]

{^acXofi -»■ a,tom [Bl]

+ iJac^o^ [B2]

- jJac^OA. [B3]

aXom ** ladon. [B4]

outom ->■ mmexic [§2.2] [CI]

(VuMumtlc-function [§2.3] [C2]

(o^Lci/ime^c-exp-^ei^xon) [C3]

4-cgma [C4]

4-cgitia -> SIGMA -indtxXng-zxpfL2A6-lon (^ajv<Xhn^tLc-2.xpnsJ>iiloYi)

Ajn.d(LxXnQ-zxpfiUi,A^on -> [§6.3]

An aAAXhmztX.C.-ZXpHZA)i>AjOn represents the numerical value determined by the following recursive algorithm:

The value of an a/iXt/imCxtic-exp-^e<54-con is the value of a tOJun [1], the sum of the values of an aJil.tim(ltic-(lxpAU6A.on and of a ^e/U7i [2], or the value of an afLCthne^CCc-Zxp^ZA-bion minus the value of a tznm [3].

The value of a teAtn in the value of a iacXoX [Al], the product of the values of a ieAm and a (^actofi [A2], the value of a ^eAm divided by

-10-

the value of a dadcX [A3], the rounded value of a tSAin integer-divided by the rounded value of a (^actCi [A4], or the rounded value of a tMm modulo the rounded value of a ^acXoA [A5].

The value of a ^actofi is the value of an atom [Bl] or of another (^acXofi [B2], the negative of the value of a {^acJuOK [B3], or the value of an cutOD^ raised to the power of the value of a {^acXoK [B4].

The value of an a,tom is the value represented by a numeA/CC [CI] or by an OAAjJmnQJtLc-(^ancJU-On [C2]; or is the value of the parenthesized a/iXtfurte^C-exp4C44^on [C3]; or is the value of a 4-cgma [CA].

The value of a A-tgma is found as follows: the parenthesized o^Xc/ime^c-ex/o^ei-i'COn is evaluated once with respect to each index determined by the X.nde.XA.ng-e.KpfLZii-Lon (§§6.A-6.6); and all resulting values are summed. If the -IndcXAng-e-Xp^eJii-con specifies an empty index set, the value of the 6A.gma is zero.

(Examples of ctAAJ:hneJxc-ZXpAeA6Zons of many kinds appear in the sample models in Part III of this specification.)

§2.5 Coni)tant-cvuX!vm;tlc- zxpfLti Scons

A coMtwnX-a.'vLthmQXic.-Q.xp'iUSi.on is any aJuMvmoXA^c.-(i.xp>tti>i>.ioyi (§2.4) containing no vaAAjxbtt-fitiQAznde^s or obJQ,cJU.vz->i2.i(lfiQ.ncQ.s (§5.2).

The value of a COn^btCiVit-aAAj:hmQjtLc.-(LXpKQJ>SA^on does not depend on the variables' activities, and so is unchanged from solution to solution. In this sense, it is a constant of the model.

-11-

§2.6 LcngaA-g/L-ctfaneX^c-exp^e^i-cons

A tln^A-cL'UXlvv.eXLC-e.KpA.z&iZon is any cvUX}vms,tic-zxpn.(i^&-ion (§2.4) that satisfies the following restrictions:

• It contains no objeci<lve--^eiieACnces (§5.2).

• In every -te/un, at most one {^acton. contains voAXabZz-Kzizuzncds (§5.2).

• In every tzHm of the form tojim I ^acton., the {^acion. contains no vanA,abtQ.-n.z{^2AQ,nz(Ls.

' No toAm of the form tzhm DIV {^actoH or tOJm MOD ^acXofi contains vcUu.ablz-n.zffZfi2.nczs.

• No {^acXon. of the form aXjom ** (^actoH. contains yjaJvLabtz-Kz^zAznczs.

• No oAXXhnztic- ^unctAJJn contains vaAAjxbtz-fizizfiznczs. Every tA^nzaA-oJuMvinztLc-zxpn.Zii6'Lx}n is either a cOYU:>ta.Yit-aAAM-mztA.c-

ZxpfLZi>i>-Lon (§2.5), or represents a linear combination of the activities of one or more variables.

-13-

3 REPRESENTATION OF SET VALUES

§3.1 SPUnqs

A it'iA.n.Q is any sequence of characters beginning and ending with an apostrophe (') a..d containing no apostrophes elsewhere, or beginning and ending with a double-quote (") and containing no double-quotes elsewhere.

St^i.nas represent character-string values ; arbitrary sequences of characters. The character-string value represented by a particular &tAA.nQ is exactly the sequence of characters between the apostrophes or double-quotes.

An empty sequence of characters (that is, a sequence of zero characters) is called the null character-string value. It is represented by a &tAJ.ng comprising two consecutive apostrophes or double-quotes (" or "").

§3.2 Items

An item is either an integral numerical value or a character-string value. Items represent the "things" that a model is concerned with (factories, products, cities, periods, and so forth); they are the fundamental constituents of sets.

Two items are equal if they are identical integer values or identical character-string values. (An integer item is never equal to a string item.)

Items are represented by -ctew-exio^aii-UJns of the form:

XX^m- zxpfiUi, ion ^■

itAlng [§3.1]

inte-gz-t [§2.1]

coni> tant-afUXlimctXc-ex.pA.z6i-ion [§2.5]

OKU'X-HiVric [§6.2]

-14-

A 6tAAMg (representing a character-string value) or an itlt<lQ2.K (representing an integral numerical value) may serve as an /.io^-exp^ai-i-tCK anywhere in a model.

A c.onlitant-cUuXkinQXX.C.-Q,xpK(li>filon may serve as an Aji2m-(l.xpfii2Ai>A.on anywhere in a model, subject to restrictions on the ntoneA-CCs within it (§2.2). It represents the integer item produced by rounding its arithmetic value.

An A,ndzx-namo, may serve as an lt2!n^-2.xpK<lAi>■i.on only within its scope of definition (§6.7). It represents items chosen from a specified index set, according to the rules given in §§6.4-6.6.

§3.3 Objects

An object comprises a single item or an ordered sequence of two or more items. The number of items in an object is its length .

Two objects are equal if and only if they have the same length and comprise the same items in the same order.

Thus, an object of length 1 is essentially just an item. An object of length 2 represents an "ordered pair" of items, an object of length 3 represents an "ordered triple" of items, and so forth. In general, an object of length n represents an "ordered list" of n items.

Objects are represented by use of the form obje.cX-ZXpH.zit&'ijOn'.

obiQ,cJ:-2.xpnjii)i>lon -+

^(ijm-(?yy^ii>i>lon [1]

iitQjin-zxpK(Li,&A.ony -cteni-expA.e-44^on [, UiQji\-Q.xpK2M,.ijon] ...) [2]

iXzm-(ixpn.zA>&lon -y [§3.2]

Form [1] represents an object comprising a single item. Form [2] represents the ordered sequence of items in an object of length 2 or more.

-15-

§3-4 Set values

A set value Is an unordered collection of any nunier of distinct objects. These objects are said to be contained in the set value, and are referred to as its members . A set value having no members is empty .

All members of a set value must have the same length, referred to as its menJjer-1 ength . Thus one may have sets of single items (taember-length of 1), sets of ordered pairs of items (member-length of 2), and so forth. The member-length of an empty set is undefined.

Two set values are equal if every member of the first is equal to some member of the second, and every member of the second is equal to some member of the first.

Set values may be represented by use of the form 6e.t-constant:

6eX-coii&tciyU. -»-

{}

{membeA [, membeA.] ...}

mambeA-^ objZct-e.xpfie^6.lon [: cutia^]

obje.ct-ZKp^U6-ion-^ [§3.3]

atccLi ->• 6tAA.ng [§3.1]

Each object-ZxpH^ii6ton between the braces represents one member of the set value denoted by the se.t-COH!>tant' Braces with nothing between them denote an empty set.

The optional aJLLoA specifies a member's alternative name for use in reports. For example, a set of cities could be written

{'BO':'BOSTON', 'NY':'NEV/ YORK', 'PH' :'PHILADELPHIA') KH.Caites are not part of the set value; they are ignored in interpreting hkit- {^unctions (§3.5) and Slt-HXp^Ui^ions (§3.6).

-16-

§3.5 S^t-^unc^t^JOns

A 6eX-{)Unc.tion represents a set value computed from one or more other set values, items, or numerical values. Its general form is:

i^uncJUjon-namz -> PRO J SECT SEQ

afigu/mnt -> ^(im-e,xp^2.66yion [53.2] 4c^-expA.fc4-5-con [§3.6] con6tant-(VuJ:lm^^t^.c-^xpn.2^6lon [§2.5]

Each ^unctAjon-nam^ imposes additional requirements upon the number and form of OAgumznts, and indicates a particular method of computing a set value. Particulars are given in §§3.5.1-3.5.3 below.

§3.5.1 Projection of a set; PROJ

?R0J(6(it-e.x.pAZ&6^n [, con6tanX.-(VUMmztic-zxpfi2M-ion] ...) 6eX-zxpA.e^6lon ->■ [§3.6] con!>tayvt-anAXimcX^Ca-^xp^eA6wn -> [§2.5]

PROJ projects a set value (represented by the ^eX-txp^QA'i-con) onto specified coordinates (either as indicated by the conitant-OAAXlmeJXC.-e.xpfiti6^ons, or else the first coordinate by default). The projection is determined as follows:

If there are ccnl)tayit-a''iiX}imcXic-Q.xp'ieJ>!>-C0K5, they must represent

-17-

distlnct positive Integral numerical values; denote these values by -c, , .... t . Otherwise, let M = 1 and -c, = -c =1.

Denote by 5 the set value represented by the 6<li-^KpA.eAi'L0n; denote by Z the member-length of 5. Then it is required that £ ^ n, and £ ^ -c, , ,..,£> -i .

The computed (projection) set value has member-length n: for each object (ci, , ..., Go) In S, the object (a , . . . , a . ) is in the computed projection.

Example : Suppose ROUTES represents the set

{('BO','NY',0), (•BO','PH',0), ('BO'/PH'.D, ('BO','WA',0), ('B0','WA',1), ('NY','WA',0)}

The following are some possible uses of PROJ:

PROJ(ROUTES) is {'BO', 'NY'}

PROJ(ROUTES,2) is {'NY','PH','WA'}

PROJ(ROUTES, 1,2) is {('BO','NY'), ('BO' ,'PH'),

('BO' ,'WA'),('NY' ,'WA')}

PROJ(ROUTES,3,1) is { (0, 'BO'),(1,'BO'),(0,'NY')} §3.5.2 Section of a set: SECT

SECT (6e.t-^xp^Q^6A.on ,<Xem-&xpn.aM-Con)

SECT(i>2.t-&Kp^(iM-ton [ ,tt(>in-&KpA{i.i,S-u>n,cun6tiiitt-a.n.i-tliimtA.c- zxpA.QA>6-<.on] ...)

62X-PKpAe.SiA.on -> [§3.6]

-6tem-expA.e44-ton ->■ [§3.2]

com>tant-aAAXh}r\2ytlc-txpfLeM<.on -> [§2.5]

SECT sections, or "slices", a set value (represented by the ieX-dXp^eAS-ion) on specified items (represented by the 'Ctdjm-e.xpfiUiXons) at specified coordinates (as indicated by the coniiant-cUu.thyneJU.c-e.xpA<li6-ions, or else the first coordinate if none is indicated). The section is determined

-18-

as follows:

Denote by C,, .... Z the items represented by the ■Ctojm-ZxpKUiA.ons. If there are C0ni>ta.iit-CL'uXhmeJxc.-ZKpfi&i>6Xj0ns, they must represent distinct positive integral numerical values; denote these values by ^, , .. . , jI . Otherwise, n = 1; set -c. = 1.

Denote by S the set value represented by the 6eX-e.x.p^eJ>'i>-con; denote by Z the member-length of S. It is required that Z > n, and Z > -i^, ..., Z > l^.

The computed (section) set value has member-length Z ~ n. For

each object (a,, ..., a») in S for which

a ■ =ei,...,a. =e -t^ 1 ^n '^

the computed section contains the same object with items a. , ..., a.

deleted.

Example ; Consider again the set ROUTES of §3.5.1. Some possible

uses of SECT are:

SECT(ROUTES, 'BO') is { ('NY' ,0) ,( 'PH' ,0),('PH',1),

(•WA',0),('WA',1)}

SECT(ROUTES, 'NY') is {('WA',0)}

SECT(ROUTES,'PH') is { }

SECT(ROUTES, 'WA', 2) is {('BO' ,0) ,('BO',1),('NY',1)}

SECT(ROUTES,1,3) is { ('BO' ,'PH'), ('BO' ,'WA')}

SECT(R0UTES,1,3,'B0',1) is {'PH','WA'}

§3.5.3 Set of a sequence of integral values: SEQ

SEQioAgumzntl, oAgumzntZ [, aAgwmnt3] )

oAgwmnti -*■ con^tattt-oAlthm^ytic-zxpAaAiZon [§2.5]

An.gu)Wntl and OAgurmntZ are evaluated and rounded; denote the resulting integral values by m and n, respectively. If aAguj'"e.nf3 is

-19-

present, it is evaluated and rounded; denote the resulting integral value by fe. If cUigLWiQ.ntS is not present, let fe be 1.

The computed set value contains all integers of the form m + -ik for which -t is a nonnegative integer and m + -ik < n.

Exampl e; Some instances of SEQ are:

SEQd.lO) is {1,2,3,4,5,6,7,8,9,10}

SEQ(1975,2000,5) is {1975,1980,1985,1990,1995,2000}

§3.6 S(lt-^xpA&i6^ons

A &£.t-Q.xpfiZi>6-ion Is the most general form for representation of set values. It is written:

&zt-dU.iiQAznci2. [1]

&<iX-Q.xpfi2A&ion * 'i,llt-dl{^{iQ.flQ.nCZ [2]

&2X-(Ui{i2.fiz.ncQ. ->■ 6eX-anion [Al]

&cX-diiitKQ.yiCQ. - 6zt-aition [A2]

ieX-uyiion -^ ^^--CnteAAdcM-on [Bl]

^eX-uyUon OR 6zt-'CnteA6section [B2]

ieX-lnt^Jv!)action ->■ 6eJ:-cUom [CI]

6eX-lntQ,n^zctlon AND iat-aXom [C2]

6&t-cutom ->- ^zX-conitant [§3.4] [Dl]

■dzt-iimcXlon [§3.5] [D2]

■b^Z-^tiOAznan [§5.2] [D3]

(4et-expA.e44^on) [D4]

J

A i,QX-Q.xpfiZi>ii'Lon represents the set value determined by the following recursive algorithm:

The value of a Ae^-expAei-i-coti is the value of a i>Q.t-di^{^Zfie.ncz [1], or (s tlic cartesian product of the values of a ie t-c.xp'LC6-6 <V'H and a

-20-

ieX-di^^QAe.ncz [2] determined as follows: Let S, and S. denote the values of the 6eX-Zxp^eA6A,on and 6eX-dl{,^&fiencz; let t, and £_ denote their respective member-lengths. Then the cartesian product has member-length Z, + Zj' ^°^ every pair of members (a,, .... a» ) of S^ and (6 , ..., b„ ) of S-, the cartesian product contains (a,, ..., a» , b , .... bp ).

The value of a 4e^-cit)5j$eACJlce is the value of a 6eX-Littion [Al], or is the complement of a 6eX-uyiion in a 4e^-etc i^i^ GAcncd [A2] determined as follows: Let S, and S„ denote the values of the icXi-di{,{jSACnce. and 6eX-u.yiCony respectively; they must have the same member-length. Then the complement contains all members of S-, that are not members of S^.

The value of a 6e.t-uyu.on is the value of a 6e.t--cntdUdction [Bl], or is the union of a 6Zt.-anion and a 6dt--intCMAtction [B2] determined as follows: Let S, and S. denote the values of the ieX-uyiion and ieX--cnteA^e.cX<jOn; they must have the same member-length. Then their union contains an object if and only if it is a member of S, or_ a member

of S^.

The value of a ^eX-^nte.fil>e.ctlon is the value of a i>eX-cUom [CI], or is the intersection of the values of a ie.t-iiVte.Ue.cJu.On and a iet-atom [C2] determined as follows: Let S-i and S~ denote the values of the 6eX-'Lnte/ii>ectlon and -iet-atum; they must have the same member-length. Then their intersection contains an object if and only if it is a member of S, and a member of S^.

The value of a 6eX-a.to>r\ is the value represented by a ieX-COH^tant [Dl], -6eX-function [D2], or 6eX-^Z^Z^encZ Iirl, or is the value of the parenthesized 6eX-&xpfieM-i.on [D4].

-21-

Examples . Represent some sets as follows:

51 {1,2,3}

52 (2,3,A,5}

53 {'A'.'B'}

54 CC'D'}

Some typical set expressions and their values are:

53 * S4 {('A','C'),('A','D'),CB','C'),('B','D')}

SI * SI (d.l),(1,2),(1,3),(2,1),(2,2),(2,3),(3.1),(3,2),(3,3)]

82 - SI {4,5}

SI - S2 {1}

54 - S3 {}

SI OR S2 {1,2,3,4,5}

SI AND S2 {2,3}

S3 AND S4 {} "

-23-

4 REPRESENTATION OF LOGICAL VALUES

§4.1 Logical values

There are two logical values ; true and false . Forms for representing logi_al values are given in the following sections.

A syntactic form is said to be true when it represents the logical value true, and to be false when it represents the value false.

§4.2 lQuaZLtA£yt

An Q.qualAXy is true or false according to whether two values are equal or unequal. Its form is:

J

zqualltij

vala^l = valae.2 [1]

vaZuzl ~= valwii [2]

vaXazl, vatanZ -> con{>tcLnt-aAX.thmeJxc-zxpfiz^6icn [§2.5] -6Cew^exp'^e44^on [§3.2] obje.ct-ZKp^e^6lon [§3.3] 6Zt-e.)(.pfiZ66lon [§3.6]

Form [1] is true and form [2] is false if and only if the two indicated values are equal. The sort of equality to be tested is determined by valuci and valuQl as follows:

If vaZuel and value2 are coniitant-a'vithjtr}P_tLc-zxpn.2^6ion^i the zquaZAJiiJ tests whether they represent equal numerical values [§2.1].

Otherwise, if valael and ua£ue2 are Itom-zxpfKLfif^'Lons, the zquaLitiJ tests whether they represent equal items [53.2]; if uoXuel and Vdtazl are ob/cct-exp^ei-i tons, the zquatitij tests whether they represent equal objects [53.3].

If vaCucl and uaiuL'2 are ic f-explC/iA-COHs, the equucU-itiJ tests whether tliey represent equal set values [§3.4].

-2A-

§4.3 Jnzquxi£-ltte J>

An -CnzquaiAXiJ is true, or false according to whether one numerical value is greater than or less than another. Its form is:

valuzi > \jalaz2 [1]

vaZuzl <■■= valvi^l [2]

ua£ae.l < valuzl [3]

vaJbizl >= voJiazl [4]

vaZuzly valiLZl -»■ con&tjXYVt-anAXhmztic-zxp'iQJiiilon [§2.5]

Form [1] is true and form [2] is false if and only if the numerical value represented by vatazl is greater than that represented by vaZazl.

Form [3] is true and form [4] is false if and only if the numerical value represented by uoXuel is less than that represented by V(itu2.2.

§4.4 Me/ft eMJ>hX.ps -

A m^mb^Ukip is true or false according to whether an object or objects are members of a given set. Its form is:

mcmb&Ai>hA.p -»•

objZct-ZKp^&{,6-ion IN 6eX-ZKp^eJ>6ion [1]

ieX-zxp^di'fi-ion IN 4e^-expA.e44-ton [2]

obj^ct-e.xpAe^6■lon -> [§3.3]

6eX-zxp^QA6Zon -»- [§3.6]

Form [1] is true if and only if the object represented by objccX-CxpteiAcon is a member of the set value represented by ioX-exp^Z-ii ion.

-25-

Form [2] is true if and only If every object contained in the set value represented by the left-hand izt-e-XpfieAti-Con is also contained in the set value represented by the right-hand ieX-CKp^ilH-ion.

§4.5 Loq-lcjoZ-zxp-XQ^iions

A tOQlcat-ZXpA.Ziiii'ion is the most general form for representation of logical values. It is written as follows:

toQlcat- zxpfiQJi'fi'ion ->

loQlaal-tzAm [1]

loQ-i(iaJi-zxpfiU6lon OR toglcjcUL-toJim [2]

toQlcaJL-to.'nn -> loQlcoJi- ^acton. [Al]

loQlcjOil-tfifm AND log-icaZ-^acto^ [A2]

loglccLt- (,acton. -y tog-lcat-atom [Bl]

NOT logicjdl- ^acto-i [B2]

logical-atom -> tquatltij [§4.2] [CI]

Inzquuxtuttj [54.3] [C2]

manbeAAltlp [§A.4] [C3]

(logtcal-txpfLU^-con) [C4]

The truth or falsity of a togZcaZ-2.xp^e^6'Con is determined by the following recursive algorithm:

The value of a Zoglcat-zxp^eyiiton is the value of a togltaJi-tdHm [1]; or is false if and only if both a Zog-Ccxil-e.xp^eA6.ion and a toglCjaJi-teJm are false [2].

The value of a togicaJi-t<lHm is the value of a togtcat-^actofi [Al]; or is true if and only if both a tinj-icaZ-tzitr] and a l^og-icat-{jactun. are true [A2].

The value of a toglcoZ-f^actoH. is the value of a £og<.ca£-afoni [Bl]; or Is true if and only if a togicaZ- ^actoH. is false fB2l.

-26-

The value of a log<xial-<ttcm is the value represented by an ^quatUy [CI], ZmqualU,^ [C2], or mmb^uUp [C3]. or is the value of the parenthesized loQlcal-Q.xpfitK>i>ion [C4].

-27-

5 REFERENCES TO MODEL COMPONENTS

§5.1 MoDi&s

A yvame. is any sequence of letters, digits (0, 1, 2, ..., 9), and underscores (_) of which the first character is a letter.

Wonies serve as identifiers for model components, as described below. Womcs also identify indices employed in indexing operations (§§6.1-6.7).

The following reser'/ed words are notnes that XML uses for special purposes, and so are not allowed as compomnt-names (§5.2) or lnde.x-norms (§6.2):

§5.2 Componetit-^g'^eAences

A component-n.^^QAe.nce. refers to a particular component (§1.1) of the model, and represents a value associated with that component (§§2.2, 3.6). Its form is:

component-^ei^£/Lence ->■

componznt-name. [1]

compomnt-y^Mr^e.UXejft^-zxp^eAi-ion [, Itom-Q,xpfi(iA>'i,lon] ...] [2]

compomnt-narm -> norm [§5.1]

-ctein-exp-^e^^-con ->■ [§3.2]

Note: underscored brackets ^ ^nd J_ are part of the component-^e.^^QAencQ.

The component that is referred to is determined as follows:

Form [1]: The compone-nt-ncmz must be the name (?i.2) of a

-28-

declaratlon of a single (§1.2) component In the model. The componznt-Kd^eAZncZ refers to this component.

Form [2] ; The compomnt-namz must be the name of a declaration of a group (§1.2) of components in the model. This group must be indexed by a set value that contains either (a) a member represented by

Ajtoxn- z xpfveJi -4 -co n if the COmpomnt-njZ^ZfieAcz contains just one ■Ctem-e.xpn.Ui><.on; or (b) a member represented by

(-ctem-exp/^eiA^onl, ..., -it(m-zxp^zi>'i>-lon±) if the compone.nZ-.n.Q.^(2AzncQ. contains -c > 2 ■item-^xp'l2^6■ions. The component-fie.{,2Ae.nce. refers to the group's component corresponding to this member.

Component-^e.(ieAe.nce.s are designated a e-t-^ej$eAences, paAa»iefc'A-fie-ffZAznccs, v(VujCible.-Kz{f£Aznczs, (iott4t^uuRt-A.ei$eAenccs, or objzctivz-A.ejJcAence.s according to the type of component to which they refer.

Examples ; (1) A variable declaration has name X and declares a

group indexed over {'WA','PH','NY',' BO'} . The followinc va^abl^-

/^Ci^eAences represent the variables:

X['WA'] X['PH'] X['NY'] X['BO']

(2) A parameter declaration has name DEMAND and declares a group

indexed over {(1,2), (1,3), (1,4), (2, 3), (2, 4), (3, 4)}. The following

paJijamitQA-n.z{ie.fiQ,nzzs represent the parameters:

DEMAND [1,2] DEMAND [1,3] DEMAND[1,4] DEMAND[2,3] DEMAND [2,4] DEMAND [3,4]

-29-

§5.3 Circular declarations

Some restriction must be placed upon compomnt~A.e.^eA.e.nce.s to avoid declarations that define components in terms of themselves.

For this purpose, declaration A is said to depend upon declaration B if either

(a) A contains a coinponenX-'^ei^eAencc for a component declared by B; or

(b) A depends on some declaration C, and C dcpands on B. A declaration is circular if it depends on itself.

A compomyvt-^t^ieAznce. is invalid if its presence results in a circular declaration.

-31-

6 INDEXING

§6.1 Definition

Indexing Is the means by which model entities are associated with members of sets. XML uses indexing in two ways: to define groups of components (§1.2) and to specify indexed (E) sums (52.4).

There are two aspects to indicating Indexing in XML:

(a) Specifying a set value called the index set . Members of this set are called indices , and the items in each member are a list of index items .

(b) Evaluating 4et-expA.e4-6^ons, aAXt/u)ie.^c-expA.e<44^ons, and togA,cat-e.xpfieJ>i-LOns with respect to each of the Indices, For this purpose, -index-ncumzs may be defined to represent index items.

The syntactic forms for indicating indexing are given in §6.2 and §6.3.

Rules for determining the index set are put forth in §6.4, and evaluation

of expressions with respect to indices is described in §§6.5-6.6. Limits

on appearance of an ■index-name, within a model are explained in §6.7.

-32-

§6.2 J ndzx-lnq-unlets

JndcKcng-uniXs express the simplest concepts of Indexing. They are written in either of two forms:

lnd<LXA.nq-gyvCt -»■

[Index-tLA>t] OVER 0V2A-2.XP [WHERE MhoAZ-ZXp] [1]

Undex-nawie] FROM ifiom-axp TO to-txp [BY bi/-exp] [where iMkanz-dxp] [2]

indzx-tlitt -> Indzx-Yiamz

(Xndzx-namt, index-naimd [, index-ncwiz] ...)

-cnrfex-muMe -* name [§5.1]

ove^-exp -^ i^et-expfizAtlon [§3.6]

{^fwm- exp •\

to-exp > -» coni>tant-aA.i.tlw^etcc-expfie'i6<.on [§2.5]

by-exp J

u}heAe-exp -> £og^ca£-cxp^e6A'Con [§4.5]

Each index-name in the index-ZAJ^t (in form [1]), or the initial index-name (in form [2]), is said to be defined in the iyidexing-unct.

An index-name defined in an indexing-uyuX must be different from:

(a) every other index-najve defined in the indexing-unit;

(b) every other index-noine in whose scope (56.7) the indexing-unit lies; and

(c) every noJ^C specified In a name element of any declaration. The number of index-nomes in the index-tii>t (for fomi [1]) must

equal the member-length (§3.4) of the set value represented by the oveA-exp.

-33-

§6.3 J nd^XA-HQ- zxpn.e^i,.lons

Jnd^Xying-S.xp^ey&A'Cons are the general forms for indicating indexing. They are written as lists of -endzxJ^ng-units:

-cnriex^nq-expAe6^Xon ->■

AJidtXAjn.Q-anct [Al]

inAjUjcUi-in.dzxA.nQ-zxpn.2A6-ion, tznminaZ-indzxMig-unAJ: [A2]

inCtCat-indzxA.ng-zxpfizM'Con -> indzxA-ng-zxp^zi^ijon

tzAynCnaZ-indzxA,ng-unit -* indzxing-urUjt

Indzxlng-uniX. ^' [§6.2]

Form [Al] consists of a single ■indzxA.ng-UYuX., while form [A2] comprises a sequence of AJidzxA.ng-uiiCts.

§6.4 Determining the index set

Every iyvdzXA^ng-ZXpfiZA^-ion specifies an index set (§6.1). The manner in which this set is determined depends on the form of the indzxing-zxpfizMion, as follows:

Single Indzxing-unit, form [1], no iA}hzAZ-Zxp : The index set is the set value represented by the OVZA-Zxp.

Single indzxinq-unct, form [2], no wkzfiz-zxp : If the bij-zxp is not present, the index set is the set value represented by

SEQi^jfLOm-Zxp, to-zxp) If the biJ-ZXp is present, the index set is the set value represented by

SEQi^nvm-zxp, to-zxp, by-zxp) (On SEQ, see §3.5.3.)

-34-

Single X.ndQ.XA.nQ-ayuX, viUi whcA^-zxp : The Index set is the set value determined by the following algorithm:

(a) Determine a tentative index set by ignoring the W/ieAe-c.xp and following the rules for form [1] or

[2] given above.

(b) Place an index in the index set if and only if (i) it is a member of the tentative index set, and (ii) the W^eAe-CXp is true with respect to it.

(On evaluation with respect to an index, see §6.6.)

Sequence of i.nd(lXAJiPi-aYlLts : The index set is the set value determined by the following algorithm:

(a) Determine an initial index set from the ^nXJUXlZ-

A.nde.King-dxpfumZon, by applying the rules of this

section (§6.4) recursively. Denote the members of

the initial index set by i^, , . . . , w .

1 n

(b) For each m. determine a terminal index set T. from the teAminat-yCndzXA.ng-uyuJ:, by (i) interpreting any oucA-exp, (J/wm-exp, to-zxp, by-s.xp, or ivhe-fie.-axp with respect to m - (§6.6), and (ii) following the rules for single-unit 'indexing-^xpAeJiiZons given above.

(c) Compute the index set as:

({m^} * T^) OR ({m^] * T^) OR ... OR ({m^} * T^^)

(On operators * and OR, see §3.6.)

Examples : (1) Suppose that CITY represents the set {'PH','NY','BO'}

Then the index set specified by

OVER CITY, FROM 1972 TO 1Q«A BY 4

is just CITY * SEQ(1972,1984,4), whose members (indices) are

('PH',1972), ('NY',1972) ('BO',1972)

('PH',1976) ('NY',1976) ('BO',1976)

(•PH',1980) ('NY',1980) ('BO',1980)

('PH',1984) (•NYM984) ('BO',1984)

-35-

(2) Consider the following <.ndz)U.ng-e.xpA.U.iZon: >—

I FROM 1 TO 5, J FROM 1 TO I

The initial index set is {1,2,3,4,5}; the terminal index sets are

T. = (1, ...» -1}. Thus the entire index set is

({1}*{1}) OR ({2}*{1,2}) OR ({3}*{1,2,3})

OR ({4}*{1,2,3,4}) OR ({5}*{1,2,3,4,5})

which is just the "triangular" set of pairs

{(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),

(4,4),(5,1),(5,2),(5,3),(5,4),(5,5)}

(3) Either of these lnde,XA.ng-^Kp^^^6^ons:

CI OVER CITY, C2 OVER CITY WHERE CI ~= C2 (C1,C2) OVER CITY * CITY WHERE CI ~= C2

specifies an index set that contains all members of CITY * CITY whose

two items are not the same. Hence the index set is:

{('?H','NY'),('PH','BO'),('NY','PH'),

(•NY','BO'),('BO','PH'),('BO','NY')}

§6.5 Representing index items by ■i.nde.X-namzs

An Ajn.d2.x.-namz defined in an indzxA.nQ-e,xpfi(^6A,on represents the feth item of every index, for some fe. The value of fe is determined by where the -indzx-ncmz appears in the lndzXA.nQ-(lxpfi2^i>i.on, in the following way:

Single. i,ndfAX.nCi-gyict, form [1] ; The feth indzx-nam(L in the indzx-ZAJ>t represents the feth item in each index.

Single i.ndQJU.nq-iuvCt, form [2] : The one A.ndo.x-name, represents the first (and only) item in each index.

Sequence of indilxX.ng-nyujts : Let I be the length of the indices determined by the lniXA.aZ-indQ.XA.nQ-Q.xpfiUi>-ion. Then an -LnddX-name, is determined to represent the feth item in each index as follows:

-36-

(a) For an inddx-ncuna defined in the iiiltiat-lndzXA.ng-txpfuiiiii-iony determine fe by applying the rules of this section (§6.5) recursively to the ■iyiLtAJX.t--ind^-XA^nQ-e,xpfLtl>6.lon.

(b) For an -cndS-X-nOine defined in the tQAminaZ--Cnd^XA.ng-ault, determine a k' by applying the above rules for form

[1] or [2] to the tznminat-A^nde.xX.nQ-avuX. Then fe = £ + fe'.

Examples ; Let ROUTE represent a set value whose member-length is 2, and let PRODUCT and USE represent sets whose member-lengths are 1.

(1) The following ■indtXA.ng-exp^QAi-ion specifies iiidices whose length is A:

I OVER PRODUCT, (J1,J2) OVER ROUTE, K OVER USE JndtX-name. I represents the first item in each index. Jl represents the second item, J2 the third, and K the fourth.

(2) Indices specified by the following A^nd(lXA.nQ-Q.xpfiQ2>i>A,on also have length 4:

I OVER PRODUCT, FROM 1968 TO 1992 BY 4, (.I,K) OVER ROUTE Index-no/ne, I represents the first item in each index, J represents the third, and K represents the fourth. No -Lndux-nfuno. represents the second item in each index.

-37-

§6.6 Evaluation with respect to an index

An aAithmoZic-zxp'tzA^^on, i>QX-ex.p\&^6ion, or logA.caZ-ZKpA.e.iiX.on is evaluated with respect to an index as follows:

(a) Each -tudcx-nowe in the expression is taken to represent some item of the index, as explained in §6.5.

(b) The value of the expression is computed according to the usual rules.

AAAJJmeJxc-e.x.pn.z.i,-i,Aions are evaluated with respect to indices in 6lgmxs (§2.4); in f,fiom-zxps, to-zxps, and by-zxps of -tndexing-expA-eA-i-cons (§§6.2-6.4); and in specification elements for parameter, variable, constraint, and objective components (§§B.4,C.4,D.4,E.4).

Seyt-e,xpA.^iX.ons are evaluated with respect to indices in OVQA-CXps of <.ndzXA,ng-^xpAl^^6X.ons (§§6.2-6.4) and in specification elements for set components (§A.4).

Log'icaZ-ZKpfiZ66-cons are evaluated with respect to indices in W^e-^-exps of -Cnde.XA,ng-ilxpA.&.66Zons (§§6.2-6.4) and in specification elements for constraint components (§D.4).

Exanyle : Consider the following i-Cgma, in which X names a variable;

SIGMA I OVER {'PH','NY','BO'},

J FROM 1972 TO 1984 BY 4 ( (J-1970) * X[I,J+4] )

The -indexing-e.xp^^'iiA.on in this -ii-igmx specifies a set of 12 indices of

length 2 (see §6.4, example 1); .Inde^X-name. 1 represents the first item

of each index, and J represents the second item of each index.

Thus evaluating the expression (J-1970) * X[I,J+4] with respect to,

say, the index ('NY',1976) yeilds the value of 6 * X['NY',1980].

Evaluating the same expression with respect to ('BO',1984) yields

14 * X['BO',1988].

-38-

§6.7 Scopes of -cndcK-namQ.s

A scope of an -Lndzx-nainz is that portion of the model in which the A.nde,X-namo. may be used to represent values of index items (as described in §§6.5-6.6).

An -cndex-nowie has one scope for each X.nde.XA,ng-unit that defines it. Scopes of the same -indzx-name, for different X.nde.XA.ng-units may not overlap (§6.2).

A scope of an indzK-nomz for a particular inde.XA.ng-unit includes:

(a) the MheAQ.-e.xp of the -indexing-untt (if any, §6.2);

(b) all succeeding indexing-units in the same indextng-expleMiton (if any);

(c) if the Indzxtng-anit is part of a declaration's indexing element (§§A. 3,B. 3,C. 3,D. 3,E. 3): any specification element (§ §A.4,B. A ,C.4 ,D. A ,E. 4) in the same declaration;

(d) if the indexing-unit is part of a 6igrm. (§2.A): the parenthesized afiitlmettc-expKeA^ion that follows that 4-tgma's Indzxlng-expfieMlon.

The remainder of the model is not included in the scope.

PART II

XML LANGUAGE FORMS FOR PARTICULAR COMPONENTS AND ELEMENTS

-41-

A SET DECLARATIONS

§A.l Name element (required)

&QX-namQ.-(it(mQ.ivt ->

name [§5.1]

This element specifies the name (§1.2) for the declaration.

No 4e^-name-e£cnie)tt may be the same as any other 4e-t-name-element, po/Lome^eA-name-eXcment (§B.l), uaA^6£e-name-e£emeni (§C.l), conittAain-t-name-zl(2)n^nt (§D.l), obje.cXivz-name.-eI.&mnt (§E.l), or ^ncfex-name (§6.2) defined in the model.

§A.2 Attribute element (optional)

6eX-cuttfUba.tz-tlejimnt -> [LENGTH] n

n -^ -tn^egeA. [§2.1]

This element states that the declared set or sets must represent a set value whose member-length (§3.4) is n.

The constant n must be a positive -Cntegd^. Default: LENGTH 1 is assumed.

-42-

§A.3 Indexing element (optional)

6 2,t-indzKinq- oZennznt -»■

lndzxAJaQ-zxpK2^&lon [§6.3]

A group (§1.2) of sets is declared if and only if this element is present. The group contains one set corresponding to each index (§6.1) specified by the XndexXng-expA.C/44^n.

Default : A single (§1.2) set component is declared.

§A.4 Specification element (optional)

&<^-6\:)ZcX.iljzaticn-tit2ynznt -> 6eX-zxpfiU6-con [§3.6]

This element indicates what set value each declared set represents, as follows:

If the declaration is for a single set: any reference to that set represents the set value yielded by evaluating the 6eX-<lxpfLU6'L0n.

If the declaration is for a group of sets: any reference to a set in the group represents the value yielded by evaluating the iZt-e.xpfiZ&6Aj0n with respect to that set's corresponding index (§§6.6, A.3)

DefacuLi.. The model does not indicate what set value each declared

set is to represent.

-A3-

5A.5 Alias element (optional)

6 zt- atloA - atejncitt

&tAX.nQ [§3.1]

The sequence of characters represented by the i>tAA.ng is the alias (§1.2) for the declaration.

Default: No alias is defined.

§A.6 Comment element (optional)

'i eX-cornntut-zter>tznt -*■

6tAA.ng [§3.1]

The sequence of characters represented by the ipLtng is a comment to accompany the declaration.

Default: No comment is defined.

-45-

B PARAMETER DECLARATIONS

§B.l Name element (required)

name. [§5.1]

This element specifies the name (§1.2) for the declaration.

No paAa>neieA-Maine-e£ejnen^ may be the same as any other pcuUmoXeA-name.-dLomiiYVt, 6eX-namn-eI.QmQ.nt (§A.l), vaAA,able-name-eZemQnt (§C.l), con!it/Lcu.nt-name-element (§D.l), objective-name-eler^^znt (§E.l), or ^nde.X-name. (§6.2) defined in the model.

5B.2 Attribute element (optional)

paAametLeA-att'Ubute- element -"

fieAitAA.cJJ.on [fieAtnXction]

fieAtAicJ:.ion -> positive NEGATIVE NONPOSITIVE NONNEGATTVE NONZERO INTEGER

This element states that numerical values represented by the declared parameter(s) must satisfy the listed KeA>t?vic.tA.ons.

Default*. Tiio declared parameter(s) may represent any numerical v.i I'.iiv;.

-A6-

§B.3 Indexing element (optional)

Andzx^ng-zy.freA6Xx)n [§6.3]

A group (§1.2) of parameters is declared if and only if this element is present. The group contains one parameter corresponding to each index (§6.1) specified by the -cndex^ng-expA.e44^ott.

Default: A single (§1.2) parameter component is declared.

§B.4 Specification element (optional)

con6tayvt-aAitlvmXla-e.xpn.eA6Ajon [§2.5]

This element indicates what numerical value each declared parameter represents, as follows:

If the declaration is for a single parameter: any reference to that parameter represents the numerical value yielded by evaluating the coyi&tanX-aA(XhmztA.c.-zxp^z6i,/.on.

If the declaration is for a group of parameters: any reference to a parameter in the group represents the value yielded by evaluating the coyi6ta.nt-aAithjneJU.c-expAZS-l>^on with respect to that parameter's corresponding index (§§6.6, B.3).

Default: The model does not indicate what numerical, value each

declared parameter is to represent.

-47-

§B.5 Alias element (optional)

paAatmteA- atlai - al omzivt &tfUnQ [§3.1]

The sequence of characters represented by the i,VvinQ is the alias (§1.2) for the declaration.

Default: No alias is defined.

§B.6 Comment element (optional)

6tAZng [§3.1]

The sequence of characters represented by the ^txLng is a comment to accompany the declaration.

Default: No comment is defined.

-49-

C VARIABLE DECLARATIONS

§C.l Name e lement (required)

vcuUabl?.- nav.z-oZomznt nayr\z [§5.1]

This element specifies the name (§1.2) for the declaration.

No \}(VUjxblQ.-ncm(L-Ql.2yn2.nX. may be the same as any other vOJiiabto.-mmz-^e/mnt, ^eX-narm-^ermnt (§A.l), paAame.t^-naxm-&Z2rmnt (§B.l), corUt/uUnt-ncumz-^Z^ymnt (§D.l), obje,ctlv&-na}-ne.-2Z2}mnt (§E.l), or Ind^X-name. (§6.2) defined in the model.

§C.2 Attribute element (optional)

attfu.biite.i .. .

oUJAX-butzl ->■ NONNEGATIVE NONPOSITIVE UNRESTRICTED

CiWUbuX&2 -^ CONTINUOUS INTEGER

There must be at most one attAlb'.Lte.!. The choice of (Xtt^bute.1 may impose a restriction on the class of feasible solutions, as follows:

-50-

NONNEGATRn; — A solution Is feasible only if all variables defined by the declaration have zero or positive activities.

NONPOSITIVE — A solution is feasible only if all variables defined by the declaration have zero or negative activities.

UNRESTRICTED — A solution may be feasible regardless of the signs of the variables defined by the declaration.

There must be at most one cutXnXhatZl. If cuWu.buX.z2 is INTEGER, a solution is feasible only if all variables defined by the declaration have integral activities. If cuWUbtxtcl is CONTINUOUS, a solution may be feasible regardless of the activities' integrality.

Default ; If no cUt/UbuXzl is specified, UNRESTRICTED is assumed. If no (vUUUhutzl is specified, CONTINUOUS is assumed.

§C.3 Indexing element (optional)

\)cvila.blt-lndQ.xX.nc\-di(m2.nt ->■

lnd<iXA,nQ-<Lxpfi(K>&i.on [§6.3]

A group (§1.2) of variables is declared if and only if this element is present. The group contains one variable corresponding to each index (§6.1) specified by the lndzxln2-ZxpfiU>i>lon.

Default: A single (§1.2) variable component is declared.

-51-

IC.A Specific ation element (optional)

LinoaA-OinAMmzXMc-zxpfi^&A^on [§2.6]

This element indicates that each declared variable represents the activity of a particular linear form (which may be a constant), as follows;

If the declaration is for a single variable: any reference to that variable represents the activity yielded by evaluating the LinZOA-aJUXkir\QjUjn- dxpfiojillon.

If the declaration is for a group of variables: any reference to a variable in the group represents the activity yielded by evaluating the tin^/XM.-aAXMmiltic.-ilxpn.ZMition with respect to that variable's corresponding index (§§6.6, C.3).

Default : The model does not indicate what activity each declared variable is to represent.

§C.5 Alias element (optional)

va/UablQ.-aLlcL6-zteme.nt -*■ 4>VUng [§3.1]

The sequence of characters represented by the JkiAi-ViQ is the alias (§1.2) for the declaration.

Default: No alias is defined.

-52-

§C.6 Comment element (optional)

vaAX/J.bl£.- conrndnt- (^Z<im(iYVt 6tAlnQ [§3.1]

The sequence of characters represented by the 6VvinQ is a comoent to accompany the declaration.

Default: No comment is defined.

-53-

D CONSTRAINT DECLARATIONS

§D.l Name eletoent (required)

con&tAdiyit-namt-iZ&mnt

namz [§5.1]

This element specifies the name (§1.2) for the declaration.

No C0Yi6tAaA,)\t-)iamz-zZ(mznt may be the same as any other C0Yii>tnj0U.nt-Yicanz-dLamZYVt^ ^oX-namz-zlomzYit (§A.l), poAMnztoJi-mmz-dizmzrvt (§B.l), \janlabl.z-n(mz-zZQm2yit (§C.l), objzcitivz-namz-dizmzYVt (§D.l), or -turfex-no/rie (§6.2) defined in the model.

§D.2 Attribute element (optional)

BOUND GUB

This element indicates that each declared constraint has one of

the following special forms:

BOUND — an upper bound, lower bound, or both on one particular variable.

GUB — a "generalized upper bound": upper and lower bounds on an unweighted sum of variables, or on the difference of two such sums.

Default : No special form is indicated.

-54-

§D.3 Indexing element (optional)

yind(Lxi.nQ-e.x.pfiQj>i,A.on [§6.3]

A group (§1.2) of constraints is declared if and only if this element is present. The group contains one constraint corresponding to each index (§6.1) specified by the xnc/excng-expA.eA4-con.

Default ; A single (§1.2) constraint component is declared.

§D.A Specification element (required)

lk& = nki> [1]

llu <== nk& [2]

£/lA >= A/l4 [3]

nJui <= Ihs <= fihj>2 [4]

I , -^1 >= lhf> >= Aiii>2 [5]

togicjxJi-zxpns^iilon [§4.5] [6]

Zk& -> ^neoA-oA.c-t/wie-tcc-exp'^eA^-con [§2.6]

nk6 -> tinzjOLA.-anAjhmQjtic--Q,xpfiu&lon [§2.6]

fih&l, nhi>2 -»- coni>tayvt-aMX.lvmtic-ZKpKeMA,on [§2.5]

If the declaration is for a single .^castraint, this element specifies a condition that must be satisfied by a feasible solution.

If the declaration is for a group of constraints, each constraint in the group imposes a condition that must be satisfied by a feasible solution. The condition imposed by any particular constraint is

-55-

deterndned by interpreting lk6 ^ hki, or Ahil and n>U2, or the toglcaZ.-e.Kp^eAi>ion with respect to the particular constraint's corresponding index (§§6.6, D.3).

The nature of the condition represented by a CCnitfiO-int-Ap^CA-^CCLtcon-elemejit depends on its form. Specifically, a solution is feasible only if:

Form [1] ; The numerical value represented by tki equals that represented by AivJ.

Form [2] ; The numerical value represented by Iki is less than or equal to that represented by aPU).

Form [3] ; The numerical value represented by Zh6 is greater than or equal to that represented by fih&.

Form [4 ]; The numerical value represented by aJuI is less than or equal to that represented by £/i6, and the numerical value represented by £/i4 is less than or equal to that represented by fihil.

Form [5] : The numerical value represented by fihil is greater than or equal to that represented by Zkiy and the numerical value represented by th& is greater than or equal to that represented by -'l/iAZ.

Form [6] : The £ogXca£-expAe64-con is true. (Since a loglcjxl-ZXpn.U,&A.on may not contain vaA^a6£&-4ei^e/Lences, this form does not constrain the activities of any variable; rather, it specifies a condition on the model's set and parameter data. Hence this form can be used to insure that the model's data are valid, as demonstrated in the examples of Part III.)

-56-

§D.5 Alias element (optional)

constAOAnt-atLaA-iiZafmnt

6tAA.ng [§3.1]

The sequence of characters represented by the 6tAA,ng is the alias (§1.2) for the declaration.

Default: No alias is defined.

§D.6 Comment element (optional)

conit/uUnt-conrne.nt-eZoytie.yvt

itxing [§3.1]

The sequence of characters represented by the iitA<.nQ is a comment to accompany the declaration.

Default: No comment is defined.

-57-

E OBJECTIVE DECLARATIONS

§E.l Name elgnh^nt (required)

noma [§5.1]

This element specifies the name (§1.2) for the declaration.

No objQ,(lti\}Z-ncm^-^Z^yi\lli^t may be the same as any other obje.ctlve.-namerzlermnt, ^zt-namz-QZoynznt (§A.l), paJumoJizfi-namz-ztQynzYVt (§B.l), vaAA^abZe.-n(me,-zZQjnzYit (§c.l), con^.tAacnt-nattie-eXoTieitt (§D.l), or Indzx-ncm^. (§6.2) defined In the model.

§E.2 Attribute element (optional)

ob izctcvz-attilbutz- eZ^rmnt

COMPUTE

MAXIMIZE

MINIMIZE

MAXIMIZE indicates that: (a) the declared objective, or objectives in the declared group, specify linear combinations of the model's variables; and (b) the value represented by any such objective may meaningfully be maximized subject to conditions imposed by the model on the variables' feasibility (§§C.2, D.4).

MINIMIZE is analogous to MAXIMIZE, except that it indicates objectives whose values may meaningfully be minimized.

-58-

COMPUTE indicates that no assuaptions of the sort specified by MAXIMIZE or MINIMIZE are to be made. Default : COMPUTE is assumed.

§E.3 Indexing element (optional)

ZndzxA.ng-iLxpn.Q^6<.on [§6.3]

A group (§1.2) of objectives Is declared If and only if this element is present. The group contains one objective corresponding to each index (§6.1) specified by the -cnd^xx^ng-exp-^^4-i.con.

Default: A single (§1.2) objective component is declared.

§E.A Specification element (required)

ob izctlve.-6pzcX.f^ccLtcon-Ql2}nQ.nt -> (Vilthir]ztlc-e,xpAe.6:,wn [§2.4]

This element indicates what each declared objective represents, as follows:

If the declaration is for a single objective, it represents the function of the variables' activities determined by evaluating the oA-cthmeXtc-expA.e64^on.

If the declaration is for a group of objectives, each objective in the group represents the function of the variables determined by

-59-

interpretlng the cVuX}wiQjU.C-Zxpn.U.iA.on with respect to that objective's corresponding index (§§6.6, E.3).

If the declaration's obja.cXX\J^-Citt''uhtLt(l-^tQjin(liit (§E.2) is MAXIMIZE or MINIMIZE, the OAAMmeJUc-ZXpfieJt^-ion must be a tindOA-(VuXivneXia-e.xpA.e.66-ion (§2.6).

§E.5 Alias element (optional)

obj'active,-clIIcus -^emant ->-iPUng [§3.1]

The sequence of characters represented by the ^t^ting is the alias (§1.2) for the declaration.

Default ; No alias is defined.

§E.6 Comment element (optional)

itfUYlQ [§3.1]

The sequence of characters represented by the ttxing is a comment to accompany the declaration.

DefauiLt: No comment is defined.

PART III EXAMPLES OF XML MODELS

-63-

EXAMPLE 1:

A MULTIPLE-PERIOD INPUT-OUTPUT MODEL

This problem is a variation on coimnon input-output economic models. A fixed set of artivity matrices is used to model production over many periods. The objective is maximum cumulative production in one industry (rather than lainimum cost, which is more common).

The model given here is a generalization of an example presented in G. Hadley's Linear Programming [3], problem 13-23, page 513. An account of how a typical matrix-generator system handles the same model may be found in the DATAMAT Reference Manual [5], Part 1, Example 2.

The transcription to XML is fairly straightforward. Original parameter and variable names have been retained in the XML model for clarity; alias elements could be added if more mnemonic names were desired for reporting. Note that the model declares a group of objectives, each representing total production of a different industry in set OBJ: the modeler may choose to maximize any of these, or even several successively.

-64-

ORIGINA L FORMULATION, EXAJ-tPLE 1

An economy comprises a variety of industries, each manufacturing a particular product. Production is to be modeled over a number of time periods, subject to the following constraints:

• There is an initial stock of each product. Stocks may be built up or run down in subsequent periods.

• Each industry requires certain fixed amounts of various inputs for each unit of its product manufactured. The Inputs are of two sorts: endogenous inputs which are products of industries in the economy, and exogenous inputs whose supplies are postulated (labor, for instance).

• Each industry has an initial capacity. Capacities may be increased (but not decreased) in any period, but the added capacity may not be used until the following period. Analogously to production, each industry requires certain fixed amounts of various inputs — endogenous and exogenous — for each unit of increase in capacity.

• There is an initial supply of each exogenous input; the supply Increases by a fixed percentage in each subsequent period.

• Each industry must satisfy an exogenous demand for its product in each period. There is an initial exogenous demand for each product, and this demand increases by a fixed percentage in each subsequent period.

The objective is to maximize the total production of a particular

industry over all periods.

To express the problem as a linear program, let T be the number of

periods, n the number of industries, and PI the number of exogenous inputs.

The variables may then be specified as:

-65-

4 .(^) stock of product i. at beginning of period t\ ^ = 1, ..., n; ;t = 1, .... T+1

X-C-t) quantity of product i. manufactured in period -t;

''I. (-i) increase in capacity of industry i in period -t;

The parameters of the problem can be specified as four matrices and

six vectors, whose elements are:

A.. number of units of product i. required to produce 1 unit of product /;^ = 1, ...,n;y = l, ...,)a

A. - number of units of exogenous input -c required to produce 1 unit of product j; ^ = 1, ..., k; y = 1 n

v. number of units of product -c required to increase

capacity of industry j by 1 unit; x^ = 1, ..., n; y = 1, ..., n

P. • number of units of exogenous input i. required to increase capacity of industry j by 1 unit;

e- initial stock of product ^; ^c = 1, ..., n

C- initial capacity of industry x; ^ = 1, ..., n

C. initial supply of exogenous input ^; -c = 1, ..., n

Y • fractional increase in supply of exogenous input -i per period; ^ = 1, ..., n

b. initial exogenous demand for product 't; X = 1, ..., n

3 . fractional increase in exogenous demand for product i. per period; -c = i, ..., n

The objective is to maximize the total production, Ej. X (-C) , of some

'C Z

industry j. The constraints may be expressed in five classes. First are the initial stock constraints

4^(1) = e^ I = \y ... , n

-66-

Second are the production constraints , which specify thit the quantity of a product manufactured in a period equals (i) the quantity required by

all industries for production in the period, plus (ii) the quantity

required by all industries for expansion of capacity in the period, plus

(ili) the exogenous demand in the period, plus (iv) the net change in

stocks:

Third, capacity constraints dictate that production must not exceed an industry's capacity, which is its initial capacity plus the sum of all increases in prior periods:

x^C-t) ^ (^1 + l~^i '^^('^) ^ = 1, ... , n; ^ = 1, ... , T

Fourth, supply constraints ensure that the quantity of exogenous inputs consumed does not exceed the available supplies:

Fifth, all variables must be nonnegative.

-67-

XML REPRESENTATION, EXAMPLE 1

SETS

ind COMM: 'Industries'

ex COMM. 'Exogenous inputs'

obj COMM: 'Subset of industries whose production may be maximized'

dhat

ATTR: INDX: COMM:

ATTR: INDX: COMM:

ATTR: INDX: COMM:

ATTR: INDX: COMM:

POSITIVE INTEGER 'Number of periods'

NONNEGATIVE

OVER ind * ind

'Endogenous production matrix: a[i,j] is units of product i required to make 1 unit of product j'

NONNEGATIVE

OVER ex * ind

'Exogenous-input production matrix: ahat[i,j] is units of exogenous input i required to make 1 unit of product j'

NONNEGATIVE

OVER ind * ind

'Endogenous capacity-increase matrix: d[i,j] is units of product i required to increase capacity of industry j by 1 unit'

NONNEGATIVE

OVER ex * ind

'Exogenous-input capacity-increase matrix: dhat[i,j] is units of exogenous input i required to increase capacity of industry j by 1 unit'

NONNEGATIVE

OVER ind

'Initial stocks of products'

NONNEGATIVE

OVER ind

'Initial capacities of industries'

-68-

PARAMETERS (continued)

chat ATTR: NONNEGATIVE INDX: OVER ex COMM: 'Initial supplies of exogenous inputs'

gamma ATTR: NONNEGATIVE

INDX: OVER ex

COMM: 'Fractional Increases (per period) in supplies of exogenous inputs'

b ATTR: NONNEGATIVE INDX: OVER ind COMM: 'Initial exogenous demands for products'

beta ATTR: NONNEGATIVE INDX: OVER ind COMM: 'Fractional increases (per period) in exogenous demands'

VARIABLES

s ATTR: NONNEGATIVE

INDX: OVER ind, FROM 1 TO p+l

COMM: 'Stocks: s[i,t] is stock of product 1 at beginning of period t'

X ATTR: NONNEGATITO

INDX: OVER ind, FROM 1 TO p

COMM: 'Production: x[l,t] is quantity of p'-oduct i manufactured in period t'

r ATTR: NONI'IEGATIVE

INDX: OVER ind, FROM 1 TO p

COMM: 'Capacity increase: r[i,t] is increase in capacity of industry i in period t'

OBJECTIVES

prod

ATTR: MAXIMIZE

INDX: i OVER obj

SPEC: SIGMA t FROM 1 TO p (x[i,t])

COMM: 'Maximize total production (over all periods) in objective industry'

-69-

CONSTRAINTS

subset SPEC: COMM:

inlt ATTR: INDX: SPEC: COMM:

prod INDX: SPEC:

COMM:

cap

sup

INDX: SPEC: COMM:

INDX: SPEC:

COMM:

obj IN ind

'Objective industries are a subset of all Industries.'

BOUND

i OVER ind

s[i,l] = e[i]

'For each industry: stock variable for period 1 must equal initial stock.'

i OVER ind, t FROM 1 TO p

x[i,t] = SIGMA j OVER ind (a[i,j] * x[j.t]) + SIGMA j OVE,R ind (d[i,j] * r[j,t]) + (l+beta[i])**(t-l) * b[i] + s[i,t+l] - s[i,t]

'For each industry in each period: production must equal the sura of:

(1) Output used in endogenous production,

(2) Output used in increasing capacity,

(3) Output absorbed by exogenous demands, and

(4) Net change in stocks.'

i OVER ind, t FROM 1 TO p

x[i,t] <= c[i] + SIGMA tt FROM 1 TO t-1 (r[i,tt])

'For each industry in each period: production must not exceed initial capacity plus total of capacity added in previous periods.'

i OVER ex, t FROM 1 TO p

SIGMA j OVER ind (ahat[i,j] * x[j,t]) + SIGMA j OVER ind (dhat[i,j] * r[j,t])

<= (l+gamma[i])**(t-l) * chat[i]

'For each exogenous input in each period: total input used in production plus total input used to increase capacity must not exceed current supply.'

-71-

EXAMPLE 2:

A MODEL FOR ALLOCATING TRAIN CARS

This model describes the allocation of cars to trains in a route network, given a schedule and demands for each scheduled train. The objective may be to minimize total cars, total car-miles, or some tradeoff between the two.

The original formulation given below is adapted from a study of service requirements in the Northeast Corridor [1], The equivalent XML model differs mainly in employing more mnemonic terminology. Note the convenience of using a set of ordered quadruples to represent the schedule.

-72-

ORIGINAL FORMULATION, EXAMPLE 2

A uniform fleet of passenger cars provides railroad service to a set of cities. Service is offered by means of a set of scheduled "trains", each comprising one or more cars and running between a given pair of cities. At any given time, each car in the fleet is either part of some currently running train, or is sitting in storage at one of the cities.

Three things constrain the size and deployment of the fleet: a fixed schedule, known demands for scheduled trains, and a standard station length at all cities.

Fixed schedule . The schedule lists all trains that depart in a chosen schedule-period (a day, for example). IXiring the schedule-period, every scheduled train must be run, carrying one or more cars.

It is assumed that each schedule-period is followed immediately by another, identical schedule-period. Moreover, the same service is to be provided in every schedule-period: that is, the same schedule must be rim, with the same allocation of cars to cities and trains.

Each entry in the schedule specifies a city of departure and a city of arrival, and corresponding departure and arrival times. In general, a train may arrive during the schedule-period (e.g., day) of departure, or during any subsequent period. For simplicity, however, it is assumed here that every train arrives either in the same period, or at an earlier time in the next period. (If the schedule-period is a day, this just says that a train arrives either the same day that it leaves, or the next day; and that every trip lasts less than 24 hours.)

A car that arrives at city c at time t is free to leave c in any scheduled train that departs at t or later. (Stopover delays at the arrival city — to discharge and board passengers, for example — are

-73-

consldered part of the preceding trip, and are reflected by adjusting the arrival time in the schedule accordingly.)

Demands . For each scheduled train there is a known demand which must be ir.et; hence there is a minimum number of cars required in each train. A train may be larger than its minimum size, however, if circumstances require that extra (deadhead) cars be shifted from one city to another.

Station length . Stations' loading platforms can accomodate only a certain number of cars (assumed to be fixed throughout the system). If the demand for a scheduled train exceeds this number, two or more sections are run.

For each train, there is a minimum number of sections that can meet demand. Since sections are expensive, it is required that no train be run with more than the minimum number of sections. This requirement places an upper limit on the number of cars (including deadheads) assigned to a train.

All of these requirements can be expressed formally as linear

constraints on variables. To begin, define the following sets:

C The set of cities

T = {0, ».., T-1} A set of T times into which the

schedule-period is divided.

S c {(c^,t^,C2>t2)' C-^cCj 0-2^^, t^zT, t2^T; c^ ^ C2)

The schedule: each member represents a train that leaves city c-^ at time ti and arrives at city C- at t„

-74-

d_ ^ [^T,-to] The smallest (integral) number of cars C1C2 1 ^

required to meet demand for train

^^l''^l''^2'^2^ e S

Define two collections of variables:

u.„[t] Unused cars stored at city c in the interval

beginning at time -t, for all ceC, tcT

X [-t^,-t„] Number of cars assigned to the scheduled train that leaves c, at t, and arrives at

0-2 ^^ ^2 The model can now be expressed by three sets of constraints. First,

all cars must be accounted for at each time in each city:

ujt] = aj(i-l) n^d T] + I X [^^.^] - I ^,^^'^2^

for all CeC, teT

(In words: cars in storage at C at time -t must equal cars in storage in the preceding interval, plus cars that arrived in trains at t, less cars that left in trains at t.) Second, the nunfcer of cars in each train must both meet demand and require no superfluous sections:

for all (c^,^. ,c„,;f-) e S

Third, the number of cars stored must be nonnegative:

u^[t] > 0 for all ceC, tcT

In addition, a useful solution must deal only in integral numbers of cars; but, fortunately, these constraints have 3 or>.->cial form that guarantees integrality of every basic solution produced by the simplex algorithm.

It remains to formulate some linear objectives for the model. Two simple ones are as follows:

-75-

Cars . Minimize the number of cars in the system, expressed as the following linear form:

CeC ^ (Cj^,t^,c^,t^)cS ^^1^2

This counts all cars at the last interval, x-l, of the schedule-period. The first sum is all cars in storage during this interval, while the second counts all cars in transit during the interval.

Miles . Minimize total car-miles run in a schedule-period. Letting

m be the distance from C, to c„, this objective is also a linear form:

C1C2 1 2' -■

-76-

XML REPRESENTATION, EXAJIPLE 2

SETS

cities

times

COMM:

SFEC: COMM:

'Set of cities'

SEQ(0,intervals-l)

'Set of intervals into which a schedule-period is divided'

schedule ATTR: LENGTH 4

COMM: 'Member (cl,tl ,c2,t2) of this set represents a train that leaves city cl at time tl and arrives at city c2 at t2'

PARAMETERS

intervals

section

ATTR: POSITIVE INTEGER

COMM: 'Number of intervals into which a schedule-period is divided'

ATTR: POSITIVE INTEGER

COMM: 'Maximum number of cars in one section of a train'

POSITIVE INTEGER

OVER schedule

'For each scheduled train: smallest (integral) number of cars that meets demand for the train'

POSITIVE

OVER PROJ(schedule,1,3)

'Inter-city distances: distance[cl,c2] is miles between city cl and city c2'

VARIABLES

u

ATTR: NONNEGATIVE

INDX: OVER cities * times

ALIAS: 'unused'

COMM: 'Storage variables. u[c,tj is number of unused cars stored at city c in the interval beginning at time t'

INDX: OVT.R schedule

ALIAS: 'train'

COMM: 'Train variables: x(cl,tl ,c2,t2 ] is number of cars assigned to scheduled train that leaves cl at tl ami arrives c2 at t2'

OBJECTIVES

-77-

cars

miles

ATTR: MINIMIZE

SPEC: SIGMA c OVER cities (u[c,intervals-l]) + SIGMA (cl,tl,c2,t2) OVER schedule

WHERE t2 < tl (x[cl,tl,c2,c2])

COMl-I: 'Number of cars in the system: Sum of unused cars and cars in trains during the last interval of the schedule-period.'

ATTR: MINIMIZE

SPEC: SIGJIA (cl, tl,c2 , t2) OVER schedule

(disitance[cl,c2] * x[cl,tl,c2, t2])

COMM: 'Total car-miles run by all scheduled trains in one schedule-period.'

satisfy

COMM:

ATTR: INDX: SPEC:

COMM:

(cl,c2) OVER PR0J(schedule,l,3)

cl IN cities AND c2 IN cities AND cl ~= c2

'Every train in the schedule must go between two different recognized cities.'

(tl,t2) OVER PROJ(schedule,2,A)

tl IN times AND t2 IN times

'Every train in the schedule must leave and arrive at recognized times.'

c OVER cities, t OVER times

u[c,t] = u[c,(t-l) MOD intervals] + SIGMA (cl,tl) OVER SECT(schedule ,c, 3,t,4) (x[cl,tl,c,t]) SIGMA (c2,t2) OVER SECT(schedule ,c,l, t,2) (x[c,t,c2,t2])

'For every city and time: Unused cars in present interval must equal unused cars in previous interval, plus cars just arriving in trains, minus cars just leaving in trains.'

BOUND

(cl,tl,c2,t2) OVER schedule

demand[cl,tl,c2,t2]

x[cl,tl,c2,t2] <=

section * CEIL(demand[cl,tl,c2,t2]/section)

'For each scheduled train: Number of cars must meet demand, but must not be so great that unnecessary sections are run.'

-79-

EXAMPLE 3:

MODELING ALTERNATIVE ENERGY SOURCES

This model was developed by Alan S. Manne and Oliver S. Yu [4] to project the interaction of alternative future electricity-generating systems, with their corresponding fuel needs and limits, under certain assumptions of demand growth.

The original description of the model is reproduced below, followed by a fairly straightforward XML transcription. Periods numbered through 75 in the original have been changed in XML to actual year numbers (1970 through 2045). For clarity, all parameters of the XML model are symbolic; the explicit numerical values for some parameters in the original would be included with the rest of the XML model's data.

-80-

ORIGINAL FORIIULATION, EXA>tPLE 3

Unknowns:

PC = base-load equivalent capacity, source i, period t

DP = annual rate of capacity, source 1, period t

3 (units of measurement: TW = terawatts = 10 GW

= 6.57 • 10^^ K\m/yeaT.)

NURQ = annual requirements for natural uranium, cost level I, period t (Units of measurement: 10 tons)

Note: A bar' above a symbol indicates that the particular variable is exogenously specified.

Constraints:

CP - capacities, energy sector (i = COAL, LWR, FBR, ADV)

capacity and production, current period

capacity and production, 3 years previously

+3

annual capacity increase, current period

annual capacity retirement, after 30 years of service

PC^

1

PC

t-3

+3 [

DP

DP

t-30

where PC = 0

-81-

NC - new capacity shares (i = COAL, LWR, FBR, ADV)

These represent limitations on the availability and rate of adoption of new technologies.

^^COAL ^ '" f^^COAL ^ Km "■ ^4br] where 6*^ = .30 for t = 3, 6, ..., 30

and e*^ = .24, .18, .12, .06

for t = 33, 36, 39, 42, respectively.

DPj^^ < .00148t for t = 3, 6, ..., 30.

where 6*^ = .10, .20, .40, .60

for t = 24, 27, 30, 33, respectively.

Note: DP^„„ =0 for t = 3, 6, .... 21.

where 9*^ = .10, .20, .30, .40, .50, .60

for t = 45, 48, 51, 54, 57, 60, respectively.

Note: DP^ = 0 for t = 3, 6, ..., 42.

-82-

DM^ „„ - final demands

iLEC

remaining initial electric capacity, fossil-fired, exogenous

+

hydroelectric capacity, exogenous

4-

new electric capacity.

endogenous

final demands for

electricity, exogenous

RI

FOSS

+

PC

HYDR

^ t^^COAL + Km ■" ^^BR •" ^^IdvJ ^ ^^-ELEC ^'-^'^

where D>Lj,

0

LEG

J2

1.53 10 KWH/year ^

8.76(.75) 10-

H/year

!33

TW

PC

,247

HYDR 8,76 (.75)

(1.01)

= .038 (1.01) TW

RI

0

1.53-.247

FOSS 8.76(.75)

= .195

TW

The retirement schedule for the remaining initial electric capacity from fossil fuel (Rip ^) is calculated on the basis of a 30-year service life, assuming that the capacity increments grew at the annual rate of 7% during the 30 years preceding time 0.

-83-

t 18

SM - cumulative sum of coal cunsumption (10 BTU)

cumulative sum, end of current period

cumulative sum, 3 years previously

fio3 h

hours +3 per year

r

J.

heat rate

base-load

equivalent

capacity

CS

COAL

CS

t-3 COAL

+3 [8.76(.75)] [.01 ] [.54RI4^-.PCJ^^]

SM^ - natural uranium requirements (10 tons)

current annual consumption of uranium

annual refueling requirements

annual requirements for initial inventories, next period

^2^ NURqJ > .18 PC

LWR

+

,50 DP

t+3 LWR

CRQU - upper bound on uranium consumption at cost level 5, (10 tons)

cumulative uranium consumption at cost level i

cumulative availability of uranium at cost level £, exogenous

3 lHo NURqJ

CAVU.

-84-

COST - minimand

Present value of costs incurred annually during each 3-year period over 75-year horizon:

present value of 3-year costs

current costs, annua

) /invest

+ V costs,

troent \ annuaiy

/termJ-nal \ /present value\ /valuationx / factor for \

factor, 30-year

,service

Uife

P fa

incurring capital costs 2 years prior \to period t ,

-2,

flt=0 ^^^ ^^i ^"''i ^^i ^ ^^i ^^Pi °^i ^ ^^ " "^t^ ^^ ^

] ]

(unit: $10 )

Where B = -rr^ = one year present-value factor at r% discount rate .78-t

TV^ = 6

for t > 45; 0 otherwise

It is supposed that interest during construction is included in the capital cost coefficients, cap.. These costs are incurred at the coTTimissioning date — two years prior to full power operations — hence the terra 3 ~.

-85-

XML REPRESENTATION, EXAMPLE 3

SETS

source

SPEC:

{coal: 'coal-fueled fossil plants',

Iwr: 'light-water reactors',

fbr: 'fast breeder reactors',

adv: 'advanced technology'}

'Energy sources'

'Arbitrary set of uranium cost levels'

SEQ(1970,2045,3) 'Planning horizon'

POSITIVE

'One-year present-value factor'

t 0\^R horizon

(pv**(2048-t)) * MAX(0,t-20Q0)/(t-2G00)

••Terminal valuation factors: tv[t] = pv ** (2048-t) if t > 2000, = 0 otherwise'

POSITIVE

OVER source

'Annual current costs'

POSITIVE

OVER source

'Annual capital costs'

NONNEGATIVE

FROM 1973 TO 2012 BY 3

'Minimum share in new capacity, coal'

NONNEGATIVE

Factor for maximum new capacity, Iwr'

NONNEGATIVE

FROM 1994 TO 2003 BY 3

'Maximum share in new capacity, fbr'

-86-

PARAMETERS (continued)

sh adv

dm elec

pc_hydr

ri foss

cavu

ATTR: NONNEGATIVE

INDX: FROM 2015 TO 2030 BY 3

COMM: 'Maximum share in new capacity, adv'

ATTR: POSITIVE

COMM: 'Initial final demand for electricity'

ATTR: POSITIVE

COMM: 'Initial hydro-electric capacity'

ATTR: NONNEGATIVE

INDX: OVER horizon

COMM: 'Remaining initial electric capacity, fossil fired'

ATTR: POSITIVE

INDX; OVER cost

COMM: 'Cumulative availabilities of uranium'

NONNEGATIVE

OVER source * horizon

'Base-load equivalent capacities, each source and period'

NONNEGATIVE

OVER source * horizon

'Annual rate of addition of new capacity, each source and period'

NONNEGATIVE

OVER cost * horizon

'Annual requirement for natural uranium, each cost level and period'

NONNEGATIVE

OVER horizon

'Cumulative sum of coal consumption, end of each period'

OBJECTIVES

-87-

cost

ATTR: MINIMIZE

SPEC: SIGMA t OVER horizon (3 * pv**(t-1970) *

(SIGMA i OVER source (cur[i] * pc[i,t]) + SIGMA i 0\'ER source (capfi] * dp[i,t]) *

(l-tv[t]) / pv**2) )

COMM: 'Sum of present values of current costs and

investment costs incurred in all periods over horizon'

init dp Iwr

nc Iwr

inlt_dp_coal ATTR SPEC COMM

nc_coal INDX: SPEC:

COMM:

ATTR SPEC COMM

ATTR IITDX SPEC COMM

BOUND

i OVER source

pc[i,1970] = 0

'Initial base-load equivalent capacities are zero,'

i OVER source, t OVER horizon WHERE t ~= 1970

pc[i,t] = pc[i,t-3] + 3*(dp[i,t]-dp[i,MAX(1970,t-30)])

'For each source and period: Capacity now must

equal capacity 3 years ago, plus change in capacity

over previous 3 years (assuming retirement after 30 years' service).'

BOUND

dp['coal',1970] = 0

'Initialize dp for coal.'

t FROM 1973 TO 2012 BY 3 /

dp['coal',t] >= sh_coal[t] *

(dp['coal',t]+dp['lwr',t]+dp['fbr',t])

'From 1973 to 2012: Coal must have at least a certain share of new capacity.'

BOUND

dp['lwr',1970] = 0

'Initialize dp for Iwr.'

BOUND

t FROM 1973 TO 2000 BY 3

dp['lwr',t] <= sh_lwr * (t-1970)

'From 1973 to 2000: New capacity in Iwr cannot exceed sh Iwr per year,'

-88-

CONSTRAINTS (continued)

lnit_dp_fbr

nc fbr

inlt dp adv

nc adv

fdm elec

init cs coal

sm coal

ATTR: BOUND

INDX: t FROM 1970 TO 1991 BY 3

SPEC: dp['fbr',t] = 0

COMIl: 'No fbrs before 1994.'

INDX: t FROM 199A TO 2003 BY 3

SPEC: dp['fbr',t] <= sh_fbr[t] *

(dp['coal' ,t]+dp['lwr' ,t]+dp['fbr',t])

COMM: 'From 1994 to 2003: fbr must have at most a certain share of new capacity.'

ATTR: BOUND

INDX: t FROM 1970 TO 2012 BY 3

SPEC: dp['adv',t] = 0

COMM: 'No adv before 2015.'

INDX: t FROM 2015 TO 2030 BY 3

SPEC: dp['adv',t] <= sh_adv[t] * SIGMA i OVER source (dp[i,t])

COMM: 'From 2015 to 2030: adv must have at most a certain share of new capacity.'

INDX: t OVER horizon

SPEC: ri_foss[t] + 1.01**(t-1970) * pc_hyfir

+ SIGMA i OVER source (pc[i,t])

>= 1.05**(t-1970) * dm_elec

COMM: 'For each period: Final demand for electricity must be met by sura of: remaining initial fossil-fired electric capacity (exogenous); hydro-electirc capacity (exogenous); and new endogenous capacities.'

ATTR: BOUND

SPEC: cs_coal[1970j = 0

COMM: 'Initial cumulative sum of coal consumption is zero.'

INDX: t OVER horizon \fflERE t ~= 1970

SPEC: cs_coal[t] = cs_coal[t-3] +

1.971 * (0.54*ri_foss[t] + pc['coal",.])

COMM: 'For each period: Cumulative sum of coal consumption equals cumulative sum to previous period plus additional consumption during period.'

-89-

CONSTRATNTS (continued)

sm natu

crqu

INDX: t OVER horizon \vHERE t ~= 2045

SPEC: SIGMA c OVER cost (nurq[c,t])

>= 0.18*pc['lwr' ,t] + 0.50*dp['lwr',t+3]

COMM: 'For each period: Annual consumption of uranium

must equal or exceed annual refueling requirements plus annual requirement for initial inventories in next period.'

ATTR: GUB

INDX: c OVER cost

SPEC: 3 * SIGMA t OVER horizon (nurq[c,tj) <= C3vu[c]

COMM: 'For uranium at each cost level: Cumulative

consumption must not exceed cumulative availability.'

-9i-

REFERFNCES

[1] Fourer, Robert, Judith B. Gertler, and Howard J. Simkowitz,

"Models of Railroad Passenger-Car Requirements in the Northeast Corridor". Annals of Economic and Social Measuremen t, vol. 6, no. 4 (1977), pp. 367-398.

[2] Fourer, Robert and Michael J. Harrison, "A Modern Approach to

Computer Systems for Linear Programming". Working Paper 988-78, Center for Computational Research in Economics and Management Science, Alfred P. Sloan School of Management, MIT. March 1978.

[3] Hadley, G., Linear Programming . Addison-Wesley Publishing Company, Reading, Massachusetts, 1962.

[4] Manne, Alan S. and Oliver S. Yu, "Breeder Benefits and Uranium Ore Availability" (preliminary draft). Electric Power Research Institute, Palo Alto, California, October 1974.

[5] National Bureau of Economic Research, DATAMAT Reference Manual (Third Edition). NBER Computer Research Center for Economics and Management Science, order no. D0078, July 1975.