1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/NEWS Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,1532 @@
1.4 +GLPK 4.45 (release date: Dec 05, 2010)
1.5 +
1.6 + This is a bug-fix release.
1.7 +
1.8 + Several bugs/typos were fixed. Thanks to
1.9 + Xypron <xypron.glpk@gmx.de>,
1.10 + Robbie Morrison <robbie@actrix.co.nz>, and
1.11 + Ali Baharev <ali.baharev@gmail.com> for reports.
1.12 +
1.13 + Some glpk documents was re-formatted and merged into a single
1.14 + document. Now the glpk documentation consists of the following
1.15 + three main documents (all included in the distribution):
1.16 +
1.17 + GLPK: Reference Manual
1.18 +
1.19 + GLPK: Graph and Network Routines
1.20 +
1.21 + Modeling Language GNU MathProg: Language Reference
1.22 +
1.23 +GLPK 4.44 (release date: Jun 03, 2010)
1.24 +
1.25 + The following suffixes for variables and constraints were
1.26 + implemented in the MathProg language:
1.27 +
1.28 + .lb (lower bound),
1.29 + .ub (upper bound),
1.30 + .status (status in the solution),
1.31 + .val (primal value), and
1.32 + .dual (dual value).
1.33 +
1.34 + Thanks to Xypron <xypron.glpk@gmx.de> for draft implementation
1.35 + and testing.
1.36 +
1.37 + Now the MathProg language allows comment records (marked by
1.38 + '#' in the very first position) in CSV data files read with the
1.39 + table statements. Note that the comment records may appear only
1.40 + in the beginning of a CSV data file.
1.41 +
1.42 + The API routine glp_cpp to solve the Critical Path Problem was
1.43 + added and documented.
1.44 +
1.45 +GLPK 4.43 (release date: Feb 20, 2010)
1.46 +
1.47 + This is a maintainer release.
1.48 +
1.49 + `configure.ac' was changed to allow building the package under
1.50 + Mac OS and Darwin with ODBC support.
1.51 + Thanks to Xypron <xypron.glpk@gmx.de> for suggestions and Noli
1.52 + Sicad <nsicad@gmail.com> for testing.
1.53 +
1.54 + The SQL table driver was improved to process NULL data. Thanks
1.55 + to Xypron <xypron.glpk@gmx.de>.
1.56 +
1.57 + Some bugs were fixed in the LP/MIP preprocessor.
1.58 +
1.59 +GLPK 4.42 (release date: Jan 13, 2010)
1.60 +
1.61 + The following new API routines were added:
1.62 +
1.63 + glp_check_dup check for duplicate elements in sparse
1.64 + matrix
1.65 + glp_sort_matrix sort elements of the constraint matrix
1.66 + glp_read_prob read problem data in GLPK format
1.67 + glp_write_prob write problem data in GLPK format
1.68 + glp_analyze_bound analyze active bound of non-basic variable
1.69 + glp_analyze_coef analyze objective coefficient at basic
1.70 + variable
1.71 + glp_print_ranges print sensitivity analysis report (this
1.72 + routine replaces lpx_print_sens_bnds and
1.73 + makes it deprecated)
1.74 +
1.75 + For description of these new routines and the GLPK LP/MIP
1.76 + format see a new edition of the reference manual included in
1.77 + the distribution. (Chapter "Graph and network API routines" was
1.78 + carried out from the main reference manual and included in the
1.79 + distribution as a separate document.)
1.80 +
1.81 + The following new command-line options were added to the stand-
1.82 + alone solver glpsol:
1.83 + --glp filename read problem data in GLPK format
1.84 + --wglp filename write problem data in GLPK format
1.85 + --ranges filename print sensitivity analysis report (this
1.86 + option replaces --bounds)
1.87 +
1.88 + Now all GLPK routines performing file I/O support special
1.89 + filenames "/dev/stdin", "/dev/stdout", and "/dev/stderr", which
1.90 + can be specified in the same way as regular filenames. This
1.91 + feature is plaform-independent.
1.92 +
1.93 +GLPK 4.41 (release date: Dec 21, 2009)
1.94 +
1.95 + The following new API routies were added:
1.96 +
1.97 + glp_transform_row transform explicitly specified row
1.98 + glp_transform_col transform explicitly specified column
1.99 + glp_prim_rtest perform primal ratio test
1.100 + glp_dual_rtest perform dual ratio test
1.101 +
1.102 + For description of these new routines see a new edition of the
1.103 + reference manual included in the distribution.
1.104 +
1.105 + The following API routines are deprecated: lpx_transform_row,
1.106 + lpx_transform_col, lpx_prim_ratio_test, lpx_dual_ratio_test.
1.107 +
1.108 + Some improvements were made in the MIP solver (glp_intopt).
1.109 +
1.110 + The SQL table driver used to read/write data in MathProg models
1.111 + was changed to allow multiple arguments separated by semicolon
1.112 + in SQL statements. Thanks to Xypron <xypron.glpk@gmx.de>.
1.113 +
1.114 + Two new options were added to the glpsol stand-alone solver:
1.115 + --seed value (to initialize the pseudo-random number generator
1.116 + used in MathProg models with specified value), and
1.117 + --ini filename (to use a basis previously saved with -w option
1.118 + as an initial basis on solving similar LP's).
1.119 +
1.120 + Two new MathProg example models were included. Thanks to
1.121 + Nigel Galloway <nigel_galloway@operamail.com> and Noli Sicad
1.122 + <nsicad@gmail.com> for contribution.
1.123 +
1.124 + Scripts to build GLPK with Microsoft Visual Studio 2010 for
1.125 + both 32-bit and 64-bit Windows were included. Thanks to Xypron
1.126 + <xypron.glpk@gmx.de> for contribution and testing.
1.127 +
1.128 +GLPK 4.40 (release date: Nov 03, 2009)
1.129 +
1.130 + The following new API routines were added:
1.131 +
1.132 + glp_del_vertices remove vertices from graph
1.133 + glp_del_arc remove arc from graph
1.134 + glp_wclique_exact find maximum weight clique with the exact
1.135 + algorithm developed by Prof. P. Ostergard
1.136 + glp_read_ccdata read graph in DIMACS clique/coloring
1.137 + format
1.138 + glp_write_ccdata write graph in DIMACS clique/coloring
1.139 + format
1.140 +
1.141 + For description of these new routines see a new edition of the
1.142 + reference manual included in the distribution.
1.143 +
1.144 + The hybrid pseudocost branching heuristic was included in the
1.145 + MIP solver. It is available on API level (iocp.br_tech should
1.146 + be set to GLP_BR_PCH) and in the stand-alone solver glpsol
1.147 + (via the command-line option --pcost). This heuristic may be
1.148 + useful on solving hard MIP instances.
1.149 +
1.150 + The branching heuristic by Driebeck and Tomlin (used in the
1.151 + MIP solver by default) was changed to switch to branching on
1.152 + most fractional variable if an lower bound of degradation of
1.153 + the objective is close to zero for all branching candidates.
1.154 +
1.155 + A bug was fixed in the LP preprocessor (routine npp_empty_col).
1.156 + Thanks to Stefan Vigerske <stefan@math.hu-berlin.de> for the
1.157 + bug report.
1.158 +
1.159 + A bug was fixed and some improvements were made in the FPUMP
1.160 + heuristic module. Thanks to Xypron <xypron.glpk@gmx.de>.
1.161 +
1.162 + A bug was fixed in the API routine glp_warm_up (dual
1.163 + feasibility test was incorrect in maximization case). Thanks to
1.164 + Uday Venkatadri <Uday.Venkatadri@dal.ca> for the bug report.
1.165 +
1.166 +GLPK 4.39 (release date: Jul 26, 2009)
1.167 +
1.168 + The following new API routines were added:
1.169 +
1.170 + glp_warm_up "warm up" LP basis
1.171 + glp_set_vertex_name assign (change) vertex name
1.172 + glp_create_v_index create vertex name index
1.173 + glp_find_vertex find vertex by its name
1.174 + glp_delete_v_index delete vertex name index
1.175 + glp_read_asnprob read assignment problem data in DIMACS
1.176 + format
1.177 + glp_write_asnprob write assignment problem data in DIMACS
1.178 + format
1.179 + glp_check_asnprob check correctness of assignment problem
1.180 + data
1.181 + glp_asnprob_lp convert assignment problem to LP
1.182 + glp_asnprob_okalg solve assignment problem with the
1.183 + out-of-kilter algorithm
1.184 + glp_asnprob_hall find bipartite matching of maxumum
1.185 + cardinality with Hall's algorithm
1.186 +
1.187 + Also were added some API routines to read plain data files.
1.188 +
1.189 + The API routines glp_read_lp and glp_write_lp to read/write
1.190 + files in CPLEX LP format were re-implemented. Now glp_write_lp
1.191 + correctly writes double-bounded (ranged) rows by introducing
1.192 + slack variables rather than by duplicating the rows.
1.193 +
1.194 + For description of these new routines see a new edition of the
1.195 + reference manual included in the distribution.
1.196 +
1.197 + The 'xfree(NULL)' bug was fixed in the AMD routines. Thanks to
1.198 + Niels Klitgord <niels@bu.edu> for bug report.
1.199 +
1.200 + The message "Crashing..." was changed to "Constructing initial
1.201 + basis..." due to suggestion by Thomas Kahle <tom111@gmx.de>.
1.202 +
1.203 + Some typos were corrected in glpsol output messages. Thanks to
1.204 + Xypron <xypron.glpk@gmx.de> for patch.
1.205 +
1.206 +GLPK 4.38 (release date: May 02, 2009)
1.207 +
1.208 + API routines glp_read_mps and glp_write_mps were improved.
1.209 +
1.210 + Some improvements were made in the dual simplex routines.
1.211 +
1.212 + Two external software modules AMD and COLAMD were included in
1.213 + the distribution (for more details please see src/amd/README
1.214 + and src/colamd/README). Now they are used in the interior-point
1.215 + solver to reorder the matrix prior to Cholesky factorization.
1.216 +
1.217 + API routine glp_ipt_status may return two new statuses due to
1.218 + changes in the routine glp_interior. For details please see the
1.219 + reference manual included in the distribution.
1.220 +
1.221 + A minor bug was fixed in the graph/network routines. Thanks to
1.222 + Nelson H. F. Beebe <beebe@math.utah.edu> for bug report.
1.223 +
1.224 +GLPK 4.37 (release date: Mar 29, 2009)
1.225 +
1.226 + The 0-1 Feasibility Pump heuristic was included in the GLPK
1.227 + integer optimizer glp_intopt. On API level the heuristic can be
1.228 + enabled by setting the parameter fp_heur in glp_iocp to GLP_ON.
1.229 + This feature is also available in the solver glpsol through
1.230 + command-line option '--fpump'. For more details please see the
1.231 + reference manual included in the distribution.
1.232 +
1.233 + The following new API routines were added:
1.234 +
1.235 + glp_print_sol write basic solution in printable format
1.236 + glp_print_ipt write interior-point solution in printable
1.237 + format
1.238 + glp_print_mip write MIP solution in printable format
1.239 + glp_read_graph read (di)graph from plain text file
1.240 + glp_write_graph write (di)graph to plain text file
1.241 + glp_weak_comp find all weakly connected components
1.242 + glp_strong_comp find all strongly connected components
1.243 +
1.244 + The following API routines are deprecated: lpx_print_sol,
1.245 + lpx_print_ips, lpx_print_mip, lpx_print_prob (the latter is
1.246 + equivalent to glp_write_lp).
1.247 +
1.248 + A bug was fixed in the interior-point solver (glp_interior) to
1.249 + correctly compute dual solution components when the problem is
1.250 + scaled.
1.251 +
1.252 + The files configure.ac and Makefile.am were changed:
1.253 + (a) to allow using autoreconf/autoheader;
1.254 + (b) to allow building the package in a directory other than its
1.255 + source directory.
1.256 + Thanks to Marco Atzeri <marco_atzeri@yahoo.it> for bug report.
1.257 +
1.258 + An example model in the GNU MathProg language was added.
1.259 + Thanks to Larry D'Agostino <Larry.D'Agostino@gmacrescap.com> for
1.260 + contribution.
1.261 +
1.262 +GLPK 4.36 (release date: Feb 06, 2009)
1.263 +
1.264 + The following new API routines were added to the package:
1.265 +
1.266 + glp_mincost_okalg find minimum-cost flow with out-of-kilter
1.267 + algorithm
1.268 + glp_maxflow_ffalg find maximal flow with Ford-Fulkerson
1.269 + algorithm
1.270 +
1.271 + For detailed description of these new routines and related data
1.272 + structures see chapter "Graph and Network API Routines" in a new
1.273 + edition of the reference manual included in the distribution.
1.274 +
1.275 + The following two new command-line options were added to the
1.276 + solver glpsol:
1.277 +
1.278 + --mincost read min-cost flow data in DIMACS format
1.279 + --maxflow read maximum flow data in DIMACS format
1.280 +
1.281 + Duplicate symbols in the header glpk.h were removed to allow
1.282 + using swig.
1.283 + Thanks to Kelly Westbrooks <kellywestbrooks@yahoo.com> and
1.284 + Nigel Galloway <nigel_galloway@operamail.com> for suggestion.
1.285 +
1.286 + A minor defect was fixed in the routine glp_write_lp.
1.287 + Thanks to Sebastien Briais <sbriais@free.fr> for bug report.
1.288 +
1.289 + A minor bug was fixed in the SQL module.
1.290 + Thanks to Xypron <xypron.glpk@gmx.de> for patch.
1.291 +
1.292 + Some new example models in the GNU MathProg modeling language
1.293 + were added. Thanks to Sebastian Nowozin <nowozin@gmail.com> and
1.294 + Nigel Galloway <nigel_galloway@operamail.com> for contribution.
1.295 +
1.296 +GLPK 4.35 (release date: Jan 09, 2009)
1.297 +
1.298 + The following new API routines were added to the package:
1.299 +
1.300 + glp_create_graph create graph
1.301 + glp_set_graph_name assign (change) graph name
1.302 + glp_add_vertices add new vertices to graph
1.303 + glp_add_arc add new arc to graph
1.304 + glp_erase_graph erase graph content
1.305 + glp_delete_graph delete graph
1.306 + glp_read_mincost read minimum cost flow problem data in
1.307 + DIMACS format
1.308 + glp_write_mincost write minimum cost flow problem data in
1.309 + DIMACS format
1.310 + glp_mincost_lp convert minimum cost flow problem to LP
1.311 + glp_netgen Klingman's network problem generator
1.312 + glp_gridgen grid-like network problem generator
1.313 + glp_read_maxflow read maximum flow problem data in DIMACS
1.314 + format
1.315 + glp_write_maxflow write maximum flow problem data in DIMACS
1.316 + format
1.317 + glp_maxflow_lp convert maximum flow problem to LP
1.318 + glp_rmfgen Goldfarb's maximum flow problem generator
1.319 +
1.320 + For detailed description of these new routines and related data
1.321 + structures see chapter "Graph and Network API Routines" in a new
1.322 + edition of the reference manual included in the distribution.
1.323 +
1.324 + A minor change were made in the internal routine xputc. Thanks
1.325 + to Luiz Bettoni <bettoni@cpgei.ct.utfpr.edu.br> for suggestion.
1.326 +
1.327 + A minor bug was fixed in the internal routine mpl_fn_time2str.
1.328 + Thanks to Stefan Vigerske <stefan@vigerske.de> for bug report.
1.329 +
1.330 +GLPK 4.34 (release date: Dec 04, 2008)
1.331 +
1.332 + The GNU MathProg modeling language was supplemented with three
1.333 + new built-in functions:
1.334 +
1.335 + gmtime obtaining current calendar time
1.336 + str2time converting character string to calendar time
1.337 + time2str converting calendar time to character string
1.338 +
1.339 + (Thanks to Xypron <xypron.glpk@gmx.de>.)
1.340 +
1.341 + For detailed description of these functions see Appendix A in
1.342 + the document "Modeling Language GNU MathProg", a new edition of
1.343 + which was included in the distribution.
1.344 +
1.345 + A bug was fixed in the MIP solver. Thanks to Nigel Galloway
1.346 + <nigel_galloway@operamail.com> for bug report.
1.347 +
1.348 + A new makefile was added to build the GLPK DLL with Microsoft
1.349 + Visual Studio Express 2008 for 64-bit Windows. Thanks to Xypron
1.350 + <xypron.glpk@gmx.de> for contribution and testing.
1.351 +
1.352 +GLPK 4.33 (release date: Oct 30, 2008)
1.353 +
1.354 + The following new API routines were added to the package:
1.355 + glp_copy_prob copy problem object content
1.356 + glp_exact solve LP in exact arithmetic
1.357 + (makes lpx_exact deprecated)
1.358 + glp_get_unbnd_ray determine variable causing unboundedness
1.359 + (makes lpx_get_ray_info deprecated)
1.360 + glp_interior solve LP with interior-point method
1.361 + (makes lpx_interior deprecated)
1.362 +
1.363 + The following new API routines for processing models written in
1.364 + the GNU Mathprog language were added to the package:
1.365 + glp_mpl_alloc_wksp allocate the translator workspace
1.366 + glp_mpl_read_model read and translate model section
1.367 + glp_mpl_read_data read and translate data section
1.368 + glp_mpl_generate generate the model
1.369 + glp_mpl_build_prob build LP/MIP instance from the model
1.370 + glp_mpl_postsolve postsolve the model
1.371 + glp_mpl_free_wksp deallocate the translator workspace
1.372 + (These routines make lpx_read_model deprecated.)
1.373 +
1.374 + For description of all these new API routines see the reference
1.375 + manual included in the distribution.
1.376 +
1.377 + A crude implementation of CPLEX-like interface to GLPK API was
1.378 + added to the package. Currently it allows using GLPK as a core
1.379 + LP solver for Concorde, a well known computer code for solving
1.380 + the symmetric TSP. For details see examples/cplex/README.
1.381 +
1.382 + Some bugs were fixed in the SQL table driver. Thanks to Xypron
1.383 + <xypron.glpk@gmx.de>.
1.384 +
1.385 +GLPK 4.32 (release date: Oct 03, 2008)
1.386 +
1.387 + The following new features were included in the MIP solver
1.388 + (the API routine glp_intopt):
1.389 +
1.390 + * MIP presolver
1.391 + * mixed cover cut generator
1.392 + * clique cut generator
1.393 + * Euclidean reduction of the objective value
1.394 +
1.395 + Due to changes the routine glp_intopt may additionally return
1.396 + GLP_ENOPFS, GLP_ENODFS, and GLP_EMIPGAP.
1.397 +
1.398 + The API routines lpx_integer are lpx_intopt are deprecated,
1.399 + since they are completely superseded by glp_intopt.
1.400 +
1.401 + The following new branch-and-cut API routines were added:
1.402 + glp_ios_row_attr determine additional row attributes
1.403 + glp_ios_pool_size determine current size of the cut pool
1.404 + glp_ios_add_row add constraint to the cut pool
1.405 + glp_ios_del_row delete constraint from the cut pool
1.406 + glp_ios_clear_pool delete all constraints from the cut pool
1.407 +
1.408 + For description of these new routines see the reference manual
1.409 + included in the distribution.
1.410 +
1.411 + The stand-alone solver glpsol was changed to allow multiple
1.412 + data files.
1.413 +
1.414 + A new edition of the supplement "Using Data Tables in the GNU
1.415 + MathProg Modeling Language" was included.
1.416 +
1.417 + As usual, some bugs were fixed (in the MathProg translator).
1.418 + Thanks to Xypron <xypron.glpk@gmx.de>.
1.419 +
1.420 +GLPK 4.31 (release date: Sep 02, 2008)
1.421 +
1.422 + The core LP solver based on the dual simplex method was
1.423 + re-implemented and now it provides both phases I and II.
1.424 +
1.425 + The following new API routines were added:
1.426 + glp_scale_prob automatic scaling of problem data
1.427 + glp_std_basis construct standard initial LP basis
1.428 + glp_adv_basis construct advanced initial LP basis
1.429 + glp_cpx_basis construct Bixby's initial LP basis
1.430 +
1.431 + For description of these new routines see the reference manual
1.432 + included in the distribution.
1.433 +
1.434 + The following API routines are deprecated:
1.435 + lpx_scale_prob, lpx_std_basis, lpx_adv_basis, lpx_cpx_basis.
1.436 +
1.437 + Necessary changes were made in memory allocation routines to
1.438 + resolve portability issues for 64-bit platforms.
1.439 +
1.440 + New version of the routine lpx_write_pb to write problem data
1.441 + in OPB (pseudo boolean format) was added to the package. Thanks
1.442 + to Oscar Gustafsson <oscarg@isy.liu.se> for the contribution.
1.443 +
1.444 + Two new makefiles were added to build the package for 32- and
1.445 + 64-bit Windows with Microsoft Visual Studio Express 2008.
1.446 + Thanks to Heinrich Schuchardt <heinrich.schuchardt@gmx.de> (aka
1.447 + Xypron) for the contribution and testing.
1.448 +
1.449 + Two new makefiles were added to build the package with Digital
1.450 + Mars C/C++ 8.50 and Open Watcom C/C++ 1.6 (for 32-bit Windows).
1.451 +
1.452 +GLPK 4.30 (release date: Aug 13, 2008)
1.453 +
1.454 + The core LP solver based on the primal simplex method was
1.455 + re-implemented to allow its further improvements. Currently the
1.456 + new version provides the same features as the old one, however,
1.457 + it is a bit faster and more numerically stable.
1.458 +
1.459 + Some changes were made in the MathProg translator to allow <,
1.460 + <=, >=, and > on comparing symbolic values. Thanks to Heinrich
1.461 + Schuchardt <heinrich.schuchardt@gmx.de> for patches.
1.462 +
1.463 + Internal routine set_d_eps in the exact LP solver was changed
1.464 + to prevent approximation errors in case of integral data.
1.465 + Thanks to Markus Pilz <pilz@cs.uni-bonn.de> for bug report.
1.466 +
1.467 +GLPK 4.29 (release date: Jul 06, 2008)
1.468 +
1.469 + The configure script was changed to disable all optional
1.470 + features by default. For details please see file INSTALL.
1.471 +
1.472 + The following new API routines were added:
1.473 + glp_erase_prob erase problem object content
1.474 + glp_read_mps read problem data in MPS format
1.475 + glp_write_mps write problem data in MPS format
1.476 + glp_read_lp read problem data in CPLEX LP format
1.477 + glp_write_lp write problem data in CPLEX LP format
1.478 +
1.479 + For description of these new routines see the reference manual
1.480 + included in the distribution.
1.481 +
1.482 + The following API routines are deprecated:
1.483 + lpx_read_mps, lpx_read_freemps, lpx_write_mps,
1.484 + lpx_write_freemps, lpx_read_cpxlp, and lpx_write_cpxlp.
1.485 +
1.486 + Two bugs were fixed. Thanks to
1.487 + Anne-Laurence Putz <anne-laurence.putz@eurodecision.com> and
1.488 + Xypron <xypron.glpk@gmx.de> for bug report.
1.489 +
1.490 +GLPK 4.28 (release date: Mar 25, 2008)
1.491 +
1.492 + The iODBC and MySQL table drivers, which allows transmitting
1.493 + data between MathProg model objects and relational databases,
1.494 + were re-implemented to replace a static linking by a dynamic
1.495 + linking to corresponding shared libraries.
1.496 + Many thanks to Heinrich Schuchardt <heinrich.schuchardt@gmx.de>
1.497 + for the contribution, Rafael Laboissiere <rafael@debian.org>
1.498 + for useful advices concerning the shared library support under
1.499 + GNU/Linux, and Vijay Patil <vijay.patil@gmail.com> for testing
1.500 + this feature under Windows XP.
1.501 +
1.502 + A new optional feature was added to the package. This feature
1.503 + is based on the zlib data compression library and allows GLPK
1.504 + API routines and the stand-alone solver to read and write
1.505 + compressed data files performing compression/decompression "on
1.506 + the fly" (compressed data files are recognized by suffix `.gz'
1.507 + in the file name). It may be useful in case of large MPS files
1.508 + to save the disk space (up to ten times).
1.509 +
1.510 + The `configure' script was re-implemented. Now it supports the
1.511 + following specific options:
1.512 +
1.513 + --with-gmp Enable using the GNU MP bignum library
1.514 + --without-gmp Disable using the GNU MP bignum library
1.515 + --with-zlib Enable using the zlib data compression
1.516 + library
1.517 + --without-zlib Disable using the zlib data compression
1.518 + library
1.519 + --enable-dl Enable shared library support (auto check)
1.520 + --enable-dl=ltdl Enable shared library support (GNU)
1.521 + --enable-dl=dlfcn Enable shared library support (POSIX)
1.522 + --disable-dl Disable shared library support
1.523 + --enable-odbc Enable using ODBC table driver
1.524 + --disable-odbc Disable using ODBC table driver
1.525 + --enable-mysql Enable using MySQL table driver
1.526 + --disable-mysql Disable using MySQL table driver
1.527 +
1.528 + For more details please see file INSTALL.
1.529 +
1.530 +GLPK 4.27 (release date: Mar 02, 2008)
1.531 +
1.532 + Three new table drivers were added to the MathProg translator:
1.533 +
1.534 + xBASE built-in table driver, which allows reading and writing
1.535 + data in .dbf format (only C and N fields are supported);
1.536 +
1.537 + MySQL table driver, which provides connection to a MySQL
1.538 + database;
1.539 +
1.540 + iODBC table driver, which provides connection to a database
1.541 + through ODBC.
1.542 +
1.543 + The MySQL and iODBC table drivers were contributed to GLPK by
1.544 + Heinrich Schuchardt <heinrich.schuchardt@gmx.de>.
1.545 +
1.546 + The table driver is a program module which allows transmitting
1.547 + data between MathProg model objects and external data tables.
1.548 +
1.549 + For detailed description of the table statement and table
1.550 + drivers see the document "Using Data Tables in the GNU MathProg
1.551 + Modeling Language" (file doc/tables.txt) included in the
1.552 + distribution. Some examples which demonstrate using MySQL and
1.553 + iODBC table drivers can be found in subdirectory examples/sql.
1.554 +
1.555 +GLPK 4.26 (release date: Feb 17, 2008)
1.556 +
1.557 + The table statement was implemented in the GNU MathProg
1.558 + modeling language. This new feature allows reading data from
1.559 + external tables into model objects such as sets and parameters
1.560 + as well as writing results of computations to external tables.
1.561 +
1.562 + A table is a (unordered) set of records, where each record
1.563 + consists of the same number of fields, and each field is
1.564 + provided with a unique symbolic name called the field name.
1.565 +
1.566 + Currently the GLPK package has the only built-in table driver,
1.567 + which supports tables in the CSV (comma-separated values) file
1.568 + format. This format is very simple and supported by almost all
1.569 + spreadsheets and database management systems.
1.570 +
1.571 + Detailed description of the table statement and CSV format can
1.572 + be found in file doc/tables.txt, included in the distribution.
1.573 +
1.574 +GLPK 4.25 (release date: Dec 19, 2007)
1.575 +
1.576 + A tentative implementation of Gomory's mixed integer cuts was
1.577 + included in the branch-and-cut solver. To enable generating
1.578 + Gomory's cuts the control parameter gmi_cuts passed to the
1.579 + routine glp_intopt should be set to GLP_ON. This feature is
1.580 + also available in the solver glpsol through command-line option
1.581 + '--gomory'. For more details please see the reference manual
1.582 + included in the distribution.
1.583 +
1.584 +GLPK 4.24 (release date: Nov 21, 2007)
1.585 +
1.586 + A tentative implementation of MIR (mixed integer rounding) cuts
1.587 + was included in the MIP solver. To enable generating MIR cuts
1.588 + the control parameter mir_cuts passed to the routine glp_intopt
1.589 + should be set to GLP_ON. This feature is also available in the
1.590 + stand-alone solver glpsol via command-line option '--mir'. For
1.591 + more details please see the reference manual included in the
1.592 + distribution.
1.593 +
1.594 + The implementation is mainly based on the following two papers:
1.595 +
1.596 + 1. H. Marchand and L. A. Wolsey. Aggregation and mixed integer
1.597 + rounding to solve MIPs. CORE discussion paper 9839, CORE,
1.598 + Universite catholique de Louvain, June 1998.
1.599 +
1.600 + 2. G. Andreello, A. Caprara, and M. Fischetti. Embedding cuts
1.601 + in a Branch&Cut framework. Preliminary draft, October 2003.
1.602 +
1.603 + MIR cuts can be generated on any level of the search tree that
1.604 + makes the GLPK MIP solver to be a real branch-and-cut solver.
1.605 +
1.606 + A bug was fixed in the routine lpx_write_cpxlp. If a variable
1.607 + x has upper bound and no lower bound, it should appear in the
1.608 + bounds section as "-inf <= x <= u", not as "x <= u". Thanks to
1.609 + Enric Rodriguez <erodri@lsi.upc.edu> for the bug report.
1.610 +
1.611 +GLPK 4.23 (release date: Oct 28, 2007)
1.612 +
1.613 + The following new API routines were added:
1.614 +
1.615 + glp_read_sol read basic solution from text file
1.616 + glp_write_sol write basic solution to text file
1.617 + glp_read_ipt read interior-point solution from text file
1.618 + glp_write_ipt write interior-point solution to text file
1.619 + glp_read_mip read MIP solution from text file
1.620 + glp_write_mip write MIP solution to text file
1.621 +
1.622 + For description of these routines and corresponding file
1.623 + formats see Chapter "API Routines", Section "Utility routines"
1.624 + in the reference manual included in the distribution.
1.625 +
1.626 + Advanced API routine glp_free_env was added. It may be used by
1.627 + the application program to free all resources allocated by GLPK
1.628 + routines.
1.629 +
1.630 + The following three new command-line options were added to the
1.631 + solver glpsol:
1.632 +
1.633 + --mipgap tol set relative MIP gap tolerance
1.634 + -r filename read solution from filename
1.635 + -w filename write solution to filename
1.636 +
1.637 +GLPK 4.22 (release date: Sep 19, 2007)
1.638 +
1.639 + This is a maintainer release.
1.640 +
1.641 + A bug was fixed in the MIP preprocessor (ios_preprocess_node).
1.642 + Thanks to Roberto Bagnara <bagnara@cs.unipr.it> (Department of
1.643 + Mathematics, University of Parma, Italy) for the bug report.
1.644 +
1.645 + A bug was fixed in the MIP preprocessor (col_implied_bounds),
1.646 + due to which constraint coefficients with small magnitude could
1.647 + lead to wrong implied bounds of structural variables.
1.648 +
1.649 + A similar bug was fixed in the routine reduce_bounds.
1.650 +
1.651 + A bug was fixed in the routines glp_set_mat_row and
1.652 + glp_set_mat_col. (The bug appeared due to incorrect removing
1.653 + zero elements from the row/column lists.)
1.654 +
1.655 + A bug was fixed in the API routines lpx_read_mps and
1.656 + lpx_read_freemps, due to which bounds of type LI specified in
1.657 + BOUNDS section were incorrectly processed.
1.658 +
1.659 + A call to standard function vsprintf was replaced by a call to
1.660 + vsnprintf for security reasons. Many thanks to Peter T. Breuer
1.661 + <ptb@inv.it.uc3m.es> and Rafael Laboissiere <rafael@debian.org>.
1.662 +
1.663 +GLPK 4.21 (release date: Aug 28, 2007)
1.664 +
1.665 + Additional reasons for calling the callback routine used in the
1.666 + MIP solver (glp_intopt) were introduced. Currently the following
1.667 + reasons are supported:
1.668 +
1.669 + * request for subproblem selection
1.670 + * request for preprocessing
1.671 + * request for row generation
1.672 + * request for heuristic solution
1.673 + * request for cut generation
1.674 + * request for branching
1.675 + * better integer solution found
1.676 +
1.677 + A basic preprocessing component used to improve subproblem
1.678 + formulations by tightening bounds of variables was included in
1.679 + the MIP solver. Depending on the control parameter pp_tech
1.680 + passed to the routine glp_intopt the preprocessing can be
1.681 + performed either on the root level or on all levels (default)
1.682 + or can be disabled.
1.683 +
1.684 + Backtracking heuristic used by default in the MIP solver was
1.685 + changed to the "best local bound".
1.686 +
1.687 + For more details see Chapter "Advanced API routines", Section
1.688 + "Branch-and-bound interface routines" in a new edition of the
1.689 + reference manual included in the distribution.
1.690 +
1.691 +GLPK 4.20 (release date: Jul 26, 2007)
1.692 +
1.693 + API routine lpx_integer was replaced by API routine glp_intopt,
1.694 + which provides equivalent functionality and additionally allows
1.695 + the application to control the solution process by means of the
1.696 + user-written callback routine, which is called by the solver at
1.697 + various points of the branch-and-bound algorithm. Besides, the
1.698 + new MIP solver allows generating "lazy" constraints and cutting
1.699 + planes on all levels of the branch-and-bound tree, not only on
1.700 + the root level. The routine lpx_integer is also still available
1.701 + for the backward compatibility.
1.702 +
1.703 + The following new advanced API routines, which may be called
1.704 + from the B&B callback routine, were included in the package:
1.705 +
1.706 + glp_ios_reason determine reason for calling callback
1.707 + routine
1.708 + glp_ios_get_prob access the problem object
1.709 + glp_ios_tree_size determine size of the branch-and-bound tree
1.710 + glp_ios_curr_node determine current active subproblem
1.711 + glp_ios_next_node determine next active subproblem
1.712 + glp_ios_prev_node determine previous active subproblem
1.713 + glp_ios_up_node determine parent subproblem
1.714 + glp_ios_node_level determine subproblem level
1.715 + glp_ios_node_bound determine subproblem local bound
1.716 + glp_ios_mip_gap compute relative MIP gap
1.717 + glp_ios_heur_sol provide solution found by heuristic
1.718 + glp_ios_terminate terminate the solution process
1.719 +
1.720 + For description of these routines see Chapter "Advanced API
1.721 + routines", Section "Branch-and-bound interface routines" in a
1.722 + new edition of the reference manual, which was included in the
1.723 + distribution.
1.724 +
1.725 + Old version of the integer optimization suite (IOS) as well as
1.726 + TSP solver tspsol based on it are no longer supported and were
1.727 + removed from the package.
1.728 +
1.729 + A minor error in the MIP presolver was fixed; thanks to Graham
1.730 + Rockwell <bionomicron@gmail.com> for the bug report.
1.731 +
1.732 +GLPK 4.19 (release date: Jul 05, 2007)
1.733 +
1.734 + The principal change is upgrading to GPLv3.
1.735 +
1.736 + A serious bug in the routine glp_del_cols was fixed; thanks to
1.737 + Cedric[FR] <fox2113@wanadoo.fr> for the bug report. The bug
1.738 + appeared because on deleting non-basic columns the basis header
1.739 + remained valid, however, contained invalid (old) column ordinal
1.740 + numbers.
1.741 +
1.742 + A new advanced API routine glp_mem_limit was added.
1.743 +
1.744 + The case GLP_EBOUND was added to the routine lpx_simplex.
1.745 + Thanks to Cameron Kellough <Cameron.Kellough@sri.com> for the
1.746 + bug report.
1.747 +
1.748 + An API routine lpx_write_pb to write the problem instance in
1.749 + OPB (pseudo boolean) format format was added. Thanks to Oscar
1.750 + Gustafsson <oscarg@isy.liu.se> for the contribution.
1.751 +
1.752 + Two new options --wpb and --wnpb were added to glpsol to write
1.753 + the problem instance in OPB format.
1.754 +
1.755 +GLPK 4.18 (release date: Jun 25, 2007)
1.756 +
1.757 + The following new API routines were added:
1.758 +
1.759 + glp_set_rii set (change) row scale factor
1.760 + glp_set_sjj set (change) column scale factor
1.761 + glp_get_rii retrieve row scale factor
1.762 + glp_get_sjj retrieve column scale factor
1.763 + glp_simplex solve LP problem with the simplex method
1.764 + (this routine replaces lpx_simplex, which is
1.765 + also available for backward compatibility)
1.766 + glp_init_smcp initialize simplex method control params
1.767 + glp_bf_exists check if the basis factorization exists
1.768 + glp_factorize compute the basis factorization
1.769 + glp_bf_updated check if the basis factorization has been
1.770 + updated
1.771 + glp_get_bfcp retrieve basis factorization control params
1.772 + glp_set_bfcp change basis factorization control params
1.773 + glp_get_bhead retrieve the basis header information
1.774 + glp_get_row_bind retrieve row index in the basis header
1.775 + glp_get_col_bind retrieve column index in the basis header
1.776 + glp_ftran perform forward transformation
1.777 + glp_btran perform backward transformation
1.778 +
1.779 + For description of all these routines see a new edition of the
1.780 + reference manual included in the distribution.
1.781 +
1.782 + Type names ulong_t and uldiv_t were changed to glp_ulong and
1.783 + glp_uldiv to avoid conflicts with standard type names on some
1.784 + platforms. Thanks to Boris Wirtz <Boris.Wirtz@uni-oldenburg.de>
1.785 + for the bug report.
1.786 +
1.787 + Some new examples in the MathProg language were added. Thanks
1.788 + to Sebastian Nowozin <nowozin@gmail.com>.
1.789 +
1.790 +GLPK 4.17 (release date: May 26, 2007)
1.791 +
1.792 + API routines glp_set_mat_row, glp_set_mat_col, and glp_load_mat
1.793 + were modified to allow zero constraint coefficients (which are
1.794 + not stored in the constraint matrix). Note that constraint
1.795 + coefficients with duplicate row/column indices are not allowed.
1.796 +
1.797 + Another form of LP basis factorization was implemented in the
1.798 + package. It is based on LU-factorization of an initial basis
1.799 + and Schur complement to reflect changes in the basis. Currently
1.800 + the implementation is incomplete and provides only updating the
1.801 + factorization on replacing a column of the basis matrix. On API
1.802 + level the user can set the control parameter LPX_K_BFTYPE to
1.803 + choose between the folloiwng forms of LP basis factorization to
1.804 + be used in the simplex method routines:
1.805 + 1) LU + Forrest-Tomlin update;
1.806 + 2) LU + Schur complement + Bartels-Golub update;
1.807 + 3) LU + Schur complement + Givens rotation update.
1.808 + The GLPK implementation is similar to LUSOL/LUMOD developed by
1.809 + Michael A. Saunders.
1.810 +
1.811 + The user can choose the form of LP basis factorzation used by
1.812 + the simplex method routines by specifying the folloiwng options
1.813 + of glpsol: --luf, --cbg, --cgr.
1.814 +
1.815 +GLPK 4.16 (release date: May 05, 2007)
1.816 +
1.817 + A number of basic GLPK API routines, which now are in the
1.818 + stable stable, were renamed to be prefixed with 'glp_'. Note
1.819 + that all these routines are available via their old names
1.820 + prefixed with 'lpx_' that keeps the downward compatibility with
1.821 + older versions of the package.
1.822 +
1.823 + Three new GLPK API routines were added to the package:
1.824 + glp_version, glp_term_hook, and glp_mem_usage; for more details
1.825 + see a new edition of the GLPK reference manual included in the
1.826 + distribution. The routine glp_version reports the actual version
1.827 + of the GLPK library and also can be used (along with the header
1.828 + glpk.h) in Autotools specification files to check if the GLPK
1.829 + library has been installed.
1.830 +
1.831 + The header glpk.h was changed to conform to C++ environment.
1.832 +
1.833 +GLPK 4.15 (release date: Feb 18, 2007)
1.834 +
1.835 + Autotools specification files (configure.ac, Makefile.am) were
1.836 + changed to use GNU Libtool. This allows building the static as
1.837 + well as shared GLPK library.
1.838 +
1.839 +GLPK 4.14 (release date: Feb 05, 2007)
1.840 +
1.841 + Now GLPK conforms to ILP32, LLP64, and LP64 programming models
1.842 + (the latter seems to be the ultimate choice regarding 64-bit
1.843 + architectures). Note that GLPK itself is a 32-bit application,
1.844 + and the conformity only means that the package works correctly
1.845 + on all these arenae. Nevertheless, on 64-bit platforms it is
1.846 + possible to use more than 4GB of memory, if necessary.
1.847 +
1.848 +GLPK 4.13 (release date: Nov 13, 2006)
1.849 +
1.850 + A tentative implementation of the "exact" simplex method based
1.851 + on bignum (rational) arithmetic was included in the package.
1.852 +
1.853 + On API level this new feature is available through the routine
1.854 + lpx_exact, which is similar to the routine lpx_simplex.
1.855 +
1.856 + In the solver glpsol this feature is available through two new
1.857 + command-line options: --exact and --xcheck. If the '--exact'
1.858 + option is specified, glpsol solves LP instance using the exact
1.859 + simplex method; in case of MIP it is used to obtain optimal
1.860 + solution of LP relaxation. If the --xcheck option is specified,
1.861 + LP instance (or LP relaxation) is solved using the standard
1.862 + (floating-point) simplex method, however, then glpsol calls the
1.863 + exact simplex routine to make sure that the final LP basis is
1.864 + exactly optimal, and if it is not, to perform some additional
1.865 + simplex iterations in exact arithmetic.
1.866 +
1.867 +GLPK 4.12 (release date: Nov 08, 2006)
1.868 +
1.869 + A tentative implementation of some simplex method routines
1.870 + based on exact (bignum) arithmetic was included in the package.
1.871 + Currently these routines provide computing LU-factorization of
1.872 + the basis matrix and computing components of basic solution.
1.873 +
1.874 + These routines were used to implement a routine, which checks
1.875 + primal and dual feasibility of basic solution exactly, i.e. in
1.876 + rational numbers, without round-off errors. In glpsol this
1.877 + feature is available through the command-line option --xcheck.
1.878 +
1.879 + GLPK has its own low-level routines implementing operations on
1.880 + integer and rational numbers that makes it independent on other
1.881 + software packages. However, to attain a much better performance
1.882 + it is highly recommended to install (before configuring GLPK)
1.883 + the GNU Multiple Precision Arithmetic Library (GMP). Using GMP
1.884 + makes computations 100-200 times faster.
1.885 +
1.886 +GLPK 4.11 (release date: Jul 25, 2006)
1.887 +
1.888 + Three new built-in functions in the modeling language were
1.889 + implemented: card (cardinality of set), length (length of
1.890 + character string), and substr (substring of character string).
1.891 + Another improvement concerns the printf statement which now
1.892 + allows redirecting its output to a specified file. These new
1.893 + features are illustrated in example models crypto.mod and
1.894 + graph.mod included in the distribution. For more details see
1.895 + the document "Modeling Language GNU MathProg".
1.896 +
1.897 + Four batch files (along with corresponding makefiles) were
1.898 + included in the distribution to simplify building GLPK under
1.899 + MS Windows; see them in subdirectory 'w32'.
1.900 +
1.901 +GLPK 4.10 (release date: May 11, 2006)
1.902 +
1.903 + Cutting planes of two new classes were implemented: mixed cover
1.904 + cuts and clique cuts. On API level this feature can be enabled
1.905 + by setting control parameter LPX_K_USECUTS passed to the routine
1.906 + lpx_intopt. In glpsol this feature is available through the
1.907 + command-line options --cover and --clique. For more details see
1.908 + the reference manual.
1.909 +
1.910 + Now the routines lpx_read_mps and lpx_read_freemps support LI
1.911 + bound type. It is similar to LO, however, indicates the column
1.912 + as of integer kind.
1.913 +
1.914 +GLPK 4.9 (release date: Jan 17, 2006)
1.915 +
1.916 + An advanced MIP solver was implemented. It includes:
1.917 +
1.918 + - basic presolving technique (removing free, singleton and
1.919 + redundant rows, improving bounds of columns, removing fixed
1.920 + columns, reducing constraint coefficents);
1.921 +
1.922 + - generating cutting planes to improve LP relaxation (currently
1.923 + only Gomory's mixed integer cuts are implemented);
1.924 +
1.925 + - using the branch-and-bound method to solve resultant MIP;
1.926 +
1.927 + - recovering solution of the original MIP.
1.928 +
1.929 + The solver is available on API level via the routine lpx_intopt
1.930 + (see the reference manual). It is similar to the routine
1.931 + lpx_integer, however, does not require initial solution of LP
1.932 + relaxation.
1.933 +
1.934 + The solver is also available in the command-line utility glpsol
1.935 + via two options: --intopt (only presolving) and --cuts (assumes
1.936 + --intopt plus generating cuts).
1.937 +
1.938 + Note that efficiency of the MIP solver strongly depends on the
1.939 + internal structure of the problem to be solved. For some hard
1.940 + instances it is very efficient, but for other instances it may
1.941 + be significantly worse than the standard branch-and-bound.
1.942 +
1.943 + For some comparative benchmarks see doc/bench1.txt.
1.944 +
1.945 + Well, what else...
1.946 +
1.947 + Three built-in functions were added to MathProg: sin, cos, and
1.948 + atan (the latter allows one or two arguments).
1.949 +
1.950 + Some bugs were fixed.
1.951 +
1.952 + Several new examples in MathProg were included: color.mod
1.953 + (graph coloring problem), tsp.mod (traveling salesman problem),
1.954 + and pbn.mod (paint-by-numbers puzzle).
1.955 +
1.956 +GLPK 4.8 (release date: Jan 12, 2005)
1.957 +
1.958 + Core simplex method and interior-point method routines were
1.959 + re-implemented and now they use a new, "storage-by-rows" sparse
1.960 + matrix format (unlike previous versions where linked lists were
1.961 + used to represent sparse matrices). For details see ChangeLog.
1.962 +
1.963 + Also a minor bug was fixed in API routine lpx_read_cpxlp.
1.964 +
1.965 +GLPK 4.7 (release date: Aug 23, 2004)
1.966 +
1.967 + Now GLPK supports free MPS format. Two new API routines
1.968 + lpx_read_freemps (to read problem data in free MPS format) and
1.969 + lpx_write_freemps (to write problem data in free MPS format)
1.970 + were added. This feature is also available in the solver glpsol
1.971 + via new command-line options --freemps and --wfreemps. For more
1.972 + details see the GLPK reference manual.
1.973 +
1.974 + API routines lpx_read_cpxlp and lpx_write_cpxlp for reading and
1.975 + writing problem data in CPLEX LP format were re-implemented to
1.976 + allow long symbolic names (up to 255 characters).
1.977 +
1.978 + The following three modules were temporarily removed from the
1.979 + GLPK distribution due to licensing problems: DELI (an interface
1.980 + module to Delphi), GLPKMEX (an interface module to Matlab), and
1.981 + JNI (an interface module to Java).
1.982 +
1.983 +GLPK 4.6 (release date: Aug 04, 2004)
1.984 +
1.985 + Three new statements were implemented in the GNU MathProg
1.986 + language: solve, printf, and for. Their detailed description can
1.987 + be found in the GLPK documentation included in the distribution.
1.988 + (See also a sample model, examples/queens.mod, which illustrates
1.989 + using these new statements.)
1.990 +
1.991 + Two new API routines were added to the package: lpx_read_prob
1.992 + and lpx_write_prob. They allow reading/writing problem data in
1.993 + GNU LP low-level text format.
1.994 +
1.995 + Three new command-line options were implemented in the LP/MIP
1.996 + solver glpsol: --glp (to read problem data in GNU LP format),
1.997 + --wglp (to write problem data in GNU LP format), and --name (to
1.998 + change problem name). Now glpsol also supports processing models
1.999 + where the new statements (see above) are used.
1.1000 +
1.1001 + A new version of GLPKMEX, a Matlab MEX interface to GLPK, was
1.1002 + included. For more details see contrib/glpkmex/ChangeLog.
1.1003 +
1.1004 +GLPK 4.5 (release date: Jul 19, 2004)
1.1005 +
1.1006 + The branch-and-bound solver was completely re-implemented.
1.1007 +
1.1008 + Some modifications were made in memory allocation routines that
1.1009 + allows using the package on 64-bit platforms.
1.1010 +
1.1011 + For more details see ChangeLog.
1.1012 +
1.1013 +GLPK 4.4 (release date: Jan 17, 2004)
1.1014 +
1.1015 + All API routines were re-implemented using new data structures.
1.1016 + The new implementation provides the same specifications and
1.1017 + functionality of API routines as the old one, however, it has
1.1018 + some important advantages, in particular:
1.1019 + * linked lists are used everywhere that allows creating and
1.1020 + modifying the problem object as efficiently as possible
1.1021 + * all data stored in the problem object are non-scaled (even if
1.1022 + the internal scaling is used) that prevents distortion of the
1.1023 + original problem data
1.1024 + * solution components obtained by the solver remain available
1.1025 + even if the problem object has been modified
1.1026 + * no solver-specific data are used in the new data structures
1.1027 + that allows attaching any external lp/mip solver using GLPK
1.1028 + API as an uniform interface
1.1029 + Note that some API routines became obsolete being replaced by
1.1030 + new, more convenient routines. These obsolete routines are kept
1.1031 + for backward compatibility, however, they will be removed in
1.1032 + the future. For more details please see ChangeLog and the GLPK
1.1033 + Reference Manual.
1.1034 +
1.1035 + New edition of the GLPK Reference Manual was included in the
1.1036 + distribution.
1.1037 +
1.1038 + GLPKMEX, a Matlab MEX interface to GLPK package, contributed by
1.1039 + Nicolo Giorgetti <giorgetti@dii.unisi.it> was included in the
1.1040 + distribution.
1.1041 +
1.1042 + GLPK FAQ contributed by Harley Mackenzie <hjm@bigpond.com> was
1.1043 + included in the distribution.
1.1044 +
1.1045 +GLPK 4.3 (release date: Dec 12, 2003)
1.1046 +
1.1047 + The bug, due to which the standard math library is not linked
1.1048 + on building the package on some platforms, was fixed.
1.1049 +
1.1050 + The following new built-in functions were added to the MathProg
1.1051 + language: round, trunc, Irand224, Uniform01, Uniform, Normal01,
1.1052 + Normal. For details see the language description.
1.1053 +
1.1054 + The MathProg syntax was changed to allow writing 'subj to' that
1.1055 + means 'subject to'.
1.1056 +
1.1057 + The new api routine lpx_get_ray_info was added. It is intended
1.1058 + to determine which (non-basic) variable causes unboundness. For
1.1059 + details see the reference manual.
1.1060 +
1.1061 + The module glpmps.c was changed to avoid compilation errors on
1.1062 + building the package on Mac OS X.
1.1063 +
1.1064 + Several typos was fixed and some new material was added to the
1.1065 + GLPK documentation.
1.1066 +
1.1067 +GLPK 4.2 (release date: Nov 14, 2003)
1.1068 +
1.1069 + A preliminary implementation of the Integer Optimization Suite
1.1070 + (IOS) was included in the package. The Branch-and-Cut Framework
1.1071 + being completely superseded by IOS was removed from the package.
1.1072 +
1.1073 + New API routine lpx_print_sens_bnds intended for bounds
1.1074 + sensitivity analysis was contributed to GLPK by Brady Hunsaker
1.1075 + <hunsaker@engr.pitt.edu>. This function is also available in
1.1076 + the solver glpsol (via command-line option --bounds).
1.1077 +
1.1078 + An improved version of GLPK JNI (Java Native Interface) was
1.1079 + contributed by Chris Rosebrugh <cpr@pobox.com>.
1.1080 +
1.1081 + GLPK DELI (Delphi Interface) was contributed by Ivo van Baren
1.1082 + <i.van.baren@freeler.nl>.
1.1083 +
1.1084 + Several makefiles were added to allow compiling GLPK on some
1.1085 + non-GNU 32-bit platforms:
1.1086 + * Windows single-threaded static library, Visual C++ 6.0
1.1087 + * Windows multi-threaded dynamic library, Visual C++ 6.0
1.1088 + * Windows single-threaded static library, Borland C++ 5.2
1.1089 + * DOS single-threaded static library, Digital Mars C++ 7.50
1.1090 +
1.1091 + And, of course, some bugs were fixed.
1.1092 +
1.1093 + For more details see ChangeLog.
1.1094 +
1.1095 +GLPK 4.1 (release date: Aug 23, 2003)
1.1096 +
1.1097 + Some improvements were made in the lp/mip solver routines and
1.1098 + several bugs were fixed in the model translator.
1.1099 +
1.1100 + For more details see ChangeLog.
1.1101 +
1.1102 +GLPK 4.0 (release date: May 06, 2003)
1.1103 +
1.1104 + Now GLPK supports the GNU MathProg modeling language, which is
1.1105 + a subset of the AMPL modeling language.
1.1106 +
1.1107 + The document "GLPK: Modeling Language GNU MathProg" included in
1.1108 + the distribution is a complete description of GNU MathProg. (See
1.1109 + the files lang.latex, lang.dvi, and lang.ps in the subdirectory
1.1110 + 'doc'. See also some examples in the subdirectory 'sample'.)
1.1111 +
1.1112 + New version of the solver glpsol, which supports models written
1.1113 + in GNU MathProg, was implemented. (Brief instructions how to use
1.1114 + glpsol can be found in the GNU MathProg documentation.)
1.1115 +
1.1116 + The GLPK/L modeling language is no more supported. The reason is
1.1117 + that GNU MathProg being much more powerful completely supersedes
1.1118 + all features of GLPK/L.
1.1119 +
1.1120 +GLPK 3.3 (release date: Mar 25, 2003)
1.1121 +
1.1122 + LP PRESOLVER
1.1123 + ------------
1.1124 +
1.1125 + Now the routine lpx_simplex (which is a driver to the simplex
1.1126 + method for solving LP) is provided with the built-in LP
1.1127 + presolver, which is a program that transforms the original LP
1.1128 + problem to an equivalent LP problem, which may be easier for
1.1129 + solving with the simplex method than the original one. Once the
1.1130 + transformed LP has been solver, the presolver transforms its
1.1131 + basic solution back to a corresponding basic solution of the
1.1132 + original problem. For details about this feature please see the
1.1133 + GLPK reference manual.
1.1134 +
1.1135 + Currently the LP presolver implements the following features:
1.1136 + * removing empty rows;
1.1137 + * removing empty columns;
1.1138 + * removing free rows;
1.1139 + * removing fixed columns;
1.1140 + * removing row singletons, which have the form of equations;
1.1141 + * removing row singletons, which have the form of inequalities;
1.1142 + * removing column singletons, which are implied slack variables;
1.1143 + * fixing and removing column singletons, which are implied free
1.1144 + variables;
1.1145 + * removing forcing rows that involves fixing and removing the
1.1146 + corresponding columns;
1.1147 + * checking for primal and dual infeasibilities.
1.1148 +
1.1149 + The LP presolver is also used by default in the stand-alone
1.1150 + program glpsol. In order *not* to use it, the option --nopresol
1.1151 + should be specified in the command-line.
1.1152 +
1.1153 + CHANGES IN GLPK/L
1.1154 + -----------------
1.1155 +
1.1156 + The syntax and semantics of the GLPK/L modeling language was
1.1157 + changed to allow declaration of "interval" sets. This means that
1.1158 + now the user can declare a set, for example, as:
1.1159 +
1.1160 + set task = [8:11];
1.1161 +
1.1162 + that is exactly equivalent to the following declaration:
1.1163 +
1.1164 + set task = (task_8, task_9, task_10, task_11);
1.1165 +
1.1166 + For details see the language description.
1.1167 +
1.1168 + JAVA INTERFACE
1.1169 + --------------
1.1170 +
1.1171 + Now GLPK includes the package GLPK JNI (Java Native Interface)
1.1172 + that implements Java binding for GLPK. It allows Java programs
1.1173 + to utilize GLPK in solving LP and MIP problems. For details see
1.1174 + a brief user's guide in the subdirectory contrib/java-binding.
1.1175 + This package was developed and programmed by Yuri Victorovich
1.1176 + <yuri@gjt.org>, who contributed it to GLPK.
1.1177 +
1.1178 +GLPK 3.2.4 (release date: Feb 18, 2003)
1.1179 +
1.1180 + This is a bug-fix release. For details see ChangeLog.
1.1181 +
1.1182 +GLPK 3.2.3 (release date: Nov 11, 2002)
1.1183 +
1.1184 + A new implementation of the api routine lpx_integer which now
1.1185 + is based on the b&b driver (which is based on the implicit
1.1186 + enumeration suite) was included in the package. This new
1.1187 + implementation has exactly the same functionality as the old
1.1188 + version, so all changes are transparent to the api user.
1.1189 +
1.1190 + Four new api routines were included in the package:
1.1191 + lpx_check_kkt checks Karush-Kuhn-Tucker optmality conditions;
1.1192 + lpx_read_bas reads predifined basis in MPS format;
1.1193 + lpx_write_bas writes current basis in MPS format;
1.1194 + lpx_write_lpt writes problem data in CPLEX LP format.
1.1195 +
1.1196 + Also other minor improvements were made (for details see the
1.1197 + file 'ChangeLog').
1.1198 +
1.1199 +GLPK 3.2.2 (release date: Oct 14, 2002)
1.1200 +
1.1201 + The api routine lpx_read_lpt was included in the package. It
1.1202 + is similar to the routine lpx_read_mps and intended to read
1.1203 + LP/MIP data prepared in CPLEX LP format. Description of this
1.1204 + format is given in the GLPK reference manual, a new edition of
1.1205 + which was also included in the distribution (see the files
1.1206 + 'refman.latex', 'refman.dvi', 'refman.ps' in the subdirectory
1.1207 + 'doc'). In order to use data files in CPLEX LP format with the
1.1208 + solver glpsol the option '--lpt' should be specified in the
1.1209 + command line.
1.1210 +
1.1211 + Several bugs were fixed and some minor improvements were made
1.1212 + (for details see the file 'ChangeLog').
1.1213 +
1.1214 +GLPK 3.2.1 (release date: Aug 12, 2002)
1.1215 +
1.1216 + Now GLPK includes a preliminary implementation of the
1.1217 + branch-and-cut framework, which is a set of data structures and
1.1218 + routines intended for developing branch-and-cut methods for
1.1219 + solving mixed-integer and combinatorial optimization problems.
1.1220 +
1.1221 + Detailed decsription of the branch-and-cut framework is given in
1.1222 + the document "GLPK: A Preliminary Implementation of the
1.1223 + Branch-And-Cut Framework" included in the distribution (see the
1.1224 + file 'brcut.txt' in the subdirectory 'doc').
1.1225 +
1.1226 + In order to illustrate how the GLPK branch-and-cut framework
1.1227 + can be used for solving a particular optimization problem there
1.1228 + is an example included in the package. This is a stand-alone
1.1229 + program, TSPSOL, which is intended for solving to optimality the
1.1230 + symmetric Traveling Salesman Problem (TSP), a classical problem
1.1231 + of the combinatorial optimization (see the file 'tspsol.c' in
1.1232 + the subdirectory 'sample').
1.1233 +
1.1234 +GLPK 3.2 (release date: Jul 15, 2002)
1.1235 +
1.1236 + New edition of the document "GLPK: Reference Manual" was
1.1237 + included (see the files 'refman.latex', 'refman.dvi', and
1.1238 + 'refman.ps' in the subdirectory 'doc').
1.1239 +
1.1240 + New edition of the document "GLPK: Modeling Language GLPK/L" was
1.1241 + included (see the files 'lang.latex', 'lang.dvi', and 'lang.ps'
1.1242 + in the subdirectory 'doc').
1.1243 +
1.1244 + The following new API routines were added to the package:
1.1245 +
1.1246 + lpx_transform_row (transform explicitly specified row);
1.1247 + lpx_transform_col (transform explicitly specified column);
1.1248 + lpx_prim_ratio_test (perform primal ratio test);
1.1249 + lpx_dual_ratio_test (perform dual ratio test);
1.1250 + lpx_interior (solve LP problem using interior point method);
1.1251 + lpx_get_ips_stat (query status of interior point solution);
1.1252 + lpx_get_ips_row (obtain row interior point solution);
1.1253 + lpx_get_ips_col (obtain column interior point solution);
1.1254 + lpx_get_ips_obj (obtain interior point value of obj.func.);
1.1255 + lpx_read_lpm (read LP/MIP model written in GLPK/L);
1.1256 + lpx_write_mps (write problem data using MPS format);
1.1257 + lpx_print_ips (print interior point solution).
1.1258 +
1.1259 + Detailed description of all these new API routines are given in
1.1260 + the new edition of the reference manual.
1.1261 +
1.1262 + New version of the stand-alone solver glpsol (which is based on
1.1263 + the new API) was implemented.
1.1264 +
1.1265 + So long as the new API (introduced in glpk 3.0) now provides
1.1266 + all the functions, which were provided by the old API, the old
1.1267 + API routines were removed from the package at all.
1.1268 +
1.1269 +GLPK 3.1 (release date: May 27, 2002)
1.1270 +
1.1271 + A preliminary implementation of new API routines was completed
1.1272 + and included in the package.
1.1273 +
1.1274 + These new API routines provide much more flexible interaction
1.1275 + between the application program, LP/MIP problem instances, and
1.1276 + solver routines. Based on completely changed data structures
1.1277 + they are, however, similar to the API routines and provide the
1.1278 + same functionality. Please note that three routines, namely,
1.1279 + solving LPs using interior point method, reading model written
1.1280 + in the GLPK/L modeling language, and writing problem data in
1.1281 + the MPS format, are not implemented in the new API, however,
1.1282 + these routines are planned to be implemented in the next version
1.1283 + of the package.
1.1284 +
1.1285 + A description of the new API routines is given in the document
1.1286 + "GLPK Reference Manual", a draft edition of which is included
1.1287 + in the package (see the files 'refman.latex', 'refman.dvi', and
1.1288 + 'refman.ps' in the subdirectory 'doc').
1.1289 +
1.1290 + Although the old API routines are kept in the package, they are
1.1291 + no longer supported and will be removed in the future.
1.1292 +
1.1293 +GLPK 3.0.8 (release date: May 13, 2002)
1.1294 +
1.1295 + A preliminary implementation of new API routines was included
1.1296 + in the package. These new API routines are intended to provide
1.1297 + much more flexible interaction between the application program,
1.1298 + LP/MIP problem and solver routines. See the document "New GLPK
1.1299 + API Routines" (the file 'newapi.txt' in the subdirectory 'doc')
1.1300 + also included in the package.
1.1301 +
1.1302 + The api routines glp_simplex2, glp_call_ipm1, glp_call_bbm1 were
1.1303 + renamed, respectively, to glp_simplex, glp_interior, glp_integer
1.1304 + in order to reflect changes in implementation. The api routines
1.1305 + glp_call_rsm1, glp_simplex1, glp_pivot_in, glp_pivout_out were
1.1306 + removed from the package since they are completely supreseded by
1.1307 + the new API routines (however, these routines still can be found
1.1308 + in the subdirectory 'oldsrc'). Please consult a new edition of
1.1309 + the document "GLPK User's Guide" about all these changes in the
1.1310 + existing api routines.
1.1311 +
1.1312 + The document "GLPK Library Reference" was removed from the
1.1313 + package (into the subdirectory 'oldsrc') since it describes the
1.1314 + obsolete library routines, most of which are no longer used.
1.1315 +
1.1316 +GLPK 3.0.7 (release date: Apr 22, 2002)
1.1317 +
1.1318 + A new, more efficient implementation of the primal/dual simplex
1.1319 + method was included in the package. Due to some improvements the
1.1320 + simplex-based solver allows solving many LP problems faster and
1.1321 + provides more reliable results. Note that the new implementation
1.1322 + is currently incomplete and available only via the api routine
1.1323 + glp_simplex2.
1.1324 +
1.1325 + All the changes are transparent on API level.
1.1326 +
1.1327 +GLPK 3.0.6 (release date: Mar 28, 2002)
1.1328 +
1.1329 + New version of LU-factorization and basis maintenance routines
1.1330 + (based on Forrest-Tomlin updating technique) was implemented.
1.1331 + Since these new routines functionally supersede some routines
1.1332 + (which implement other forms of the basis matrix) and make them
1.1333 + obsolete, the latter were removed from the package (they still
1.1334 + can be found in the subdirectory 'oldsrc').
1.1335 +
1.1336 + All the changes are transparent on API level.
1.1337 +
1.1338 +GLPK 3.0.5 (release date: Jan 29, 2002)
1.1339 +
1.1340 + New edition of the document "GLPK User's Guide" was included in
1.1341 + the distribution. Now it describes all additional API routines,
1.1342 + which were recently added to the package.
1.1343 +
1.1344 + Structure of the package was re-organized in order to make its
1.1345 + maintenance easier (all small files in the subdurectory 'source'
1.1346 + were merged in bigger units). These changes are transparent for
1.1347 + the user.
1.1348 +
1.1349 +GLPK 3.0.4 (release date: Dec 10, 2001)
1.1350 +
1.1351 + A new, more efficient implementation of the two-phase primal
1.1352 + simplex method was included in the package. Due to some new
1.1353 + features (an advanced initial basis, projected steepest edge,
1.1354 + recursive updating values and reduced costs) the new LP solver
1.1355 + is faster and numerically more stable than the old one.
1.1356 +
1.1357 + The new LP solver is available as API routine glp_simplex2 and
1.1358 + has the same purpose as API routine glp_call_rsm1. For detailed
1.1359 + specification see the file 'newapi.txt' in the directory 'doc'.
1.1360 +
1.1361 + Now the new LP solver is also used by default to solve an
1.1362 + initial LP problem in the branch-and-bound routine glp_call_bbm1
1.1363 + instead the routine rsm1_driver. Note that the branch-and-bound
1.1364 + procedure itself is still based on rsm1_driver.
1.1365 +
1.1366 + The new LP solver is also used as default solver in GLPSOL for
1.1367 + solving LP and MIP problems. In order to choose the old solver
1.1368 + the option '--old-sim' can be specified in the command line.
1.1369 +
1.1370 +GLPK 3.0.3 (release date: Oct 03, 2001)
1.1371 +
1.1372 + Some minor changes were made in the simplex method routines in
1.1373 + order to improve numerical stability of the method.
1.1374 +
1.1375 +GLPK 3.0.2 (release date: Sep 24, 2001)
1.1376 +
1.1377 + A new implementation of the basis maintaining routines was
1.1378 + included in the package. These routines, which are based on so
1.1379 + called FHV-factorization (a variety of LU-factorization) of the
1.1380 + basis matrix and Gustavson's data structures, allows performing
1.1381 + the main operations faster at the expense of some worsening
1.1382 + numerical accuracy.
1.1383 +
1.1384 + AFI (Advanced Form of the Inverse), which is the form of the
1.1385 + basis matrix based on FHV-factorization, is available via the
1.1386 + parameter form = 3 (on API level) or via the option --afi (in
1.1387 + GLPSOL solver).
1.1388 +
1.1389 +GLPK 3.0.1 (release date: Aug 01, 2001)
1.1390 +
1.1391 + Old GLPK API routines have been removed from the package.
1.1392 +
1.1393 + New GLPK API routines were added:
1.1394 +
1.1395 + - scaling routines;
1.1396 +
1.1397 + - a routine for writing problem data in MPS format;
1.1398 +
1.1399 + - a comprehensive driver to the simplex method;
1.1400 +
1.1401 + - basis maintaining routines.
1.1402 +
1.1403 + A description of the new API routines is given in the document
1.1404 + "Additional GLPK API Routines". This document is included into
1.1405 + the distribution in plain text format (see the file 'newapi.txt'
1.1406 + in the subdirectory 'doc').
1.1407 +
1.1408 + Now the distribution includes a non-trivial example of using
1.1409 + GLPK as a base LP solver for Concorde, a well known program that
1.1410 + solves Traveling Salesman Problem (TSP). For further details see
1.1411 + comments in the file 'sample/lpglpk30.c'.
1.1412 +
1.1413 +GLPK 3.0 (release date: Jul 19, 2001)
1.1414 +
1.1415 + Now GLPK is provided with new API, which being more flexible
1.1416 + can be used in more complex algorithmic schemes.
1.1417 +
1.1418 + New edition of the document "GLPK User's Guide" is included in
1.1419 + the distribution. Now it completely corresponds to the new GLPK
1.1420 + API routines.
1.1421 +
1.1422 + Old API routines are not removed yet from the package, however
1.1423 + they became obsolete and therefore should not be used. Since now
1.1424 + the header glpk.h corresponds to new API, in order to compile
1.1425 + existing programs that use old GLPK API routines the statement
1.1426 +
1.1427 + #define GLP_OLD_API
1.1428 +
1.1429 + should be inserted before the statement
1.1430 +
1.1431 + #include "glpk.h"
1.1432 +
1.1433 +GLPK 2.4.1 (release date: Jun 14, 2001)
1.1434 +
1.1435 + The document "Modeling language GLPK/L" is included into the
1.1436 + distribution in texinfo format.
1.1437 +
1.1438 + New edition of the document "GLPK User's Guide" is included in
1.1439 + the distribution. Now it describes all additional API routines
1.1440 + which were recently added to the package.
1.1441 +
1.1442 +GLPK 2.4 (release date: May 10, 2001)
1.1443 +
1.1444 + Now GLPK includes an implementation of a preliminary version
1.1445 + of the GLPK/L modeling language. This language is intended for
1.1446 + writing mathematcal programming models. The name GLPK/L is
1.1447 + derived from GNU Linear Programming Kit Language.
1.1448 +
1.1449 + A brief description of the GLPK/L language is given in the
1.1450 + document "GLPK/L Modeling Language: A Brief Description". This
1.1451 + document is included into the distribution in plain text format
1.1452 + (see the file 'language.txt' in the subdirectory 'doc').
1.1453 +
1.1454 + The language processor (which is a program that analyzes model
1.1455 + description written in GLPK/L and translates it to internal data
1.1456 + structures) is available as the GLPK API routine.
1.1457 +
1.1458 + The stand-alone solver GLPSOL now is able: a) to process model
1.1459 + descriptions written in the GLPK/L language; b) to solve pure LP
1.1460 + problems using the interior point method (therefore the program
1.1461 + GLPIPM was removed from the package).
1.1462 +
1.1463 +GLPK 2.3 (release date: Apr 09, 2001)
1.1464 +
1.1465 + New edition of the document "GLPK User's Guide" is included in
1.1466 + the distribution. Now it describes all additional API routines
1.1467 + which were recently added to the package.
1.1468 +
1.1469 + The MIP solver was fully re-programmed in order to improve its
1.1470 + robustness and performance. In particular, a basis recovering
1.1471 + procedure was implemented (this procedure allows switching to
1.1472 + the primal simplex method in case when the dual simplex method
1.1473 + fails).
1.1474 +
1.1475 +GLPK 2.2 (release date: Mar 15, 2001)
1.1476 +
1.1477 + Now GLPK includes a tentative implementation of the
1.1478 + branch-and-bound procedure based on the dual simplex method for
1.1479 + mixed integer linear programming (MIP).
1.1480 +
1.1481 + Complete description of this new feature of the package is given
1.1482 + in the preliminary document "Mixed Integer Linear Programming
1.1483 + Using GLPK Version 2.2 (Supplement to GLPK User's Guide)". This
1.1484 + document is included into the distribution in plain text format
1.1485 + (see the file 'mip.txt' in the subdirectory 'doc').
1.1486 +
1.1487 + The MIP solver (glp_integer) can be used as GLPK API routine in
1.1488 + the same way as the pure LP solver (glp_simplex).
1.1489 +
1.1490 + The stand-alone program 'glpsol' is now able to solve LP as well
1.1491 + as MIP problems.
1.1492 +
1.1493 + Note that the current version of GLPK MIP solver is based on
1.1494 + easiest heuristics for branching and backtrackng. Therefore the
1.1495 + solver is fit mainly for MIP problems which are not very hard
1.1496 + and have few integer variables.
1.1497 +
1.1498 +GLPK 2.1 (release date: Feb 19, 2001)
1.1499 +
1.1500 + The document "GLPK Implementation of the Revised Simplex Method"
1.1501 + is included into the distribution. This document describes most
1.1502 + of routines related to the revised simplex method.
1.1503 +
1.1504 +GLPK 2.0 (release date: Jan 25, 2001)
1.1505 +
1.1506 + Now GLPK includes a tentative implementation of the primal-dual
1.1507 + interior point method for large-scale linear programming.
1.1508 +
1.1509 + The interior point solver can be used as GLPK API routine in the
1.1510 + same manner as the simplex method solver (glp_simplex):
1.1511 +
1.1512 + ret = glp_interior();
1.1513 +
1.1514 + Note that currently the interior point solver implemented in
1.1515 + GLPK doesn't include many important features, in particular:
1.1516 +
1.1517 + * it can't process dense columns; therefore if the problem has
1.1518 + dense columns, the solving will be extremely inefficient;
1.1519 +
1.1520 + * it has no special features against numerical unstability;
1.1521 + some problems may cause premature termination of the solving
1.1522 + when the matrix A*D*A' becomes ill-conditioned;
1.1523 +
1.1524 + * it computes only values of primal (auxiliary and structural)
1.1525 + variables and doesn't compute values of dual variables (i.e.
1.1526 + reduced costs) which are just set to zero;
1.1527 +
1.1528 + * it doesn't identify optimal basis corresponding to the found
1.1529 + interior point solution; all variables in the found solution
1.1530 + are just marked as basic variables.
1.1531 +
1.1532 + GLPK also includes a stand-alone program 'glpipm' which is a
1.1533 + demo based on the interior point method. It may be used in the
1.1534 + same way as the program 'glpsol' that is based on the simplex
1.1535 + method.