[Help-glpk] patch to upgrade glpk 4.5 to 4.6

[Andrew Makhorin]

N.B. THIS IS NOT AN OFFICIAL RELEASE OF GLPK 4.6.

Here is a patch to upgrade glpk 4.5 to 4.6 (please see the attachment).
Its MD5 check-sum must be:

757c51aaf23fb2e32feed95a0a2922f1 *glpk.diff.gz

To upgrade the package do the following:

1. Download glpk-4.5.tar.gz from GNU ftp site or some its mirror.

2. Unzip and untar glpk-4.5.tar.gz in a working subdirectory.

3. Unzip the patch attached and place it in the same working directory,
   i.e. the subdirectory 'glpk-4.5' and the file 'glpk.diff' must be in
   the same subdirectory.

4. Run the command (only once!): patch -p0 < glpk.diff
   There will be some warnings about patching glpkmex files. Never mind
   on them.

5. Rename the subdirectory 'glpk-4.5' to 'glpk-4.6'.

6. Configure and compile/install the package as usual.


What's new in glpk 4.6:
***********************

Two new statements of the GNU MathProg language were implemented:
solve and printf.

The solve statement is optional and can be used only once in the model
description. It has the following syntax:

   solve;

Having been executed the solve statement makes all model variables to
be similar model parameters, i.e. below the solve statement any variable
can be referenced in the same way as a parameter. Note that variable,
constraint, and objective statements can be used only above the solve
statement while set, parameter, display, and printf statements can be
used above as well as below the solve statement.

The printf statement is intended to produce resulting reports. It has
the following syntax:

   printf format-string, expr, expr, ..., expr;

   printf { domain } : format-string, expr, expr, ..., expr;

where format-string is a symbolic literal or expression which specifies
a format control string in the same way as in the C language; expr is a
numeric, symbolic, or logical expression (if printf is used below the
solve statement, the expression may refer to model variables).

Both statements solve and printf are supported by the solver glpsol.
The output may be redirected with '-y' or '--display' option.

Below here is a brief example which illustrates how to use the solve and
printf statements.

Any comments and suggestions are welcome.


Andrew Makhorin


========================================================================
# 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 */

solve;

printf "";
printf "From       To               Cost   Shipping Total cost";
printf "---------- ---------- ---------- ---------- ----------";
printf {i in I, j in J: x[i,j] != 0}:
       "%-10s %-10s %10.3f %10d %10.3f", i, j, c[i,j], x[i,j],
       c[i,j] * x[i,j];
printf "------------------------------------------------------";
printf "                                            %10.3f",
       sum{i in I, j in J} c[i,j] * x[i,j];
printf "";

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;
========================================================================
$ ./glpsol transp.mod
Reading model section from transp.mod...
Reading data section from transp.mod...
76 lines were read
Generating cost...
Generating supply...
Generating demand...
Model has been successfully generated
lpx_simplex: original LP has 6 rows, 6 columns, 18 non-zeros
lpx_simplex: presolved LP has 5 rows, 6 columns, 12 non-zeros
lpx_adv_basis: size of triangular part = 5
      0:   objval =   0.000000000e+00   infeas =   1.000000000e+00 (0)
      4:   objval =   1.563750000e+02   infeas =   0.000000000e+00 (0)
*     4:   objval =   1.563750000e+02   infeas =   0.000000000e+00 (0)
*     5:   objval =   1.536750000e+02   infeas =   0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.2M (174146 bytes)

From       To               Cost   Shipping Total cost
---------- ---------- ---------- ---------- ----------
Seattle    Chicago         0.153        300     45.900
San-Diego  New-York        0.225        325     73.125
San-Diego  Topeka          0.126        275     34.650
------------------------------------------------------
                                               153.675

Model has been successfully processed
========================================================================

glpk.diff.gz
Description: GNU Zip compressed data