LP-packages: working with real-life LP-problems

To practise with real-life LP-models some software has been made available in many different ways, some of it has been installed on the LBS-aio computer network. In genral the re are many software packages available that can handle optimization problems in genral, and linear and integr programming problems in particular. Software is available for mainframes, PC's and workstation. Examples are OSL, CPLEX, LINDO, MPSX, PC-Prog, SIMPLEX. Furthermore there are packages that not only solve LP-problems, but have additonal possibilities for a structured and user-friendly way of setting up models and dealing with (several) instances. Such packages are called 'modelling languages'. Examples are AIMMS, AMPL, GAMS. Because of the diversity in LP-packages it is impossible to give a completely general description of how to work with these poackages and we have to refer to the respective manuals. In particular the way to handle the important sensitivity analysis differs from system to system. There are more or less two rather general ways to INPUT a linear programming model. These are the so-called LP-format and the MPS-format. They will be described below.

Student version of SIMPLEX and of PC-PROG have been installed on the LBS-aio computer network. However they lack good documentation, and are not so easy to use. Moreover they cannot handle real-life size LP-problems. Another PC-product available on campus is LINDO. The student version is downloadable from the EUT application server. This LINDO Solver Suite contains the LINDO LP/ILP-solver, as well as a modelling language LINGO, and a spreadsheet interface What's Best. It is well documented with a lot of examples and help-files.

Finally one may use the package CPLEX. This is state-of-the-art LP-software for which the size of problems to work with is merely limited by the computer capacity. A drawback is that the avaiblable version is licensed only on workstations in the Department of Mathematics and Computing Science. There exist PC-versions of CPLEX of course. In order to work with the CPLEX software in the Mathematics Department one may send email to 2s720@win.tue.nl. This is a program that interprets the body of the email message as input to CPLEX. The LP-model is processed and the solution is sent back to the sender. A disadvantage is that the sender has no real control over the solution process. An LP-problem that is not perfectly stated may yield a meaningless email reply by our program. This construction is only intended for on-campus use, and for educational purposes only.

The email message for 2s720@win.tue.nl should only contain an LP-model, written in the LP-format required by CPLEX, in its BODY. NO attachments are to be used. It is wise to add a comment in the email's subject-line so as to recognize the response by 2s720@win.tue.nl. Some email programmes - like the one under GroupWise - can not handle message with large texts in the body (up to 32 KiloBytes). Select a more flexible mail program if this problem occurs.

MPS-format

The MPS-matrix fromat (MPS = Mathematical Programming Structure) is a structured way to store the relevant data of a mathamtical programming problem. The format has remained from the punch-card era. Nowadays, one punch card translates to one line of input, using at most 80 positions. In general, on each line, one distinguishes between SIX fields: field ONE (indicactor) covers columns 1 to 4, field TWO (name) covers 5 to 12, field THREE (name) covers 15 to 22, field FOUR (value) covers columns 25 to 36, field FIVE (name) covers columns 40 to 47, field SIX (value) covers columns 50 to 61.

Below the MPS-format is described with comment between brackets. The MPS file consists of several SECTIONS, which, if present, appears in the following order.

Section 1: the namecard.

The first line consists of the word NAME, possibly followed by the problemname.

Format: column 1-4   NAME
               15-22 problemname

Section 2: the rows.

Here all rows are given a name and a type: a restriction has type G, L, or E; other rows like the objective are of neutral type N. One may have sevral rows of neutral type (for purposes of sensitivity analysis for instance). In the optimization phase the first neutral rows is considered to be the objective.

Format: 
  first line:    column  1 - 4   ROWS
  other lines:   column  1       space
                         2 of 3  N (neutral, no restriction)
                                 G (restriction >=, greater than or equal to)
                                 L (restriction <=, smaller than or equal to)
                                 E (restriction  =, equal to)
                         4       space
                         5 - 12  name of row

Section 3: the columns.

Here all columns (variables) are mentioned. Furthermore, for each variable the non-zero entries in the constraint matrix are mentioned. There is room for two non-zero entries in each MPS-matrix line. The non-zero entry is identified by the name of the row in which it appears, and the value it has.

Format:
  first line:    column  1 -  7  COLUMNS
  other lines:   column  1 -  4  spaces
                         5 - 12  column name
                        15 - 22  row name
                        25 - 36  value matrix coefficient
                        40 - 47  row name                   (refers to same variable)
                        50 - 61  value matrix coefficient  (refers to same variable)

Section 4: right hand side.

