[Help-glpk] proposal for gnu lp/mip low-level format

[Andrew Makhorin]

I propose a (GNU) low-level format for coding lp/mip instances. Below
here is its brief description. I would appreciate any suggestions.

Andrew Makhorin


It is a text format. The file may contain the following lines:

* comment

N problem-name

P problem-class objective-sense num-rows num-cols num-nz

R row-num F
R row-num L lower-bound
R row-num U upper-bound
R row-num D lower-bound upper-bound
R row-num S fixed-value

C col-num F
C col-num L lower-bound
C col-num U upper-bound
C col-num D lower-bound upper-bound
C col-num S fixed-value

F col-num objective_coef
F 0 constant-term

A row-num col-num constraint-coefficient

I row-num row-name

J col-num col-name

E O F

All lines, except P-line and E-line, are optional and may follow in
arbitrary order.


Example
=======

The model transp.mod from the glpk reference manual:

------------------------------------------------------------------------
# A TRANSPORTATION PROBLEM
#
# This problem finds a least cost shipping schedule that meets
# requirements at markets and supplies at factories.
#
#  References:
#              Dantzig G B, "Linear Programming and Extensions."
#              Princeton University Press, Princeton, New Jersey, 1963,
#              Chapter 3-3.

set I;
/* canning plants */

set J;
/* markets */

param a{i in I};
/* capacity of plant i in cases */

param b{j in J};
/* demand at market j in cases */

param d{i in I, j in J};
/* distance in thousands of miles */

param f;
/* freight in dollars per case per thousand miles */

param c{i in I, j in J} := f * d[i,j] / 1000;
/* transport cost in thousands of dollars per case */

var x{i in I, j in J} >= 0;
/* shipment quantities in cases */

minimize cost: sum{i in I, j in J} c[i,j] * x[i,j];
/* total transportation costs in thousands of dollars */

s.t. supply{i in I}: sum{j in J} x[i,j] <= a[i];
/* observe supply limit at plant i */

s.t. demand{j in J}: sum{i in I} x[i,j] >= b[j];
/* satisfy demand at market j */

data;

set I := Seattle San-Diego;

set J := New-York Chicago Topeka;

param a := Seattle     350
           San-Diego   600;

param b := New-York    325
           Chicago     300
           Topeka      275;

param d :              New-York   Chicago   Topeka :=
           Seattle     2.5        1.7       1.8
           San-Diego   2.5        1.8       1.4  ;

param f := 90;

end;
------------------------------------------------------------------------

The same model in the proposed format:

------------------------------------------------------------------------
N transp
P LP MIN 6 6 18
R 1 F
R 2 U 350
R 3 U 600
R 4 L 325
R 5 L 300
R 6 L 275
C 1 L 0
C 2 L 0
C 3 L 0
C 4 L 0
C 5 L 0
C 6 L 0
F 1 0.225
F 2 0.153
F 3 0.162
F 4 0.225
F 5 0.162
F 6 0.126
A 1 1 0.225
A 1 2 0.153
A 1 3 0.162
A 1 4 0.225
A 1 5 0.162
A 1 6 0.126
A 2 3 1
A 2 2 1
A 2 1 1
A 3 6 1
A 3 5 1
A 3 4 1
A 4 4 1
A 4 1 1
A 5 5 1
A 5 2 1
A 6 6 1
A 6 3 1
I 1 cost
I 2 supply[Seattle]
I 3 supply[San-Diego]
I 4 demand[New-York]
I 5 demand[Chicago]
I 6 demand[Topeka]
J 1 x[Seattle,New-York]
J 2 x[Seattle,Chicago]
J 3 x[Seattle,Topeka]
J 4 x[San-Diego,New-York]
J 5 x[San-Diego,Chicago]
J 6 x[San-Diego,Topeka]
E O F
------------------------------------------------------------------------