news

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

GLPK 4.10 (release date: May 11, 2006)

        Cutting planes of two new classes were implemented: mixed cover
        cuts and clique cuts. On API level this feature can be enabled
        by setting control parameter LPX_K_USECUTS passed to the routine
        lpx_intopt. In glpsol this feature is available through the
        command-line options --cover and --clique. For more details see
        the reference manual.

        Now the routines lpx_read_mps and lpx_read_freemps support LI
        bound type. It is similar to LO, however, indicates the column
        as of integer kind.

GLPK 4.9 (release date: Jan 17, 2006)

        An advanced MIP solver was implemented. It includes:

        - basic presolving technique (removing free, singleton and
          redundant rows, improving bounds of columns, removing fixed
          columns, reducing constraint coefficents);

        - generating cutting planes to improve LP relaxation (currently
          only Gomory's mixed integer cuts are implemented);

        - using the branch-and-bound method to solve resultant MIP;

        - recovering solution of the original MIP.

        The solver is available on API level via the routine lpx_intopt
        (see the reference manual). It is similar to the routine
        lpx_integer, however, does not require initial solution of LP
        relaxation.

        The solver is also available in the command-line utility glpsol
        via two options: --intopt (only presolving) and --cuts (assumes
        --intopt plus generating cuts).

        Note that efficiency of the MIP solver strongly depends on the
        internal structure of the problem to be solved. For some hard
        instances it is very efficient, but for other instances it may
        be significantly worse than the standard branch-and-bound.

        For some comparative benchmarks see doc/bench1.txt.

        Well, what else...

        Three built-in functions were added to MathProg: sin, cos, and
        atan (the latter allows one or two arguments).

        Some bugs were fixed.

        Several new examples in MathProg were included: color.mod
        (graph coloring problem), tsp.mod (traveling salesman problem),
        and pbn.mod (paint-by-numbers puzzle).

GLPK 4.8 (release date: Jan 12, 2005)

        Core simplex method and interior-point method routines were
        re-implemented and now they use a new, "storage-by-rows" sparse
        matrix format (unlike previous versions where linked lists were
        used to represent sparse matrices). For details see ChangeLog.

        Also a minor bug was fixed in API routine lpx_read_cpxlp.

GLPK 4.7 (release date: Aug 23, 2004)

        Now GLPK supports free MPS format. Two new API routines
        lpx_read_freemps (to read problem data in free MPS format) and
        lpx_write_freemps (to write problem data in free MPS format)
        were added. This feature is also available in the solver glpsol
        via new command-line options --freemps and --wfreemps. For more
        details see the GLPK reference manual.

        API routines lpx_read_cpxlp and lpx_write_cpxlp for reading and
        writing problem data in CPLEX LP format were re-implemented to
        allow long symbolic names (up to 255 characters).

        The following three modules were temporarily removed from the
        GLPK distribution due to licensing problems: DELI (an interface
        module to Delphi), GLPKMEX (an interface module to Matlab), and
        JNI (an interface module to Java).

GLPK 4.6 (release date: Aug 04, 2004)

        Three new statements were implemented in the GNU MathProg
        language: solve, printf, and for. Their detailed description can
        be found in the GLPK documentation included in the distribution.
        (See also a sample model, examples/queens.mod, which illustrates
        using these new statements.)

        Two new API routines were added to the package: lpx_read_prob
        and lpx_write_prob. They allow reading/writing problem data in
        GNU LP low-level text format.

        Three new command-line options were implemented in the LP/MIP
        solver glpsol: --glp (to read problem data in GNU LP format),
        --wglp (to write problem data in GNU LP format), and --name (to
        change problem name). Now glpsol also supports processing models
        where the new statements (see above) are used.

        A new version of GLPKMEX, a Matlab MEX interface to GLPK, was
        included. For more details see contrib/glpkmex/ChangeLog.

GLPK 4.5 (release date: Jul 19, 2004)

        The branch-and-bound solver was completely re-implemented.

        Some modifications were made in memory allocation routines that
        allows using the package on 64-bit platforms.

        For more details see ChangeLog.

GLPK 4.4 (release date: Jan 17, 2004)

        All API routines were re-implemented using new data structures.
        The new implementation provides the same specifications and
        functionality of API routines as the old one, however, it has
        some important advantages, in particular:
        * linked lists are used everywhere that allows creating and
          modifying the problem object as efficiently as possible
        * all data stored in the problem object are non-scaled (even if
          the internal scaling is used) that prevents distortion of the
          original problem data
        * solution components obtained by the solver remain available
          even if the problem object has been modified
        * no solver-specific data are used in the new data structures
          that allows attaching any external lp/mip solver using GLPK
          API as an uniform interface
        Note that some API routines became obsolete being replaced by
        new, more convenient routines. These obsolete routines are kept
        for backward compatibility, however, they will be removed in
        the future. For more details please see ChangeLog and the GLPK
        Reference Manual.

        New edition of the GLPK Reference Manual was included in the
        distribution.

        GLPKMEX, a Matlab MEX interface to GLPK package, contributed by
        Nicolo Giorgetti <[e-mail]> was included in the
        distribution.

        GLPK FAQ contributed by Harley Mackenzie <[e-mail]> was
        included in the distribution.

GLPK 4.3 (release date: Dec 12, 2003)

        The bug, due to which the standard math library is not linked
        on building the package on some platforms, was fixed.

        The following new built-in functions were added to the MathProg
        language: round, trunc, Irand224, Uniform01, Uniform, Normal01,
        Normal. For details see the language description.

        The MathProg syntax was changed to allow writing 'subj to' that
        means 'subject to'.

        The new api routine lpx_get_ray_info was added. It is intended
        to determine which (non-basic) variable causes unboundness. For
        details see the reference manual.

        The module glpmps.c was changed to avoid compilation errors on
        building the package on Mac OS X.

        Several typos was fixed and some new material was added to the
        GLPK documentation.

GLPK 4.2 (release date: Nov 14, 2003)

        A preliminary implementation of the Integer Optimization Suite
        (IOS) was included in the package. The Branch-and-Cut Framework
        being completely superseded by IOS was removed from the package.

        New API routine lpx_print_sens_bnds intended for bounds
        sensitivity analysis was contributed to GLPK by Brady Hunsaker
        <[e-mail]>. This function is also available in
        the solver glpsol (via command-line option --bounds).

        An improved version of GLPK JNI (Java Native Interface) was
        contributed by Chris Rosebrugh <[e-mail]>.

        GLPK DELI (Delphi Interface) was contributed by Ivo van Baren
        <[e-mail]>.

        Several makefiles were added to allow compiling GLPK on some
        non-GNU 32-bit platforms:
        * Windows single-threaded static library, Visual C++ 6.0
        * Windows multi-threaded dynamic library, Visual C++ 6.0
        * Windows single-threaded static library, Borland C++ 5.2
        * DOS single-threaded static library, Digital Mars C++ 7.50

        And, of course, some bugs were fixed.

        For more details see ChangeLog.

GLPK 4.1 (release date: Aug 23, 2003)

        Some improvements were made in the lp/mip solver routines and
        several bugs were fixed in the model translator.

        For more details see ChangeLog.

GLPK 4.0 (release date: May 06, 2003)

        Now GLPK supports the GNU MathProg modeling language, which is
        a subset of the AMPL modeling language.

        The document "GLPK: Modeling Language GNU MathProg" included in
        the distribution is a complete description of GNU MathProg. (See
        the files lang.latex, lang.dvi, and lang.ps in the subdirectory
        'doc'. See also some examples in the subdirectory 'sample'.)

        New version of the solver glpsol, which supports models written
        in GNU MathProg, was implemented. (Brief instructions how to use
        glpsol can be found in the GNU MathProg documentation.)

        The GLPK/L modeling language is no more supported. The reason is
        that GNU MathProg being much more powerful completely supersedes
        all features of GLPK/L.

GLPK 3.3 (release date: Mar 25, 2003)

        LP PRESOLVER
        ------------

        Now the routine lpx_simplex (which is a driver to the simplex
        method for solving LP) is provided with the built-in LP
        presolver, which is a program that transforms the original LP
        problem to an equivalent LP problem, which may be easier for
        solving with the simplex method than the original one. Once the
        transformed LP has been solver, the presolver transforms its
        basic solution back to a corresponding basic solution of the
        original problem. For details about this feature please see the
        GLPK reference manual.

        Currently the LP presolver implements the following features:
        * removing empty rows;
        * removing empty columns;
        * removing free rows;
        * removing fixed columns;
        * removing row singletons, which have the form of equations;
        * removing row singletons, which have the form of inequalities;
        * removing column singletons, which are implied slack variables;
        * fixing and removing column singletons, which are implied free
          variables;
        * removing forcing rows that involves fixing and removing the
          corresponding columns;
        * checking for primal and dual infeasibilities.

        The LP presolver is also used by default in the stand-alone
        program glpsol. In order *not* to use it, the option --nopresol
        should be specified in the command-line.

        CHANGES IN GLPK/L
        -----------------

        The syntax and semantics of the GLPK/L modeling language was
        changed to allow declaration of "interval" sets. This means that
        now the user can declare a set, for example, as:

           set task = [8:11];

        that is exactly equivalent to the following declaration:

           set task = (task_8, task_9, task_10, task_11);

        For details see the language description.

        JAVA INTERFACE
        --------------

        Now GLPK includes the package GLPK JNI (Java Native Interface)
        that implements Java binding for GLPK. It allows Java programs
        to utilize GLPK in solving LP and MIP problems. For details see
        a brief user's guide in the subdirectory contrib/java-binding.
        This package was developed and programmed by Yuri Victorovich
        <[e-mail]>, who contributed it to GLPK.

GLPK 3.2.4 (release date: Feb 18, 2003)

        This is a bug-fix release. For details see ChangeLog.

GLPK 3.2.3 (release date: Nov 11, 2002)

        A new implementation of the api routine lpx_integer which now
        is based on the b&b driver (which is based on the implicit
        enumeration suite) was included in the package. This new
        implementation has exactly the same functionality as the old
        version, so all changes are transparent to the api user.

        Four new api routines were included in the package:
        lpx_check_kkt checks Karush-Kuhn-Tucker optmality conditions;
        lpx_read_bas reads predifined basis in MPS format;
        lpx_write_bas writes current basis in MPS format;
        lpx_write_lpt writes problem data in CPLEX LP format.

        Also other minor improvements were made (for details see the
        file 'ChangeLog').

GLPK 3.2.2 (release date: Oct 14, 2002)

        The api routine lpx_read_lpt was included in the package. It
        is similar to the routine lpx_read_mps and intended to read
        LP/MIP data prepared in CPLEX LP format. Description of this
        format is given in the GLPK reference manual, a new edition of
        which was also included in the distribution (see the files
        'refman.latex', 'refman.dvi', 'refman.ps' in the subdirectory
        'doc'). In order to use data files in CPLEX LP format with the
        solver glpsol the option '--lpt' should be specified in the
        command line.

        Several bugs were fixed and some minor improvements were made
        (for details see the file 'ChangeLog').

GLPK 3.2.1 (release date: Aug 12, 2002)

        Now GLPK includes a preliminary implementation of the
        branch-and-cut framework, which is a set of data structures and
        routines intended for developing branch-and-cut methods for