Analogously to the columns section various right hand sides are mentioned and its non-zeroes described. Different right hand sides may be used for sensitivity analysis purposes. The first one is applied when optimizing.

Format:
  first line:    column  1 -  3  RHS
  other lines:   column  1 -  4  spaces
                         5 - 12  name right hand side 
                        15 - 22  row name
                        25 - 36  value right hand side
                        40 - 47  row name
                        50 - 61  value right hand side

Section 5: range-section.

Offers the opportunity to give lower and upper bounds to a row. If in the row section a row of type L has been declared, and if the right hand side of this less than constraint is b, and if r is the value for the range, then b-r is considered a lower bound, and b is an upper bound on the row. If the rows was declared of type G, it is now bound between b and b+r.

Format:
  first line:    column  1 -  6  RANGES
  other lines:   column  1 -  4  spaces
                         5 - 12  name range 
                        15 - 22  row name (not objective!)
                        25 - 36  value range
                        40 - 47  row name (not objective!)
                        50 - 61  value range

Section 6: the bounds.

Here variables cam be fisxed, or bounded bwteen a lower and an upper bound. Note that it is more efficient to give the restriction (x <= 5) implicitly in the bounds section, than putting it explicitly in the rows section. The latter would give the same mathematical model but would require a bigger constraint matrix. In the working of the simplex method, bounds on variables are taken into account very efficiently.

Format:
  first line:    column  1 -  6  BOUNDS
  other lines:   column  1       space    
                         2 - 3   LO (lower bound)
                                 UP (upper bound)
                                 FX (fixed value)
                         4       space
                         5 - 12  name of bound
                        15 - 22  column name 
                        25 - 36  value of bound

Section 7: end

Format:          column  1 -  6  ENDATA

Often it is a problem to type in a problem in MPS format without errors. To this purpose one often uses matrixgenerators. Some speadsheets and modelling languages contain such matrix generators. INTEGRALITY of certain variables is indicated by the use of so-called MARKERS (see example below), or by the use of alternative bound-types like UI for Upper bound on Integer.

LP-foraat

Most LP-solvers (among which LINDO and CPLEX) allow to enter the LP-problem in a more natural manner, giving a row-wise oriented view of the problem at hand. In a dialog with the solver problems can be entered from file or from keyboard. Again, there are some rules to follow for a proper entering of the problem data. Below follow the rules for entering a problem in CPLEX LP-format. The rules for LINDO are very similar. One is referred to the manual and examples of LINDO.
CPLEX accepts any problem stored in an ASCII-file provided the following rules are obeyed.

Rule_1: Everything following a backslash up to the next end-of-line is considered comment. Very useful when setting up, or maintaining a model. In computations, all comment lines are neglected. Comment lines can be placed all over in the document.

Rule_2: In general, spaces between characters are irrelevant and are skipped when the file is being read. However, you may not use a space within a name of a constraint of a variable, or within names of delimiters such as MAX, MIN, BOUNDS and ST. Lines are limited to a maximum length of 255 characters.

Rule_3: A problem description always starts with either MINIMIZE or MAXIMIZE, MINIMUM or MAXIMUM, the abbreviations MIN or MAX, in whatever combination of upper and lower case letters. This word is followed by the objective and is separated from it by at least one space.

Rule_4: Variables can have arbitrary names, provided that the length is not more than 16 characters, and that one uses alfanumeric characters only (a-z,A-Z,0-9), or one of

    !"#$^&*()/,.;?@_`'{}|~

Longer names will be truncated after 16 characters. The name of a variables cannot start with a decimal point . or a digit (0-9). Nor should the variable name start with e or E, followed by + or - sign or a digit as such combination is considered a numerical value in scientific notation (1e-6 = 0.000001). Do not use names as E8, E-23, e4cats.

Rule_5: The objective function should follow immediately after MINIMIZE or MAXIMIZE. It can run over multiple lines as long as no variable or contant is split by a carriage-return.

Rule_6: The object function can be labeled by preceding it by a name followed by a semi-colon :. Names of objective have to comply with the same rules as names of variables. If no name is assigned CPLEX will use the name "obj".

Rule_7: The start of the constraint sectioon is marked with SUBJECT TO. In its place one mayt also use "such that", "st", "S.T." or "ST." in an arbitrary mix of lower and upper case letters. One of these expression has to precede the first constraint mentioned, and has to be separated from it by at least one space.

Rule_8: Contraints can be labeled by preceding them by a name followed by a semi-colon :. Names of constraints have to comply with the same rules as names of variables. If no name is assigned CPLEX will use the names "c1", "c2", and so on.

