|
ALLO and SAMO ...
ALLO - Algebraic Language for Linear Optimisation is a linear mathematical modeling language, the only language of its kind in the country. The language together with its translator were completed and implemented in 1995 by the National Institute for Research and Development in Informatics (ICI, ROMÂNIA) within the Modeling and Optimization Laboratory led by Dr. eng., Mat., CP1, Neculai Andrei. ALLO allows easy modeling of linear modeling problems in a form close to the algebraic description. More importantly, it allows prototyping of practical or theoretical problems. A prototype together with the concrete data instantiates a concrete model. The translator instantiates the prototype into a model and translates it into the equivalent MPS form (MPS wiki) that has been the standard input file recognized by any well-known optimizer for decades. It solves the problem and provides a unique solution if any. ALLO stands out for its simple syntax, close to the algebraic mathematical language and even the FORTRAN (EN) / FORTRAN (RO) programming language. ALLO has a small number of reserved keywords. We can say that, at the time of its creation, ALLO was in the top ten similar languages in the world, most of which were made commercially in several countries with a tradition in research in any strategic field. Historic The idea to create the ALLO language was had by two research mathematicians from ICI, specialists in mathematical optimization problems. These are Dr. mat., CP1, Cornel Resteanu and Dr. eng., Mat., CP1, Neculai Andrei who did not give up the project and overcame all obstacles through an iron will. At the beginning, they appealed (by contract) to the Department of Informatics within the Faculty of Mathematics and Informatics, University of Bucharest. After a while they received a printed work. After 1990 he went to Germany for an internship at Humboldt. He called Matt to him. Mircea Bărbulescu, employee in ICI. There they made a first form of the grammar of the ALLO language, after which Mircea Bărbulescu made it in the Borland C language. It is about the lexical-syntactic analyzer without the expression part due to the short time and his departure as an assistant at Fac. Mathematics, University of Bucharest and from here to Canada. Left alone on his return from Germany, Neculai Andrei co-opted for the project Mat., CP3, Gheorghe Borcan with a master's degree in Formal Languages and Compilation Construction Techniques (Fac. Mat., Univ. Bucharest) who had ,previous, important contribution to the resumption and continuation of the LPTR project. Because at that time the two did not have a PC, they started to design the second phase of the translator. He first finalized the form (a reverse and mixed polish) that had to be produced by the lexical-syntactic analyzer, including for the area of expression not yet programmed. After that they designed the model translation process in MPS format. Meanwhile, Neculai Andrei received a PC from the Humboldt Foundation in Germany, and Mircea Bărbulescu recommended a former student of Informatics (Faculty of Mathematics, University of Bucharest), namely Cristian Dubălaru who was employed in ICI. He did the Borland C language programs on expression and completed the exit from step one, then left ICI because of the salary. To speed things up, the second step was taken by Gheorghe Borcan in FORTRAN. He also took care of some error corrections in step one. Thus in 1995 we had the first version of the ALLO translator. During this period Gheorghe Borcan took care of the adaptation of an old solver (received over ten years ago by NA, compiled and executed on the FELIX C256 computer with French operating system SIRIS, see the history of Romanian computers) and compilation (with the only compiler available ) to be executable (now called Dsolver) on a PC with the WINDOWS 3.1 operating system. He also recompiled the routines (about 100) from the MINOS package (received by N.A. from Stanford University, California, USA). The package was created, compiled, tasked and executed on an operating system other than ours. At the first compilation he found multiple errors that seemed insurmountable because changing the routines would have been not only a serious job but also risky. Eventually he found a correct solution that allowed tests (performed by N.A.) with nonlinear problems because the package also had this feature in addition to the one related to linear problems. Moreover, he completed the SAMO system (Advanced Modeling and Optimization System, a system started by Cristian Dubălaru in Visual Basic) which integrated a Text Editor, ALLO Translator, Dsolver Optimizer as well as a solution viewer. There are several such trading systems in the world. Solving a linear optimization problem was much easier for SAMO. So I was able to test the translator on several hundred models. The most interesting prototype model was related to CETSUD Bucharest. A CETSUD instantiated model has thousands of variables and thousands of restrictions! Prof. Univ. Alexandru Badea (Politehnica Bucharest) specialist in thermal power plants had a decisive contribution to this prototype. He provided us (in a first linear approximation although the more precise model is nonlinear) with the equations of boilers, turbines, balloons, etc. as well as the central cost / profit equations. It is a first in the country to have access to a global vision of the operation of such a plant. This would not have been possible without the existence of the ALLO translator, the DSolver and even more of SAMO. After about three years from the first tests and after hundreds of modeling experiments, the ALLO language reached version one by restoring syntax and semantics. 17 implicit functions have been introduced in language that considerably increase the force of language expression. Version 1 of the ALLO language was made entirely by Gheorghe Borcan who also implemented the translator consisting of the two components Pas1 (in C) and Pas2 (in Fortran). Here is a list (RO) / list (EN) with category programming languages. The grammar of the ALLO language was brought to the form that meets the criterion LL1 SAMO - Advanced Modeling and Optimization System
An
IDE
(Integrated Development Environment) for the SAMO system was
started by mat. Cristian Dubălaru in Visual Basic at the
indications of CP3., Mat. Gheorghe Borcan who completed it and
with the help of which he tested hundreds of models.
SAMO has a built-in Text Editor (to make it easier to write templates and correct them in the compilation process, etc.). ALLO Translator, Dsolver Optimizer as well as a solution viewer. Solving a linear optimization problem is much easier by SAMO. Thus, the translator could be tested on several hundred models. Like the ALLO translator, we believe that it is the first system of this kind developed in our country as a result of special efforts in times when such objectives are disregarded by many IT decision-makers who were unfortunately in positions beyond them. Functions
A SAMO image with the CETSUD prototype file in process working
Operating system The ALLO translator and the SAMO system survived on the WINDOWS 3.1, WINDOWS 95 and WINDOWS Vista operating systems. When switching to each of these systems, it was necessary to recompile and redo the tasks starting from compatible compilers on these systems. Given the sources in Borland C, Fortran and Visual Basic, the transition was not easy. The required compilers had to be changed to be compatible on that system. For this reason, some source components had to be rebuilt. Portability of programs on various operating systems is still an unresolved issue. Mathematical Modeling Systems or Languages
1.
AIMMS - Advanced Interactive
Multidimensional Modeling System. In AIMMS you can model problems: Linear, Quadratic, Nonlinear,
Mixed with integers and others. It has a complex IDE For solving AIMMS launches multiple solvents. A company with several production / storage centers delivers the products to certain markets / customers according to their requirements. To meet the demand of a market, the company can deliver products from several centers. Transport costs, market demand and the production (or storage) capacity of the centers are known. For simplification, the products are given in conventional units because here the transport costs and the capacity of the centers are significant. Customer satisfaction is required as well as minimizing transportation costs. MODEL Transport
/*-----------------------------------------------------------------------*/
FILE
VARIABLES /*
The condition is not necessary being supplemented by
restrictions */ OBJECTIVES CONSTRAINTS /* An
additional restriction for discussion. The quantity delivered to
all markets in each
*/
/* The quantity delivered to a market from all centers */ END Transport prototype instantiation data file
/* translpl.dat------------------------------------------*/
/* nrcp */ 10
Extract from the MPS file generated by the ALLO translator that
is input to Dsolver NAME Transport
... omit iterations to a feasible solution ...omit iterations to
an optimal solution Optimal Solution found in 15 iterations
NoVar Name AT Value
Let us remember that these are the variables:
x[j,k] The quantity transported from center j to market k It is noted that from
center 9 no products are delivered to markets. In order to
deliver from here as well (in order not to reach the activity
block) we should put another condition in the model. For
example, we want the sum of deliveries from any center to be
greater than a certain part of the capacity. Here is a variant
that changes the situation. But usually the objective function
will have a higher value than the previous one:
Objective function = 13495.68 The
ALLO language is built on a character set called the language
alphabet. Based on the alphabet, tokens or words of the language
are constructed (according to lexical rules) which are elements
of the set called the vocabulary of the language. Some words
will be used frequently by any user of the language. They form
the set of reserved words or the set of keywords with a special
role in the syntactic and semantic construction of what we call
source program or prototype / source model.
The other words are
not known, but are constructed by those who use this language.
The vocabulary would be an infinite lot but there are
restrictions on word length limitation. With the alphabet and
vocabulary we can create complex assemblies from the
instructions and finally we can create the assembly with the
highest semantic load called program. Of course with the
observance of some syntactic and semantic rules because
otherwise it will not be validated by an assembler, translator,
interpreter or compiler. We have seen above a global structure of an ALLO program. Seen
only through the prism of the alphabet, a program is a finite
string of characters recognized by the translator. This string
can be the result of a mix of file strings decided by the main
file that refers to the others. Everything is coordinated by the
ALLO translator. Below is the alphabet or character set
recognized by the ALLO language:
Observation
1. The IN operator
can be written in any combination of uppercase / lowercase
letters as desired by the modeler. This also applies to the IS
operator but also to any reserved word.
2. The difference
between the operator: = and the IS operator is that the first
refers to the definition of a mass component (with the role of
objective function name, constraint name) while IS announces the
beginning of the definition of an auxiliary variable of mass
type or the condition of validation of an auxiliary variable
(scalar or solid-type), announces the boundary condition of a
model variable (scalar or massive-type), and finally announces
the beginning of the body defining an objective function or
constraint (scalar or massive type).
3. The set of
characters <CR> <SP> <TAB>,:; {} [] () + - * / <=> is a special
set whose elements signal the beginning or end of words / tokens
recognized by the lexical analyzer of the ALLO translator. These
tokens are part of the language vocabulary only if they comply
with the construction rules imposed by the language.
Based on the alphabet and vocabulary, new vocabulary words or
more and more complex assemblies are built up to the assembly
with maximum syntactic and semantic load called program or
model. The basics of the ALLO language are : Below we will detail each of the basic elements in the
construction of a model presented above. Comments Comments are especially useful in any language. In ALLO comments
are accepted anywhere in the source files related to a prototype
/ model. An
ALLO comment is a sequence of characters in the ALLO set that is
nested at the beginning and end of the comment. After the
comment is opened, the lexical analyzer scans the string until
it encounters the closing sequence. If necessary, the <CR> <LF>
source line end sequence is exceeded when a comment continues on
multiple lines. This fact is useful not only in explaining the
model but also for a possible troubleshooting. Comments and
space areas are unproductive elements with the role of design
and explanation of the source model. Name The
name is an essential element in the construction of any ALLO
prototype / model being a vocabulary element, a token
identifiable by the ALLO lexical analyzer. Names are formed
using letters, numbers, and an underscore character that links
two or more components to which the user assigns a meaning. Of
course, no one is stopping us from pasting these names and not
using this link. It depends on your preference. However, the use
of character is often useful because it highlights the
components. A
valid name starts only with a letter that can be followed by: a
letter, a number, the underscore link character. The length must
not exceed the maximum allowed case solved by truncation. Details of
the metalanguage used in defining the ALLO syntax ::=
tells us that its left element is constructed as follows (or is
by definition);
|
is a separator from the list items. Any element can participate
in the construction of the respective complex assembly;
Space between two metalanguage elements or between a
metalanguage element and an atom (eg link character _) means the
concatenation operation between two strings. A metalanguage
element means a class / set of possible assemblies (strings on
the alphabet) constructed with the rules of that element.
lambda is the symbol for
the null element relative to the character or string
concatenation operation. It is an empty string that has no
character being of zero length. Sintax nume ::= litera | nume litera
| nume cifra | nume _ Examples :
nrfprod, fprod, ump, xprod,
cost_prod, st_cost, per_1 Remarks The
words in the table above are reserved. They can also be used in
combined capitalization as the user wishes. All (including the
resulting combinations) can no longer be used as variable names.
Those in the range [17,33] are names of default functions that
must be called according to their definition with respect to the
number of arguments and the required type.
Constants are necessary elements for any programming or
specialized language. In the ALLO language they are used either
directly in the construction of a model or indirectly by the
fact that they serve to initialize auxiliary variables that are
used in that construction. ALLO allows the construction and use
of the following types of constants: integer | real | domain /
range | string of characters. Integer constant An integer constant is a sequence of decimal digits in front of
which the + or - sign can appear. ALLO allows integer constants
in the single word value range, i.e. [-32768, + 32767]. For
higher values there are real constants or integer variables that
can be assigned with the desired expression. Sintax
Exemple: 3457, -15481, +12 , -32768, +32767 Real Constant Real constants are composed of the sign, integer part, decimal
point, fractional part possibly followed by an exponent. It
consists of the letter E or is followed by an integer with or
without a sign. The approximate value range of such a constant
is the negative range [- 3.4028235E + 38, - 1.1754944E-38] plus
the positive range [1.1754944E-38, 3.4028235E + 38] and of
course the value 0 as a mandatory element in operations. Sintax Observatii.
1. p_int may be missing when p_frac is present and vice versa.
but I can't miss it at the same time. Exemple :
.517, -32.7564, +3. 0.342E-15,
-2.51e+9, -3.4028235E+38 Domain constants There are elements of the ALLO language that define an interval
on the real axis or in the set of integers. They contain the two
sizes that define such an interval: the lower edge and the upper
edge. These quantities are enclosed in square brackets and are
separated by a comma. The quantities can be real or integer
constants but can also be arithmetic expressions calculable at
the point where the domain constant appears and is used as the
initialization quantity of a domain variable or as an ad hoc
domain. In
ALLO, field constants are allowed that can only be evaluated in
a certain context and whose value may differ depending on the
value of some cycling indices that participate in the margin
expressions. This is the case for so-called dynamic field
constants that support their re-evaluation every time the cycle
to which they belong is initialized. Sintax const_domeniu ::= [
expr_aritm , expr_aritm ] Exemple :
[ -2, 17], [ 34.5, 70.18], [ m/2, 3*n
] , [ a+3.2*(k+1), b+18.65 ]
Observație. Integer auxiliary variables m and n must be defined in advance
for the expressions to be calculable at the time of meeting this
field. Also a and b are auxiliary variables whose values are
already known and k is a cycling index in a FOR clause in whose
instruction block this domain constant appears, so in this cycle
the expressions are calculable. Strings of characters They consist of one or more characters of the ALLO alphabet
delimited by a pair of double quotation marks which thus can no
longer be included in any string. Strings are used to define the
external file identification specification under the DOS
operating system. Such a specification may contain only the name
and type separated by a period, in which case the file is
searched in the translator's working directory, or it may also
contain the path in which case it is searched in accordance with
it. Sintax sir ::= " secv_car " Exemple :
"e:\lpmodels\allo\prod.dat"
"cetsud.dat" "twood.dat" Massifs are special creations of a programming language and
more. They consist of one or more identical cells / objects
organized according to a known dimensional rule that allows the
identification of the place occupied (in this structure) by each
object. Massifs are characterized by a list of dimensions, by
the space allocated to each cell and by the rule of allocation
or retrieval of each cell. One-dimensional massifs are known as
vectors, those with two dimensions as matrices.
Three-dimensional massifs are called three-dimensional massifs,
with n-dimensional massive dimensions. Sintax Exemple : storcost [rmat] ump
[rmat,fprod] xsmat[rmat,perpext] Dimension list As I said, a massif is marked by a list of dimensions that
define its size, its shape. A dimension of a massif is a domain
of integers that has a number of elements given by the
difference between the top edge and the bottom edge after which
one must be added. This number participates in the calculation
of the total number of elements of the array as the product of
all numbers associated with the dimensions. A classical
dimension represents a domain [1, n] so that the number of
elements represented by this dimension is n-1 + 1 = n, even the
upper edge. A whole and one-dimensional whole domain can be put
in biunivocal correspondence with such a classical domain. Sintax l_dim ::= dim | dim , l_dim Exemple de listă dimensiuni: [1,10] , rmat, / rmat, fprod /
(fără cele două /)
Observație
[1,10] is a domain constant, the others are constructed by
domain names that should be defined before using them elsewhere
or in this list. Allocation method In ALLO the linearization of a massif is done "on lines" in
which the last index increases faster until the end and is
restored at the beginning not before increasing it with 1 on the
previous one, etc. A three-dimensional massif, a [m, n, p] is regarded as a cube
consisting of m * n * p identical cubes or consisting of p
floors of cubes each floor being a matrix of cubes a [m, n]. So
the cube a [i, j, k] is on the floor k at the intersection of
line i with column j. In ALLO auxiliary variables of integer or real type, model
variables, objective function variables and constraint variables
can be declared as masses of vector, matrix, three - dimensional
variables, etc. This makes it easier to write a large, complex
model. Reference to a massive
element
Sintax ref_element_masiv ::=
nume_masiv [ l_expr_ind ] Exemple :
ump [r,f], storcost[r], xprod[f,p]
Rprd [ATR(opczindl[j],h) + ATR((h-1)/nrprod+1,m)+h-(m-1)*nrprod , f] Observație The index expressions in the first three examples above are
simple invoking the name of auxiliary variable r, f, p. In the
last example the first index expression is a complicated
arithmetic expression in which two intermediate actions occur.
ATR (opczindl [j], h) is the function that assigns to h the
calculated value of the vector element opczindl [j]. Then this
value of h enters the calculation of the expression that is
assigned to m and then the value of the expression h- (m-1) *
nrprod is calculated which converted to the integer is the first
reference index of Rprd, the second being m with the calculated
value immediately before but which must eventually be converted
to the whole. ALLO
language variables are the basic elements in the construction of
a model. Except for the INDEX type (implicitly recognized from
the context) all must have a statement / definition. In terms of
size we have two types of variables: scalar variables and
compound variables with one or more dimensions. Scalar variables
are defined by name, type and possibly a value. Compound
variables are defined by name, type, size list and possibly list
of values. The elements of the compound variables are accessible
by name and the list of indices possibly resulting from a list
of index expressions. Based on this list and the list of
dimensions, the linear place of the element is calculated and
thus the value or a linearized scalar name is calculated.
Details on this subject are in the description of the massifs. Auxiliary variables
Auxiliary variables together with constants help to build the
model by: coefficients, facilitating the expression of
relationships and constraints, etc. All auxiliary variables must
have a value at the time of their use. This category includes
the following types: integer; index ; real ; domain ; file name.
Integer auxiliary variables
These
variables can be scalar or compound, vectors, matrices, etc. A
scalar variable is represented in complementary code with sign
and on four bytes. A value in the range [- 2147483648,
2147483647] can be assigned to such a variable.
Sintax
var_intreg ::= var_intreg_scalara
| var_intreg_masiv
Exemple : nrfprod, nrperp,
opczindl [opcze]
Observation. All quoted variables are integers if they are in an
INTEGER statement in that model.
Index auxiliary
variables
They are only of the scalar type by name and are not the subject
of an explicit statement. They are considered as whole and can
participate in index expressions, coefficient expressions, or
even in the definition of dynamic domains that can be evaluated
only in a certain context of execution of an instruction. An
index variable is present as a cycling index in the FOR and SUM
sequences. At that time this index must not be used by another
FOR or SUM. So its purpose is precise until the end of the
operation in which it is involved after which it can be reused.
Sintax
var_indice ::= nume
Exemple : j, k, k1, m, n, r, f, p
Observation. There is a certain simplicity in the role of the
index auxiliary variable, but we can also use more complicated
names. Real
auxiliary variables
Real auxiliary variables can be scalar or compound (vectors,
matrices, etc.). A scalar variable is represented by a floating
point with a sign and four bytes. The approximate value range of
such a variable is the negative range [- 3.4028235E + 38, -
1.1754944E-38] plus the value 0 and the positive range
[1.1754944E-38, 3.4028235E + 38]. A real variable must appear in a REAL statement that contains
its entire statement. Real auxiliary variables are used in the
construction of coefficient expressions or real domains used as
model variable boundary domains or model constraint variables.
Sintax
var_real ::= var_real_scalara | var_real_masiv
Exemple : prodmax, storcost
[rmat] , ump [rmat,fprod] , profdc [fprod,perp]
Observation. All quoted variables are real only if they are
included in a REAL statement. Domain auxiliary variables
Auxiliary domain variables are scalar-type only and are used as
size domains, cycling domains, or model variable boundary
domains or model constraint variables. The first two types have
integer values and the other real ones. A domain variable has
two values. One value represents the lower edge and the other
the upper edge. Because the subsequent use of this field is not
known (because the translator makes a single pass through the
source text) these values are retained as real values but also
as integer values. Such a variable can represent an interval on
the real axis or on the integer axis.
A domain variable must appear in a RANGE statement that contains
its entire definition. Sintax
var_domeniu ::= nume
File name auxiliary variables
The ALLO
language allows the definition of such variables whose value is
a DOS file specification. The definition is made by the FILE
statement which also means the default Open to be prepared to
satisfy the first variable in a READ statement that refers to
this name. Sintax
var_fisier ::= nume
Exemple : fpp, fdist, fcsd
Observation. These names must appear in the FILE statement. They
are chosen as desired, simpler if they are required in the
model.
The variables of the model to be optimized are all defined after
the auxiliary variables section. The date type associated with
such a variable is only the actual type. If in the definition is
not the boundary clause then the variable is assumed to be
positive. If it has the lower boundary clause then its range is
up to infinite plus. If it has only the upper margin clause then
this margin must be strictly positive and the range considered
for this variable is from zero to this value. If the clause is
double bounded then the domain can be negative, positive or
mixed only if it is correctly represented by the edges, ie the
lower edge <= the upper edge. The result of processing the
boundary clause can be found in the BOUNDS section of the
resulting MPS file. A model variable can be scalar or compound (vector, matrix,
etc.) which allows us to use general (strong) instructions to
define both boundary clauses and constraints. Scalar pattern variables appear in the MPS file with their names
when it is at most eight characters long. Otherwise the name is
the result of truncating to the first 8 characters. For compound
variables there is a need to encrypt the linearized index of the
referred cell in the name. This is done on as many characters as
needed on the back up to the eight allowed. That is why the user
must choose his generic name shorter than 8 characters and
correlated with the respective size. Otherwise inconsistencies
may occur on the same representation of final names because the
translator does not do this check. This procedure seemed to us
the best at the time. Otherwise, it would have been necessary to
build a very useful dictionary in the recovery operation, of the
optimizer solution, in terms of the original names with
non-linearized clues. Sintax
var_model ::= var_model_scalara |
var_model_masiv
Exemple : xprod [fprod,perp],
xsmat[rmat,perpext], Rprd[prod,fact],
XRZP [hrze] , XIRZP [hrz] , XORZP
[hrz] , XAF
Variables
Functions Objective
These variables allow the definition of objective functions in
the objective functions section. They can be scaled or compound.
At the end of this section, a single scalar function or
component can be selected in the MINIMIZE / MAXIMIZE statement.
The result of processing an objective function definition can be
found in the MPS file in the ROWS and COLUMNS sections. Sintax
var_fobj ::= var_fobj_scalara | var_fobj_masiv
Exemple : profit | cost
Constraint variables are names for the constraint lines in the
model necessary for its understanding, for the form to be solved
by the solver (in our case the MPS) and for the form of the
solution (provided by the solver) necessary in its
interpretation for the real decision-making process. They can be
scaled or compounded as defined in the model restrictions
section. The result of processing a restriction can be found in
the MPS file in the ROWS, COLUMNS, RHS (Right Hand Section)
sections and possibly in the RANGES section if the restriction
had a double border clause.
Sintax
var_restr ::= var_restr_scalara |
var_restr_masiv
Exemple : limprod [perp] ,
pmbal [rmat,perp] , rtlim | DRZP [hrz]
Operators act on one or more operands to produce a value, an
action, and a value, a domain limitation for certain model
variables or constraints. ALLO language operators are in the
categories: arithmetic; function; relational; symbolic border. Aritmetic operators Arithmetic operators are used in the construction of arithmetic and symbolic expressions. In arithmetic expressions it acts on an operand or two operands producing a new operand that further participates in the evaluation of the expression. In a symbolic expression they can be in an arithmetic expression coefficient, operator on symbolic expression or operator on two symbolic expressions producing a new operand of type symbolic expression. We have unary operators and binary operators, additive or multiplicative. Sintaxa opr_aritm ::= opr_unar | opr_binar
Function operators are invoked by the name of the default function recognized by the language and the ALLO translator. They act on the call parameters a closed list between two round brackets following the name. The result of the execution of that function is an operand that further participates in the calculation of that expression. Before the execution of the function, all parameters from left to right are evaluated, resulting in a list of concrete values with the type of each. The correctness of the call is checked as number of parameters and as type. If everything was correct, the respective operand results, otherwise the error is signaled. Sintaxa opr_fun ::= ABS | AND | APX | ATR | DIP | IFP | IFS | LOR | LOG | apel_fun ::= opr_fun ( l_param_act )
Observatie. Numele de operatori funcție se pot scrie cu litere mici sau chiar în combinație mari cu mici. Example function call: ATR(rtl[d,w]*((d-1)*nrwhse+w),h) , ABS(a[j,k]+5.3] , SEARCH(h,rtindl[1],find) ,
Functions recognized by the ALLO translator
They are used in relational expressions necessary for the validation of auxiliary variables of integer or real type that may be subject to restrictions. The result is 1 (true) or 0 (false) depending on whether or not the relationship was fulfilled. Sintaxa opr_rel ::= < | <= | = | >= | > | <> Symbolic variable boundary operators Model variables can only receive values if they are in a certain domain. This request is marked in the MPS file in the BOUNDS section. Thus the optimizer takes into account the condition in the process of finding an optimal solution. And model constraint variables may be subject to similar conditions. Conditioning is obtained by using symbolic boundary operators from variable boundary clauses or model restrictions. Sintaxa opr_marg ::= <= | = | >= | IN Observation. In case = we have a fixed value model variable (FX in the BOUNDS section). A model constraint is a constraint with equality (E in the ROWS section). IN determines membership in a domain with finite real margins. The operators <= or >= say that the model variable / model restriction variable is allowed to take the respective value as well. There is no strict case in standard modeling. For the model variable the operators <= or> = transmit UP or LO in the BOUNDS section. For the model restriction variable the operators <= or> = transmit L or G in the ROWS section. Parenthesis The ALLO language uses three pairs of parentheses: round brackets () ; square brackets [] ; brackets {} Round brackets are used in the construction of complex
expressions or in the construction of default function
calls. The parenthesed expression is calculated as a value
and becomes an operand. If it is the case of a default
function call, the values of the parameters are
calculated, after which the function that possibly performs
an action but produces an operand used in the calculation is
"called". Sintaxa p_rotunda ::= ( | )
The basic element of the ALLO language is the expression
which is absent from almost all instructions except the
instructions for structuring the model into sections. We
have the following types of expressions: arithmetic;
relational; symbolic.
Arithmetic expresions Arithmetic expressions are constructions with operands,
operators and round brackets. As operands can be integer or
real constants, integer or real type auxiliary variables,
references to integer elements of integer or real variables,
implicit function calls. The result of evaluating an
arithmetic expression is an operand, real or integer value. Sintaxa expr_aritm ::= termen rest_suma
Examples : (d-1)*nrwhse+w ; h-(m-1)*nrprod ; ATR(h+IFS(rtl[d,w],1,0),h) ; SUM[f IN fact,p IN prod](Ifp(rpc[f,p],0,1,0)) ; +2.3 ; N ; 5 * M . Validation condition expressions These expressions are constructions based on two arithmetic expressions linked by a relational operator. The result of evaluating such an expression is an integer value 0 or 1 with the meaning of false or true. The two arithmetic expressions are first evaluated and compared. These expressions are used in the instructions for defining auxiliary variables of integer or real type, namely in the validation clause. Sintaxa expr_cond_valid ::= expr_aritm opr_rel expr_aritm Exemple : prodmax > 0.0 | omin[f] <= omax[f] | nrdctr < nrwhse Symbolic linear expressions are expressions constructed and evaluated in a similar way to arithmetic expressions. But here also appear variable scalar model operands or references to massive elements. In multiplicative binary operators we cannot have symbolic expressions simultaneously because the resulting expression would no longer be a linear thing signaled by the translator in the evaluation process. Objective function variables or constraint variables have nothing to do with a symbolic expression. They can receive a linear symbolic expression as a value. Sintaxa expr_simb ::= termen_simb rest_suma_simb
Exemple : Sum[f In fprod,p In perp](profdc[f,p]*xprod[f,p]) , xsmat[r,p] - Sum[f In fprod](ump[r,f] * xprod[f,p])
Repetitive blocks are ALLO semantic constructions that allow
us to repeat (with other parameters related to the cycle)
the instructions or operations in their body. This feature
is especially useful in concentrated model writing even for
large processes / systems. Blocks have a header defining one
or more cycles simultaneously. A cycle is defined by a
cycling index as well as an entire domain in which it is
allowed to evolve with the default step 1. To initiate a
cycle, the cycling range is evaluated (there are dynamic
domains with expressions that include variable cycling
indexes that are active / have value only in this context)
after which the cycling index is initialized with the value
of the lower edge of the range.
FOR
block
It allows the resumption of a group of instructions that
form the body of the cycle whose beginning and end are
perceived by syntax. If the body has several instructions it
starts with {and ends with}. Each instruction in the body
ends with; except for the last whose end is recognized by}.
Sintaxa
antet_for ::= FOR [ l_expr_apart ]
Exemplu : FOR [p
IN perp] |
FOR [r
IN rmat, f
IN fprod]
SUM block
It allows the resumption of the process of summing an
expression between two round brackets that form the body of
the cycle. The SUM block is particularly useful in
expressing very large symbolic expressions that can be
concentrated to the maximum. The summation process starts
with the value 0.0 to which is added what results in each
repeated pass over the expression (which is reclassified and
added) until the cycle is exhausted.
Sintaxa
antet_sum ::= SUM [ l_expr_apart ]
Exemplu : SUM[r
IN rmat] , SUM
[f IN fprod, p IN perp]
ALLO language instructions are special assemblies with
complex semantics that define the sections of a model and
each variable used in each section of the model. The
instruction categories are: model structuring; preparation
of auxiliary data; defining model variables; defining
objective functions; objective function selection and
optimization direction specification; defining model
restrictions.
Statements
for model structuring
Their role is to create a sectional structure of an ALLO
model. Apart from the template statement, all others are
defined only by those keywords that indicate the destination
of the next section or end of the template. Each section
appears only once. Sintaxa
instr_struct_model ::= MODEL nume_model |
VARIABLES |
OBJECTIVES |
CONSTRAINTS |
END
Sintax of program / model ALLO
Below is the syntactic scheme of an optimization model
written in ALLO language. Syntax is free in white areas
consisting of spaces, tabs, empty source lines. Also
reserved words are not case sensitive and can be used as
desired. Any ALLO name behaves the same. Sintaxa
Program ::= MODEL nume_model
sect_var_aux
VARIABLES
OBJECTIVES
CONSTRAINTS
END
Secțiunea variabile auxiliare
sect_var_aux ::= s_instr
Secțiunea variabile model
sect_var_model ::= s_instr_var_model
Secțiunea variabile funcții obiectiv
sect_var_fobj ::= s_instr_fobj instr_select_fobj
instr_select_fobj ::= MINIMIZE ref_fobj |
MAXIMIZE ref_fobj
Secțiunea variabile restricții
sect_var_restr ::= s_instr_restr
Statements
for preparation of auxiliary data They allow us to define the auxiliary variables needed in
the construction of any model. We have a specific
instruction for each type of date. Each statement begins
with the appropriate keyword. The INTEGER and REAL
statements are the same except for the keyword. Here is the
type of instructions: FILLE; RANGE; INTEGER; REAL.
FILE
statement We can define auxiliary variables of type FILE whose value
is a file specification string recognized by the DOS
operating system. The file is secondary with data attached
to the model prototype in the main file. Access to it is
done by invoking the variable name (internal name for the
file) in the READ command from the instructions for defining
the auxiliary variables of type INTEGER or REAL if they have
the initialization data in the associated file. Through an
instruction we can define several secondary files separated
by a semicolon character. A secondary file is opened by
default for access to the current data in them. This
statement can appear anywhere in the section.
Sintaxa
instr_file ::= FILE s_decl_file
Exemple : FILE fpp = "prodplan.dat" , FILE fcsd="cetsud.dat"
RANGE
statement
Allows you to define one or more RANGE variables (integer or
real range domain). Through an instruction we can define
several fields separated by the semicolon character. The
domain constant must be calculable at the time of definition
in the sense that both edge expressions must be calculable.
If they contain other auxiliary variables of integer or real
type they must be previously defined and of course
initialized. This statement can appear anywhere in the
section. Sintaxa
instr_domeniu ::= RANGE s_decl_domeniu
Exemple : RANGE fprod = [1,nrfprod] ; rmat = [1,nrrmat ]
Observation. Above we
have defined two fields in a single statement that can be
written even on several source lines. Each domain could be
defined in a separate statement. It is assumed that the
auxiliary variables nrfprod and nrmat are already known when
reaching the RANGE statement so the margin expressions are
all calculable. These values must also be greater than or
equal to 1 due to the lower edge present and the constant 1.
INTEGER
statement Allows the definition of one or more auxiliary variables of
integer, scalar or massive type. If they are multiple then
their definitions must be separated by a semicolon token.
Each definition is composed of three components, the first
of which is mandatory because it has the name and size of
the variable. The second component is dedicated to the
initialization of the variable that can be done even by
reading the data from a secondary file from the pointer that
was reached at the time of the READ command. Component three
deals with validation. If it is not component two, for
dimensioned variables it is interpreted as a data assignment
procedure for some (even all) elements of the mass. In this
case only the relational operator = which is reinterpreted
as the assignment operator can appear in the validation
sequence. That is why only the references to the massive
element can stand in front of it.
Sintaxa
instr_integer ::= INTEGER s_decl_integer
Examples:
INTEGER M = 10 ; N = 23
INTEGER V[ [3,5] ] ={1,2,3}
INTEGER nrfprod
READ fpp
IS nrfprod >0 ;
nrperp
READ fpp
IS nrperp >0
Observation. In the first
instruction the auxiliary variables M and N are defined with
the initialization values 10 respectively 23. In the second
instruction we defined a vector with indices in the range
[3,5] whose initial values are V [3] = 1, V [ 4] = 2 and V
[5] = 3. In the last instruction, two scalar auxiliary
variables are defined. For each variable the value is read
from the fpp file and validated by the condition after the
IS keyword. REAL statement
Everything that has been said about the INTEGER type
auxiliary variables remains valid here as well. From the
syntax part_init and part_valid are defined exactly as in
the previous syntax. Only the following are added to them:
Sintaxa
instr_real ::= REAL s_decl_real
Exemple :
REAL ump [rmat,fprod]
READ fpp
IS FOR [r IN rmat,f
IN fprod] ump[r,f]>= 0.0
Observation. Above is
defined a single matrix auxiliary variable whose values are
taken from the fpp file. Each initialization value of the
matrix element cannot be a negative number because it does
not allow the validation clause in the body of the FOR block
that cycles on two indices of the rmat and fprod domains.
Model variable
definition statement
It allows us to define symbolic variables, basic elements
that participate in symbolic expressions in the definition
of objective function variables and model constraint
variables. A model variable has a name, a dimensional list
if it is of massive type as well as a possible boundary
condition. Model variables have no initial value. As an
initial value we can consider the condition value if it
exists and which consists of the code of the boundary
operator and of one or two values that represent the lower
edge or the upper edge as an admissible range of values. We
have a two-value domain when the operator is IN. Model
variables will receive values only in the optimization
process that tries to determine an optimal solution. This
process is independent of the model analysis, validation and
translation process in standard MPS format.
The statement
are
separated by a semicolon character, except for the last.
Sintaxa
instr_var_model ::= var_model part_cond_marg
Examples : xprod [fprod,perp] , xsmat[rmat,perpext]
IS FOR[r
IN rmat] xsmat[r,1] <= stinimax[r]
Observation. The first
statement defines a matrix model variable that contains no
boundary clause in which all elements are assumed in the
real positive domain. The second statement defines a
variable that contains a boundary clause for all components
that have the index 1 on the second dimension and are
required not to exceed the upper limit with value in the
stinimax vector the first dimensional index. The clause is
with the FOR block which has only one component: xsmat [r,
1] <= stinimax [r].
Objective function variable
definition statement An objective function variable has a name, a dimensional
list (if it is of massive type) as well as a part of
definition with symbolic expression. The instructions for defining objective function variables
are separated from each other by the semicolon character. An
exception is the last statement that ends before a MINIMIZE
/ MAXIMIZE keyword.
Sintaxa
instr_fobj ::= var_fobj IS proced_def_fobj
Exemplu: fobj IS fobj := SUM[f
IN fprod,p
IN perp](profdc[f,p]*xprod[f,p])
Observation. Above we
have a scalar variable function objective fobj as a sum of
symbolic expressions.
Objective
function selection statement
This instruction, the last in the objective functions
section allows not only the selection of the objective
function (considered by the optimizer) but also the type of
problem. The ALLO translator puts min / max on the line
corresponding to this function in the ROWS section of the
resulting MPS file but also N in front of the name. The
other objective functions (if any) do not influence the
solution. The reference to the function to be optimized
consists in quoting the name of a scalar variable or of a
reference element from the objective type variable of
massive type. Sintaxa
instr_select_fobj ::= MINIMIZE ref_fobj |
MAXIMIZE ref_fobj
Exemple : MAXIMIZE profit ,
MINIMIZE cost
Restriction variable
definition statement
The basic structure of a linear model consists of model
constraints that provide the model matrix. In the ALLO
language, each restriction also has a name required by the
MPS standard. On the other hand, a model constraint variable
can be a massive one that facilitates the work of defining
the model.
Sintaxa
instr_restr ::= var_restr IS proced_defrestr
Examples:
limprod [perp] IS FOR [p
IN perp] limprod[p]:= SUM[f
IN fprod](xprod [f,p]) <= prodmax;
Observation. The
statement defines a vector constraint variable called
limprod. The definition of each component is in the body of
a FOR cycle and contains a symbolic expression made with the
SUM operator plus a higher boundary condition.
Structure of ALLO program /
model
The model has a structure marked by the keywords MODEL,
VARIABLES, OBJECTIVES, CONSTRAINTS, END
MODEL nume_model
VARIABLES
OBJECTIVES
CONSTRAINS
END
Section of
auxiliary variables
Starts with the MODEL statement and ends before the
VARIABLES statement. It is dedicated to defining and
preparing all the data needed to build the model in the last
three sections: the model variables section, the objective
functions section and the constraints section.
Section of
model variables It is signaled by the VARIABLES
statement and holds up to the
OBJECTIVES statement. All model variables are defined
here. A boundary condition may appear in a definition /
instruction. If the variable does not appear, it is
considered positive (from 0 to + infinity) For the massive
type variable, the rest of the elements in the massif (if
any) that were not invoked in the boundary condition are
considered positive model variables.
Section of
objective function
Start with the OBJECTIVES
statement and stick to
CONSTRAINTS. Here are defined all the objective
functions from which we select only one (scalar or solid
element reference) for model optimization. Both the function
definitions and the selection instruction have an equivalent
in the MPS file by marking, in the ROWS section, all
functions with N in front of the name (linearized if they
come from solid) and with MIN or MAX after the name of the
selected function. Of course, the names of the objective
functions are also invoked in the COLUMNS section. All
objectively unselected functions do not influence the
solution. A new selection can be easily made by changing the
selection instruction, generating a new MPS, etc.
The section ends with the
selection statement which is mandatory if we want to solve
the problem.
Section of
model restriction
Start with the CONSTRAINTS
statement and continue to the
END statement that ends the ALLO text. all model
restrictions are defined in this section. Simple equal or
non-equal constraints and double-bounded restrictions can be
defined. They produce a line in the
RHS and
RANGES section of the
resulting MPS file. All
constraints produce lines in the
ROWS section marked with E, L or G. Of course the
names of the constraint functions are also invoked in the
COLUMNS section of the
MPS.
Sintax ALLO
Metalimbaj pentru Sintaxa ALLO
::=
tells us that its left element is constructed as follows (or
is by definition);
| is a separator from the list items. Any element can
participate in the respective assembly;
Space between two metalanguage elements or between a
metalanguage element and an atom (eg link character _) means
the concatenation operation between two strings. A
metalanguage element means a class / set of possible
assemblies (strings on the alphabet) constructed with the
rules of that element. lambda is the
symbol for the null element relative to the character or
string concatenation operation. It is an empty string that
has no character being of zero length.
Gramar of ALLO language was
brought to the form that meets the
criterion LL1
Begin of ALLO
sintax nume ::= litera | nume litera | nume cifra | nume _
var_intreg ::= var_intreg_scalara | var_intreg_masiv
secv_cifra ::= cifra | cifra secv_cifra
const_domeniu ::= [ expr_aritm , expr_aritm ]
sir ::= " secv_car "
masiv ::= nume_masiv [ l_dim ]
opr_aritm ::= opr_unar | opr_binar
opr_fun ::= ABS | AND | APX | ATR | DIP | IFP | IFS | LOR | LOG | MAX | MIN |
opr_rel ::= < | <= | = | >= | > | <>
opr_marg ::= <= | = | >= | IN
Program ::= MODEL nume_model
sect_var_aux ::= s_instr
instr_file ::= FILE s_decl_file
instr_domeniu ::= RANGE s_decl_domeniu
instr_integer ::= INTEGER s_decl_integer
instr_real ::= REAL s_decl_real
sect_var_model ::= s_instr_var_model
sect_var_fobj ::= s_instr_fobj instr_select_fobj
instr_select_fobj ::= MINIMIZE ref_fobj | MAXIMIZE ref_fobj
sect_var_restr ::= s_instr_restr
LPTR Language
In the
1975s the ICI Institute (founded in 1970) was tasked with
compiling a compiler for
RTL - Real Time Language (designed
and developed by Imperial Chemical Industries Limited,
London) to equip minicomputers
Independent 100
and Coral. The RTL compiler was implemented on the American
minicomputers DEC - PDP 11 with
RSX 11 operating system, a
family of multi-user operating systems made in the 1970s.
Two PDPs were bought by Romania, both without the RTL
compiler due to the embargo imposed.
Due to limited human resources and lack of technical
resources (PDP 11 with
Macro 11 assembler) the faculty
handed over the project to the ICI institute. In addition to
filling the gaps in the project followed the hardest part
related to semantic analysis, code generation, programming
also in Macro 11, testing, etc. The institute still did not
have specialists in the field (with some exceptions) because
only in 1974 it hired dozens of graduates specialized in
mathematics, computer science, computers, cybernetics but
not in the construction of compilers. To continue the LPTR
project, a team was formed (out of 8 employees from the
Computing Center) led by Mat. Petre Preoteasa.
Fortunately Mat. Gheorghe Borcan found a
continuation solution that preserved most of the work done
(especially by the first team) until this phase. It was the
result of specialization through the master's degree in
formal languages and compilation writing techniques and
more. The solution was also agreed by the Politehnica team.
As a result, the concept of implementation was revived by
introducing a new step that would be in fact the first step
in the source text. Some essential routines (missing from
the project) were designed that finalized the mechanism of
operation and understanding (by the whole team) of this
compiler. Thus, the functional structure of the compiler was
finalized, as well as the mandatory linking structure at
that time due to the internal memory limit (for execution)
imposed by the PDP-11M minicomputer, RSX-11M operating
system. ICI had a copy to which the LPTR team (from the
Computing Center) had limited access because the
minicomputer belonged to the Research Department! The first
step was exceptionally programmed in Macro 11 by the
brilliant Mat. Vasile Coardoș who left us prematurely.
Due to the ALLO language, in Feb.1998, we
returned to the LPTR grammar, processing and testing the
form below that meets the LL1 condition. It is based on the
grammar of the LPTR project with some modifications. I hope
it will be useful for students from the profile faculties
and not only.
A
LL1 gramar of
LPTR language The metalanguage used is similar to that of ALLO
Recognized characters: Ignored characters:
Ascii Cod(9) - Ascii Cod(13) ! any from interval Comments are left and right bordered by character "%"
/*-----------------Tokens results from the Lexical Analyzer------------------------*/
nrop ::= cifra
/*-------------------------------
Productions ---------------------------*/ End LPTR language gramar | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ALLO and SAMO, Language for Modeling and Optimisation System
Subscribe to:
Posts (Atom)