news

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

        '--gomory'. For more details please see the reference manual
        included in the distribution.

GLPK 4.24 (release date: Nov 21, 2007)

        A tentative implementation of MIR (mixed integer rounding) cuts
        was included in the MIP solver. To enable generating MIR cuts
        the control parameter mir_cuts passed to the routine glp_intopt
        should be set to GLP_ON. This feature is also available in the
        stand-alone solver glpsol via command-line option '--mir'. For
        more details please see the reference manual included in the
        distribution.

        The implementation is mainly based on the following two papers:

        1. H. Marchand and L. A. Wolsey. Aggregation and mixed integer
           rounding to solve MIPs. CORE discussion paper 9839, CORE,
           Universite catholique de Louvain, June 1998.

        2. G. Andreello, A. Caprara, and M. Fischetti. Embedding cuts
           in a Branch&Cut framework. Preliminary draft, October 2003.

        MIR cuts can be generated on any level of the search tree that
        makes the GLPK MIP solver to be a real branch-and-cut solver.

        A bug was fixed in the routine lpx_write_cpxlp. If a variable
        x has upper bound and no lower bound, it should appear in the
        bounds section as "-inf <= x <= u", not as "x <= u". Thanks to
        Enric Rodriguez <[e-mail]> for the bug report.

GLPK 4.23 (release date: Oct 28, 2007)

        The following new API routines were added:

        glp_read_sol    read basic solution from text file
        glp_write_sol   write basic solution to text file
        glp_read_ipt    read interior-point solution from text file
        glp_write_ipt   write interior-point solution to text file
        glp_read_mip    read MIP solution from text file
        glp_write_mip   write MIP solution to text file

        For description of these routines and corresponding file
        formats see Chapter "API Routines", Section "Utility routines"
        in the reference manual included in the distribution.

        Advanced API routine glp_free_env was added. It may be used by
        the application program to free all resources allocated by GLPK
        routines.

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

        --mipgap tol    set relative MIP gap tolerance
        -r filename     read solution from filename
        -w filename     write solution to filename

GLPK 4.22 (release date: Sep 19, 2007)

        This is a maintainer release.

        A bug was fixed in the MIP preprocessor (ios_preprocess_node).
        Thanks to Roberto Bagnara <[e-mail]> (Department of
        Mathematics, University of Parma, Italy) for the bug report.

        A bug was fixed in the MIP preprocessor (col_implied_bounds),
        due to which constraint coefficients with small magnitude could
        lead to wrong implied bounds of structural variables.

        A similar bug was fixed in the routine reduce_bounds.

        A bug was fixed in the routines glp_set_mat_row and
        glp_set_mat_col. (The bug appeared due to incorrect removing
        zero elements from the row/column lists.)

        A bug was fixed in the API routines lpx_read_mps and
        lpx_read_freemps, due to which bounds of type LI specified in
        BOUNDS section were incorrectly processed.

        A call to standard function vsprintf was replaced by a call to
        vsnprintf for security reasons. Many thanks to Peter T. Breuer
        <[e-mail]> and Rafael Laboissiere <[e-mail]>.

GLPK 4.21 (release date: Aug 28, 2007)

        Additional reasons for calling the callback routine used in the
        MIP solver (glp_intopt) were introduced. Currently the following
        reasons are supported:

        * request for subproblem selection
        * request for preprocessing
        * request for row generation
        * request for heuristic solution
        * request for cut generation
        * request for branching
        * better integer solution found

        A basic preprocessing component used to improve subproblem
        formulations by tightening bounds of variables was included in
        the MIP solver. Depending on the control parameter pp_tech
        passed to the routine glp_intopt the preprocessing can be
        performed either on the root level or on all levels (default)
        or can be disabled.

        Backtracking heuristic used by default in the MIP solver was
        changed to the "best local bound".

        For more details see Chapter "Advanced API routines", Section
        "Branch-and-bound interface routines" in a new edition of the
        reference manual included in the distribution.

