Sebastian Pokutta's Blog

Mathematics and related topics

GLPK 4.36 released / Updated GUSEK version

with 5 comments

A new version of the GNU linear programming kit (GLPK) (one of my favorite solvers) has been released today. While not being CPLEX it is probably one of the best freely available solvers out there and it comes with its own modeling language GMPL which is very similar to AMPL. GLPK comes with an interesting feature: It has an exact simplex algorithm. The new version includes new API functions for networks and flows and can read flow data in DIMACS format:

In this release:

The following new API routines were added to the package:

glp_mincost_okalg     find minimum-cost flow with out-of-kilter
algorithm

glp_maxflow_ffalg     find maximal flow with Ford-Fulkerson
algorithm

For detailed description of these new routines and related data
structures see chapter “Graph and Network API Routines” in the
reference manual included in the distribution.

The following new command-line options were added to the solver
glpsol:

–mincost             read min-cost flow data in DIMACS format
–maxflow             read maximum flow data in DIMACS format

Also GUSEK, a freely available GLPK IDE for Windows has been updated as well to include the new GLPK 4.36 version. GUSEK is pretty decent and if you are using Windows and you want to use GLPK you should definitely give it a closer look. Unfortunately, it is available for Windows only – maybe there will be a version for Macs or Linux soon? As GUSEK is based on open source it might be rather easy to do I suppose? There is also an IEOR Tools interview available with Luiz Bettoni, the developer of GUSEK.

UPDATE (17.02.2009): Great tutorials on how to use GLPK are available as well!

GLPK benchmarks for NETGEN instances:

Below here are benchmarks for 50 original NETGEN instances of min-cost
flow problem obtained with the glpk primal simplex.

Solver:   GLPSOL 4.36 (options used: --mincost --nopresol)
Computer: Intel Pentium 4, 3.0 GHz
Platform: Cygwin/Windows XP
Compiler: GCC 3.4.4 (options used: -O3)
Test set: 50 original NETGEN instances of min-cost flow problem
         (generated by glpk/examples/netgen.c)

Problem    Nodes   Arcs       Optimum        Iters  Time,s
--------  ------  ------  ----------------  ------  ------
netgn101    5000   25336  +6.191726000e+06   17222      41
netgn102    5000   25387  +7.233714400e+07   28528      71
netgn103    5000   25355  +2.189475530e+08   35530      91
netgn104    5000   25344  -1.910037100e+07   16962      41
netgn105    5000   25332  +3.119257800e+07   17112      42
netgn106    5000   12870  +4.314276000e+06   11813      17
netgn107    5000   37832  +7.393769000e+06   20941      69
netgn108    5000   50309  +8.405738000e+06   24587     104
netgn109    5000   75299  +9.190300000e+06   30547     188
netgn110    5000   12825  +8.975048000e+06   12012      18
netgn111    5000   37828  +4.747532000e+06   19920      65
netgn112    5000   50325  +4.012671000e+06   22034      92
netgn113    5000   75318  +2.979725000e+06   24210     147
netgn114    5000   26514  +5.821181000e+06   13548      27
netgn115    5000   25962  +6.353310000e+06   15917      35
netgn116    5000   25304  +5.915426000e+06   13874      34
netgn117    5000   12816  +4.420560000e+06    9225      14
netgn118    5000   37797  +7.045842000e+06   16456      55
netgn119    5000   50301  +7.724179000e+06   18006      77
netgn120    5000   75330  +8.455200000e+06   20607     127
netgn121    5000   25000  +6.636636000e+07   25563      56
netgn122    5000   25000  +3.099752900e+07   23774      52
netgn123    5000   25000  +2.338877700e+07   24382      56
netgn124    5000   25000  +1.780344300e+07   24357      60
netgn125    5000   25000  +1.411962200e+07   24245      62
netgn126    5000   12500  +1.880221800e+07   13808      21
netgn127    5000   37500  +2.767464700e+07   32483     103
netgn128    5000   50000  +3.090619400e+07   40121     164
netgn129    5000   75000  +4.090520900e+07   51742     322
netgn130    5000   12500  +3.893960800e+07   15259      23
netgn131    5000   37500  +1.675297800e+07   28777      86
netgn132    5000   50000  +1.330295100e+07   31967     117
netgn133    5000   75000  +9.830268000e+06   35709     178
netgn134    1000   25000  +3.804874000e+06    7426      12
netgn135    2500   25000  +1.172961600e+07   15506      29
netgn136    7500   25000  +3.331810100e+07   29578      82
netgn137   10000   25000  +4.642603000e+07   31433     104
netgn138    5000   25000  +6.071087900e+07   46106     134
netgn139    5000   25000  +3.272968200e+07   34657      93
netgn140    5000   25000  +2.718383100e+07   28635      71
netgn141    5000   25000  +1.996328600e+07   20610      43
netgn142    5000   25000  +2.024345700e+07   17830      36
netgn143    5000   25000  +1.858677700e+07   13875      25
netgn144    5000   25000  +2.504591000e+06   24581      56
netgn145    5000   25000  +2.159561380e+08   24018      55
netgn146    5000   25000  +2.253113811e+09   24680      57
netgn147    5000   25000  -4.279083730e+08   47990     144
netgn148    5000   25000  -9.296531800e+07   37528     105
netgn149    5000   25000  +8.605122400e+07   24057      54
netgn150    5000   25000  +6.193149190e+08   23429      52

