Here is a small model to be implemented in LPL:
The implementation in LPL of this model is straightforward:
model firstModel;
variable x; y;
constraint C: 5*x + 5*y <= 350;
D: 6*x + 2*y <= 300;
maximize Obj: 300*x + 200*y;
Writep(x,y);
end
Every model begin with the keyword model followed by an identifier and a semicolon and ends with keyword end.
The LPL model consists of five declarations and a statement.
Two variable declaration with the name x and y begin with keyword variable. If the same declaration repeats, the keyword can be dropped.
Two constraint declarations with name C and D followed by a colon and an expression. Note that constraints always have a name.
A maximizing declaration with name Obj also followed by a colon and an expression.
Finally, a statement, a function call Writep to print the two variables with their value.
Copy this model and paste it here: empty (A browser opens). Then click on the button Run and Solve. A moment later, the solution of this model is displayed: x = 40,y = 30.
To formulate larger models with thousands of variables and constraints, we use a notation in mathematics that is called indexed notation. The following is a linear model with m > 0 constraints and n > 0 variables.
One of the main strength of LPL is to use the index notation. Data can be declared by parameters :
parameter m := 1000;
n := 2000;
The keyword parameter starts a parameter declaration. A name follows and optional a assignment. It means that m gets a value of 1000, and n gets a value of 2000.
Index sets also are a fundamental concept in larger models. LPL declares index sets using the keyword set declaring the sets I and J in the same way as above in the mathematical notation :
set I := 1..m;
J := 1..n;
In the parameter declaration, not only singleton data can be defined also vector data, or matrices, or higher dimensional data. The vectors b_{i} with i ∈ I, c_{j} with j ∈ J, and the matrix a_{i,j} are declared (without assignment) :
parameter b{i in I};
c{j in J};
a{i in I, j in J};
These parameters can be assigned in the same way. The assignment can take place directly at the declaration or later on in a proper assignment as in :
a{i in I,j in J} := if(Rnd(0,1)<0.02 , Rnd(0,60));
c{j in J} := if(Rnd(0,1)<0.87 , Rnd(0,9));
b{i in I} := if(Rnd(0,1)<0.87 , Rnd(10,70000));
The assignment is done through an expression that generates random numbers. The function if(cond , exp) returns a value defined by exp if the Boolean condition cond is true else it returns zero. (It is the same as the ternary operator c ? a : b in some programming languages as C, Java, Python, and others.) The function Rnd(a,b) returns a random number uniformly distributed between a and b. Hence, the first assignment generates first a random number between 0 and 1, and if it is smaller than 0.02 then a second random number between 0 and 60 is generated and assigned to the matrix else 0 is assigned. This operation is repeated for all elements in I combined with all elements in J. The statement is similar to a double loop in a programming language like C (suppose myrand() returns a double between 0 and 1) :
double a[][]; int i,j;
for (i=0; i<m; i++) {
for (j=0; j<n; j++) {
a[i,j] = myrand() < 0.02 ? 60*myrand() : 0;
}
}
As in the loops, the LPL statement
a{i in I, j in J} := ...
runs through the sets in lexicographical order, that is, right-most index first, left-most index last, and on each pass it assigns a random value or zero to the matrix entry.
In other words, the matrix a contains about 2% of data that are different from zero. The large majority of its elements is zero. Of course, LPL only stored the non-zeroes (in a sparse way).
A last remark about a simplified notation in LPL is notable: Although the previous notation as in a{i in I, j in J} is perfectly legal syntax in LPL, a shorter notation is preferable. In LPL set names are normally in lowercase letters and can be used as indexes too. There is generally no need to use a separate symbol for sets. So the previous declarations could also simply be written as:
set i := 1..m;
j := 1..n;
parameter a{i,j};
c{j};
b{i};
In the same way as parameters, also variables (x{i}) and constraints C{i} can be indexed to specify a vector or a higher dimensional quantity of single objects. The same indexing mechanism can also be applied to several index operators, such as ∑ _{i}… (in LPL sum{i} ...).
Now all elements are ready to formulate the general linear model with 1000 constraints and 2000 variables :
model largerModel;
parameter m := 1000; n := 2000;
set i := 1..m; j := 1..n;
parameter
a{i,j} := if(Rnd(0,1)<0.02 , Rnd(0,60));
c{j} := if(Rnd(0,1)<0.87 , Rnd(0,9));
b{i} := if(Rnd(0,1)<0.87 , Rnd(10,70000));
variable x{j};
constraint
C{i}: sum{j} a[i,j]*x[j] <= b[i];
maximize Obj: sum{j} c[j]*x[j];
Write('Objective Value = %7.2f ' n', Obj);
Write{j|x}(' x%-4s = %6.2f' n' , j,x);
end
Again, copy this model and paste it here: empty (A browser opens). Then click on the button Run and Solve. A moment later, the solution of this model is displayed:
Objective Value = 77599.07 x22 = 34.64 x31 = 14.46 x69 = 110.61 ... about 85 more values ...
About 90 variables out of the 2000 have a value different from zero. Three are shown in the list above.
Note that the function Write was used to write a formatted output of the solution. This function is a very powerful method to generate text output, sophisticated reports using the library of FastReport, as well as database tables or even Excel sheets. See the reference manual for more information [5].
Data can also be directly added to the model. As an exercise, the simple example above is written in an indexed notation:
model secondModel;
set i := [1 2];
j := [a b];
parameter b{i} := [350 300];
c{j} := [300 200];
a{i,j} := [5 5 , 6 2];
variable x{j};
constraint C{i}: sum{j} a[i,j]*x[j] <= b[i];
maximize Obj: sum{j} c[j]*x[j];
Writep(x);
end
(As before, copy this model, paste it here: empty and run it.) Inline data tables are enclosed in [...] and are evaluated and assigned before any other assignment. The elements are listed in lexicographical order. Note that set elements in this case are strings.
Another feature in LPL is repeated execution and branching in its execution. The two statements for looping begin with for and while and for branching it begins with if. The syntax is:
for{setName} do
...statement list...
end;
while expr do
...statement list...
end
if expr then
...statement list...
else //optional part
...statement list...
end
The following program implements the greatest common divider of two numbers (the algorithm is quite inefficient – there are much better methods, but it shows a loop and a branching statement):
model gcd;
integer a := 1943; b := 2813;
c := if(a<b, a, b);
d := 1;
for{i in 1..c} do
if a%i = 0 and b%i = 0 then d:=i; end
end
Write('The gcd of %d and %d is %d' n', a, b, d);
end
(Copy this model, paste it here: empty and run it.) Note first, that the assignment operator is := (not = like in C, Python, Java etc.) and the Boolean equal operator is = (not ==). % is the modulo operator. The keyword integer start a parameter declaration that is integer. It is a shortcut for integer parameter. if has two different uses: the first was already explained above and is a function. The second starts a branching statement. Finally, {i in 1..c} declares an anonymous set with a local index i.
The example shows that LPL is a complete programming language and is Turing complete, in order to be able to pre- and postprocess data before and after solving a model. However, it is far from be a modern programming language – in its actual version. It lacks object oriented concept; its memory is not stack-based, that is, although one can define user defined functions (see below), the function cannot be called recursively; it is interpreted and a just-in-time compiler is missing; so it is not very efficient for most algorithmic tasks. Nevertheless, LPL does something very well: large models, eventually with sparse data sets, can be efficient and compactly formulated and ran. It links well to several commercial and free solver libraries.