GLPK 4.20 (release date: Jul 26, 2007)

        API routine lpx_integer was replaced by API routine glp_intopt,
        which provides equivalent functionality and additionally allows
        the application to control the solution process by means of the
        user-written callback routine, which is called by the solver at
        various points of the branch-and-bound algorithm. Besides, the
        new MIP solver allows generating "lazy" constraints and cutting
        planes on all levels of the branch-and-bound tree, not only on
        the root level. The routine lpx_integer is also still available
        for the backward compatibility.

        The following new advanced API routines, which may be called
        from the B&B callback routine, were included in the package:

        glp_ios_reason     determine reason for calling callback
                           routine
        glp_ios_get_prob   access the problem object
        glp_ios_tree_size  determine size of the branch-and-bound tree
        glp_ios_curr_node  determine current active subproblem
        glp_ios_next_node  determine next active subproblem
        glp_ios_prev_node  determine previous active subproblem
        glp_ios_up_node    determine parent subproblem
        glp_ios_node_level determine subproblem level
        glp_ios_node_bound determine subproblem local bound
        glp_ios_mip_gap    compute relative MIP gap
        glp_ios_heur_sol   provide solution found by heuristic
        glp_ios_terminate  terminate the solution process

        For description of these routines see Chapter "Advanced API
        routines", Section "Branch-and-bound interface routines" in a
        new edition of the reference manual, which was included in the
        distribution.

        Old version of the integer optimization suite (IOS) as well as
        TSP solver tspsol based on it are no longer supported and were
        removed from the package.

        A minor error in the MIP presolver was fixed; thanks to Graham
        Rockwell <[e-mail]> for the bug report.

GLPK 4.19 (release date: Jul 05, 2007)

        The principal change is upgrading to GPLv3.

        A serious bug in the routine glp_del_cols was fixed; thanks to
        Cedric[FR] <[e-mail]> for the bug report. The bug
        appeared because on deleting non-basic columns the basis header
        remained valid, however, contained invalid (old) column ordinal
        numbers.

        A new advanced API routine glp_mem_limit was added.

        The case GLP_EBOUND was added to the routine lpx_simplex.
        Thanks to Cameron Kellough <[e-mail]> for the
        bug report.

        An API routine lpx_write_pb to write the problem instance in
        OPB (pseudo boolean) format format was added. Thanks to Oscar
        Gustafsson <[e-mail]> for the contribution.

        Two new options --wpb and --wnpb were added to glpsol to write
        the problem instance in OPB format.

GLPK 4.18 (release date: Jun 25, 2007)

        The following new API routines were added:

        glp_set_rii        set (change) row scale factor
        glp_set_sjj        set (change) column scale factor
        glp_get_rii        retrieve row scale factor
        glp_get_sjj        retrieve column scale factor
        glp_simplex        solve LP problem with the simplex method
                           (this routine replaces lpx_simplex, which is
                           also available for backward compatibility)
        glp_init_smcp      initialize simplex method control params
        glp_bf_exists      check if the basis factorization exists
        glp_factorize      compute the basis factorization
        glp_bf_updated     check if the basis factorization has been
                           updated
        glp_get_bfcp       retrieve basis factorization control params
        glp_set_bfcp       change basis factorization control params
        glp_get_bhead      retrieve the basis header information
        glp_get_row_bind   retrieve row index in the basis header
        glp_get_col_bind   retrieve column index in the basis header
        glp_ftran          perform forward transformation
        glp_btran          perform backward transformation

        For description of all these routines see a new edition of the
        reference manual included in the distribution.

        Type names ulong_t and uldiv_t were changed to glp_ulong and
        glp_uldiv to avoid conflicts with standard type names on some
        platforms. Thanks to Boris Wirtz <[e-mail]>
        for the bug report.

        Some new examples in the MathProg language were added. Thanks
        to Sebastian Nowozin <[e-mail]>.

