3 Index Notation in LPL

LPL is a computer language that implements basically the index mechanism described. In this section, this implementation is presented. For a general reference of the LPL language see the Reference Manual (see [3]). LPL implements the indexed notation as close as possible to the mathematical notation. But there are some differences. By mean of several examples, we explain the relationship.

In an LPL code, one needs to specify the index sets first. They are available throughout the whole model code. This is done by a declaration that begins with a keyword set. It is followed by the name of the set and an assignment of the elements as follows:

  set I := 1..10; 
  set J := 1..100; 
  set K := 1..n; 
  parameter n;

This declaration defines the three sets I = {110}, J = {1100} and a set K = {1n}. Note that the identifiers can be declared in any order in LPL. n can or cannot have a value (it must be assigned later on).

This set declarations can be used in expressions. The following expressions:

     ∑              ∑                  ∑
A  =     1  ,  B  =     j  ,  C  =            x2
      i∈I             j∈J            x∈J|10≤x ≤20

can be implemented directly as follows:

  parameter A := sum{i in I} 1; 
  parameter B := sum{j in J} j; 
  parameter C := sum{x in J|x>=10 and x<=20} x^2;

The index operator is the keyword sum. The indexing term i I is appended to the index operator and bracketed with { and }. We also need to declare new parameters A, B, and C that hold the calculated value. The indexing condition is a proper Boolean expression in the language. Hence, 10 x 20 can be formulated as 10<=x<=20. Note that we use := as an assignment operator.

If we use tables such as vi, ai,j, and bi,j,k with i I, j J, k K, we must declare them first in the code as follows:

  parameter v{i in I}; 
  parameter a{i in I, j in J}; 
  parameter b{i in I, j in J, k in K};

Using these declaration we now can build other expressions like:

                         (        )
     ∑                     ∑                       ∑
D  =     vi  ,  E =  mai∈xI       ai,j    ,  Fk ∈K =        bi,j,k
     i∈I                   j∈J                   i∈I, j∈J

using the following syntax:

  parameter D := sum{i in I} v[i]; 
  parameter E := max{i in I} (sum{j in J} a[i,j]); 
  parameter F{k in K} := sum{i in I, j in J} b[i,j,k];

The passive indexes in the indexed expression are enclosed in the brackets [ and ]. So there is a clear syntactical distinction between the passive and the active indexes in the language.

In LPL there exist a slightly shorter syntax that could also be used for an indexing term. The examples above could be coded as follows:

  set i := 1..10; 
  set j := 1..100; 
  parameter n; 
  set k := 1..n; 
  parameter A := sum{i} 1; 
  parameter B := sum{j} j; 
  parameter C := sum{j|10<=j<=20} j^2; 
  parameter v{i}; 
  parameter a{i,j}; 
  parameter b{i,j,k}; 
  parameter D := sum{i} v[i]; 
  parameter E := max{i} (sum{j} a[i,j]); 
  parameter F{k} := sum{i,j} b[i,j,k];

In this code, the active index has the same name as the corresponding index set. Hence, {i in I}, an indexing term, can just be written as {i}. This makes the expressions more readable and – in most context – much shorter. However, this can lead to difficulties as soon as the same index set is used more than once in an indexed expression as in the following simple expression:

H  =     ci,j


In such a case, LPL allows one to define one or two alias names for the same index set. We then could code this as following:

  set i, j := 1..10; 
  parameter c{i,j}; 
  parameter H := sum{i,j} c[i,j];

Of course, one always can use the more “traditional” notation as follows:

  set I := 1..10; 
  parameter c{i in I, j in J} 
  parameter H := sum{i in I,j in I} c[i,j];

The alias names – separated by commas – are just other names for the index set and can be used as unique active indexes name in indexed notations. LPL allows at most two aliases for each index sets. If we use more than two, then we always need to use the longer syntax as in the following example:

L =        di,j,k,p

in which case we need to code this as:

  set i, j,k := 1..10; 
  parameter d{i,j,k,p in i}; 
  parameter L := sum{i,j,k,p in i} d[i,j,k,p];

The two versions of the LPL code can be downloaded or executed directly at: exercise0a and exercise0b

Let us now code the Exercise 1 given in section 2.4 as an LPL model. First we implement the declarations: The set of products and factories which are P = {1, 2, 3} and F = {1, 2, 3, 4} the cost table ci,j, the value table vp and the quantity table xp,i,j with i,j F and p P. In LPL these data tables can be implemented as follows:

  set p    := 1..3; 
  set i, j := 1..4; 
  parameter c{i,j|i<>j} := [. 1 5 2 , 2 . 4 2 , 1 2 . 3 , 1 3 1 .]; 
  parameter v{p}        := [6 2 3]; 
  parameter x{p,i,j|i<>j} := [ 
      . 48 37 45 36 . 43 46 44 36 . 33 36 39 34 . , 
      . 46 35 39 32 . 47 35 45 49 . 39 47 46 30 . , 
      . 32 32 40 30 . 41 30 45 43 . 45 44 41 34 .  ];

