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