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