ORSpek

m
OR Spektrum (1993) 15:43-55

9 Springer-Verlag 1993

LPL: A mathematical programming language

T. Hiirlimann
Institute for Automation and Operations Research, University of Fribourg, CH-1700 Fribourg, Switzerland

Received May 19, 1992/ Accepted in revised form October 21, 1992

Summary. This paper describes the new version of the mann and Kohlas 1988). The new version, exposed in this
modeling language, named LPL (Linear Programming paper, has been improved in several respects: A powerful
Language). It may be used to build, modify and document input and report generator has been integrated, the
mathematical models. The LPL language has been suc- expression syntax has been enlarged with several new
cessfully applied to generate automatically MPS input functions and operators, units can be used to measure
files and reports of large LP models. The available LPL numerical entities, restricted string manipulation is now
compiler translates LPL programs to the input code of possible, goal and multi-stage programming are also
any L P / M I P solver, calls the solver automatically, reads supported to some extent, and, finally, an open interface
the solution back to its internal representation, and the to most L P / M I P solver has been added. Many more
integrated Report Generator produces the user defined modifications and, hopefully, improvements have taken
reports of the model. Furthermore, an Input Generator place, but will not be mentioned here. A speciality of the
can read the data from many formats. old LPL version was its hierarchical indexing: Indices
were nested lists which could be used as any other index
Zusammenfassung. Dieser Artikel beschreibt die neue within a model. To use nested lists for indexing is very
Version der Modellierungssprache LPL (Linear Program- intriguing, since many sets of objects can be arranged as a
ming Language), die sich dazu eignet, mathematische tree in a natural way. Practical experiences, however, have
Modelle aufzubauen, zu warten und zu dokumentieren. shown that they obscured the model structure - at least in
Die LPL-Sprache wurde zum Erstellen yon MPS-Input- the form they have been implemented in LPL. Further-
Dateien und Resultate-Tabellen gr613erer LP-Modelle more, few modeling examples came around which used
erfolgreich eingesetzt. Der LPL-Compiler iibersetzt ein this option really. Many examples could be formulated
LPL-Programm, das ein vollst/indiges Modell reprfisen- more simply using relations. It was, therefore, decided to
tiert, in den Eingabecode eines LP/MIP-L6sungspro- drop hierarchical indexing from the LPL language. More
gramms, ruft den L6sungsalgorithmus auf, liest die L6- research work should be done, before hierarchical index-
sung, und ein integrierter Tabellengenerator gibt vom ing can be integrated in an advanced modeling language.
Benutzer definierte Resultate-Tabellen aus. Auf~erdem A first step in the right direction is (Bisschop 1991).
erlaubt ein Dateneingabe-Generator, die Daten in ver- Different modeling languages have recently been deve-
schiedenen Formaten zu lesen. loped. AMPL (Fourer et al. 1990), GAMS (Brooke et al.
1988), L I N G O (Schrage 1989), and SML (Geoffrion 1989)
Key words: Modeling, linear programming, compiler, are closest to the LPL language. These languages, and
MPS some others, have been compared in (Steiger and Sharda
1991). LPL has been updated since then and differs in
Schlfisselwiirter: Modellierung, lineare Programmierung, some respects from these other languages:
Compiler, MPS
9 LPL has an open interface to any L P / M I P solver. This
means that any linear solver can be called from within the
LPL code. The user can configure the communication
1. Introduction between LPL and the solver.
9 LPL contains input and report generator to read the
This paper presents the new version of the modeling data from files and to write the results to files. While
language LPL. A first version of LPL was developed and GAMS too includes a report generator only LPL has an
implemented some times ago. It was described in (Ht~rli- input generator. Actually, the input/report generator can
44 T. Hiirlimann: LPL

only read/write text files, although in a rather sophisti- Indices

cated way. A future version is planed to embed SQL j bonds (j-I,...,N)
statements to extend the language for database access. t time periods (t=l,...,T) with T ~ 50
9 LPL has a flexible syntax: entities can be reassigned as Data Tables
in GAMS, but unlike GAMS a model structure can be cj current market price for bond j
parsed and compiled without the data specified. fit c a s h f l o w p r o d u c e d b y b o n d j attheendofperiodt
Lt cash requirement at the end of period t
9 LPL includes a Unit statement for measurement checks.
qj conditional m i n i m u m purchase quantity of bond j
9 Furthermore, LPL allows the user to generate alias- Qj m a x i m u m allowable purchase of bond j
names for variables and restrictions. at r e - i n v e s t m e n t rate for p e r i o d t
On the other hand, LPL is restricted to linear and integer Variables
models, and is not interactive. Another disadvantage xj quantity of bond j to be purchased here and now
which is common to all modeling languages should be s~ cash surplus to be a c c u m u l a t e d at the end of
period t
addressed: the poor and restricted communication to
dj is i, if bond j is selected for portfolio,
other model functions. Since the modeling language is a else it is 0
closed system, it must handled the model to the solver via
file transfer. For linear model, MPS is a standard. It is Minimize
costly in time to make the detour via the MPS-file. It ~=iC jXj+SO
would be much simpler to generate the model within the subject to
main memory where the optimizer can directly manipu- N L t for t=2, . . . ,T
j=ifjtxj+atst-l-St
late the model data. This is possible only when the LPL
xj-qjdj~O for j = l , . . . , N
object code and the optimizer code could be linked
xj-Qjdj<O for j = l , . . . , N
together.
A modeling language is certainly an important part of xj>O,st>O and dj~{O,l]
a modeling system, but various other tools should be Fig. 1
integrated within a model management system: Tools to
manage the model data (Blanning 1987; Dolk 1988), to
verify and analyse the model (Greenberg 1990), to docu-
ment the model (Gass 1984; Geoffrion 1989), as well as
2. A simple example
tools to support the evolution of a model.
The contribution of LPL is certainly only a first but
Figure 1 displays the algebraic formulation of a simple
important step towards a general model management
portfolio model (Shapiro 1988, p. 589f). This formulation
system. To summarize, the main features of LPL are:
can be translated directly on an LPL model formulation as
9 a simple syntax of models with indexed expressions shown in Fig. 2.
close to the mathematical notation, and directly appli- The algebraic formulation of Fig. 1 contains different
cable for documentation sections: Index-sets, numerical data-tables, variables (the
9 formulation of both small and large LP's with optional unknowns), a minimization function, and different con-
separation of the data from the model structure straints. Note that this formulation in Fig. 1 represents
9 availability of a powerful index mechanism, making only a model structure not a specific, instantiated model,
model structuring very flexible since no data are defined. To produce a specific model, it
9 an innovative and high-level Input and Report Gener- must be supplemented by the values of all index-sets and
ator data-tables.
9 intermediate indexed expression evaluation (much like Figure2 shows the entire model structure in LPL
matrix manipulation) syntax. The different sections of index-sets, data, varia-
9 automatic or user-controlled production of row- and bles, minimizing function, and constraints are headed by
column-names the reserved words, SET, COEF, VAR, MINIMIZE, and
9 tools for debugging the model (e.g. explicit equation MODEL. Units can be defined using the UNIT statement.
listing) Comments can be added anywhere between quotes or
9 built-in text editor to enter the LPL model {...}. Comments surrounded by the curly brackets can be
9 fast production of the MPS file used to document a model, but they do not belong to the
9 open interface to most L P / M I P solver packages. formal part of the model. Quoted comments, on the other
side, are part of the formal documentation used in the
The basic ideas of LPL are presented in Sects. 2 and 3
reports.
using a simple portfolio model example. Sections 4 and 5
Since an LPL model can be processed directly by the
examine the indices and expressions, the most important
LPL compiler, its formulation has some particularities
constructs of LPL. Some aspects of the report and input
compared to the algebraic notation: The sigma sign 2 is
generator are discussed in Sect. 6. Appendix. A lists, a
replaced by the reserved word SUM; subscript indices are
complete assignment model containing 2700 0-1 variables listed between parentheses; a semicolon must end every
(assign 180 players to 15 teams), which covers some
declaration. It is also possible to use multi-letter names in
interesting features of LPL. place of single-letter names. Hence, e ( j ) might be
replaced by marketprice (bond).
T. Hiirlimann: LPL 45

P R O G R A M portfolio; {syntax in LPL} {$C}

SET {Indices}
j; "list of bonds"
t; "time periods"

UNIT {measurement unitsi

dollar; "unit of cash"
percent = i/I00; "unit of percent (%)"
pieces;
unit Prix = dollar/pleces;

COEF {data tables}

c(j) UNIT 100*unit Prix; "current market price for bond j (in $i00)"
f(j,t) UNIT unit Prix; "cash flow produced by bond j in period t"
q(j) UNIT pieces; "conditional minimum purchase quantity of bond j"
Q(j) UNIT pieces; "maximum allowable purchase of bond j"
a(t) UNIT percent; "reinvestment rate for period t"
L(t) UNIT dollar; "cash available in period t"

VAR {variables}
x(j) UNIT pieces; "quantity of bond purchased"
s(t) UNIT dollar; "cash susplus"
d(j) BINARY; "=i if bond is seleeted, else =0"

MODEL {constraints}
invest UNIT dollar: SUM(j) c*x + s[l];
Cash_bal(t[t>l) UNIT dollar: SUM(j) f*x + a'sit-l} - s - L;
C(j) UNIT pieces: x - q*d > = 0{pieces};
D(j) UNIT pieces: x - Q*d < - 0{pieces};
initS UNIT dollar: s[l] = 0{dollar};

{$I model.dat} {read the model data from file MODEL.DAT}

MINIMIZE invest; {call the solver, and read the solution}
PRINT invest; x; s; d; {print the solution tables to a file}
END {--end of model formulation}

Fig. 2

{The file M O D E L . D A T is}

SET
j [ o I q [ Q: /
{.......................... }
A1 I 2 I lO l 5oo
A2 [ 2.S r I 7OO
A3 l 4 l I 700
A4 I 1 l 15 l 8oo
A5 1 2.4 ] 20 I 900
/;
COEF
TMAX INTEGER [0,i00] - 50; {a data not declared up to here}
L UNIT 1000*dollar; {redefine the unit (L is measured in $ I000)}
SET
t l a l a- /
{................... }
Ta I 12 l 90
T3 I 14 I 80
T4 I 5 I 80 / ;
COEF
f -
l T2 T3 T4
A1 4 4 4
A2 5.5 5 4
A3 5 3 6
A4 6 6
A5 4 5 61;
"some data c o n s i s t e n c y tests"
CHECK This(t): q < Q; "every q must be smaller than Q"
CHECK This: #t <= TMAX; "the eardinality of set t must be smaller than TMAX"

Fig. 3
46 T. Hfirlimann: LPL

Four additional instructions are found in the LPL SETMust_be_in(p,t)=/PlT2,P2T6,P3T7/;

model in Fig. 2:
This tuple-list defines a relation M u s t _ b e _ i n between
9 {$I... reads the model data from file M O D E L . D A T
the players p and the teams t . It tells, that player P1
written also in LPL syntax (Fig. 3),
belongs to team T 2 , player P2 to team T 6 , and player P3
9 M I N I M I Z E ... calls the solver and reads the solution
to team TT. It is important to note, that this relation
back to the LPL internal representation,
assigns only a sparse sublist of the whole (Cartesian)
9 PRINT ... prints the required tables to the output file,
tuplelist. Another example is to define sublists of players
9 the UNIT statements used within the model (see
as
Sect. 3.7).
A specific data set for this model is shown in Fig. 3 written SET p l a l ( p ) = / P l P45 P56 P67 P78 P 1 2 2 / ;
in LPL syntax. The data-tables can also be in plain text. SET p l a 2 ( p ) = / P2 P67 P 1 2 3 P 1 4 5 P 1 2 P 1 7 8 / ;
LPL includes a flexible Input Generator to read external
data definition (see Sect. 6). Indexed sets may also be assigned by logical expressions.
The union, the intersection and the difference of set p l a l
and p l a 2 may be defined as
3. A brief overview of the LPL language
SET u n i o n ( p ) - p l a l or pla2;
In this section, the different compoents of an L P L model SET i n t e r s e c t i o n ( p ) = p l a l and pla2;
are briefly presented. SET d i f f e r e n c e ( p ) = p l a l and not pla2;

Index-set is one of the most important components in any

3.1. Index-sets large-scale LP model. L P L offers a broad variety of
different set types.
An index-set is an unordered or ordered collection of
objects. They are called elements. The set o f b o n d s j i n our
example is such a set. A set is declared in LPL as 3.2. Numerical data

SET j ; "bonds" Numerical data within the model are collected in coeffi-
cients. Its declaration is headed by the reserved word
The elements itselfs of this set are not defined at this place, COEF. The simplest coefficient consists of only one value:
they are part of the model data defined in file
M O D E L . D A T (Figs. 2-3). The modeler is, however, free COEF TMAX INTEGER [0,100];
to declare a set and to assign its elements at the same place
within the model. The set j could have been defined as T M A X is declared as a coefficient, but its value is not yet
known. The declaration, however, tells that TMAX must be
SET j = / A I : A S / ; " j is a set of five b o n d s " an integer value within the range [0,100]. The LPL
compiler tests these conditions and reports an error, if
The two elements A1 and A5 separated by a colon define a they are violated. L P L offers also the CHECK stament
range of elements, which is the same as which can check the data consistency using more complex
conditions. The instruction
SET j = /A1 A2 A3 A 4 AS/;
CHECK This(j) : q < Q ;
where every element is mentioned explicitly. The element- "q m u s t be s m a l l e r t h a n Q for e v e r y j",
names A1, ..., A5 might also be replaced by more
meaningful names as in checks for every q over j , if q is smaller than Q.
Coefficients can also be indexed, and their values are
SET j = /World_bank88 Treasury_bills collected in tables, c ( j ) is such a coefficient in our
S a n d o z _ b a b y EFF A T T 8 7 / ; example. It declares a marketprice c for every bond j. The
conditional minimum purchase quantity q and the allow-
Index-sets may be indexed, in which case they define a able purchase Q are also indexed over j. (Note that L P L
tuple-list of its indices. If the sets p and t are defined in the does not distinguish lower and upper-case letter by
following way (see Appendix A) default, but the directive {$ C} within a model instructs the
compiler to do so, therefore, q and Q are distinct in this
SET p : / P I : P I 8 0 /; model).
"a list of 180 p l a y e r s " The first table of Fig. 3 is a convenient way to define the
SET t = / T I : T I 5 /; setj together with the three coefficients c, q, and Q. This is
"a l i s t of 15 t e a m s " possible, because all three coefficients run over the indexj
only. This is, however, not the only way to enter the data.
then an indexed set M u s t _ b e _ i n can be specified as a list The modeler is free to declare and define the data within
of three elements the model structure as
T. Hiirlimann: LPL 47

SET j = /Al:A5/; optimizing function can be included within the list. The
COEF c ( j ) = [ 200 230 400 lO0 240 ]; restriction name is followed by a colon and a linear
COEF q(j) : [ I0 20 15 20 ] ; expression. Restrictions can also be indexed.
COEF Q(j) - [ 50 70 70 80 90 ]; The restriction

L P L offers different table formats for the data. But the MODEL B(j): x[j] - q[j]*d[j] >- 0;
most flexible way to get the data from external formats is
to use the input generator. is defined for every element of the setj. This generates as
Indexed coefficients are not restricted to only one- m a n y single restrictions as j has elements. Any algebraic
dimensional (with only one index) items. They can be two- expression is allowed as long as the expression is linear in
three- or higher-dimensional.f (j, t), for example, declares the variables. Summations begin with the reserved word
a two-dimensional coefficient, where the cash flow f is SUM. The term
defined for every b o u n d j within every time period t. D a t a
tables are reassignable. ... SUM(j) c[j]*x[j] ...

COEF a ~ I0; sums the product c*x over the set j. This is close the
"I0is a s s i g n e d to the c o e f f i c i e n t a" mathematical notation. The indices of c[j] and x[j] can
COEF b = a; also be dropped, if no ambiguities arise from the ex-
"the value of a is c o p i e d to b (lO)" pression.
COEF a = 20; This simplifies the term to
"a gets a n e w v a l u e 20,
the old one is erased, ... SUM(j) c*x ...
but b is still lO"
The declaration of restrictions can also be separated from
their definition. The declaration
3.3. Variables
Model
Variables have the same properties as coefficients. They Invest;
can also be defined as multidimensional objects and nu- "total b o u n d p u r c h a s e
merical values can be assigned to them. The only differ- and i n i t i a l cash i n v e s t m e n t "
ences are, that their declarations are headed by the reserved B a l a n c e ( t I t>l);
word 7AR and their values are usually assigned under the "cash b a l a n c e e q u a t i o n
solver's control. A typical variable declaration is in all p e r i o d s t>l"
C(j); O(j);
VAR x ( j ) ; "logical conditions"
"purchased quantity x of bound j".
is perfectly correct. The assignment of the restriction may
The variable x is declared o v e r j and may be interpreted as take place in a different model part. The reserved word
a numerical one-dimensional table of unknown values. M O D E L can also be replaced by the reserved word
But the modeler m a y also assign values to them. It is also E Q U A T I O N . But only the restrictions collected within
possible to restrict the values of the variables. Lower and the M O D E L statement make part of a model that is
upper bounds on variables are often used. Sometimes passed to the solver. This makes it possible - using the
variables must be integers. These options can be added to solver statement ( M I N I M I Z E or M A X I M I Z E ) at several
any variable declaration as in places within the model - to call the solver repeatedly
within a LPL model with different model variants.
VAR d(j) INTEGER; Another useful application of this option is multi-goal
programming.
The declaration of d declares a variable over set j. If the The objective function begins with the reserved word
reserved word INTEGER is replaced by B O O L E A N or M I N I M I Z E or M A X I M I Z E , depending whether the
L O G I C A L , its values can only be the integers 0 or 1. These function is minimized or maximized. This instruction calls
restrictions are automatically translated by the L P L directly the solver.
compiler as B O U N D S and I N T - M A R K E R S in the
B O U N D - und COLUMN-Section of the MPS input-code
for the L P / M I P solver (see any OR text-book for more 3.5. The solver
details of the MPS code).
LPL has no integrated solver, but can call an external
solver automatically. The interface between most avail-
3.4. The model able L P / M I P solvers and LPL can even be specified by the
modeler. The c o m m a n d MINIMIZE or MAXIMIZE in-
The model restrictions are declared in the M O D E L structs the L P L compiler to produce the MPS file, the
statement. Each restriction begins with a name. The standard solver input file, then to call the solver itself with
48 T. Hiirlirnann: LPL

the right parameters, and to read the solution back to the this one may add the unit expression as following
LPL internal data structure. The interface is explained in
detail in the reference manual (Htirlimann 1992). By PRINT invest UNIT 1000*dollar;
default, the interface to the XA solver is "hardwired"
within the LPL compiler, but other solver packages such But note that units are optional. The modeler may or may
as OSL, Cplex, MOPS or LINDO work too. not use them within his model.
The different parts of an LPL model have now been
described very briefly. Some aspects will be explained in
3. 6. Reports greater detail in the subsequent sections. Most examples
are from the model in Appendix A.
LPL does not only to formulate a complete model, but can
also produce model reports. This is integrated part of
LPL. The reserved word PRINT is used to generate even 4. The use of indices
most complex reports. The simplest reports are generated
using the syntax shown in Fig. 2 as The indices are used to define multi-dimensional items,
such as coefficient, variables, restrictions, or indexed sets.
PRINT Invest; x; s; d; The are called tables.

which prints four tables in a predefined format. COEF a(i,j) = l;

A more complex Print statement is found in the VAR x(i,j,k,l);
Appendix A, and is explained in Sect. 6. M O D E L r(i);
SET s(i,j);

3. 7. Units a declares a two-dimensional numerical table - a matrix -

and assigns the value 1 to every table-entry, x is four-
Every declaration of numerical entities can be extended by dimensional variable, r is a restriction-vector, and s is a
indication the units. This increases the reliability and the two-dimensional indexed set. In the same manner, the
readability. Furthermore; explicit declaration of units indices are used for the different index-operators (SUM,
gives the compiler additional checking power that may PROD,...). They are operators, which iterate over index-
reduce the number of syntax errors. Every expression is sets.
checked of unit commensurateness, before it is evatuated.
Automatic unit conversion takes place without the inter- .... S U M ( i , j ) a [ i , j ] . . .
vention of the user. .... P R O D ( i , j , k , I ) x [ i , j , k , l ] . . .
Units must be declared using the Unit Statement
beginning with the keyword UNIT. Basic units (as The first example returns the sum of all values in the table
"meter") are just declared by its name. Derived units (as a[i,j], the second returns the product of all x[i,j, k, l].
"speed = meter/sec") are declared by its unit expression In the last examples, the indices play an active part: In
the expression COEF a ( i , j ) = 1 , for example, the indices
UNIT i and j determine how many entries the table a contains,
meter; and the same indices decide how many terms the sum-
"a basic length measure" mation extends in the expression SUM ( j , j ) a [ i , j ] .
kilo = i000; One may compare this syntax with the nested loops in a
"a derived unit commensurable classical programming language.
to type number" Indices, however, are also used in algebraic expression
km = kilo*meter; (within the brackets [...]) in the above examples, where
"a d e r i v e d m e a s u r e , they play a passive part. In the expression
c o m m e n s u r a b l e to ' m e t e r ' "
cm = m / l O 0 ; COEF a(i,j) = b[i,j] + i;
"a d e r i v e d measure,
a l s o c o m m e n s u r a b l e to ' m e t e r ' " every table-entry of b plus one will be copied to the
speed = meter/sec; corresponding table-entry of a. The indices in [i, j] play a
" a n o t h e r d e r i v e d unit, passive part. Every passive index must be bound to an
n o t c o m m e n s u r a b l e to 'meter '" active index. In the last example, the index i in [i, j] will be
bound to the i n d e x / i n (i,j), a n d j in [i,j] is bound t o j in
The use of units within the model structure as well as (i, j). The binding guarantees a unique expression evalu-
within the data tables (defined in LPL) is simple: just ation. In the assignment
extend the declaration with the reserved word UNIT and
add a unit expression. A number within an expression COEF a ( i , i , j ) = b[i,j]; "no error, but..."
must be extended by [<unit expression>]. The report
generator too accepts units. The table invest might be the index i in [i, j] could be bound to the first or second i
written in 1000 $ instead of $ to the output device. To do within the index-list (i, i, j). Therefore, a unique binding is
T. Hiirlimann: LPL 49

not possible. (By default LPL will bind it to the last, but 9 to evaluate and to output intermediate expressions and
this may be implementation dependent). tables
Binding is flexible in LPL. It is, however, necessary 9 to declare sparse, indexed tables.
that the bound and the binding indices represent the same
Expressions are built using the usual mathematical no-
index-set. An expression such as
tation with arithmetical (+ - */^ ) and logical (and, or, not)
operators, coefficients, numbers and functions (Fig. 5).
COEF a(i,j) = b[i,k]; "bound error!"

p r o d u c e s a n e r r o r . It m u s t b e r e p l a c e d by
sin, log, . . . functions
COEF a ( i , j ) = b[i,j IN k ] ; "correct" + - not#IN unary operators
A power
j IN k returns the position of a specific element of/within */% p r o d u c t and d i v i s i o n
the set k. (In this case, k is regarded as an ordered set). If sum, prod,.., index-operators
the specific element o f j is not in k, the whole expression + - a d d i t i o n and s u b t r a c t i o n
-<><><= >= ~ relational operators
b [ i , j IN k ] returns zero. If the intersection o f j and k is
and l o g i c a l AND
a real subset of k, then the table a will be filled up only or logical OR
partially by the assignment, the rest of the table a will , (or I) enumeration operator
remain unchanged.
In general, the LPL compiler tries to bind the passive Fig. 4. Operators
indices automatically, identified by their names. The
modeler, however, has the possibility to force any binding
using dummy-indices. The corresponding, active indices
must be headed be a dummy-index, followed be an equal max(x,y) returns x, if x>y, else r e t u r n s y
sign or the IN reserved word. min(x,y) returns x, if x<y, else r e t u r n s y
abs(x) returns the a b s o l u t e value of x
ceil(x) returns next integer g r e a t e r than x
COEF a ( d l = i , d B = j ) = b[dl,dE]; floor(x) returns next integer less than x
COEF a ( d l IN i,d2 IN j) = b[dl,dB]; trunc(x) returns the t r u n c a t e d x
"the same" sin(x) returns the sinus of x
cos(x) returns the cosines of x
The dummy-indices d l and d2 can then be used instead of log(x) returns the nat. l o g a r i t h m of x
sqrt(x) returns the root of x
the passive indices within the expressions. This forces the rnd(x,y) returns a uniform distributed number
binding from d l to i and from d2 to j . Every active rndn(x,y) returns a normal distributed number
index within an LPL model can be extended by a dummy. if(x,y,z) returns y, if x is TRUE, else r e t u r n s z
The same dummies may be used in different expressions,
since they have only local effect. (They are really treated Fig. 5. Functions
like local variables in programming languages). In some
situations dummies are necessary, but in most contexts
they may be dropped. It is a matter of style, whether the
modeler wants to use them systematically or not. LPL SUM(i) a[i] sum all a over i
PROD(i) a[i] m u l t i p l y all a over i
even makes it possible to drop all passive indices, if they SMIN(i) a[i] the s m a l l e s t a[i]
can be bound uniquely. Since this relaxed use of indices SMAX(i) a[i] the b i g g e s t a[i]
within LPL models might be dangerous, LPL also offers a EXIST(i) a[i] tests, w h e t h e r all a[i] is FALSE
compiler switch, which restricts this practice (Hiirlimann FORALL(i) a[i] tests, w h e t h e r all a[i] are TRUE
1992, p 69). PMAX(i) a[i] p o s i t i o n i of the b i g g e s t a[i]
Indices can also be used as terms within expressions. In PMIN(i) a[i] p o s i t i o n i of the s m a l l e s t a[i]
COL(i) . . . horizontal table-expander
this case, they return the position of an element within the
ROW(i) ... vertical table-expander
index-set. The expression
Fig. 6. Index-operators
COEF a(i) = i,

assings the values 1, 2, 3,..., and n to the table a, if n is the

cardinality of index-set i. They may also contain index-operators (Fig. 6), which are
iterated over index-sets. The sum-operator Z, replaced by
the reserved word SUM, is such an index-operator. LPL,
like the programming language C, does not distingguish
5. Algebraic and logical expressions
between algebraic and logical expressions. In logical
Algebraic and logical expressions are an important part of expressions zero is used as FALSE and any other number
is interpreted as TRUE. Figure 4 gives an overview of all
any LPL model. They are used in three different contexts:
operators in LPL in order of decreasing precedence. Every
9 to define model restrictions expression returns a numerical value.
 50 T. Hfirlimann: LPL

Coefficients or variables within an expression return 5. 2. Evaluating tables

the corresponding value. If a coefficient or variable has
not been assigned before in the model, a default value is Expressions are also used to produce intermediate results.
taken. The default value can be entered through the
reserved word DEFAULT following a declaration as in COEF a(i,j) = b [ j , i ] ;
C O E F d(i,j) = a [ i , j ] + b [ i , j ] ;
COEF a(i) DEFAULT 2; E Q U A T I O N e(i,k) = SUN(j) a [ i , j ] * c [ j , k ] ;
P R I N T ( i , j ) : SUN(k) c [ j , k ] + a [i,j];
If no default value has been declared by the modeler, it is
zero. The first assignment copies the transposed table b into the
Examples of expressions are table a. The second assigns the addition of the two
matrices a and b to the table d. The third defines a matrix-
4.6e5 + 7^9 - sin(879.8) multiplication, but the statement is not executed at this
( ( ( 4 + 5 ) * 4 ) ^ 2 - 12) + i f ( a > 0 , 3 , 7 ) point, the evaluation is delayed instead: each time e is used
a or b and not (3*4) in another expression the term at the right hand side is
sum(i) ( a [ i ] + b [ i ] ) / 2 evaluated. The forth calculates and outputs a two-
prod(i) x[i,j] dimensional table.

The last expression contains an unbound index j. There-

fore, it returns not one single numerical value, but a one- 5.3. Sparse tables
dimensional table of values over j. The index can be
bound, if the expression is assigned to a table b, or if Another important application of expressions is the
another index-operator is added to the expression: definition of sparse tables. This is explained by an
example. Suppose we have to define a transportation
COEF b ( j ) = p r o d ( i ) x[i,j]; model; the following model components are needed:
sum(j) (prod(i) x[i,j]);
SET i; " a list of l o c a t i o n s "
It is important to see, that LPL allows to evaluate and to SET l i n k s ( i , i ) ;
return indexed expressions and not only single values. "an list of l i n k s b e t w e e n the l o c a t i o n s "
Insofar, LPL is more a table-manipulator language than a COEF costs(i,i);
modeling language. "the t r a n s p o r t a t i o n c o s t s of the l i n k s "
VAR x(i,i);
"the u n k n o w n t r a n s p o r t a t i o n q u a n t i t i e s "
5.1. Restrictions
The indexed set links defines which transportation links
Expressions allow to define model constraints. The syntax exist between the different locations i. Normally, this list is
of an expression representing a restriction is limited. No a (sparse) subset of all possible link-combination. Since
logical operators are allowed; furthermore, the expression the links exist between some but not all locations, it is clear
must be linear relative to the defined variables. The LPL that the transportation costs make sense on these links
compiler tests such conditions. Restrictions may also only. Suppose, furthermore, that a quantity x is only
defined as ranges. The same variable may occur several transported on links with costs less or equal to 1000. In
times within the expression. If the constant expression of a LPL, it is possible to define such sparse tables in the
variable evaluates to zero, then the corresponding vari- following way
able is automatically from the restriction.
COEF oosts(dl=i,d2=i ] links[dl,d2]);
M O D E L R: x + y = sum(i) z[i]; {or: C O E F c o s t s ( l i n k s ) ; }
" d e f i n e s a r e s t r i c t i o n s R" VAR x(dl=ijd2=i I links[dl,d2]
M O D E L B: a < = x + y < = b; and costs[dljd2]<=lO00);
,,defines a r a n g e " {or: V A R x ( l i n k s I o o s t s < = l O 0 0 ) ; }
M O D E L L(i) : x [ i ] + y = 5;
"defines a restrictions over i " Costs is defined over (i, i), if links (i, i) is TRUE. If the
M O D E L S: x + 3*y = 4 * ( x + y ) ; expression - headed by a '[ '-evaluates to TRUE, the tuple
"x a n d y o c c u r s two t i m e s " exists; otherwise it is not defined. The subsequent use of
M O D E L T: x + z -y = ( 4 - 4 ) * x +x; the variable x restricts the list automatically to the existing
"x w i l l be e l i m i n a t e d " ones. Therefore, the expression

The restriction S will be automatically simplified to - 3 * x ... + S U M ( d l = i , d 2 = i ) x[dl,d2] + ...

-y = 0, and T the variable x is eliminated.
does not sum all (i, i)-tuptes of x, but only the existent
ones defined in links and restricted by the expression
costs <= 1000.
T. Hiirlimann: LPL 51

The same syntax may be used for the iteration process PRINT : a ' b : 1 2 ;
of the index-operators too. An example is the following " o u t p u t a v a l u e on 12 p o s i t i o n s "
expression: Sum the values of the table a(i), such that PRINT(j,i) : a[i,j];
i<=5 "output the t r a n s p o s e d m a t r i x a"
PRINT : ' t h i s text';
SUM(i I i < = 5) a [ i ] ; "output a text line"
PRINT(j) : SUM(i) a[i,j],
The portfolio model used this option in the C a s h _ b a l "output the column totals of a"
constraints
The reserved word PRINT is followed by an index-list, if
MODEL C a s h _ b a l ( t ] t > l ) : the expression is indexed.
SUM(j) f * x + a * s [ t - 1 ] - s - L;

This constraint is only defined for t > l , but will not be 6.2. Masks
produced for the period t = l . Another example is the
restrictin Must in the soccer model of Appendix A For more complex layouts, the modeler can define a
layout mask through a Mask statement. The Mask
Must(p,t ] Must_be_in): Work - i; statement is headed by the reserved word MASK an a
mask-name. This is followed by the content of the mask,
which would produce 2700 (= 180 • 15) single restrictions which extends to the reserved word ENDMASK. The
without the condition Mus t _ b e _ i n , but produces actu- content of the mask may be any string of characters. The
ally only the following three constraints two characters # and $, however, have a special signifi-
cation and are called place-holder. They are replaced by
Mustl: Work[P1,T2]-I the numerical or string expressions of subsequent Print
Must2: Work[PE,T6]-I statement. Example
Must3: Work[P3,T7]-i
MASK ml " ' m l ' is the mask-name"
since M u s t _ b e _ i n is defined as Month: $$$$$$$$ : ####.##~ #####.####gallons
ENDMASK
SET Must_be_in(p,t) = / P I T 2 , P 2 T 6 , P 3 T 7 / ; PRINT ml ('April', 17.15"2, 2378.567321);

which is an indexed set containing three tuples. These two statements produce the following output

Month: April : 34.30% 2378.5673 gallons

6. The report and input generator The Print statement consists of the reserved word PRINT,
the mask-name, and an expression-list within parentheses.
The Print statement allows the output of tables. They are
A comma separates the different expressions within the
written to a file, which may be further edited with the
list. The expressions are filled into the mask from left to
modeler's favoured text-processor. The most simple state-
right and from top to bottom at the different place-
ments are the following, where LPL uses a standard layout holders.
of the output tables.
But only the two index-operators ROW and COL
reveal the real power of the report generator. The index-
PRINT a;
operator R O W (COL) can expand a place-holder vertically
"output table a"
(horizontally) over index-sets. The combination of both
PRINT b:2;
index-operators allows the user to produce rather com-
"output table b with 2 positions"
plex tables. The syntax of both operators is the same as for
PRINT c:I0:2;
any other index-operators. Figure 7 shows the results of
"output table c with l0 p o s i t i o n s
the Mask and Print statement of the model defined in
and 2 decimals"
Appendix A (some lines have been cut).
PRINT a; b:2; c:10:2;
The mask contains 11 place-holder. The first four are
"output all three tables"
defined on line 5 as
PRINT a [i0,I0];
"output the table a in blocks of 10• $$$$$$ ## ## $$$$

They are filled by the expression

6.1. Print tables of expressions
(p, Skill, Age, COL(t]work) t)
LPL also allows us to output tables of any expression. In
this case, the reserved word PRINT is separated from the in the PRINT statement as following. The first place-
expression by a colon. The layout, once again, chosen by holder is replaced by the name of playerp, the second and
the LPL compiler third by the S k i l l and Age value of player p. The
52 T. Ht~rlimann: LPL

Results per player

player Skill Age in Team

Pl 3 i0 T2
P2 7 i0 T6
P3 4 lO T6

,.. 174 lines are cut here ...

P178 4 ii T5
P179 5 ii T9
P180 7 ii T3

Results per t e a m

team skill age Av. Skill Av.Age

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

T1 59 125 4.917 i0 417

T2 59 124 4.917 i0 333
T3 59 124 4.917 i0 333
T4 59 127 4.917 i0 583
T5 59 126 4.917 i0 500
T6 59 124 4.917 I0 333
T7 59 130 4.917 i0 833
T8 59 124 4.917 i0 333
T9 89 128 4.917 10 667
TIO 59 127 4.917 10 583
Tll 59 128 4.917 10 667
T12 59 124 4.917 10 333
T13 59 126 4.917 i0 500
TI4 59 126 4.917 I0 500
T15 60 124 5.000 10 3 3 3

team I players in the team

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

T1 P9 P41 P49 P57 PT0 P71 P86 P89 Pll8 P143 P145 P154
T2 P1 P6 P7 P22 P23 P48 P52 P55 P92 P133 P149 P162
T3 P38 P39 P54 P56 P91 P93 P97 Pll9 PI41 P142 P174 P180
T4 P20 P51 P73 P78 P80 P84 P88 PI03 PI07 Pig1 P156 P157
T5 P21 P42 P63 P75 P82 Pl00 PI02 P105 P134 P148 P175 P178
T6 P2 P3 P4 P8 P35 P47 P68 P69 P81 P85 P98 P146
T7 P24 P28 P34 P45 P58 P59 P87 P121 P126 P135 P140 P151
T8 PlO P16 P18 P19 P64 Pl08 Pl09 Plll P147 P160 P171 P173
T9 P30 P36 P37 P40 P62 P83 P90 P130 P132 P150 P158 P179
TIO P15 P46 P72 P76 P96 Pll2 Pll4 P124 P127 P137 P166 P172
Tll P5 P33 P53 P94 P120 P123 P138 P153 P155 P159 P167 P177
T12 P12 P13 P25 P26 P29 P32 P44 P50 P77 P95 PlO1 P136
T13 Pll P14 P17 P27 P65 P79 P128 P139 P144 P152 P161 P163
T14 P31 P43 P60 P67 P74 P106 Pl13 Pll5 P122 P125 P170 P176
T15 P61 P66 P99 PI04 Pll0 Pll6 Pll7 P129 P164 P165 P168 P169

Fig. 7

expression COL ( t ]work ) t runs over all t for a specificp The first place-holder is filled by the team name t, the next
and outputs all team names t horizontally for every by the total skill per team, calculated by the expression
w o r k ] p , t ] that is TRUE. Since a player p can only in SUM ( p Iwork ) S k i 1 1 . The next are calculated similarly.
one team, this outputs only one team name per line. The last two place-holders in line 16 are filled by the
Because the whole expression is also defined over expression
R 0 W ( p ) , the output of this line is repeated for every
playerp, which will produce 180 lines in our case. The next ROW(t) (t, COL(plwork) p)
five place-holder are defined on line 9 of the mask. They
are filled by the expression Note that this simple line produce a whole two dimen-
sional table. The players are collected per line. The
ROW(t) (t, S U M ( p l w o r k ) Skill, iteration of the ROW and COL index-operators can also
SUM(plwork) Age, be restricted by a condition. This allows us to select any
(Sum(plwork) Skill)/12, subset of tables and to output the result in most complex
(SUM(plwork) Age)/12), layouts.
T. Htirlimann: LPL 53

6.3. The input generator new line. COL(), too repeats to read tokens on the same
line, until the line ends.
The Input Generator is represented by the Read state- It is also possible to read from different files. The three
ment. It is similar to the Print statement, but instead of tables could have been divided into three files. In this case
output data, it allows to read data from files. As an no block indication would be necessary. The Input
example, suppose the data of the portfolio model in Fig. 3 Generator has several nice features. One is the following:
are not organized in LPL syntax, but in a plain text file empty lines or lines containing only separators between
shown in Fig. 8. tokens, such as spaces or tabs, or lines beginning with a
dot are skipped automatically. First experiences with the
input generator are promising: For an LP model with 1300
constraints and 1500 variables, a Pascal program of 32
A d a t a set of t h e p o r t f o l i o model: file PORTDATA
Three tables are defined
pages bad been written to manipulate the data; using the
new LPL input generator, it is now possible to code the
Table 1: bond data same program in 2 pages (Hiirlimann 1991).
bond pice min. pur- max p u r -
name chase quan. chase quan.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7. Conclusion
A1 2 10 500
A2 2.3 700
A3 4 700 This paper is a brief report of the new version of the LPL
A4 1 15 800 modeling language. The reference manual (H[lrlimann
A5 2.4 20 900 1992) gives a detailed description of the language. A
Endtable 1 model library of about 60 examples written in LPL is
available.
T a b l e 2: period data
period cash avail. reinvestment The development of LPL was motivated by practical
use. Different models with 1500-2000 restrictions, 2000-
T1 - - 3500 variables, and a matrix density of 7500-12000 non-
T2 12000 90 % zero elements are under continuous use and development
T3 14000 80 % at the Institute (H/ittenschwiler and Kohlas 1989). Most of
T4 5000 80 %
them are formulated in LPL. Until very recently, these
Endtable 2
models had to be solved by a solver package on a main-
Table 3: cash flow frame computer. Therefore, the important task of the LPL
T1 T2 T3 T4 was to produce the solver input file. The hardware of the
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

new generation of PCs as well as the solver software

A1 4 4 4 packages such as XA a.o. now allow to solve and
A2 5.5 5 4
A3 5 3 6
manipulate the mentioned models locally on the PC. LPL
A4 6 6 has, therefore, been extended to a point, where different
A5 4 5 6 modeling tasks (model formulation - solving and report
Endtable writing) are supported. Our practical experiences are, that
a typical modeling-cycle (modification - resolving -
Fig. 8 reporting results) has been reduced from several hours or
even days to several minutes.
The LPL compiler has been implemented with TUR-
Then the data specification of the model can be BO PASCAL from Borland Inc. under MS/DOS (any
replaced by the four Read statements version). A version in ANSI C is also implemented. The
PASCAL version is actually available at the Institute for
READ FROM ' p o r t d a t a ' BLOCK Automation and Operations Research, University Fri-
FROM ' T a b l e ' TO ' E n d t a b l e ' ; bourg, CH-1700 Fribourg, Switzerland (Fax (41)
READ BLOCK i: ROW(j) (j, o, q, Q); 37 21 96 70).
READ BLOCK 2: ROW(t) (t, L, a);
READ BLOCK 3: ROW(j) (j, COL(t) f[j,t]); Acknowledgment. The a u t h o r is grateful to Prof. Dr. J. Kohlas and
the two referees wo have made valuable c o m m e n t s on the paper.
The first Read statement indicates the filename of the
input file and the read-block-delimiters, between which a
subsequent read takes place. The second Read jumps to Appendix A
the first occurrence of Table (beginning at a new line) and
reads lines until a Endtable is encountered. On each line The following model (SOCCER.LPL) was written in a
four tokens are read, if possibly. ROW() has two func- draft form by J. Byer. ! have adapted this model for use in
tions: it reads lines repeatedly, and synchronizes the read. this paper. The model is a simple assignment problem
That means, if a line will contain more than four tokens which assigns 180 players to 15 teams. The only variable is
only the first four are read, if it contains less, less are read. Work that is indexed over the players p and the teams t. It
In either case, a fresh read of four tokens will begin on a declares totally 2700 (=180"15) single 0-1 variables.
54 T. Hiirlimann: LPL

(* S O C C E R . L P L : an a s s i g n m e n t p r o b l e m of 180 p l a y e r to 15 teams (0-I IP-problem)

Ref.: B Y E R James, p e r s o n a l c o m m u n i c a t i o n s *)
{--- c o m p i l e this m o d e l w i t h the LPL c o m p i l e r L P L L O N G . E X E ---}

PROGRAM S o c c e r ; (* {$N2??} *) {$R1 ( i n i t i a l i z e random s e e d ) }

SET
t; "the list of teams"
P; "the list of p l a y e r s "
must_be_in(p,t); " p l a y e r s p must be in t e a m t "
reject_from(p,t); "player p is r e j e c t e d from a t e a m t"
t_groups(p,p); "groups of p l a y e r s w h i c h must be t o g e t h e r in a team"
n_groups(p,p); "groups of p l a y e r s w h i c h must n e v e r be t o g e t h e r "

COEF Skill(p); "skill of p l a y e r p"

Age(p); "age of p l a y e r p"

VAR work (p,t) BINARY "work=l, if p l a y e r p is in t e a m t, else 0";

MODEL
" m a x i m i z e the a s s i g n m e n t "
obj: SUM(p, t) work;
" p l a y e r p must be only in one team"
B o u n d s ( p ) : SUM(t) w o r k = I;
"total skill level of t e a m t must be at least 59"
Skill_level(t): SUM(p) w o r k * Skill > = 59;
"total p l a y e r count per t e a m t must be 12"
H e a d s ( t ) : SUM(p) w o r k = 12;
"total t e a m age of t e a m t must be at least 124"
Team_age(t): SUM(p) w o r k * age > = 124;
" p l a y e r p m u s t be in t e a m t"
Must (i=must_be_in): w o r k [ i ] = i;
"player p is r e j e c t e d from a t e a m t"
Reject (i=reject_from): w o r k [ i ] = 0;
" p l a y e r s w h i c h must be in the same team"
Same(t,t_groups[i,j]): w o r k [ i , j ] - w o r k [ j , t ] = 0;
" p l a y e r s w h i c h m u s t not be in the same team"
Never(t,i=p lexist(j=p)n_groups[i,j]): work[j,t]<=l;

{...... data ..... }

SET
t = /Tl:T15/;
p = /PI:PI80/;
must_be_in(p,t) = / PI T2, P2 T6, P34 T7 /;
reject_from(p,t) = / PI0 TI, P20 T2,
P l e e (TI T3 T4 T5 T6 T7 T8 T9),
P64 ( T 1 T 1 2 ) /;
t_groups(p,p) = /.P2 P3, P I I 2 P76, P89 Pg, P 3 4 P135,
P4 (P35 P47 P81 P98) /;
n_groups(p,p) = / P21 P22, P55 P56,
Pll (P35 P45 P56 P67 P78 P89 Pg0 P21) /;

COEF Skill(p) = trunc (rnd (3,8));

Age(p) = trunc (rnd (I0,12));

" c h e c k that a p l a y e r p can be only in one team"

C H E C K it (p): sum (t I m u s t _ b e _ i n ) l < = i;
{. . . . . . . . . . end d a t a . . . . . . . . . . . }

MAXIMIZE obj;
M A S K ml
T. Hgrlimann: LPL 55

Results per player

player Skill Age in Team

$$$$$$ ## ## $$$$
team skill age Av. Skill Av. Age
$$$$$ ##### ### ###. ### ###. ###

Results per team

team [ players in the team

$$$$ f $$$$
ENDMASK ;
Print ml(ROW(p) (p, Skill, Age, COL(tlwork) t),
ROW(t) (t, SUM(pIwork) Skill, SUM(plwork)Age,
(SUM(plwork) Skill)/12, (SUM(plwork) Age)/12),
ROW(t) (t, COL(plwork) p));
END

work(p, t) has only the values 1 or 0, depending whether Geoffrion AM (1989) SML: a model definition language for
the player p is assigned to team t. The model has been structured modeling. Western Management Science Institute,
solved on a PC 80386 with a C o p r o c e s s o r and 4 MB R A M University of California, Los Angeles, Working Paper No. #360,
revised Nov. 1989
with X A 386 in 3 0 m i n - we have been lucky, since the
Greenberg HJ (1990) A primer of ANALYSE: a computer-assisted
model is a pure 0-1 IP (integer program). analysis system for mathematical programming models and
solutions. University of Colorado, Denver, Draft, June 28
Hgttenschwiler P, Kohlas J (1989) Wissensbasierte Systeme auf der
Grundlage linearer Modelle - Werkzeuge und Anwendungen.
Output 18(12):21-28
References Hfirlimann T, Kohlas J (1988) LPL: A structured language for linear
modeling. OR Spectrum 10:55-63
Bischop J J, Kuip CAC (1991) Hierarchical sets in mathematical Htirlimann T (1991) The input and report generator in LPL.
programming modeling languages. Working Paper, Department Institute for Automation and Operations Research, Working
of Applied Mathematics, University of Twente, The Netherlands Paper No. 190, September, Fribourg (updated April 1992)
Brooke A, Kendrick D, Meeraus A (1988) GAMS. A user's guide. Htirlimann T (1992) Reference manual for the LPL modeling
Scientific Press, language. Version 3.8, Institute for Automation and Operations
Cunningham K, Schrage L (1989) The LINGO modeling language. Research, Working Paper No. 191, September 1991, updated
University of Chicago, Preliminary, 27 February February 1992, Fribourg
Dolk DR (1988) Model management and structured modeling: the Shapiro JF (1988) Stochastic programming models for dedicated
role of an information resource dictionary system. Commun portfolio selection. In: Mitra G (ed) Mathematical models for
ACM 31:704-718 decision support (NATO ASI Ser. F, vol 48, pp587-611).
Fourer R, Gay DM, Kernighan BW (1990) A modeling language for Springer, Berlin Heidelberg New York
mathematical programming. Manage Sci 36(5): 519-554 Steiger D, Sharda R (1991) LP modeling languages for personal
Gass SI (1984) Documenting a computer-based model. Interfaces computers: a comparison. Working Paper 90-27, College of
14:84-93 Business Administration, Oklahoma State University