GLPK 4.17 (release date: May 26, 2007)

        API routines glp_set_mat_row, glp_set_mat_col, and glp_load_mat
        were modified to allow zero constraint coefficients (which are
        not stored in the constraint matrix). Note that constraint
        coefficients with duplicate row/column indices are not allowed.

        Another form of LP basis factorization was implemented in the
        package. It is based on LU-factorization of an initial basis
        and Schur complement to reflect changes in the basis. Currently
        the implementation is incomplete and provides only updating the
        factorization on replacing a column of the basis matrix. On API
        level the user can set the control parameter LPX_K_BFTYPE to
        choose between the folloiwng forms of LP basis factorization to
        be used in the simplex method routines:
        1) LU + Forrest-Tomlin update;
        2) LU + Schur complement + Bartels-Golub update;
        3) LU + Schur complement + Givens rotation update.
        The GLPK implementation is similar to LUSOL/LUMOD developed by
        Michael A. Saunders.

        The user can choose the form of LP basis factorzation used by
        the simplex method routines by specifying the folloiwng options
        of glpsol: --luf, --cbg, --cgr.

GLPK 4.16 (release date: May 05, 2007)

        A number of basic GLPK API routines, which now are in the
        stable stable, were renamed to be prefixed with 'glp_'. Note
        that all these routines are available via their old names
        prefixed with 'lpx_' that keeps the downward compatibility with
        older versions of the package.

        Three new GLPK API routines were added to the package:
        glp_version, glp_term_hook, and glp_mem_usage; for more details
        see a new edition of the GLPK reference manual included in the
        distribution. The routine glp_version reports the actual version
        of the GLPK library and also can be used (along with the header
        glpk.h) in Autotools specification files to check if the GLPK
        library has been installed.

        The header glpk.h was changed to conform to C++ environment.

GLPK 4.15 (release date: Feb 18, 2007)

        Autotools specification files (configure.ac, Makefile.am) were
        changed to use GNU Libtool. This allows building the static as
        well as shared GLPK library.

GLPK 4.14 (release date: Feb 05, 2007)

        Now GLPK conforms to ILP32, LLP64, and LP64 programming models
        (the latter seems to be the ultimate choice regarding 64-bit
        architectures). Note that GLPK itself is a 32-bit application,
        and the conformity only means that the package works correctly
        on all these arenae. Nevertheless, on 64-bit platforms it is
        possible to use more than 4GB of memory, if necessary.

GLPK 4.13 (release date: Nov 13, 2006)

        A tentative implementation of the "exact" simplex method based
        on bignum (rational) arithmetic was included in the package.

        On API level this new feature is available through the routine
        lpx_exact, which is similar to the routine lpx_simplex.

        In the solver glpsol this feature is available through two new
        command-line options: --exact and --xcheck. If the '--exact'
        option is specified, glpsol solves LP instance using the exact
        simplex method; in case of MIP it is used to obtain optimal
        solution of LP relaxation. If the --xcheck option is specified,
        LP instance (or LP relaxation) is solved using the standard
        (floating-point) simplex method, however, then glpsol calls the
        exact simplex routine to make sure that the final LP basis is
        exactly optimal, and if it is not, to perform some additional
        simplex iterations in exact arithmetic.

GLPK 4.12 (release date: Nov 08, 2006)

        A tentative implementation of some simplex method routines
        based on exact (bignum) arithmetic was included in the package.
        Currently these routines provide computing LU-factorization of
        the basis matrix and computing components of basic solution.

        These routines were used to implement a routine, which checks
        primal and dual feasibility of basic solution exactly, i.e. in
        rational numbers, without round-off errors. In glpsol this
        feature is available through the command-line option --xcheck.

        GLPK has its own low-level routines implementing operations on
        integer and rational numbers that makes it independent on other
        software packages. However, to attain a much better performance
        it is highly recommended to install (before configuring GLPK)
        the GNU Multiple Precision Arithmetic Library (GMP). Using GMP
        makes computations 100-200 times faster.

GLPK 4.11 (release date: Jul 25, 2006)

        Three new built-in functions in the modeling language were
        implemented: card (cardinality of set), length (length of
        character string), and substr (substring of character string).
        Another improvement concerns the printf statement which now
        allows redirecting its output to a specified file. These new
        features are illustrated in example models crypto.mod and
        graph.mod included in the distribution. For more details see
        the document "Modeling Language GNU MathProg".

        Four batch files (along with corresponding makefiles) were
        included in the distribution to simplify building GLPK under
        MS Windows; see them in subdirectory 'w32'.