Rule_9: Constraint are entered in the same way as the objective. In addition this is then followed by the "sense" of the constraint, and the right hand side which consists of a constant only. Accepted constraint senses are:

  <,<=,=<

for 'smaller than or equal to';

  >,>= =>

for 'greater than or equal to'; en

for 'equal to'.

Rule_10: The constraint section mentioned above is mandatory. The following sections appear only if applicable. The first one is declared by the word BOUND or BOUNDS

Rule_11: The standard way of indicating a bound on variables is

  L_i <= X_i <= U_i

with the follwoing exceptions.
Lower and Upper bounds can be entered separately:

  L_i <= X_i  or
  X_i <= U_i

where a default lower bound is 0, and a default upper bound is + infinity.
To FIX a variable a simple eqution suffices: X_3 = 5.6 which is equivalent with 5.6 <= X_3 <= 5.6
Bounds + infinity or - infinity can be entered as "-infinity" and "+infinity", or as "-inf" and "+inf".
A free variable (with lower bound -inf and upper bound + inf) can be entered as "free": X_4 FREE

Rule_12: In an interactive data entering session, input is closed by entering "End". For problems entered from files this is not necessary, although it is wise to do so as well.

Rule_13: Another optionale section that may be entered after the bounds and before the End statement is the "integer" section. It is announced by the word INTEGER, INTEGERS, or INTS, or by the words GENERALS or BINARIES. The following lines should then contain the names of the variables that should attain only integral values. One may mention several variables on a line, as long as they are separated by at least one space. GENERALS refer to integral variables with default bounds 0 and +inf, BINARIES refer to variables that can only take values 0 or 1.

Examples

Here is a small mixed-integer linear programming problem describing a facility-location problem. We give both an MPS and an (equivalent) LP-formulation. Example of a file in LP-format

\Problem name: example.lp

Minimize
 obj: 400 x1 + 500 x2 + 300 x3 + 150 x4 + 20 y11 + 48 y21 + 26 y31 + 24 y41
 + 40 y12 + 15 y22 + 35 y32 + 50 y42 + 50 y13 + 26 y23 + 18 y33 + 35 y43
Subject To
 c1:  y11 + y21 + y31 + y41  = 80
 c2:  y12 + y22 + y32 + y42  = 70
 c3:  y13 + y23 + y33 + y43  = 40
 c4:  - 100 x1 + y11 + y12 + y13 <= 0
 c5:  - 100 x2 + y21 + y22 + y23 <= 0
 c6:  - 100 x3 + y31 + y32 + y33 <= 0
 c7:  - 100 x4 + y41 + y42 + y43 <= 0
Bounds
0 <= y11
0 <= y21
0 <= y31
0 <= y41
0 <= y12
0 <= y22
0 <= y32
0 <= y42
0 <= y13
0 <= y23
0 <= y33
0 <= y43
0 <= x1 <= 1
0 <= x2 <= 1
0 <= x3 <= 1
0 <= x4 <= 1
Integer
 x1  x2  x3  x4 
End

Example of a file in MPS-format, same problem

NAME            example
MINIMIZE
ROWS
 N  obj     
 E  c1      
 E  c2      
 E  c3      
 L  c4      
 L  c5      
 L  c6      
 L  c7      
COLUMNS
    MARK0000  'MARKER'                 'INTORG'
    x1        obj                400   c4                -100
    x2        obj                500   c5                -100
    x3        obj                300   c6                -100
    x4        obj                150   c7                -100
    MARK0001  'MARKER'                 'INTEND'
    y11       obj                 20   c1                   1
    y11       c4                   1
    y21       obj                 48   c1                   1
    y21       c5                   1
    y31       obj                 26   c1                   1
    y31       c6                   1
    y41       obj                 24   c1                   1
    y41       c7                   1
    y12       obj                 40   c2                   1
    y12       c4                   1
    y22       obj                 15   c2                   1
    y22       c5                   1
    y32       obj                 35   c2                   1
    y32       c6                   1
    y42       obj                 50   c2                   1
    y42       c7                   1
    y13       obj                 50   c3                   1
    y13       c4                   1
    y23       obj                 26   c3                   1
    y23       c5                   1
    y33       obj                 18   c3                   1
    y33       c6                   1
    y43       obj                 35   c3                   1
    y43       c7                   1
RHS
    rhs       c1                  80   c2                  70
    rhs       c3                  40
BOUNDS
 UP bnd       x1                   1
 UP bnd       x2                   1
 UP bnd       x3                   1
 UP bnd       x4                   1
ENDATA