Written by Sebastian

February 6, 2009 at 8:27 pm

Posted in Software

Tagged with ,

5 Responses

Subscribe to comments with RSS.

  1. I talked to Luiz about the portability of GUSEK to Linux. His reply is that GUSEK is based on the SciTE IDE. SciTE has an common GUI toolkit, GTK i believe, that should be able to work on a Linux environment. What would need to be done is install SciTE and setup the GUSEK specific API with the Linux installation.

    I didn’t ask but I bet you could also run GUSEK on Wine.

    Larry (IEOR Tools)

    February 9, 2009 at 10:16 pm

  2. Hi Sebastian,
    do you know how to connect Data to an Oracle database using Gusek (gmpl). I didn’t find good informations how to do. Maybe you know a good website/documentation/tutorial/others.
    Thank you
    with kind regards
    Thomas

    Thomas

    July 15, 2009 at 8:54 am

    • Hi Thomas,

      that is possible indeed. The glpk distribution comes with a separate manual (“tables.pdf”) for using tables in gmpl which allow for accessing databases of various types. From the manual:

      The table driver is a program module which provides transmitting data
      between MathProg model objects and data tables.
      Currently the GLPK package has four table drivers:
      • built-in CSV table driver;
      • built-in xBASE table driver;
      • ODBC table driver;
      • MySQL table driver.

      So the ODBC driver for Oracle should do the job in your case.

      Sebastian

      July 15, 2009 at 7:44 pm

      • Thank you Sebastian, i found the file, but first i dont’t get the connection. Later i saw a better description in the AMPL book and it runs like that.
        So it’s important to do it like in the little following Example for GUSEK Interface and only the .mod file:
        —————————————-
        ### SETS ###
        set TYP;
        ### PARAMETERS ###
        ### VARIABLES ###
        ### OBJECTIVE ###
        ### CONSTRAINTS ###

        table TEST IN “ODBC”
        “DSN=dsnname;UID=uidname;PWD=password”
        “SELECT * FROM TEST”: TYP <- [ID];

        solve;
        display TYP;

        —————————————-
        if you run the example the output on the leftside in GUSEK is similar like in the following
        —————————————-
        GLPSOL: GLPK LP/MIP Solver 4.38
        Reading model section from TEST.mod
        Reading TEST…
        Connected to Oracle 10.02.0010 –
        SELECT * FROM TEST
        Model has been successfully generated
        Display statement at line 48
        TYP:
        1
        2
        3
        —————————————-

        so my tablename is TEST and the table has only one column "ID" and its a primary key. the primary stand in brackets [ID] others are added only with comma (TYP <- [ID],X,Y;). So in the disply after processing you can see, that i've only three rows in my TEST table with the id's "1,2,3"

        Thank you very much….
        mybe this helps others.

        Thomas

        July 20, 2009 at 12:52 pm

      • Hi Thomas,

        thanks for the detailed post!!!!

        All the best,
        Sebastian

        Sebastian

        July 20, 2009 at 7:40 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: