Bulletin 104, December 98 

LPL is a computer-executable mathematical modeling language, which can be used to build, modify and document (linear and non-linear) mathematical and logical models. Initially, LPL was designed at the Institute of Informatics at the University of Fribourg ten years ago [Hürlimann 1987] to formulate large linear programming models with thousands of variables and constraints. For example, a general LP with random data containing 2000 variables and 1000 constraints can be formulated in LPL as follows:

MODEL GENLP "The general LP";
OPTION randomSeed:=1;
SET m := /1:1000/; n := /1:2000/;
PARAMETER
A{m,n} := IF(RND(0,1)<0.02 , RND(0,60));
c{n} := IF(RND(0,1)<0.87 , RND(0,9));
b{m} := IF(RND(0,1)<0.87 , RND(10,70000));
VARIABLE x{n};
CONSTRAINT R{m}: SUM{n} A*x <= b;
MAXIMIZE ObjFunction: SUM{n} c*x;
WRITE x;
END

This is a complete formulation and can be submitting to the LPL compiler; it takes 1 minute to generate and solve the whole model on a typical PC.

The actual version of the LPL modeling language (financed by the Swiss National Science Foundation, project no. 1217-45922.95), however, goes far beyond the paradigm of linear programming. It can formulate non-linear models which are submitted to a non-linear solver such as MINOS or ConOPT. It also can formulate certain discrete models. As an example, let us formulate a classical NP-hard scheduling problem: the single machine weighted tardiness problem. This problem can be stated as follows: n jobs are given, each consumes a certain time p_j to be processed on the single machine. The machine can only process one job at the same time. Processing of a job cannot be interrupted until the job has been completed. Furthermore, each job has a due date d_j and a weight w_j. The problem is to find a sequence of processing the jobs such that total tardiness over all jobs is minimized. If job j is completed at time C_j , then the tardiness of job j is defined as : T_j. The objective is now to minimize their weighted sum over all permutations. A problem instance with 40 jobs - again using a randomly generated data set as defined in [Potts/Wassenhove 1985] - can be coded in LPL as follows:

MODEL wT "One machine weighted tardiness";
OPTION solver:=tabu; OPTION randSeed:=1;
SET i ALIAS j "jobs" :=/1:40/;
PARAMETER TF:=0.6; RDD:=0.2;
p{i}:=TRUNC(RND(1,100)); PP:=SUM{i} p;
l:=TRUNC(PP*(1-TF-RDD/2)); u:=TRUNC(PP*(1-TF+RDD/2));
d{i}:=TRUNC(RND(l,u)); d{i}:=IF(d<p,p,d);
w{i} := 1;
DISTINCT VARIABLE x{i} [1,#i] :=i ;
MINIMIZE wT: SUM{i} w[x[i]]*MAX(0,SUM{j|j<=i} p[x[j]]-d[x[i]]);
WRITE wT; x;
END

This time, the problem is handed over automatically by LPL to a heuristic tabu search solver. This solver finds an optimal solution in 90% of all instances with 40 jobs in less than 1 minute. As far as the author is aware, no other modeling system - even commercial once - is capable to formulate such problems in this efficient way.

LPL has many other unique features: a powerful report and input generator; formulation of logical constraints; unit checker; semi-automatically documentation generator; open and easy-to-use solver interface to many solver. LPL can also be linked as a dynamic link library into other applications.

The LPL software together with a complete documentation and 170 models is available free of charge at the LPL-site: ftp://ftp-iiuf.unifr.ch/pub/lpl/ or at the LPL homepage: http://www2-iiuf.unifr.ch/tcs/lpl/.

References

HÜRLIMANN T. [1987], LPL: A Structured Language for Modeling Linear Programs, Disseration, Peter Lang, Bern.

POTTS C.N. & van WASSENHOVE L.N. [1985], A Branch and Bound Algorithm for the Total Weighted Tardiness Problem, Operations Research 33(2), p. 363-376.

Tony Hürlimann

Université de Fribourg - IIUF,
Faucigny 2,
CH - 1700 Fribourg (Suisse)

Tel: +41 26 300 83 45
Fax: +41 26 300 97 26
tony.huerlimann@unifr.ch