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
ftr="translpl.dat" /* Prototype instantiation 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
Extract from optimizer report after resolution
... omit iterations to a feasible solution ...omit iterations to
an optimal solution Optimal Solution found in 15 iterations
... omitted about satisfying the restrictions in the optimal
solution
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 We saw that a massif is a collection of cells / objects of the same type organized according to a known allocation procedure. Access to such a cell / object is made by invoking the name of that massif and a list of index expressions whose number of elements coincides with the number of dimensions of the massif. This is the so-called reference to that element in the massif on the basis of which we access it.The expression index is an arithmetic expression that can be calculated when used in the reference list of a solid element. Calculate its value, convert it (if necessary) to an integer value and then perform the domain membership test. The same is done with any index expression in a list of index expressions. After this, the linearized index is calculated, which represents the place of the referred element. Based on the place, the address from the beginning can also be calculated by multiplying (place -1) with the unit of allocation of the variable type. 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. 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
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
/*-------------Keyword tokens are capitalized------------------*/
/*------------------------------- Productions ---------------------------*/
End LPTR language gramar |
ALLO and SAMO, Language for Modeling and Optimisation System
Subscribe to:
Posts (Atom)