alpar@1: GLPK 4.45 (release date: Dec 05, 2010) alpar@1: alpar@1: This is a bug-fix release. alpar@1: alpar@1: Several bugs/typos were fixed. Thanks to alpar@1: Xypron , alpar@1: Robbie Morrison , and alpar@1: Ali Baharev for reports. alpar@1: alpar@1: Some glpk documents was re-formatted and merged into a single alpar@1: document. Now the glpk documentation consists of the following alpar@1: three main documents (all included in the distribution): alpar@1: alpar@1: GLPK: Reference Manual alpar@1: alpar@1: GLPK: Graph and Network Routines alpar@1: alpar@1: Modeling Language GNU MathProg: Language Reference alpar@1: alpar@1: GLPK 4.44 (release date: Jun 03, 2010) alpar@1: alpar@1: The following suffixes for variables and constraints were alpar@1: implemented in the MathProg language: alpar@1: alpar@1: .lb (lower bound), alpar@1: .ub (upper bound), alpar@1: .status (status in the solution), alpar@1: .val (primal value), and alpar@1: .dual (dual value). alpar@1: alpar@1: Thanks to Xypron for draft implementation alpar@1: and testing. alpar@1: alpar@1: Now the MathProg language allows comment records (marked by alpar@1: '#' in the very first position) in CSV data files read with the alpar@1: table statements. Note that the comment records may appear only alpar@1: in the beginning of a CSV data file. alpar@1: alpar@1: The API routine glp_cpp to solve the Critical Path Problem was alpar@1: added and documented. alpar@1: alpar@1: GLPK 4.43 (release date: Feb 20, 2010) alpar@1: alpar@1: This is a maintainer release. alpar@1: alpar@1: `configure.ac' was changed to allow building the package under alpar@1: Mac OS and Darwin with ODBC support. alpar@1: Thanks to Xypron for suggestions and Noli alpar@1: Sicad for testing. alpar@1: alpar@1: The SQL table driver was improved to process NULL data. Thanks alpar@1: to Xypron . alpar@1: alpar@1: Some bugs were fixed in the LP/MIP preprocessor. alpar@1: alpar@1: GLPK 4.42 (release date: Jan 13, 2010) alpar@1: alpar@1: The following new API routines were added: alpar@1: alpar@1: glp_check_dup check for duplicate elements in sparse alpar@1: matrix alpar@1: glp_sort_matrix sort elements of the constraint matrix alpar@1: glp_read_prob read problem data in GLPK format alpar@1: glp_write_prob write problem data in GLPK format alpar@1: glp_analyze_bound analyze active bound of non-basic variable alpar@1: glp_analyze_coef analyze objective coefficient at basic alpar@1: variable alpar@1: glp_print_ranges print sensitivity analysis report (this alpar@1: routine replaces lpx_print_sens_bnds and alpar@1: makes it deprecated) alpar@1: alpar@1: For description of these new routines and the GLPK LP/MIP alpar@1: format see a new edition of the reference manual included in alpar@1: the distribution. (Chapter "Graph and network API routines" was alpar@1: carried out from the main reference manual and included in the alpar@1: distribution as a separate document.) alpar@1: alpar@1: The following new command-line options were added to the stand- alpar@1: alone solver glpsol: alpar@1: --glp filename read problem data in GLPK format alpar@1: --wglp filename write problem data in GLPK format alpar@1: --ranges filename print sensitivity analysis report (this alpar@1: option replaces --bounds) alpar@1: alpar@1: Now all GLPK routines performing file I/O support special alpar@1: filenames "/dev/stdin", "/dev/stdout", and "/dev/stderr", which alpar@1: can be specified in the same way as regular filenames. This alpar@1: feature is plaform-independent. alpar@1: alpar@1: GLPK 4.41 (release date: Dec 21, 2009) alpar@1: alpar@1: The following new API routies were added: alpar@1: alpar@1: glp_transform_row transform explicitly specified row alpar@1: glp_transform_col transform explicitly specified column alpar@1: glp_prim_rtest perform primal ratio test alpar@1: glp_dual_rtest perform dual ratio test alpar@1: alpar@1: For description of these new routines see a new edition of the alpar@1: reference manual included in the distribution. alpar@1: alpar@1: The following API routines are deprecated: lpx_transform_row, alpar@1: lpx_transform_col, lpx_prim_ratio_test, lpx_dual_ratio_test. alpar@1: alpar@1: Some improvements were made in the MIP solver (glp_intopt). alpar@1: alpar@1: The SQL table driver used to read/write data in MathProg models alpar@1: was changed to allow multiple arguments separated by semicolon alpar@1: in SQL statements. Thanks to Xypron . alpar@1: alpar@1: Two new options were added to the glpsol stand-alone solver: alpar@1: --seed value (to initialize the pseudo-random number generator alpar@1: used in MathProg models with specified value), and alpar@1: --ini filename (to use a basis previously saved with -w option alpar@1: as an initial basis on solving similar LP's). alpar@1: alpar@1: Two new MathProg example models were included. Thanks to alpar@1: Nigel Galloway and Noli Sicad alpar@1: for contribution. alpar@1: alpar@1: Scripts to build GLPK with Microsoft Visual Studio 2010 for alpar@1: both 32-bit and 64-bit Windows were included. Thanks to Xypron alpar@1: for contribution and testing. alpar@1: alpar@1: GLPK 4.40 (release date: Nov 03, 2009) alpar@1: alpar@1: The following new API routines were added: alpar@1: alpar@1: glp_del_vertices remove vertices from graph alpar@1: glp_del_arc remove arc from graph alpar@1: glp_wclique_exact find maximum weight clique with the exact alpar@1: algorithm developed by Prof. P. Ostergard alpar@1: glp_read_ccdata read graph in DIMACS clique/coloring alpar@1: format alpar@1: glp_write_ccdata write graph in DIMACS clique/coloring alpar@1: format alpar@1: alpar@1: For description of these new routines see a new edition of the alpar@1: reference manual included in the distribution. alpar@1: alpar@1: The hybrid pseudocost branching heuristic was included in the alpar@1: MIP solver. It is available on API level (iocp.br_tech should alpar@1: be set to GLP_BR_PCH) and in the stand-alone solver glpsol alpar@1: (via the command-line option --pcost). This heuristic may be alpar@1: useful on solving hard MIP instances. alpar@1: alpar@1: The branching heuristic by Driebeck and Tomlin (used in the alpar@1: MIP solver by default) was changed to switch to branching on alpar@1: most fractional variable if an lower bound of degradation of alpar@1: the objective is close to zero for all branching candidates. alpar@1: alpar@1: A bug was fixed in the LP preprocessor (routine npp_empty_col). alpar@1: Thanks to Stefan Vigerske for the alpar@1: bug report. alpar@1: alpar@1: A bug was fixed and some improvements were made in the FPUMP alpar@1: heuristic module. Thanks to Xypron . alpar@1: alpar@1: A bug was fixed in the API routine glp_warm_up (dual alpar@1: feasibility test was incorrect in maximization case). Thanks to alpar@1: Uday Venkatadri for the bug report. alpar@1: alpar@1: GLPK 4.39 (release date: Jul 26, 2009) alpar@1: alpar@1: The following new API routines were added: alpar@1: alpar@1: glp_warm_up "warm up" LP basis alpar@1: glp_set_vertex_name assign (change) vertex name alpar@1: glp_create_v_index create vertex name index alpar@1: glp_find_vertex find vertex by its name alpar@1: glp_delete_v_index delete vertex name index alpar@1: glp_read_asnprob read assignment problem data in DIMACS alpar@1: format alpar@1: glp_write_asnprob write assignment problem data in DIMACS alpar@1: format alpar@1: glp_check_asnprob check correctness of assignment problem alpar@1: data alpar@1: glp_asnprob_lp convert assignment problem to LP alpar@1: glp_asnprob_okalg solve assignment problem with the alpar@1: out-of-kilter algorithm alpar@1: glp_asnprob_hall find bipartite matching of maxumum alpar@1: cardinality with Hall's algorithm alpar@1: alpar@1: Also were added some API routines to read plain data files. alpar@1: alpar@1: The API routines glp_read_lp and glp_write_lp to read/write alpar@1: files in CPLEX LP format were re-implemented. Now glp_write_lp alpar@1: correctly writes double-bounded (ranged) rows by introducing alpar@1: slack variables rather than by duplicating the rows. alpar@1: alpar@1: For description of these new routines see a new edition of the alpar@1: reference manual included in the distribution. alpar@1: alpar@1: The 'xfree(NULL)' bug was fixed in the AMD routines. Thanks to alpar@1: Niels Klitgord for bug report. alpar@1: alpar@1: The message "Crashing..." was changed to "Constructing initial alpar@1: basis..." due to suggestion by Thomas Kahle . alpar@1: alpar@1: Some typos were corrected in glpsol output messages. Thanks to alpar@1: Xypron for patch. alpar@1: alpar@1: GLPK 4.38 (release date: May 02, 2009) alpar@1: alpar@1: API routines glp_read_mps and glp_write_mps were improved. alpar@1: alpar@1: Some improvements were made in the dual simplex routines. alpar@1: alpar@1: Two external software modules AMD and COLAMD were included in alpar@1: the distribution (for more details please see src/amd/README alpar@1: and src/colamd/README). Now they are used in the interior-point alpar@1: solver to reorder the matrix prior to Cholesky factorization. alpar@1: alpar@1: API routine glp_ipt_status may return two new statuses due to alpar@1: changes in the routine glp_interior. For details please see the alpar@1: reference manual included in the distribution. alpar@1: alpar@1: A minor bug was fixed in the graph/network routines. Thanks to alpar@1: Nelson H. F. Beebe for bug report. alpar@1: alpar@1: GLPK 4.37 (release date: Mar 29, 2009) alpar@1: alpar@1: The 0-1 Feasibility Pump heuristic was included in the GLPK alpar@1: integer optimizer glp_intopt. On API level the heuristic can be alpar@1: enabled by setting the parameter fp_heur in glp_iocp to GLP_ON. alpar@1: This feature is also available in the solver glpsol through alpar@1: command-line option '--fpump'. For more details please see the alpar@1: reference manual included in the distribution. alpar@1: alpar@1: The following new API routines were added: alpar@1: alpar@1: glp_print_sol write basic solution in printable format alpar@1: glp_print_ipt write interior-point solution in printable alpar@1: format alpar@1: glp_print_mip write MIP solution in printable format alpar@1: glp_read_graph read (di)graph from plain text file alpar@1: glp_write_graph write (di)graph to plain text file alpar@1: glp_weak_comp find all weakly connected components alpar@1: glp_strong_comp find all strongly connected components alpar@1: alpar@1: The following API routines are deprecated: lpx_print_sol, alpar@1: lpx_print_ips, lpx_print_mip, lpx_print_prob (the latter is alpar@1: equivalent to glp_write_lp). alpar@1: alpar@1: A bug was fixed in the interior-point solver (glp_interior) to alpar@1: correctly compute dual solution components when the problem is alpar@1: scaled. alpar@1: alpar@1: The files configure.ac and Makefile.am were changed: alpar@1: (a) to allow using autoreconf/autoheader; alpar@1: (b) to allow building the package in a directory other than its alpar@1: source directory. alpar@1: Thanks to Marco Atzeri for bug report. alpar@1: alpar@1: An example model in the GNU MathProg language was added. alpar@1: Thanks to Larry D'Agostino for alpar@1: contribution. alpar@1: alpar@1: GLPK 4.36 (release date: Feb 06, 2009) alpar@1: alpar@1: The following new API routines were added to the package: alpar@1: alpar@1: glp_mincost_okalg find minimum-cost flow with out-of-kilter alpar@1: algorithm alpar@1: glp_maxflow_ffalg find maximal flow with Ford-Fulkerson alpar@1: algorithm alpar@1: alpar@1: For detailed description of these new routines and related data alpar@1: structures see chapter "Graph and Network API Routines" in a new alpar@1: edition of the reference manual included in the distribution. alpar@1: alpar@1: The following two new command-line options were added to the alpar@1: solver glpsol: alpar@1: alpar@1: --mincost read min-cost flow data in DIMACS format alpar@1: --maxflow read maximum flow data in DIMACS format alpar@1: alpar@1: Duplicate symbols in the header glpk.h were removed to allow alpar@1: using swig. alpar@1: Thanks to Kelly Westbrooks and alpar@1: Nigel Galloway for suggestion. alpar@1: alpar@1: A minor defect was fixed in the routine glp_write_lp. alpar@1: Thanks to Sebastien Briais for bug report. alpar@1: alpar@1: A minor bug was fixed in the SQL module. alpar@1: Thanks to Xypron for patch. alpar@1: alpar@1: Some new example models in the GNU MathProg modeling language alpar@1: were added. Thanks to Sebastian Nowozin and alpar@1: Nigel Galloway for contribution. alpar@1: alpar@1: GLPK 4.35 (release date: Jan 09, 2009) alpar@1: alpar@1: The following new API routines were added to the package: alpar@1: alpar@1: glp_create_graph create graph alpar@1: glp_set_graph_name assign (change) graph name alpar@1: glp_add_vertices add new vertices to graph alpar@1: glp_add_arc add new arc to graph alpar@1: glp_erase_graph erase graph content alpar@1: glp_delete_graph delete graph alpar@1: glp_read_mincost read minimum cost flow problem data in alpar@1: DIMACS format alpar@1: glp_write_mincost write minimum cost flow problem data in alpar@1: DIMACS format alpar@1: glp_mincost_lp convert minimum cost flow problem to LP alpar@1: glp_netgen Klingman's network problem generator alpar@1: glp_gridgen grid-like network problem generator alpar@1: glp_read_maxflow read maximum flow problem data in DIMACS alpar@1: format alpar@1: glp_write_maxflow write maximum flow problem data in DIMACS alpar@1: format alpar@1: glp_maxflow_lp convert maximum flow problem to LP alpar@1: glp_rmfgen Goldfarb's maximum flow problem generator alpar@1: alpar@1: For detailed description of these new routines and related data alpar@1: structures see chapter "Graph and Network API Routines" in a new alpar@1: edition of the reference manual included in the distribution. alpar@1: alpar@1: A minor change were made in the internal routine xputc. Thanks alpar@1: to Luiz Bettoni for suggestion. alpar@1: alpar@1: A minor bug was fixed in the internal routine mpl_fn_time2str. alpar@1: Thanks to Stefan Vigerske for bug report. alpar@1: alpar@1: GLPK 4.34 (release date: Dec 04, 2008) alpar@1: alpar@1: The GNU MathProg modeling language was supplemented with three alpar@1: new built-in functions: alpar@1: alpar@1: gmtime obtaining current calendar time alpar@1: str2time converting character string to calendar time alpar@1: time2str converting calendar time to character string alpar@1: alpar@1: (Thanks to Xypron .) alpar@1: alpar@1: For detailed description of these functions see Appendix A in alpar@1: the document "Modeling Language GNU MathProg", a new edition of alpar@1: which was included in the distribution. alpar@1: alpar@1: A bug was fixed in the MIP solver. Thanks to Nigel Galloway alpar@1: for bug report. alpar@1: alpar@1: A new makefile was added to build the GLPK DLL with Microsoft alpar@1: Visual Studio Express 2008 for 64-bit Windows. Thanks to Xypron alpar@1: for contribution and testing. alpar@1: alpar@1: GLPK 4.33 (release date: Oct 30, 2008) alpar@1: alpar@1: The following new API routines were added to the package: alpar@1: glp_copy_prob copy problem object content alpar@1: glp_exact solve LP in exact arithmetic alpar@1: (makes lpx_exact deprecated) alpar@1: glp_get_unbnd_ray determine variable causing unboundedness alpar@1: (makes lpx_get_ray_info deprecated) alpar@1: glp_interior solve LP with interior-point method alpar@1: (makes lpx_interior deprecated) alpar@1: alpar@1: The following new API routines for processing models written in alpar@1: the GNU Mathprog language were added to the package: alpar@1: glp_mpl_alloc_wksp allocate the translator workspace alpar@1: glp_mpl_read_model read and translate model section alpar@1: glp_mpl_read_data read and translate data section alpar@1: glp_mpl_generate generate the model alpar@1: glp_mpl_build_prob build LP/MIP instance from the model alpar@1: glp_mpl_postsolve postsolve the model alpar@1: glp_mpl_free_wksp deallocate the translator workspace alpar@1: (These routines make lpx_read_model deprecated.) alpar@1: alpar@1: For description of all these new API routines see the reference alpar@1: manual included in the distribution. alpar@1: alpar@1: A crude implementation of CPLEX-like interface to GLPK API was alpar@1: added to the package. Currently it allows using GLPK as a core alpar@1: LP solver for Concorde, a well known computer code for solving alpar@1: the symmetric TSP. For details see examples/cplex/README. alpar@1: alpar@1: Some bugs were fixed in the SQL table driver. Thanks to Xypron alpar@1: . alpar@1: alpar@1: GLPK 4.32 (release date: Oct 03, 2008) alpar@1: alpar@1: The following new features were included in the MIP solver alpar@1: (the API routine glp_intopt): alpar@1: alpar@1: * MIP presolver alpar@1: * mixed cover cut generator alpar@1: * clique cut generator alpar@1: * Euclidean reduction of the objective value alpar@1: alpar@1: Due to changes the routine glp_intopt may additionally return alpar@1: GLP_ENOPFS, GLP_ENODFS, and GLP_EMIPGAP. alpar@1: alpar@1: The API routines lpx_integer are lpx_intopt are deprecated, alpar@1: since they are completely superseded by glp_intopt. alpar@1: alpar@1: The following new branch-and-cut API routines were added: alpar@1: glp_ios_row_attr determine additional row attributes alpar@1: glp_ios_pool_size determine current size of the cut pool alpar@1: glp_ios_add_row add constraint to the cut pool alpar@1: glp_ios_del_row delete constraint from the cut pool alpar@1: glp_ios_clear_pool delete all constraints from the cut pool alpar@1: alpar@1: For description of these new routines see the reference manual alpar@1: included in the distribution. alpar@1: alpar@1: The stand-alone solver glpsol was changed to allow multiple alpar@1: data files. alpar@1: alpar@1: A new edition of the supplement "Using Data Tables in the GNU alpar@1: MathProg Modeling Language" was included. alpar@1: alpar@1: As usual, some bugs were fixed (in the MathProg translator). alpar@1: Thanks to Xypron . alpar@1: alpar@1: GLPK 4.31 (release date: Sep 02, 2008) alpar@1: alpar@1: The core LP solver based on the dual simplex method was alpar@1: re-implemented and now it provides both phases I and II. alpar@1: alpar@1: The following new API routines were added: alpar@1: glp_scale_prob automatic scaling of problem data alpar@1: glp_std_basis construct standard initial LP basis alpar@1: glp_adv_basis construct advanced initial LP basis alpar@1: glp_cpx_basis construct Bixby's initial LP basis alpar@1: alpar@1: For description of these new routines see the reference manual alpar@1: included in the distribution. alpar@1: alpar@1: The following API routines are deprecated: alpar@1: lpx_scale_prob, lpx_std_basis, lpx_adv_basis, lpx_cpx_basis. alpar@1: alpar@1: Necessary changes were made in memory allocation routines to alpar@1: resolve portability issues for 64-bit platforms. alpar@1: alpar@1: New version of the routine lpx_write_pb to write problem data alpar@1: in OPB (pseudo boolean format) was added to the package. Thanks alpar@1: to Oscar Gustafsson for the contribution. alpar@1: alpar@1: Two new makefiles were added to build the package for 32- and alpar@1: 64-bit Windows with Microsoft Visual Studio Express 2008. alpar@1: Thanks to Heinrich Schuchardt (aka alpar@1: Xypron) for the contribution and testing. alpar@1: alpar@1: Two new makefiles were added to build the package with Digital alpar@1: Mars C/C++ 8.50 and Open Watcom C/C++ 1.6 (for 32-bit Windows). alpar@1: alpar@1: GLPK 4.30 (release date: Aug 13, 2008) alpar@1: alpar@1: The core LP solver based on the primal simplex method was alpar@1: re-implemented to allow its further improvements. Currently the alpar@1: new version provides the same features as the old one, however, alpar@1: it is a bit faster and more numerically stable. alpar@1: alpar@1: Some changes were made in the MathProg translator to allow <, alpar@1: <=, >=, and > on comparing symbolic values. Thanks to Heinrich alpar@1: Schuchardt for patches. alpar@1: alpar@1: Internal routine set_d_eps in the exact LP solver was changed alpar@1: to prevent approximation errors in case of integral data. alpar@1: Thanks to Markus Pilz for bug report. alpar@1: alpar@1: GLPK 4.29 (release date: Jul 06, 2008) alpar@1: alpar@1: The configure script was changed to disable all optional alpar@1: features by default. For details please see file INSTALL. alpar@1: alpar@1: The following new API routines were added: alpar@1: glp_erase_prob erase problem object content alpar@1: glp_read_mps read problem data in MPS format alpar@1: glp_write_mps write problem data in MPS format alpar@1: glp_read_lp read problem data in CPLEX LP format alpar@1: glp_write_lp write problem data in CPLEX LP format alpar@1: alpar@1: For description of these new routines see the reference manual alpar@1: included in the distribution. alpar@1: alpar@1: The following API routines are deprecated: alpar@1: lpx_read_mps, lpx_read_freemps, lpx_write_mps, alpar@1: lpx_write_freemps, lpx_read_cpxlp, and lpx_write_cpxlp. alpar@1: alpar@1: Two bugs were fixed. Thanks to alpar@1: Anne-Laurence Putz and alpar@1: Xypron for bug report. alpar@1: alpar@1: GLPK 4.28 (release date: Mar 25, 2008) alpar@1: alpar@1: The iODBC and MySQL table drivers, which allows transmitting alpar@1: data between MathProg model objects and relational databases, alpar@1: were re-implemented to replace a static linking by a dynamic alpar@1: linking to corresponding shared libraries. alpar@1: Many thanks to Heinrich Schuchardt alpar@1: for the contribution, Rafael Laboissiere alpar@1: for useful advices concerning the shared library support under alpar@1: GNU/Linux, and Vijay Patil for testing alpar@1: this feature under Windows XP. alpar@1: alpar@1: A new optional feature was added to the package. This feature alpar@1: is based on the zlib data compression library and allows GLPK alpar@1: API routines and the stand-alone solver to read and write alpar@1: compressed data files performing compression/decompression "on alpar@1: the fly" (compressed data files are recognized by suffix `.gz' alpar@1: in the file name). It may be useful in case of large MPS files alpar@1: to save the disk space (up to ten times). alpar@1: alpar@1: The `configure' script was re-implemented. Now it supports the alpar@1: following specific options: alpar@1: alpar@1: --with-gmp Enable using the GNU MP bignum library alpar@1: --without-gmp Disable using the GNU MP bignum library alpar@1: --with-zlib Enable using the zlib data compression alpar@1: library alpar@1: --without-zlib Disable using the zlib data compression alpar@1: library alpar@1: --enable-dl Enable shared library support (auto check) alpar@1: --enable-dl=ltdl Enable shared library support (GNU) alpar@1: --enable-dl=dlfcn Enable shared library support (POSIX) alpar@1: --disable-dl Disable shared library support alpar@1: --enable-odbc Enable using ODBC table driver alpar@1: --disable-odbc Disable using ODBC table driver alpar@1: --enable-mysql Enable using MySQL table driver alpar@1: --disable-mysql Disable using MySQL table driver alpar@1: alpar@1: For more details please see file INSTALL. alpar@1: alpar@1: GLPK 4.27 (release date: Mar 02, 2008) alpar@1: alpar@1: Three new table drivers were added to the MathProg translator: alpar@1: alpar@1: xBASE built-in table driver, which allows reading and writing alpar@1: data in .dbf format (only C and N fields are supported); alpar@1: alpar@1: MySQL table driver, which provides connection to a MySQL alpar@1: database; alpar@1: alpar@1: iODBC table driver, which provides connection to a database alpar@1: through ODBC. alpar@1: alpar@1: The MySQL and iODBC table drivers were contributed to GLPK by alpar@1: Heinrich Schuchardt . alpar@1: alpar@1: The table driver is a program module which allows transmitting alpar@1: data between MathProg model objects and external data tables. alpar@1: alpar@1: For detailed description of the table statement and table alpar@1: drivers see the document "Using Data Tables in the GNU MathProg alpar@1: Modeling Language" (file doc/tables.txt) included in the alpar@1: distribution. Some examples which demonstrate using MySQL and alpar@1: iODBC table drivers can be found in subdirectory examples/sql. alpar@1: alpar@1: GLPK 4.26 (release date: Feb 17, 2008) alpar@1: alpar@1: The table statement was implemented in the GNU MathProg alpar@1: modeling language. This new feature allows reading data from alpar@1: external tables into model objects such as sets and parameters alpar@1: as well as writing results of computations to external tables. alpar@1: alpar@1: A table is a (unordered) set of records, where each record alpar@1: consists of the same number of fields, and each field is alpar@1: provided with a unique symbolic name called the field name. alpar@1: alpar@1: Currently the GLPK package has the only built-in table driver, alpar@1: which supports tables in the CSV (comma-separated values) file alpar@1: format. This format is very simple and supported by almost all alpar@1: spreadsheets and database management systems. alpar@1: alpar@1: Detailed description of the table statement and CSV format can alpar@1: be found in file doc/tables.txt, included in the distribution. alpar@1: alpar@1: GLPK 4.25 (release date: Dec 19, 2007) alpar@1: alpar@1: A tentative implementation of Gomory's mixed integer cuts was alpar@1: included in the branch-and-cut solver. To enable generating alpar@1: Gomory's cuts the control parameter gmi_cuts passed to the alpar@1: routine glp_intopt should be set to GLP_ON. This feature is alpar@1: also available in the solver glpsol through command-line option alpar@1: '--gomory'. For more details please see the reference manual alpar@1: included in the distribution. alpar@1: alpar@1: GLPK 4.24 (release date: Nov 21, 2007) alpar@1: alpar@1: A tentative implementation of MIR (mixed integer rounding) cuts alpar@1: was included in the MIP solver. To enable generating MIR cuts alpar@1: the control parameter mir_cuts passed to the routine glp_intopt alpar@1: should be set to GLP_ON. This feature is also available in the alpar@1: stand-alone solver glpsol via command-line option '--mir'. For alpar@1: more details please see the reference manual included in the alpar@1: distribution. alpar@1: alpar@1: The implementation is mainly based on the following two papers: alpar@1: alpar@1: 1. H. Marchand and L. A. Wolsey. Aggregation and mixed integer alpar@1: rounding to solve MIPs. CORE discussion paper 9839, CORE, alpar@1: Universite catholique de Louvain, June 1998. alpar@1: alpar@1: 2. G. Andreello, A. Caprara, and M. Fischetti. Embedding cuts alpar@1: in a Branch&Cut framework. Preliminary draft, October 2003. alpar@1: alpar@1: MIR cuts can be generated on any level of the search tree that alpar@1: makes the GLPK MIP solver to be a real branch-and-cut solver. alpar@1: alpar@1: A bug was fixed in the routine lpx_write_cpxlp. If a variable alpar@1: x has upper bound and no lower bound, it should appear in the alpar@1: bounds section as "-inf <= x <= u", not as "x <= u". Thanks to alpar@1: Enric Rodriguez for the bug report. alpar@1: alpar@1: GLPK 4.23 (release date: Oct 28, 2007) alpar@1: alpar@1: The following new API routines were added: alpar@1: alpar@1: glp_read_sol read basic solution from text file alpar@1: glp_write_sol write basic solution to text file alpar@1: glp_read_ipt read interior-point solution from text file alpar@1: glp_write_ipt write interior-point solution to text file alpar@1: glp_read_mip read MIP solution from text file alpar@1: glp_write_mip write MIP solution to text file alpar@1: alpar@1: For description of these routines and corresponding file alpar@1: formats see Chapter "API Routines", Section "Utility routines" alpar@1: in the reference manual included in the distribution. alpar@1: alpar@1: Advanced API routine glp_free_env was added. It may be used by alpar@1: the application program to free all resources allocated by GLPK alpar@1: routines. alpar@1: alpar@1: The following three new command-line options were added to the alpar@1: solver glpsol: alpar@1: alpar@1: --mipgap tol set relative MIP gap tolerance alpar@1: -r filename read solution from filename alpar@1: -w filename write solution to filename alpar@1: alpar@1: GLPK 4.22 (release date: Sep 19, 2007) alpar@1: alpar@1: This is a maintainer release. alpar@1: alpar@1: A bug was fixed in the MIP preprocessor (ios_preprocess_node). alpar@1: Thanks to Roberto Bagnara (Department of alpar@1: Mathematics, University of Parma, Italy) for the bug report. alpar@1: alpar@1: A bug was fixed in the MIP preprocessor (col_implied_bounds), alpar@1: due to which constraint coefficients with small magnitude could alpar@1: lead to wrong implied bounds of structural variables. alpar@1: alpar@1: A similar bug was fixed in the routine reduce_bounds. alpar@1: alpar@1: A bug was fixed in the routines glp_set_mat_row and alpar@1: glp_set_mat_col. (The bug appeared due to incorrect removing alpar@1: zero elements from the row/column lists.) alpar@1: alpar@1: A bug was fixed in the API routines lpx_read_mps and alpar@1: lpx_read_freemps, due to which bounds of type LI specified in alpar@1: BOUNDS section were incorrectly processed. alpar@1: alpar@1: A call to standard function vsprintf was replaced by a call to alpar@1: vsnprintf for security reasons. Many thanks to Peter T. Breuer alpar@1: and Rafael Laboissiere . alpar@1: alpar@1: GLPK 4.21 (release date: Aug 28, 2007) alpar@1: alpar@1: Additional reasons for calling the callback routine used in the alpar@1: MIP solver (glp_intopt) were introduced. Currently the following alpar@1: reasons are supported: alpar@1: alpar@1: * request for subproblem selection alpar@1: * request for preprocessing alpar@1: * request for row generation alpar@1: * request for heuristic solution alpar@1: * request for cut generation alpar@1: * request for branching alpar@1: * better integer solution found alpar@1: alpar@1: A basic preprocessing component used to improve subproblem alpar@1: formulations by tightening bounds of variables was included in alpar@1: the MIP solver. Depending on the control parameter pp_tech alpar@1: passed to the routine glp_intopt the preprocessing can be alpar@1: performed either on the root level or on all levels (default) alpar@1: or can be disabled. alpar@1: alpar@1: Backtracking heuristic used by default in the MIP solver was alpar@1: changed to the "best local bound". alpar@1: alpar@1: For more details see Chapter "Advanced API routines", Section alpar@1: "Branch-and-bound interface routines" in a new edition of the alpar@1: reference manual included in the distribution. alpar@1: alpar@1: GLPK 4.20 (release date: Jul 26, 2007) alpar@1: alpar@1: API routine lpx_integer was replaced by API routine glp_intopt, alpar@1: which provides equivalent functionality and additionally allows alpar@1: the application to control the solution process by means of the alpar@1: user-written callback routine, which is called by the solver at alpar@1: various points of the branch-and-bound algorithm. Besides, the alpar@1: new MIP solver allows generating "lazy" constraints and cutting alpar@1: planes on all levels of the branch-and-bound tree, not only on alpar@1: the root level. The routine lpx_integer is also still available alpar@1: for the backward compatibility. alpar@1: alpar@1: The following new advanced API routines, which may be called alpar@1: from the B&B callback routine, were included in the package: alpar@1: alpar@1: glp_ios_reason determine reason for calling callback alpar@1: routine alpar@1: glp_ios_get_prob access the problem object alpar@1: glp_ios_tree_size determine size of the branch-and-bound tree alpar@1: glp_ios_curr_node determine current active subproblem alpar@1: glp_ios_next_node determine next active subproblem alpar@1: glp_ios_prev_node determine previous active subproblem alpar@1: glp_ios_up_node determine parent subproblem alpar@1: glp_ios_node_level determine subproblem level alpar@1: glp_ios_node_bound determine subproblem local bound alpar@1: glp_ios_mip_gap compute relative MIP gap alpar@1: glp_ios_heur_sol provide solution found by heuristic alpar@1: glp_ios_terminate terminate the solution process alpar@1: alpar@1: For description of these routines see Chapter "Advanced API alpar@1: routines", Section "Branch-and-bound interface routines" in a alpar@1: new edition of the reference manual, which was included in the alpar@1: distribution. alpar@1: alpar@1: Old version of the integer optimization suite (IOS) as well as alpar@1: TSP solver tspsol based on it are no longer supported and were alpar@1: removed from the package. alpar@1: alpar@1: A minor error in the MIP presolver was fixed; thanks to Graham alpar@1: Rockwell for the bug report. alpar@1: alpar@1: GLPK 4.19 (release date: Jul 05, 2007) alpar@1: alpar@1: The principal change is upgrading to GPLv3. alpar@1: alpar@1: A serious bug in the routine glp_del_cols was fixed; thanks to alpar@1: Cedric[FR] for the bug report. The bug alpar@1: appeared because on deleting non-basic columns the basis header alpar@1: remained valid, however, contained invalid (old) column ordinal alpar@1: numbers. alpar@1: alpar@1: A new advanced API routine glp_mem_limit was added. alpar@1: alpar@1: The case GLP_EBOUND was added to the routine lpx_simplex. alpar@1: Thanks to Cameron Kellough for the alpar@1: bug report. alpar@1: alpar@1: An API routine lpx_write_pb to write the problem instance in alpar@1: OPB (pseudo boolean) format format was added. Thanks to Oscar alpar@1: Gustafsson for the contribution. alpar@1: alpar@1: Two new options --wpb and --wnpb were added to glpsol to write alpar@1: the problem instance in OPB format. alpar@1: alpar@1: GLPK 4.18 (release date: Jun 25, 2007) alpar@1: alpar@1: The following new API routines were added: alpar@1: alpar@1: glp_set_rii set (change) row scale factor alpar@1: glp_set_sjj set (change) column scale factor alpar@1: glp_get_rii retrieve row scale factor alpar@1: glp_get_sjj retrieve column scale factor alpar@1: glp_simplex solve LP problem with the simplex method alpar@1: (this routine replaces lpx_simplex, which is alpar@1: also available for backward compatibility) alpar@1: glp_init_smcp initialize simplex method control params alpar@1: glp_bf_exists check if the basis factorization exists alpar@1: glp_factorize compute the basis factorization alpar@1: glp_bf_updated check if the basis factorization has been alpar@1: updated alpar@1: glp_get_bfcp retrieve basis factorization control params alpar@1: glp_set_bfcp change basis factorization control params alpar@1: glp_get_bhead retrieve the basis header information alpar@1: glp_get_row_bind retrieve row index in the basis header alpar@1: glp_get_col_bind retrieve column index in the basis header alpar@1: glp_ftran perform forward transformation alpar@1: glp_btran perform backward transformation alpar@1: alpar@1: For description of all these routines see a new edition of the alpar@1: reference manual included in the distribution. alpar@1: alpar@1: Type names ulong_t and uldiv_t were changed to glp_ulong and alpar@1: glp_uldiv to avoid conflicts with standard type names on some alpar@1: platforms. Thanks to Boris Wirtz alpar@1: for the bug report. alpar@1: alpar@1: Some new examples in the MathProg language were added. Thanks alpar@1: to Sebastian Nowozin . alpar@1: alpar@1: GLPK 4.17 (release date: May 26, 2007) alpar@1: alpar@1: API routines glp_set_mat_row, glp_set_mat_col, and glp_load_mat alpar@1: were modified to allow zero constraint coefficients (which are alpar@1: not stored in the constraint matrix). Note that constraint alpar@1: coefficients with duplicate row/column indices are not allowed. alpar@1: alpar@1: Another form of LP basis factorization was implemented in the alpar@1: package. It is based on LU-factorization of an initial basis alpar@1: and Schur complement to reflect changes in the basis. Currently alpar@1: the implementation is incomplete and provides only updating the alpar@1: factorization on replacing a column of the basis matrix. On API alpar@1: level the user can set the control parameter LPX_K_BFTYPE to alpar@1: choose between the folloiwng forms of LP basis factorization to alpar@1: be used in the simplex method routines: alpar@1: 1) LU + Forrest-Tomlin update; alpar@1: 2) LU + Schur complement + Bartels-Golub update; alpar@1: 3) LU + Schur complement + Givens rotation update. alpar@1: The GLPK implementation is similar to LUSOL/LUMOD developed by alpar@1: Michael A. Saunders. alpar@1: alpar@1: The user can choose the form of LP basis factorzation used by alpar@1: the simplex method routines by specifying the folloiwng options alpar@1: of glpsol: --luf, --cbg, --cgr. alpar@1: alpar@1: GLPK 4.16 (release date: May 05, 2007) alpar@1: alpar@1: A number of basic GLPK API routines, which now are in the alpar@1: stable stable, were renamed to be prefixed with 'glp_'. Note alpar@1: that all these routines are available via their old names alpar@1: prefixed with 'lpx_' that keeps the downward compatibility with alpar@1: older versions of the package. alpar@1: alpar@1: Three new GLPK API routines were added to the package: alpar@1: glp_version, glp_term_hook, and glp_mem_usage; for more details alpar@1: see a new edition of the GLPK reference manual included in the alpar@1: distribution. The routine glp_version reports the actual version alpar@1: of the GLPK library and also can be used (along with the header alpar@1: glpk.h) in Autotools specification files to check if the GLPK alpar@1: library has been installed. alpar@1: alpar@1: The header glpk.h was changed to conform to C++ environment. alpar@1: alpar@1: GLPK 4.15 (release date: Feb 18, 2007) alpar@1: alpar@1: Autotools specification files (configure.ac, Makefile.am) were alpar@1: changed to use GNU Libtool. This allows building the static as alpar@1: well as shared GLPK library. alpar@1: alpar@1: GLPK 4.14 (release date: Feb 05, 2007) alpar@1: alpar@1: Now GLPK conforms to ILP32, LLP64, and LP64 programming models alpar@1: (the latter seems to be the ultimate choice regarding 64-bit alpar@1: architectures). Note that GLPK itself is a 32-bit application, alpar@1: and the conformity only means that the package works correctly alpar@1: on all these arenae. Nevertheless, on 64-bit platforms it is alpar@1: possible to use more than 4GB of memory, if necessary. alpar@1: alpar@1: GLPK 4.13 (release date: Nov 13, 2006) alpar@1: alpar@1: A tentative implementation of the "exact" simplex method based alpar@1: on bignum (rational) arithmetic was included in the package. alpar@1: alpar@1: On API level this new feature is available through the routine alpar@1: lpx_exact, which is similar to the routine lpx_simplex. alpar@1: alpar@1: In the solver glpsol this feature is available through two new alpar@1: command-line options: --exact and --xcheck. If the '--exact' alpar@1: option is specified, glpsol solves LP instance using the exact alpar@1: simplex method; in case of MIP it is used to obtain optimal alpar@1: solution of LP relaxation. If the --xcheck option is specified, alpar@1: LP instance (or LP relaxation) is solved using the standard alpar@1: (floating-point) simplex method, however, then glpsol calls the alpar@1: exact simplex routine to make sure that the final LP basis is alpar@1: exactly optimal, and if it is not, to perform some additional alpar@1: simplex iterations in exact arithmetic. alpar@1: alpar@1: GLPK 4.12 (release date: Nov 08, 2006) alpar@1: alpar@1: A tentative implementation of some simplex method routines alpar@1: based on exact (bignum) arithmetic was included in the package. alpar@1: Currently these routines provide computing LU-factorization of alpar@1: the basis matrix and computing components of basic solution. alpar@1: alpar@1: These routines were used to implement a routine, which checks alpar@1: primal and dual feasibility of basic solution exactly, i.e. in alpar@1: rational numbers, without round-off errors. In glpsol this alpar@1: feature is available through the command-line option --xcheck. alpar@1: alpar@1: GLPK has its own low-level routines implementing operations on alpar@1: integer and rational numbers that makes it independent on other alpar@1: software packages. However, to attain a much better performance alpar@1: it is highly recommended to install (before configuring GLPK) alpar@1: the GNU Multiple Precision Arithmetic Library (GMP). Using GMP alpar@1: makes computations 100-200 times faster. alpar@1: alpar@1: GLPK 4.11 (release date: Jul 25, 2006) alpar@1: alpar@1: Three new built-in functions in the modeling language were alpar@1: implemented: card (cardinality of set), length (length of alpar@1: character string), and substr (substring of character string). alpar@1: Another improvement concerns the printf statement which now alpar@1: allows redirecting its output to a specified file. These new alpar@1: features are illustrated in example models crypto.mod and alpar@1: graph.mod included in the distribution. For more details see alpar@1: the document "Modeling Language GNU MathProg". alpar@1: alpar@1: Four batch files (along with corresponding makefiles) were alpar@1: included in the distribution to simplify building GLPK under alpar@1: MS Windows; see them in subdirectory 'w32'. alpar@1: alpar@1: GLPK 4.10 (release date: May 11, 2006) alpar@1: alpar@1: Cutting planes of two new classes were implemented: mixed cover alpar@1: cuts and clique cuts. On API level this feature can be enabled alpar@1: by setting control parameter LPX_K_USECUTS passed to the routine alpar@1: lpx_intopt. In glpsol this feature is available through the alpar@1: command-line options --cover and --clique. For more details see alpar@1: the reference manual. alpar@1: alpar@1: Now the routines lpx_read_mps and lpx_read_freemps support LI alpar@1: bound type. It is similar to LO, however, indicates the column alpar@1: as of integer kind. alpar@1: alpar@1: GLPK 4.9 (release date: Jan 17, 2006) alpar@1: alpar@1: An advanced MIP solver was implemented. It includes: alpar@1: alpar@1: - basic presolving technique (removing free, singleton and alpar@1: redundant rows, improving bounds of columns, removing fixed alpar@1: columns, reducing constraint coefficents); alpar@1: alpar@1: - generating cutting planes to improve LP relaxation (currently alpar@1: only Gomory's mixed integer cuts are implemented); alpar@1: alpar@1: - using the branch-and-bound method to solve resultant MIP; alpar@1: alpar@1: - recovering solution of the original MIP. alpar@1: alpar@1: The solver is available on API level via the routine lpx_intopt alpar@1: (see the reference manual). It is similar to the routine alpar@1: lpx_integer, however, does not require initial solution of LP alpar@1: relaxation. alpar@1: alpar@1: The solver is also available in the command-line utility glpsol alpar@1: via two options: --intopt (only presolving) and --cuts (assumes alpar@1: --intopt plus generating cuts). alpar@1: alpar@1: Note that efficiency of the MIP solver strongly depends on the alpar@1: internal structure of the problem to be solved. For some hard alpar@1: instances it is very efficient, but for other instances it may alpar@1: be significantly worse than the standard branch-and-bound. alpar@1: alpar@1: For some comparative benchmarks see doc/bench1.txt. alpar@1: alpar@1: Well, what else... alpar@1: alpar@1: Three built-in functions were added to MathProg: sin, cos, and alpar@1: atan (the latter allows one or two arguments). alpar@1: alpar@1: Some bugs were fixed. alpar@1: alpar@1: Several new examples in MathProg were included: color.mod alpar@1: (graph coloring problem), tsp.mod (traveling salesman problem), alpar@1: and pbn.mod (paint-by-numbers puzzle). alpar@1: alpar@1: GLPK 4.8 (release date: Jan 12, 2005) alpar@1: alpar@1: Core simplex method and interior-point method routines were alpar@1: re-implemented and now they use a new, "storage-by-rows" sparse alpar@1: matrix format (unlike previous versions where linked lists were alpar@1: used to represent sparse matrices). For details see ChangeLog. alpar@1: alpar@1: Also a minor bug was fixed in API routine lpx_read_cpxlp. alpar@1: alpar@1: GLPK 4.7 (release date: Aug 23, 2004) alpar@1: alpar@1: Now GLPK supports free MPS format. Two new API routines alpar@1: lpx_read_freemps (to read problem data in free MPS format) and alpar@1: lpx_write_freemps (to write problem data in free MPS format) alpar@1: were added. This feature is also available in the solver glpsol alpar@1: via new command-line options --freemps and --wfreemps. For more alpar@1: details see the GLPK reference manual. alpar@1: alpar@1: API routines lpx_read_cpxlp and lpx_write_cpxlp for reading and alpar@1: writing problem data in CPLEX LP format were re-implemented to alpar@1: allow long symbolic names (up to 255 characters). alpar@1: alpar@1: The following three modules were temporarily removed from the alpar@1: GLPK distribution due to licensing problems: DELI (an interface alpar@1: module to Delphi), GLPKMEX (an interface module to Matlab), and alpar@1: JNI (an interface module to Java). alpar@1: alpar@1: GLPK 4.6 (release date: Aug 04, 2004) alpar@1: alpar@1: Three new statements were implemented in the GNU MathProg alpar@1: language: solve, printf, and for. Their detailed description can alpar@1: be found in the GLPK documentation included in the distribution. alpar@1: (See also a sample model, examples/queens.mod, which illustrates alpar@1: using these new statements.) alpar@1: alpar@1: Two new API routines were added to the package: lpx_read_prob alpar@1: and lpx_write_prob. They allow reading/writing problem data in alpar@1: GNU LP low-level text format. alpar@1: alpar@1: Three new command-line options were implemented in the LP/MIP alpar@1: solver glpsol: --glp (to read problem data in GNU LP format), alpar@1: --wglp (to write problem data in GNU LP format), and --name (to alpar@1: change problem name). Now glpsol also supports processing models alpar@1: where the new statements (see above) are used. alpar@1: alpar@1: A new version of GLPKMEX, a Matlab MEX interface to GLPK, was alpar@1: included. For more details see contrib/glpkmex/ChangeLog. alpar@1: alpar@1: GLPK 4.5 (release date: Jul 19, 2004) alpar@1: alpar@1: The branch-and-bound solver was completely re-implemented. alpar@1: alpar@1: Some modifications were made in memory allocation routines that alpar@1: allows using the package on 64-bit platforms. alpar@1: alpar@1: For more details see ChangeLog. alpar@1: alpar@1: GLPK 4.4 (release date: Jan 17, 2004) alpar@1: alpar@1: All API routines were re-implemented using new data structures. alpar@1: The new implementation provides the same specifications and alpar@1: functionality of API routines as the old one, however, it has alpar@1: some important advantages, in particular: alpar@1: * linked lists are used everywhere that allows creating and alpar@1: modifying the problem object as efficiently as possible alpar@1: * all data stored in the problem object are non-scaled (even if alpar@1: the internal scaling is used) that prevents distortion of the alpar@1: original problem data alpar@1: * solution components obtained by the solver remain available alpar@1: even if the problem object has been modified alpar@1: * no solver-specific data are used in the new data structures alpar@1: that allows attaching any external lp/mip solver using GLPK alpar@1: API as an uniform interface alpar@1: Note that some API routines became obsolete being replaced by alpar@1: new, more convenient routines. These obsolete routines are kept alpar@1: for backward compatibility, however, they will be removed in alpar@1: the future. For more details please see ChangeLog and the GLPK alpar@1: Reference Manual. alpar@1: alpar@1: New edition of the GLPK Reference Manual was included in the alpar@1: distribution. alpar@1: alpar@1: GLPKMEX, a Matlab MEX interface to GLPK package, contributed by alpar@1: Nicolo Giorgetti was included in the alpar@1: distribution. alpar@1: alpar@1: GLPK FAQ contributed by Harley Mackenzie was alpar@1: included in the distribution. alpar@1: alpar@1: GLPK 4.3 (release date: Dec 12, 2003) alpar@1: alpar@1: The bug, due to which the standard math library is not linked alpar@1: on building the package on some platforms, was fixed. alpar@1: alpar@1: The following new built-in functions were added to the MathProg alpar@1: language: round, trunc, Irand224, Uniform01, Uniform, Normal01, alpar@1: Normal. For details see the language description. alpar@1: alpar@1: The MathProg syntax was changed to allow writing 'subj to' that alpar@1: means 'subject to'. alpar@1: alpar@1: The new api routine lpx_get_ray_info was added. It is intended alpar@1: to determine which (non-basic) variable causes unboundness. For alpar@1: details see the reference manual. alpar@1: alpar@1: The module glpmps.c was changed to avoid compilation errors on alpar@1: building the package on Mac OS X. alpar@1: alpar@1: Several typos was fixed and some new material was added to the alpar@1: GLPK documentation. alpar@1: alpar@1: GLPK 4.2 (release date: Nov 14, 2003) alpar@1: alpar@1: A preliminary implementation of the Integer Optimization Suite alpar@1: (IOS) was included in the package. The Branch-and-Cut Framework alpar@1: being completely superseded by IOS was removed from the package. alpar@1: alpar@1: New API routine lpx_print_sens_bnds intended for bounds alpar@1: sensitivity analysis was contributed to GLPK by Brady Hunsaker alpar@1: . This function is also available in alpar@1: the solver glpsol (via command-line option --bounds). alpar@1: alpar@1: An improved version of GLPK JNI (Java Native Interface) was alpar@1: contributed by Chris Rosebrugh . alpar@1: alpar@1: GLPK DELI (Delphi Interface) was contributed by Ivo van Baren alpar@1: . alpar@1: alpar@1: Several makefiles were added to allow compiling GLPK on some alpar@1: non-GNU 32-bit platforms: alpar@1: * Windows single-threaded static library, Visual C++ 6.0 alpar@1: * Windows multi-threaded dynamic library, Visual C++ 6.0 alpar@1: * Windows single-threaded static library, Borland C++ 5.2 alpar@1: * DOS single-threaded static library, Digital Mars C++ 7.50 alpar@1: alpar@1: And, of course, some bugs were fixed. alpar@1: alpar@1: For more details see ChangeLog. alpar@1: alpar@1: GLPK 4.1 (release date: Aug 23, 2003) alpar@1: alpar@1: Some improvements were made in the lp/mip solver routines and alpar@1: several bugs were fixed in the model translator. alpar@1: alpar@1: For more details see ChangeLog. alpar@1: alpar@1: GLPK 4.0 (release date: May 06, 2003) alpar@1: alpar@1: Now GLPK supports the GNU MathProg modeling language, which is alpar@1: a subset of the AMPL modeling language. alpar@1: alpar@1: The document "GLPK: Modeling Language GNU MathProg" included in alpar@1: the distribution is a complete description of GNU MathProg. (See alpar@1: the files lang.latex, lang.dvi, and lang.ps in the subdirectory alpar@1: 'doc'. See also some examples in the subdirectory 'sample'.) alpar@1: alpar@1: New version of the solver glpsol, which supports models written alpar@1: in GNU MathProg, was implemented. (Brief instructions how to use alpar@1: glpsol can be found in the GNU MathProg documentation.) alpar@1: alpar@1: The GLPK/L modeling language is no more supported. The reason is alpar@1: that GNU MathProg being much more powerful completely supersedes alpar@1: all features of GLPK/L. alpar@1: alpar@1: GLPK 3.3 (release date: Mar 25, 2003) alpar@1: alpar@1: LP PRESOLVER alpar@1: ------------ alpar@1: alpar@1: Now the routine lpx_simplex (which is a driver to the simplex alpar@1: method for solving LP) is provided with the built-in LP alpar@1: presolver, which is a program that transforms the original LP alpar@1: problem to an equivalent LP problem, which may be easier for alpar@1: solving with the simplex method than the original one. Once the alpar@1: transformed LP has been solver, the presolver transforms its alpar@1: basic solution back to a corresponding basic solution of the alpar@1: original problem. For details about this feature please see the alpar@1: GLPK reference manual. alpar@1: alpar@1: Currently the LP presolver implements the following features: alpar@1: * removing empty rows; alpar@1: * removing empty columns; alpar@1: * removing free rows; alpar@1: * removing fixed columns; alpar@1: * removing row singletons, which have the form of equations; alpar@1: * removing row singletons, which have the form of inequalities; alpar@1: * removing column singletons, which are implied slack variables; alpar@1: * fixing and removing column singletons, which are implied free alpar@1: variables; alpar@1: * removing forcing rows that involves fixing and removing the alpar@1: corresponding columns; alpar@1: * checking for primal and dual infeasibilities. alpar@1: alpar@1: The LP presolver is also used by default in the stand-alone alpar@1: program glpsol. In order *not* to use it, the option --nopresol alpar@1: should be specified in the command-line. alpar@1: alpar@1: CHANGES IN GLPK/L alpar@1: ----------------- alpar@1: alpar@1: The syntax and semantics of the GLPK/L modeling language was alpar@1: changed to allow declaration of "interval" sets. This means that alpar@1: now the user can declare a set, for example, as: alpar@1: alpar@1: set task = [8:11]; alpar@1: alpar@1: that is exactly equivalent to the following declaration: alpar@1: alpar@1: set task = (task_8, task_9, task_10, task_11); alpar@1: alpar@1: For details see the language description. alpar@1: alpar@1: JAVA INTERFACE alpar@1: -------------- alpar@1: alpar@1: Now GLPK includes the package GLPK JNI (Java Native Interface) alpar@1: that implements Java binding for GLPK. It allows Java programs alpar@1: to utilize GLPK in solving LP and MIP problems. For details see alpar@1: a brief user's guide in the subdirectory contrib/java-binding. alpar@1: This package was developed and programmed by Yuri Victorovich alpar@1: , who contributed it to GLPK. alpar@1: alpar@1: GLPK 3.2.4 (release date: Feb 18, 2003) alpar@1: alpar@1: This is a bug-fix release. For details see ChangeLog. alpar@1: alpar@1: GLPK 3.2.3 (release date: Nov 11, 2002) alpar@1: alpar@1: A new implementation of the api routine lpx_integer which now alpar@1: is based on the b&b driver (which is based on the implicit alpar@1: enumeration suite) was included in the package. This new alpar@1: implementation has exactly the same functionality as the old alpar@1: version, so all changes are transparent to the api user. alpar@1: alpar@1: Four new api routines were included in the package: alpar@1: lpx_check_kkt checks Karush-Kuhn-Tucker optmality conditions; alpar@1: lpx_read_bas reads predifined basis in MPS format; alpar@1: lpx_write_bas writes current basis in MPS format; alpar@1: lpx_write_lpt writes problem data in CPLEX LP format. alpar@1: alpar@1: Also other minor improvements were made (for details see the alpar@1: file 'ChangeLog'). alpar@1: alpar@1: GLPK 3.2.2 (release date: Oct 14, 2002) alpar@1: alpar@1: The api routine lpx_read_lpt was included in the package. It alpar@1: is similar to the routine lpx_read_mps and intended to read alpar@1: LP/MIP data prepared in CPLEX LP format. Description of this alpar@1: format is given in the GLPK reference manual, a new edition of alpar@1: which was also included in the distribution (see the files alpar@1: 'refman.latex', 'refman.dvi', 'refman.ps' in the subdirectory alpar@1: 'doc'). In order to use data files in CPLEX LP format with the alpar@1: solver glpsol the option '--lpt' should be specified in the alpar@1: command line. alpar@1: alpar@1: Several bugs were fixed and some minor improvements were made alpar@1: (for details see the file 'ChangeLog'). alpar@1: alpar@1: GLPK 3.2.1 (release date: Aug 12, 2002) alpar@1: alpar@1: Now GLPK includes a preliminary implementation of the alpar@1: branch-and-cut framework, which is a set of data structures and alpar@1: routines intended for developing branch-and-cut methods for alpar@1: solving mixed-integer and combinatorial optimization problems. alpar@1: alpar@1: Detailed decsription of the branch-and-cut framework is given in alpar@1: the document "GLPK: A Preliminary Implementation of the alpar@1: Branch-And-Cut Framework" included in the distribution (see the alpar@1: file 'brcut.txt' in the subdirectory 'doc'). alpar@1: alpar@1: In order to illustrate how the GLPK branch-and-cut framework alpar@1: can be used for solving a particular optimization problem there alpar@1: is an example included in the package. This is a stand-alone alpar@1: program, TSPSOL, which is intended for solving to optimality the alpar@1: symmetric Traveling Salesman Problem (TSP), a classical problem alpar@1: of the combinatorial optimization (see the file 'tspsol.c' in alpar@1: the subdirectory 'sample'). alpar@1: alpar@1: GLPK 3.2 (release date: Jul 15, 2002) alpar@1: alpar@1: New edition of the document "GLPK: Reference Manual" was alpar@1: included (see the files 'refman.latex', 'refman.dvi', and alpar@1: 'refman.ps' in the subdirectory 'doc'). alpar@1: alpar@1: New edition of the document "GLPK: Modeling Language GLPK/L" was alpar@1: included (see the files 'lang.latex', 'lang.dvi', and 'lang.ps' alpar@1: in the subdirectory 'doc'). alpar@1: alpar@1: The following new API routines were added to the package: alpar@1: alpar@1: lpx_transform_row (transform explicitly specified row); alpar@1: lpx_transform_col (transform explicitly specified column); alpar@1: lpx_prim_ratio_test (perform primal ratio test); alpar@1: lpx_dual_ratio_test (perform dual ratio test); alpar@1: lpx_interior (solve LP problem using interior point method); alpar@1: lpx_get_ips_stat (query status of interior point solution); alpar@1: lpx_get_ips_row (obtain row interior point solution); alpar@1: lpx_get_ips_col (obtain column interior point solution); alpar@1: lpx_get_ips_obj (obtain interior point value of obj.func.); alpar@1: lpx_read_lpm (read LP/MIP model written in GLPK/L); alpar@1: lpx_write_mps (write problem data using MPS format); alpar@1: lpx_print_ips (print interior point solution). alpar@1: alpar@1: Detailed description of all these new API routines are given in alpar@1: the new edition of the reference manual. alpar@1: alpar@1: New version of the stand-alone solver glpsol (which is based on alpar@1: the new API) was implemented. alpar@1: alpar@1: So long as the new API (introduced in glpk 3.0) now provides alpar@1: all the functions, which were provided by the old API, the old alpar@1: API routines were removed from the package at all. alpar@1: alpar@1: GLPK 3.1 (release date: May 27, 2002) alpar@1: alpar@1: A preliminary implementation of new API routines was completed alpar@1: and included in the package. alpar@1: alpar@1: These new API routines provide much more flexible interaction alpar@1: between the application program, LP/MIP problem instances, and alpar@1: solver routines. Based on completely changed data structures alpar@1: they are, however, similar to the API routines and provide the alpar@1: same functionality. Please note that three routines, namely, alpar@1: solving LPs using interior point method, reading model written alpar@1: in the GLPK/L modeling language, and writing problem data in alpar@1: the MPS format, are not implemented in the new API, however, alpar@1: these routines are planned to be implemented in the next version alpar@1: of the package. alpar@1: alpar@1: A description of the new API routines is given in the document alpar@1: "GLPK Reference Manual", a draft edition of which is included alpar@1: in the package (see the files 'refman.latex', 'refman.dvi', and alpar@1: 'refman.ps' in the subdirectory 'doc'). alpar@1: alpar@1: Although the old API routines are kept in the package, they are alpar@1: no longer supported and will be removed in the future. alpar@1: alpar@1: GLPK 3.0.8 (release date: May 13, 2002) alpar@1: alpar@1: A preliminary implementation of new API routines was included alpar@1: in the package. These new API routines are intended to provide alpar@1: much more flexible interaction between the application program, alpar@1: LP/MIP problem and solver routines. See the document "New GLPK alpar@1: API Routines" (the file 'newapi.txt' in the subdirectory 'doc') alpar@1: also included in the package. alpar@1: alpar@1: The api routines glp_simplex2, glp_call_ipm1, glp_call_bbm1 were alpar@1: renamed, respectively, to glp_simplex, glp_interior, glp_integer alpar@1: in order to reflect changes in implementation. The api routines alpar@1: glp_call_rsm1, glp_simplex1, glp_pivot_in, glp_pivout_out were alpar@1: removed from the package since they are completely supreseded by alpar@1: the new API routines (however, these routines still can be found alpar@1: in the subdirectory 'oldsrc'). Please consult a new edition of alpar@1: the document "GLPK User's Guide" about all these changes in the alpar@1: existing api routines. alpar@1: alpar@1: The document "GLPK Library Reference" was removed from the alpar@1: package (into the subdirectory 'oldsrc') since it describes the alpar@1: obsolete library routines, most of which are no longer used. alpar@1: alpar@1: GLPK 3.0.7 (release date: Apr 22, 2002) alpar@1: alpar@1: A new, more efficient implementation of the primal/dual simplex alpar@1: method was included in the package. Due to some improvements the alpar@1: simplex-based solver allows solving many LP problems faster and alpar@1: provides more reliable results. Note that the new implementation alpar@1: is currently incomplete and available only via the api routine alpar@1: glp_simplex2. alpar@1: alpar@1: All the changes are transparent on API level. alpar@1: alpar@1: GLPK 3.0.6 (release date: Mar 28, 2002) alpar@1: alpar@1: New version of LU-factorization and basis maintenance routines alpar@1: (based on Forrest-Tomlin updating technique) was implemented. alpar@1: Since these new routines functionally supersede some routines alpar@1: (which implement other forms of the basis matrix) and make them alpar@1: obsolete, the latter were removed from the package (they still alpar@1: can be found in the subdirectory 'oldsrc'). alpar@1: alpar@1: All the changes are transparent on API level. alpar@1: alpar@1: GLPK 3.0.5 (release date: Jan 29, 2002) alpar@1: alpar@1: New edition of the document "GLPK User's Guide" was included in alpar@1: the distribution. Now it describes all additional API routines, alpar@1: which were recently added to the package. alpar@1: alpar@1: Structure of the package was re-organized in order to make its alpar@1: maintenance easier (all small files in the subdurectory 'source' alpar@1: were merged in bigger units). These changes are transparent for alpar@1: the user. alpar@1: alpar@1: GLPK 3.0.4 (release date: Dec 10, 2001) alpar@1: alpar@1: A new, more efficient implementation of the two-phase primal alpar@1: simplex method was included in the package. Due to some new alpar@1: features (an advanced initial basis, projected steepest edge, alpar@1: recursive updating values and reduced costs) the new LP solver alpar@1: is faster and numerically more stable than the old one. alpar@1: alpar@1: The new LP solver is available as API routine glp_simplex2 and alpar@1: has the same purpose as API routine glp_call_rsm1. For detailed alpar@1: specification see the file 'newapi.txt' in the directory 'doc'. alpar@1: alpar@1: Now the new LP solver is also used by default to solve an alpar@1: initial LP problem in the branch-and-bound routine glp_call_bbm1 alpar@1: instead the routine rsm1_driver. Note that the branch-and-bound alpar@1: procedure itself is still based on rsm1_driver. alpar@1: alpar@1: The new LP solver is also used as default solver in GLPSOL for alpar@1: solving LP and MIP problems. In order to choose the old solver alpar@1: the option '--old-sim' can be specified in the command line. alpar@1: alpar@1: GLPK 3.0.3 (release date: Oct 03, 2001) alpar@1: alpar@1: Some minor changes were made in the simplex method routines in alpar@1: order to improve numerical stability of the method. alpar@1: alpar@1: GLPK 3.0.2 (release date: Sep 24, 2001) alpar@1: alpar@1: A new implementation of the basis maintaining routines was alpar@1: included in the package. These routines, which are based on so alpar@1: called FHV-factorization (a variety of LU-factorization) of the alpar@1: basis matrix and Gustavson's data structures, allows performing alpar@1: the main operations faster at the expense of some worsening alpar@1: numerical accuracy. alpar@1: alpar@1: AFI (Advanced Form of the Inverse), which is the form of the alpar@1: basis matrix based on FHV-factorization, is available via the alpar@1: parameter form = 3 (on API level) or via the option --afi (in alpar@1: GLPSOL solver). alpar@1: alpar@1: GLPK 3.0.1 (release date: Aug 01, 2001) alpar@1: alpar@1: Old GLPK API routines have been removed from the package. alpar@1: alpar@1: New GLPK API routines were added: alpar@1: alpar@1: - scaling routines; alpar@1: alpar@1: - a routine for writing problem data in MPS format; alpar@1: alpar@1: - a comprehensive driver to the simplex method; alpar@1: alpar@1: - basis maintaining routines. alpar@1: alpar@1: A description of the new API routines is given in the document alpar@1: "Additional GLPK API Routines". This document is included into alpar@1: the distribution in plain text format (see the file 'newapi.txt' alpar@1: in the subdirectory 'doc'). alpar@1: alpar@1: Now the distribution includes a non-trivial example of using alpar@1: GLPK as a base LP solver for Concorde, a well known program that alpar@1: solves Traveling Salesman Problem (TSP). For further details see alpar@1: comments in the file 'sample/lpglpk30.c'. alpar@1: alpar@1: GLPK 3.0 (release date: Jul 19, 2001) alpar@1: alpar@1: Now GLPK is provided with new API, which being more flexible alpar@1: can be used in more complex algorithmic schemes. alpar@1: alpar@1: New edition of the document "GLPK User's Guide" is included in alpar@1: the distribution. Now it completely corresponds to the new GLPK alpar@1: API routines. alpar@1: alpar@1: Old API routines are not removed yet from the package, however alpar@1: they became obsolete and therefore should not be used. Since now alpar@1: the header glpk.h corresponds to new API, in order to compile alpar@1: existing programs that use old GLPK API routines the statement alpar@1: alpar@1: #define GLP_OLD_API alpar@1: alpar@1: should be inserted before the statement alpar@1: alpar@1: #include "glpk.h" alpar@1: alpar@1: GLPK 2.4.1 (release date: Jun 14, 2001) alpar@1: alpar@1: The document "Modeling language GLPK/L" is included into the alpar@1: distribution in texinfo format. alpar@1: alpar@1: New edition of the document "GLPK User's Guide" is included in alpar@1: the distribution. Now it describes all additional API routines alpar@1: which were recently added to the package. alpar@1: alpar@1: GLPK 2.4 (release date: May 10, 2001) alpar@1: alpar@1: Now GLPK includes an implementation of a preliminary version alpar@1: of the GLPK/L modeling language. This language is intended for alpar@1: writing mathematcal programming models. The name GLPK/L is alpar@1: derived from GNU Linear Programming Kit Language. alpar@1: alpar@1: A brief description of the GLPK/L language is given in the alpar@1: document "GLPK/L Modeling Language: A Brief Description". This alpar@1: document is included into the distribution in plain text format alpar@1: (see the file 'language.txt' in the subdirectory 'doc'). alpar@1: alpar@1: The language processor (which is a program that analyzes model alpar@1: description written in GLPK/L and translates it to internal data alpar@1: structures) is available as the GLPK API routine. alpar@1: alpar@1: The stand-alone solver GLPSOL now is able: a) to process model alpar@1: descriptions written in the GLPK/L language; b) to solve pure LP alpar@1: problems using the interior point method (therefore the program alpar@1: GLPIPM was removed from the package). alpar@1: alpar@1: GLPK 2.3 (release date: Apr 09, 2001) alpar@1: alpar@1: New edition of the document "GLPK User's Guide" is included in alpar@1: the distribution. Now it describes all additional API routines alpar@1: which were recently added to the package. alpar@1: alpar@1: The MIP solver was fully re-programmed in order to improve its alpar@1: robustness and performance. In particular, a basis recovering alpar@1: procedure was implemented (this procedure allows switching to alpar@1: the primal simplex method in case when the dual simplex method alpar@1: fails). alpar@1: alpar@1: GLPK 2.2 (release date: Mar 15, 2001) alpar@1: alpar@1: Now GLPK includes a tentative implementation of the alpar@1: branch-and-bound procedure based on the dual simplex method for alpar@1: mixed integer linear programming (MIP). alpar@1: alpar@1: Complete description of this new feature of the package is given alpar@1: in the preliminary document "Mixed Integer Linear Programming alpar@1: Using GLPK Version 2.2 (Supplement to GLPK User's Guide)". This alpar@1: document is included into the distribution in plain text format alpar@1: (see the file 'mip.txt' in the subdirectory 'doc'). alpar@1: alpar@1: The MIP solver (glp_integer) can be used as GLPK API routine in alpar@1: the same way as the pure LP solver (glp_simplex). alpar@1: alpar@1: The stand-alone program 'glpsol' is now able to solve LP as well alpar@1: as MIP problems. alpar@1: alpar@1: Note that the current version of GLPK MIP solver is based on alpar@1: easiest heuristics for branching and backtrackng. Therefore the alpar@1: solver is fit mainly for MIP problems which are not very hard alpar@1: and have few integer variables. alpar@1: alpar@1: GLPK 2.1 (release date: Feb 19, 2001) alpar@1: alpar@1: The document "GLPK Implementation of the Revised Simplex Method" alpar@1: is included into the distribution. This document describes most alpar@1: of routines related to the revised simplex method. alpar@1: alpar@1: GLPK 2.0 (release date: Jan 25, 2001) alpar@1: alpar@1: Now GLPK includes a tentative implementation of the primal-dual alpar@1: interior point method for large-scale linear programming. alpar@1: alpar@1: The interior point solver can be used as GLPK API routine in the alpar@1: same manner as the simplex method solver (glp_simplex): alpar@1: alpar@1: ret = glp_interior(); alpar@1: alpar@1: Note that currently the interior point solver implemented in alpar@1: GLPK doesn't include many important features, in particular: alpar@1: alpar@1: * it can't process dense columns; therefore if the problem has alpar@1: dense columns, the solving will be extremely inefficient; alpar@1: alpar@1: * it has no special features against numerical unstability; alpar@1: some problems may cause premature termination of the solving alpar@1: when the matrix A*D*A' becomes ill-conditioned; alpar@1: alpar@1: * it computes only values of primal (auxiliary and structural) alpar@1: variables and doesn't compute values of dual variables (i.e. alpar@1: reduced costs) which are just set to zero; alpar@1: alpar@1: * it doesn't identify optimal basis corresponding to the found alpar@1: interior point solution; all variables in the found solution alpar@1: are just marked as basic variables. alpar@1: alpar@1: GLPK also includes a stand-alone program 'glpipm' which is a alpar@1: demo based on the interior point method. It may be used in the alpar@1: same way as the program 'glpsol' that is based on the simplex alpar@1: method.