In table c and x we use the indexing condition i<>j because there is no cost or quantity defined form a factory to itself. The data itself are listed in a lexico-graphical order. The expressions given in section 2.4 are then formulated as follows in LPL:

    parameter T     := sum{p,i,j} c[i,j]*x[p,i,j]; 
    parameter V     := sum{p,i,j} v[p]*x[p,i,j]; 
    parameter C{p}  := sum{i,j} c[i,j]*x[p,i,j]; 
    parameter W{i,j}:= sum{p} v[p]*x[p,i,j]; 
    parameter M{i}  := max{p,j} x[p,i,j]; 
    parameter S{i}  := max{p} (sum{j} x[p,i,j]);

The complete model can be executed at: exercise1a.

Exercise 1 (continued):

Let us now add a requirement that the transportation can only take place between a small subset of all (i,j) links between the factories i,j F. Hence, we need to introduce a property K(i,j) which is true if the transportation can take place between factory i and factory j. We define it as:

         {                                 }
Ki,j∈F =   (1,2 ) (1,4 ) (2,3)  (3,2)  (4,3)

The tuple list means that the transportation can only occur from factory 1 to 2, from 1 to 4, from 2 to 3, from 3 to 2 and from 4 to 3. Only 5 transportation links are allowed. The corresponding expressions are then as follows:

(1) The total transportation costs T is calculated as follows:

T =               ci,j ⋅ xp,i,j = 1524
     p∈P, i,j∈F|K (i,j)

(2) The total value transported is as follows:

V  =               vp ⋅ xp,i,j = 2148
     p∈P, i,j∈F|K(i,j)

(3) The total transportation costs Cp for each product p P is:

                             (    )
           ∑                   511
Cp∈P =           ci,j ⋅ xp,i,j = ( 537)
        i,j∈F|K (i,j)              476

(4) The value Wi,j transported between all factories (i,j) F × F is:

                             (                 )
                               -  476   388  -
              ∑              | -   -    475  - |
Wi,j∈F|K (i,j) =     vp ⋅ xp,i,j = |(               |)
              p∈P              -  443   -    -
                               -   -    366  -

(5) The maximum quantity Mi transported from a factory i F is:

                            (               )
Mi ∈F = p∈P,m ja∈xF|K(i,j)xp,i,j =  48  47  49  34

(6) For each product p P the sum of the maximum quantity Si transported from a factory i F is:

            (              )    (   )
                 ∑                85
S    =  max (          x   )  = || 47||
  i∈F    p∈P             p,i,j     ( 49)
              j∈F|K(i,j)           34

It is straightforward to code this in LPL. First we declare the table of property Ki,j (this is nothing else than a tuple list, see above) as following:

  set k{i,j} := [ 1 2 , 1 4 , 2 3 , 3 2 , 4 3 ];

The property K(i,j) is simply declared as a set. In fact, in LPL k{i,j} defines a tuple list which is a subset of the Cartesian Product of (i,j) I ×I. In LPL, we can code the expressions as follows:

    parameter T    := sum{p,i,j|k[i,j]} c[i,j]*x[p,i,j]; 
    parameter V    := sum{p,i,j|k[i,j]} v[p]*x[p,i,j]; 
    parameter C{p} := sum{i,j|k[i,j]} c[i,j]*x[p,i,j]; 
    parameter W{i,j|k[i,j]} := sum{p} v[p]*x[p,i,j]; 
    parameter M{i} := max{p,j|k[i,j]} x[p,i,j]; 
    parameter S{i} := max{p} (sum{j|k[i,j]} x[p,i,j]);

Since in LPL k{i,j} is itself a set, it can be used as an index set. Hence, the previous code could be written also as:

    parameter T    := sum{p,k[i,j]} c[i,j]*x[p,i,j]; 
    parameter V    := sum{p,k[i,j]} v[p]*x[p,i,j]; 
    parameter C{p} := sum{k[i,j]} c[i,j]*x[p,i,j]; 
    parameter W{k[i,j]} := sum{p} v[p]*x[p,i,j]; 
    parameter M{i} := max{p,j|k[i,j]} x[p,i,j]; 
    parameter S{i} := max{p} (sum{j|k[i,j]} x[p,i,j]);

The difference is in the first four expressions. We wrote {p,k[i,j]} instead of {p,i,j|k[i,j]}. These two indexing terms define the same set. Computationally, however, there can be a huge difference. While the first indexing term {p,i,j|k[i,j]} has cardinality of P ×I ×I the second indexing term {p,k[i,j]} only has cardinality of P ×K(i,j). The two version of LPL code can be downloaded or executed directly at: exercise1b and exercise1c.