lemon-project-template-glpk

annotate deps/glpk/NEWS @ 11:4fc6ad2fb8a6

find changesets by author, revision, files, or words in the commit message
Test GLPK in src/main.cc
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 21:43:29 +0100
parents
children
rev   line source
alpar@9 1 GLPK 4.47 (release date: Sep 09, 2011)
alpar@9 2
alpar@9 3 The new API routine glp_intfeas1 was added to the package.
alpar@9 4 This routine is a tentative implementation of the integer (0-1)
alpar@9 5 feasibility solver based on the CNF-SAT solver (which currently
alpar@9 6 is MiniSat). It may be used in the same way as glp_intopt to
alpar@9 7 find either any integer feasible solution or a solution, for
alpar@9 8 which the objective function is not worse than the specified
alpar@9 9 value. Detailed description of this routine can be found in the
alpar@9 10 document "CNF Satisfiability Problem", which is included in the
alpar@9 11 distribution (see doc/cnfsat.pdf).
alpar@9 12
alpar@9 13 The following two options were added to glpsol:
alpar@9 14
alpar@9 15 --minisat translate 0-1 feasibility problem to CNF-SAT
alpar@9 16 problem and solve it with glp_intfeas1/MiniSat
alpar@9 17 (if the problem instance is already in CNF-SAT
alpar@9 18 format, no translation is performed)
alpar@9 19
alpar@9 20 --objbnd bound add inequality obj <= bound (minimization) or
alpar@9 21 obj >= bound (maximization) to 0-1 feasibility
alpar@9 22 problem (this option assumes --minisat)
alpar@9 23
alpar@9 24 The paint-by-numbers puzzle model (pbn.mod) included in the
alpar@9 25 distribution is a nice example of the 0-1 feasibility problem,
alpar@9 26 which can be efficiently solved with glp_intfeas1/MiniSat. This
alpar@9 27 model along with a brief instruction (pbn.pdf) and benchmark
alpar@9 28 examples from <webpbn.com> encoded in GNU MathProg (*.dat) can
alpar@9 29 be found in subdirectory examples/pbn/.
alpar@9 30
alpar@9 31 The glpsol lp/mip solver was modified to bypass postprocessing
alpar@9 32 of MathProg models if the solution reported is neither optimal
alpar@9 33 nor feasible.
alpar@9 34
alpar@9 35 A minor bug in examples/Makefile.am was fixed to correctly
alpar@9 36 build glpk in a separate directory. Thanks to Marco Atzeri
alpar@9 37 <marco.atzeri@gmail.com> for bug report and patch.
alpar@9 38
alpar@9 39 GLPK 4.46 (release date: Aug 09, 2011)
alpar@9 40
alpar@9 41 The following new API routines were added:
alpar@9 42
alpar@9 43 glp_read_cnfsat read CNF-SAT problem data in DIMACS format
alpar@9 44 glp_check_cnfsat check for CNF-SAT problem instance
alpar@9 45 glp_write_cnfsat write CNF-SAT problem data in DIMACS format
alpar@9 46 glp_minisat1 solve CNF-SAT problem instance with MiniSat
alpar@9 47
alpar@9 48 The routine glp_minisat1 is a driver to MiniSat, a CNF-SAT
alpar@9 49 solver developed by Niklas Een and Niklas Sorensson, Chalmers
alpar@9 50 University of Technology, Sweden. This routine is similar to
alpar@9 51 the routine glp_intopt, however, it is intended to solve a 0-1
alpar@9 52 programming problem instance, which is the MIP translation of
alpar@9 53 a CNF-SAT problem instance.
alpar@9 54
alpar@9 55 Detailed description of these new API routines can be found in
alpar@9 56 the document "CNF Satisfiability Problem", which is included in
alpar@9 57 the distribution (see files doc/cnfsat.tex and doc/cnfsat.pdf).
alpar@9 58
alpar@9 59 The following new glpsol command-line options were added:
alpar@9 60
alpar@9 61 --cnf filename read CNF-SAT problem instance in DIMACS
alpar@9 62 format from filename and translate it to MIP
alpar@9 63 --wcnf filename write CNF-SAT problem instance in DIMACS
alpar@9 64 format to filename
alpar@9 65 --minisat solve CNF-SAT problem instance with MiniSat
alpar@9 66 solver
alpar@9 67
alpar@9 68 The zlib compression library (version 1.2.5) was ANSIfied,
alpar@9 69 modified according to GLPK requirements and included in the
alpar@9 70 distribution as an external software module. Thus, now this
alpar@9 71 feature is platform independent.
alpar@9 72
alpar@9 73 Some bugs were fixed in the SQL table driver. Thanks to Xypron
alpar@9 74 <xypron.glpk@gmx.de>.
alpar@9 75
alpar@9 76 GLPK 4.45 (release date: Dec 05, 2010)
alpar@9 77
alpar@9 78 This is a bug-fix release.
alpar@9 79
alpar@9 80 Several bugs/typos were fixed. Thanks to
alpar@9 81 Xypron <xypron.glpk@gmx.de>,
alpar@9 82 Robbie Morrison <robbie@actrix.co.nz>, and
alpar@9 83 Ali Baharev <ali.baharev@gmail.com> for reports.
alpar@9 84
alpar@9 85 Some glpk documents was re-formatted and merged into a single
alpar@9 86 document. Now the glpk documentation consists of the following
alpar@9 87 three main documents (all included in the distribution):
alpar@9 88
alpar@9 89 GLPK: Reference Manual
alpar@9 90
alpar@9 91 GLPK: Graph and Network Routines
alpar@9 92
alpar@9 93 Modeling Language GNU MathProg: Language Reference
alpar@9 94
alpar@9 95 GLPK 4.44 (release date: Jun 03, 2010)
alpar@9 96
alpar@9 97 The following suffixes for variables and constraints were
alpar@9 98 implemented in the MathProg language:
alpar@9 99
alpar@9 100 .lb (lower bound),
alpar@9 101 .ub (upper bound),
alpar@9 102 .status (status in the solution),
alpar@9 103 .val (primal value), and
alpar@9 104 .dual (dual value).
alpar@9 105
alpar@9 106 Thanks to Xypron <xypron.glpk@gmx.de> for draft implementation
alpar@9 107 and testing.
alpar@9 108
alpar@9 109 Now the MathProg language allows comment records (marked by
alpar@9 110 '#' in the very first position) in CSV data files read with the
alpar@9 111 table statements. Note that the comment records may appear only
alpar@9 112 in the beginning of a CSV data file.
alpar@9 113
alpar@9 114 The API routine glp_cpp to solve the Critical Path Problem was
alpar@9 115 added and documented.
alpar@9 116
alpar@9 117 GLPK 4.43 (release date: Feb 20, 2010)
alpar@9 118
alpar@9 119 This is a maintainer release.
alpar@9 120
alpar@9 121 `configure.ac' was changed to allow building the package under
alpar@9 122 Mac OS and Darwin with ODBC support.
alpar@9 123 Thanks to Xypron <xypron.glpk@gmx.de> for suggestions and Noli
alpar@9 124 Sicad <nsicad@gmail.com> for testing.
alpar@9 125
alpar@9 126 The SQL table driver was improved to process NULL data. Thanks
alpar@9 127 to Xypron <xypron.glpk@gmx.de>.
alpar@9 128
alpar@9 129 Some bugs were fixed in the LP/MIP preprocessor.
alpar@9 130
alpar@9 131 GLPK 4.42 (release date: Jan 13, 2010)
alpar@9 132
alpar@9 133 The following new API routines were added:
alpar@9 134
alpar@9 135 glp_check_dup check for duplicate elements in sparse
alpar@9 136 matrix
alpar@9 137 glp_sort_matrix sort elements of the constraint matrix
alpar@9 138 glp_read_prob read problem data in GLPK format
alpar@9 139 glp_write_prob write problem data in GLPK format
alpar@9 140 glp_analyze_bound analyze active bound of non-basic variable
alpar@9 141 glp_analyze_coef analyze objective coefficient at basic
alpar@9 142 variable
alpar@9 143 glp_print_ranges print sensitivity analysis report (this
alpar@9 144 routine replaces lpx_print_sens_bnds and
alpar@9 145 makes it deprecated)
alpar@9 146
alpar@9 147 For description of these new routines and the GLPK LP/MIP
alpar@9 148 format see a new edition of the reference manual included in
alpar@9 149 the distribution. (Chapter "Graph and network API routines" was
alpar@9 150 carried out from the main reference manual and included in the
alpar@9 151 distribution as a separate document.)
alpar@9 152
alpar@9 153 The following new command-line options were added to the stand-
alpar@9 154 alone solver glpsol:
alpar@9 155 --glp filename read problem data in GLPK format
alpar@9 156 --wglp filename write problem data in GLPK format
alpar@9 157 --ranges filename print sensitivity analysis report (this
alpar@9 158 option replaces --bounds)
alpar@9 159
alpar@9 160 Now all GLPK routines performing file I/O support special
alpar@9 161 filenames "/dev/stdin", "/dev/stdout", and "/dev/stderr", which
alpar@9 162 can be specified in the same way as regular filenames. This
alpar@9 163 feature is plaform-independent.
alpar@9 164
alpar@9 165 GLPK 4.41 (release date: Dec 21, 2009)
alpar@9 166
alpar@9 167 The following new API routies were added:
alpar@9 168
alpar@9 169 glp_transform_row transform explicitly specified row
alpar@9 170 glp_transform_col transform explicitly specified column
alpar@9 171 glp_prim_rtest perform primal ratio test
alpar@9 172 glp_dual_rtest perform dual ratio test
alpar@9 173
alpar@9 174 For description of these new routines see a new edition of the
alpar@9 175 reference manual included in the distribution.
alpar@9 176
alpar@9 177 The following API routines are deprecated: lpx_transform_row,
alpar@9 178 lpx_transform_col, lpx_prim_ratio_test, lpx_dual_ratio_test.
alpar@9 179
alpar@9 180 Some improvements were made in the MIP solver (glp_intopt).
alpar@9 181
alpar@9 182 The SQL table driver used to read/write data in MathProg models
alpar@9 183 was changed to allow multiple arguments separated by semicolon
alpar@9 184 in SQL statements. Thanks to Xypron <xypron.glpk@gmx.de>.
alpar@9 185
alpar@9 186 Two new options were added to the glpsol stand-alone solver:
alpar@9 187 --seed value (to initialize the pseudo-random number generator
alpar@9 188 used in MathProg models with specified value), and
alpar@9 189 --ini filename (to use a basis previously saved with -w option
alpar@9 190 as an initial basis on solving similar LP's).
alpar@9 191
alpar@9 192 Two new MathProg example models were included. Thanks to
alpar@9 193 Nigel Galloway <nigel_galloway@operamail.com> and Noli Sicad
alpar@9 194 <nsicad@gmail.com> for contribution.
alpar@9 195
alpar@9 196 Scripts to build GLPK with Microsoft Visual Studio 2010 for
alpar@9 197 both 32-bit and 64-bit Windows were included. Thanks to Xypron
alpar@9 198 <xypron.glpk@gmx.de> for contribution and testing.
alpar@9 199
alpar@9 200 GLPK 4.40 (release date: Nov 03, 2009)
alpar@9 201
alpar@9 202 The following new API routines were added:
alpar@9 203
alpar@9 204 glp_del_vertices remove vertices from graph
alpar@9 205 glp_del_arc remove arc from graph
alpar@9 206 glp_wclique_exact find maximum weight clique with the exact
alpar@9 207 algorithm developed by Prof. P. Ostergard
alpar@9 208 glp_read_ccdata read graph in DIMACS clique/coloring
alpar@9 209 format
alpar@9 210 glp_write_ccdata write graph in DIMACS clique/coloring
alpar@9 211 format
alpar@9 212
alpar@9 213 For description of these new routines see a new edition of the
alpar@9 214 reference manual included in the distribution.
alpar@9 215
alpar@9 216 The hybrid pseudocost branching heuristic was included in the
alpar@9 217 MIP solver. It is available on API level (iocp.br_tech should
alpar@9 218 be set to GLP_BR_PCH) and in the stand-alone solver glpsol
alpar@9 219 (via the command-line option --pcost). This heuristic may be
alpar@9 220 useful on solving hard MIP instances.
alpar@9 221
alpar@9 222 The branching heuristic by Driebeck and Tomlin (used in the
alpar@9 223 MIP solver by default) was changed to switch to branching on
alpar@9 224 most fractional variable if an lower bound of degradation of
alpar@9 225 the objective is close to zero for all branching candidates.
alpar@9 226
alpar@9 227 A bug was fixed in the LP preprocessor (routine npp_empty_col).
alpar@9 228 Thanks to Stefan Vigerske <stefan@math.hu-berlin.de> for the
alpar@9 229 bug report.
alpar@9 230
alpar@9 231 A bug was fixed and some improvements were made in the FPUMP
alpar@9 232 heuristic module. Thanks to Xypron <xypron.glpk@gmx.de>.
alpar@9 233
alpar@9 234 A bug was fixed in the API routine glp_warm_up (dual
alpar@9 235 feasibility test was incorrect in maximization case). Thanks to
alpar@9 236 Uday Venkatadri <Uday.Venkatadri@dal.ca> for the bug report.
alpar@9 237
alpar@9 238 GLPK 4.39 (release date: Jul 26, 2009)
alpar@9 239
alpar@9 240 The following new API routines were added:
alpar@9 241
alpar@9 242 glp_warm_up "warm up" LP basis
alpar@9 243 glp_set_vertex_name assign (change) vertex name
alpar@9 244 glp_create_v_index create vertex name index
alpar@9 245 glp_find_vertex find vertex by its name
alpar@9 246 glp_delete_v_index delete vertex name index
alpar@9 247 glp_read_asnprob read assignment problem data in DIMACS
alpar@9 248 format
alpar@9 249 glp_write_asnprob write assignment problem data in DIMACS
alpar@9 250 format
alpar@9 251 glp_check_asnprob check correctness of assignment problem
alpar@9 252 data
alpar@9 253 glp_asnprob_lp convert assignment problem to LP
alpar@9 254 glp_asnprob_okalg solve assignment problem with the
alpar@9 255 out-of-kilter algorithm
alpar@9 256 glp_asnprob_hall find bipartite matching of maxumum
alpar@9 257 cardinality with Hall's algorithm
alpar@9 258
alpar@9 259 Also were added some API routines to read plain data files.
alpar@9 260
alpar@9 261 The API routines glp_read_lp and glp_write_lp to read/write
alpar@9 262 files in CPLEX LP format were re-implemented. Now glp_write_lp
alpar@9 263 correctly writes double-bounded (ranged) rows by introducing
alpar@9 264 slack variables rather than by duplicating the rows.
alpar@9 265
alpar@9 266 For description of these new routines see a new edition of the
alpar@9 267 reference manual included in the distribution.
alpar@9 268
alpar@9 269 The 'xfree(NULL)' bug was fixed in the AMD routines. Thanks to
alpar@9 270 Niels Klitgord <niels@bu.edu> for bug report.
alpar@9 271
alpar@9 272 The message "Crashing..." was changed to "Constructing initial
alpar@9 273 basis..." due to suggestion by Thomas Kahle <tom111@gmx.de>.
alpar@9 274
alpar@9 275 Some typos were corrected in glpsol output messages. Thanks to
alpar@9 276 Xypron <xypron.glpk@gmx.de> for patch.
alpar@9 277
alpar@9 278 GLPK 4.38 (release date: May 02, 2009)
alpar@9 279
alpar@9 280 API routines glp_read_mps and glp_write_mps were improved.
alpar@9 281
alpar@9 282 Some improvements were made in the dual simplex routines.
alpar@9 283
alpar@9 284 Two external software modules AMD and COLAMD were included in
alpar@9 285 the distribution (for more details please see src/amd/README
alpar@9 286 and src/colamd/README). Now they are used in the interior-point
alpar@9 287 solver to reorder the matrix prior to Cholesky factorization.
alpar@9 288
alpar@9 289 API routine glp_ipt_status may return two new statuses due to
alpar@9 290 changes in the routine glp_interior. For details please see the
alpar@9 291 reference manual included in the distribution.
alpar@9 292
alpar@9 293 A minor bug was fixed in the graph/network routines. Thanks to
alpar@9 294 Nelson H. F. Beebe <beebe@math.utah.edu> for bug report.
alpar@9 295
alpar@9 296 GLPK 4.37 (release date: Mar 29, 2009)
alpar@9 297
alpar@9 298 The 0-1 Feasibility Pump heuristic was included in the GLPK
alpar@9 299 integer optimizer glp_intopt. On API level the heuristic can be
alpar@9 300 enabled by setting the parameter fp_heur in glp_iocp to GLP_ON.
alpar@9 301 This feature is also available in the solver glpsol through
alpar@9 302 command-line option '--fpump'. For more details please see the
alpar@9 303 reference manual included in the distribution.
alpar@9 304
alpar@9 305 The following new API routines were added:
alpar@9 306
alpar@9 307 glp_print_sol write basic solution in printable format
alpar@9 308 glp_print_ipt write interior-point solution in printable
alpar@9 309 format
alpar@9 310 glp_print_mip write MIP solution in printable format
alpar@9 311 glp_read_graph read (di)graph from plain text file
alpar@9 312 glp_write_graph write (di)graph to plain text file
alpar@9 313 glp_weak_comp find all weakly connected components
alpar@9 314 glp_strong_comp find all strongly connected components
alpar@9 315
alpar@9 316 The following API routines are deprecated: lpx_print_sol,
alpar@9 317 lpx_print_ips, lpx_print_mip, lpx_print_prob (the latter is
alpar@9 318 equivalent to glp_write_lp).
alpar@9 319
alpar@9 320 A bug was fixed in the interior-point solver (glp_interior) to
alpar@9 321 correctly compute dual solution components when the problem is
alpar@9 322 scaled.
alpar@9 323
alpar@9 324 The files configure.ac and Makefile.am were changed:
alpar@9 325 (a) to allow using autoreconf/autoheader;
alpar@9 326 (b) to allow building the package in a directory other than its
alpar@9 327 source directory.
alpar@9 328 Thanks to Marco Atzeri <marco_atzeri@yahoo.it> for bug report.
alpar@9 329
alpar@9 330 An example model in the GNU MathProg language was added.
alpar@9 331 Thanks to Larry D'Agostino <Larry.D'Agostino@gmacrescap.com> for
alpar@9 332 contribution.
alpar@9 333
alpar@9 334 GLPK 4.36 (release date: Feb 06, 2009)
alpar@9 335
alpar@9 336 The following new API routines were added to the package:
alpar@9 337
alpar@9 338 glp_mincost_okalg find minimum-cost flow with out-of-kilter
alpar@9 339 algorithm
alpar@9 340 glp_maxflow_ffalg find maximal flow with Ford-Fulkerson
alpar@9 341 algorithm
alpar@9 342
alpar@9 343 For detailed description of these new routines and related data
alpar@9 344 structures see chapter "Graph and Network API Routines" in a new
alpar@9 345 edition of the reference manual included in the distribution.
alpar@9 346
alpar@9 347 The following two new command-line options were added to the
alpar@9 348 solver glpsol:
alpar@9 349
alpar@9 350 --mincost read min-cost flow data in DIMACS format
alpar@9 351 --maxflow read maximum flow data in DIMACS format
alpar@9 352
alpar@9 353 Duplicate symbols in the header glpk.h were removed to allow
alpar@9 354 using swig.
alpar@9 355 Thanks to Kelly Westbrooks <kellywestbrooks@yahoo.com> and
alpar@9 356 Nigel Galloway <nigel_galloway@operamail.com> for suggestion.
alpar@9 357
alpar@9 358 A minor defect was fixed in the routine glp_write_lp.
alpar@9 359 Thanks to Sebastien Briais <sbriais@free.fr> for bug report.
alpar@9 360
alpar@9 361 A minor bug was fixed in the SQL module.
alpar@9 362 Thanks to Xypron <xypron.glpk@gmx.de> for patch.
alpar@9 363
alpar@9 364 Some new example models in the GNU MathProg modeling language
alpar@9 365 were added. Thanks to Sebastian Nowozin <nowozin@gmail.com> and
alpar@9 366 Nigel Galloway <nigel_galloway@operamail.com> for contribution.
alpar@9 367
alpar@9 368 GLPK 4.35 (release date: Jan 09, 2009)
alpar@9 369
alpar@9 370 The following new API routines were added to the package:
alpar@9 371
alpar@9 372 glp_create_graph create graph
alpar@9 373 glp_set_graph_name assign (change) graph name
alpar@9 374 glp_add_vertices add new vertices to graph
alpar@9 375 glp_add_arc add new arc to graph
alpar@9 376 glp_erase_graph erase graph content
alpar@9 377 glp_delete_graph delete graph
alpar@9 378 glp_read_mincost read minimum cost flow problem data in
alpar@9 379 DIMACS format
alpar@9 380 glp_write_mincost write minimum cost flow problem data in
alpar@9 381 DIMACS format
alpar@9 382 glp_mincost_lp convert minimum cost flow problem to LP
alpar@9 383 glp_netgen Klingman's network problem generator
alpar@9 384 glp_gridgen grid-like network problem generator
alpar@9 385 glp_read_maxflow read maximum flow problem data in DIMACS
alpar@9 386 format
alpar@9 387 glp_write_maxflow write maximum flow problem data in DIMACS
alpar@9 388 format
alpar@9 389 glp_maxflow_lp convert maximum flow problem to LP
alpar@9 390 glp_rmfgen Goldfarb's maximum flow problem generator
alpar@9 391
alpar@9 392 For detailed description of these new routines and related data
alpar@9 393 structures see chapter "Graph and Network API Routines" in a new
alpar@9 394 edition of the reference manual included in the distribution.
alpar@9 395
alpar@9 396 A minor change were made in the internal routine xputc. Thanks
alpar@9 397 to Luiz Bettoni <bettoni@cpgei.ct.utfpr.edu.br> for suggestion.
alpar@9 398
alpar@9 399 A minor bug was fixed in the internal routine mpl_fn_time2str.
alpar@9 400 Thanks to Stefan Vigerske <stefan@vigerske.de> for bug report.
alpar@9 401
alpar@9 402 GLPK 4.34 (release date: Dec 04, 2008)
alpar@9 403
alpar@9 404 The GNU MathProg modeling language was supplemented with three
alpar@9 405 new built-in functions:
alpar@9 406
alpar@9 407 gmtime obtaining current calendar time
alpar@9 408 str2time converting character string to calendar time
alpar@9 409 time2str converting calendar time to character string
alpar@9 410
alpar@9 411 (Thanks to Xypron <xypron.glpk@gmx.de>.)
alpar@9 412
alpar@9 413 For detailed description of these functions see Appendix A in
alpar@9 414 the document "Modeling Language GNU MathProg", a new edition of
alpar@9 415 which was included in the distribution.
alpar@9 416
alpar@9 417 A bug was fixed in the MIP solver. Thanks to Nigel Galloway
alpar@9 418 <nigel_galloway@operamail.com> for bug report.
alpar@9 419
alpar@9 420 A new makefile was added to build the GLPK DLL with Microsoft
alpar@9 421 Visual Studio Express 2008 for 64-bit Windows. Thanks to Xypron
alpar@9 422 <xypron.glpk@gmx.de> for contribution and testing.
alpar@9 423
alpar@9 424 GLPK 4.33 (release date: Oct 30, 2008)
alpar@9 425
alpar@9 426 The following new API routines were added to the package:
alpar@9 427 glp_copy_prob copy problem object content
alpar@9 428 glp_exact solve LP in exact arithmetic
alpar@9 429 (makes lpx_exact deprecated)
alpar@9 430 glp_get_unbnd_ray determine variable causing unboundedness
alpar@9 431 (makes lpx_get_ray_info deprecated)
alpar@9 432 glp_interior solve LP with interior-point method
alpar@9 433 (makes lpx_interior deprecated)
alpar@9 434
alpar@9 435 The following new API routines for processing models written in
alpar@9 436 the GNU Mathprog language were added to the package:
alpar@9 437 glp_mpl_alloc_wksp allocate the translator workspace
alpar@9 438 glp_mpl_read_model read and translate model section
alpar@9 439 glp_mpl_read_data read and translate data section
alpar@9 440 glp_mpl_generate generate the model
alpar@9 441 glp_mpl_build_prob build LP/MIP instance from the model
alpar@9 442 glp_mpl_postsolve postsolve the model
alpar@9 443 glp_mpl_free_wksp deallocate the translator workspace
alpar@9 444 (These routines make lpx_read_model deprecated.)
alpar@9 445
alpar@9 446 For description of all these new API routines see the reference
alpar@9 447 manual included in the distribution.
alpar@9 448
alpar@9 449 A crude implementation of CPLEX-like interface to GLPK API was
alpar@9 450 added to the package. Currently it allows using GLPK as a core
alpar@9 451 LP solver for Concorde, a well known computer code for solving
alpar@9 452 the symmetric TSP. For details see examples/cplex/README.
alpar@9 453
alpar@9 454 Some bugs were fixed in the SQL table driver. Thanks to Xypron
alpar@9 455 <xypron.glpk@gmx.de>.
alpar@9 456
alpar@9 457 GLPK 4.32 (release date: Oct 03, 2008)
alpar@9 458
alpar@9 459 The following new features were included in the MIP solver
alpar@9 460 (the API routine glp_intopt):
alpar@9 461
alpar@9 462 * MIP presolver
alpar@9 463 * mixed cover cut generator
alpar@9 464 * clique cut generator
alpar@9 465 * Euclidean reduction of the objective value
alpar@9 466
alpar@9 467 Due to changes the routine glp_intopt may additionally return
alpar@9 468 GLP_ENOPFS, GLP_ENODFS, and GLP_EMIPGAP.
alpar@9 469
alpar@9 470 The API routines lpx_integer are lpx_intopt are deprecated,
alpar@9 471 since they are completely superseded by glp_intopt.
alpar@9 472
alpar@9 473 The following new branch-and-cut API routines were added:
alpar@9 474 glp_ios_row_attr determine additional row attributes
alpar@9 475 glp_ios_pool_size determine current size of the cut pool
alpar@9 476 glp_ios_add_row add constraint to the cut pool
alpar@9 477 glp_ios_del_row delete constraint from the cut pool
alpar@9 478 glp_ios_clear_pool delete all constraints from the cut pool
alpar@9 479
alpar@9 480 For description of these new routines see the reference manual
alpar@9 481 included in the distribution.
alpar@9 482
alpar@9 483 The stand-alone solver glpsol was changed to allow multiple
alpar@9 484 data files.
alpar@9 485
alpar@9 486 A new edition of the supplement "Using Data Tables in the GNU
alpar@9 487 MathProg Modeling Language" was included.
alpar@9 488
alpar@9 489 As usual, some bugs were fixed (in the MathProg translator).
alpar@9 490 Thanks to Xypron <xypron.glpk@gmx.de>.
alpar@9 491
alpar@9 492 GLPK 4.31 (release date: Sep 02, 2008)
alpar@9 493
alpar@9 494 The core LP solver based on the dual simplex method was
alpar@9 495 re-implemented and now it provides both phases I and II.
alpar@9 496
alpar@9 497 The following new API routines were added:
alpar@9 498 glp_scale_prob automatic scaling of problem data
alpar@9 499 glp_std_basis construct standard initial LP basis
alpar@9 500 glp_adv_basis construct advanced initial LP basis
alpar@9 501 glp_cpx_basis construct Bixby's initial LP basis
alpar@9 502
alpar@9 503 For description of these new routines see the reference manual
alpar@9 504 included in the distribution.
alpar@9 505
alpar@9 506 The following API routines are deprecated:
alpar@9 507 lpx_scale_prob, lpx_std_basis, lpx_adv_basis, lpx_cpx_basis.
alpar@9 508
alpar@9 509 Necessary changes were made in memory allocation routines to
alpar@9 510 resolve portability issues for 64-bit platforms.
alpar@9 511
alpar@9 512 New version of the routine lpx_write_pb to write problem data
alpar@9 513 in OPB (pseudo boolean format) was added to the package. Thanks
alpar@9 514 to Oscar Gustafsson <oscarg@isy.liu.se> for the contribution.
alpar@9 515
alpar@9 516 Two new makefiles were added to build the package for 32- and
alpar@9 517 64-bit Windows with Microsoft Visual Studio Express 2008.
alpar@9 518 Thanks to Heinrich Schuchardt <heinrich.schuchardt@gmx.de> (aka
alpar@9 519 Xypron) for the contribution and testing.
alpar@9 520
alpar@9 521 Two new makefiles were added to build the package with Digital
alpar@9 522 Mars C/C++ 8.50 and Open Watcom C/C++ 1.6 (for 32-bit Windows).
alpar@9 523
alpar@9 524 GLPK 4.30 (release date: Aug 13, 2008)
alpar@9 525
alpar@9 526 The core LP solver based on the primal simplex method was
alpar@9 527 re-implemented to allow its further improvements. Currently the
alpar@9 528 new version provides the same features as the old one, however,
alpar@9 529 it is a bit faster and more numerically stable.
alpar@9 530
alpar@9 531 Some changes were made in the MathProg translator to allow <,
alpar@9 532 <=, >=, and > on comparing symbolic values. Thanks to Heinrich
alpar@9 533 Schuchardt <heinrich.schuchardt@gmx.de> for patches.
alpar@9 534
alpar@9 535 Internal routine set_d_eps in the exact LP solver was changed
alpar@9 536 to prevent approximation errors in case of integral data.
alpar@9 537 Thanks to Markus Pilz <pilz@cs.uni-bonn.de> for bug report.
alpar@9 538
alpar@9 539 GLPK 4.29 (release date: Jul 06, 2008)
alpar@9 540
alpar@9 541 The configure script was changed to disable all optional
alpar@9 542 features by default. For details please see file INSTALL.
alpar@9 543
alpar@9 544 The following new API routines were added:
alpar@9 545 glp_erase_prob erase problem object content
alpar@9 546 glp_read_mps read problem data in MPS format
alpar@9 547 glp_write_mps write problem data in MPS format
alpar@9 548 glp_read_lp read problem data in CPLEX LP format
alpar@9 549 glp_write_lp write problem data in CPLEX LP format
alpar@9 550
alpar@9 551 For description of these new routines see the reference manual
alpar@9 552 included in the distribution.
alpar@9 553
alpar@9 554 The following API routines are deprecated:
alpar@9 555 lpx_read_mps, lpx_read_freemps, lpx_write_mps,
alpar@9 556 lpx_write_freemps, lpx_read_cpxlp, and lpx_write_cpxlp.
alpar@9 557
alpar@9 558 Two bugs were fixed. Thanks to
alpar@9 559 Anne-Laurence Putz <anne-laurence.putz@eurodecision.com> and
alpar@9 560 Xypron <xypron.glpk@gmx.de> for bug report.
alpar@9 561
alpar@9 562 GLPK 4.28 (release date: Mar 25, 2008)
alpar@9 563
alpar@9 564 The iODBC and MySQL table drivers, which allows transmitting
alpar@9 565 data between MathProg model objects and relational databases,
alpar@9 566 were re-implemented to replace a static linking by a dynamic
alpar@9 567 linking to corresponding shared libraries.
alpar@9 568 Many thanks to Heinrich Schuchardt <heinrich.schuchardt@gmx.de>
alpar@9 569 for the contribution, Rafael Laboissiere <rafael@debian.org>
alpar@9 570 for useful advices concerning the shared library support under
alpar@9 571 GNU/Linux, and Vijay Patil <vijay.patil@gmail.com> for testing
alpar@9 572 this feature under Windows XP.
alpar@9 573
alpar@9 574 A new optional feature was added to the package. This feature
alpar@9 575 is based on the zlib data compression library and allows GLPK
alpar@9 576 API routines and the stand-alone solver to read and write
alpar@9 577 compressed data files performing compression/decompression "on
alpar@9 578 the fly" (compressed data files are recognized by suffix `.gz'
alpar@9 579 in the file name). It may be useful in case of large MPS files
alpar@9 580 to save the disk space (up to ten times).
alpar@9 581
alpar@9 582 The `configure' script was re-implemented. Now it supports the
alpar@9 583 following specific options:
alpar@9 584
alpar@9 585 --with-gmp Enable using the GNU MP bignum library
alpar@9 586 --without-gmp Disable using the GNU MP bignum library
alpar@9 587 --with-zlib Enable using the zlib data compression
alpar@9 588 library
alpar@9 589 --without-zlib Disable using the zlib data compression
alpar@9 590 library
alpar@9 591 --enable-dl Enable shared library support (auto check)
alpar@9 592 --enable-dl=ltdl Enable shared library support (GNU)
alpar@9 593 --enable-dl=dlfcn Enable shared library support (POSIX)
alpar@9 594 --disable-dl Disable shared library support
alpar@9 595 --enable-odbc Enable using ODBC table driver
alpar@9 596 --disable-odbc Disable using ODBC table driver
alpar@9 597 --enable-mysql Enable using MySQL table driver
alpar@9 598 --disable-mysql Disable using MySQL table driver
alpar@9 599
alpar@9 600 For more details please see file INSTALL.
alpar@9 601
alpar@9 602 GLPK 4.27 (release date: Mar 02, 2008)
alpar@9 603
alpar@9 604 Three new table drivers were added to the MathProg translator:
alpar@9 605
alpar@9 606 xBASE built-in table driver, which allows reading and writing
alpar@9 607 data in .dbf format (only C and N fields are supported);
alpar@9 608
alpar@9 609 MySQL table driver, which provides connection to a MySQL
alpar@9 610 database;
alpar@9 611
alpar@9 612 iODBC table driver, which provides connection to a database
alpar@9 613 through ODBC.
alpar@9 614
alpar@9 615 The MySQL and iODBC table drivers were contributed to GLPK by
alpar@9 616 Heinrich Schuchardt <heinrich.schuchardt@gmx.de>.
alpar@9 617
alpar@9 618 The table driver is a program module which allows transmitting
alpar@9 619 data between MathProg model objects and external data tables.
alpar@9 620
alpar@9 621 For detailed description of the table statement and table
alpar@9 622 drivers see the document "Using Data Tables in the GNU MathProg
alpar@9 623 Modeling Language" (file doc/tables.txt) included in the
alpar@9 624 distribution. Some examples which demonstrate using MySQL and
alpar@9 625 iODBC table drivers can be found in subdirectory examples/sql.
alpar@9 626
alpar@9 627 GLPK 4.26 (release date: Feb 17, 2008)
alpar@9 628
alpar@9 629 The table statement was implemented in the GNU MathProg
alpar@9 630 modeling language. This new feature allows reading data from
alpar@9 631 external tables into model objects such as sets and parameters
alpar@9 632 as well as writing results of computations to external tables.
alpar@9 633
alpar@9 634 A table is a (unordered) set of records, where each record
alpar@9 635 consists of the same number of fields, and each field is
alpar@9 636 provided with a unique symbolic name called the field name.
alpar@9 637
alpar@9 638 Currently the GLPK package has the only built-in table driver,
alpar@9 639 which supports tables in the CSV (comma-separated values) file
alpar@9 640 format. This format is very simple and supported by almost all
alpar@9 641 spreadsheets and database management systems.
alpar@9 642
alpar@9 643 Detailed description of the table statement and CSV format can
alpar@9 644 be found in file doc/tables.txt, included in the distribution.
alpar@9 645
alpar@9 646 GLPK 4.25 (release date: Dec 19, 2007)
alpar@9 647
alpar@9 648 A tentative implementation of Gomory's mixed integer cuts was
alpar@9 649 included in the branch-and-cut solver. To enable generating
alpar@9 650 Gomory's cuts the control parameter gmi_cuts passed to the
alpar@9 651 routine glp_intopt should be set to GLP_ON. This feature is
alpar@9 652 also available in the solver glpsol through command-line option
alpar@9 653 '--gomory'. For more details please see the reference manual
alpar@9 654 included in the distribution.
alpar@9 655
alpar@9 656 GLPK 4.24 (release date: Nov 21, 2007)
alpar@9 657
alpar@9 658 A tentative implementation of MIR (mixed integer rounding) cuts
alpar@9 659 was included in the MIP solver. To enable generating MIR cuts
alpar@9 660 the control parameter mir_cuts passed to the routine glp_intopt
alpar@9 661 should be set to GLP_ON. This feature is also available in the
alpar@9 662 stand-alone solver glpsol via command-line option '--mir'. For
alpar@9 663 more details please see the reference manual included in the
alpar@9 664 distribution.
alpar@9 665
alpar@9 666 The implementation is mainly based on the following two papers:
alpar@9 667
alpar@9 668 1. H. Marchand and L. A. Wolsey. Aggregation and mixed integer
alpar@9 669 rounding to solve MIPs. CORE discussion paper 9839, CORE,
alpar@9 670 Universite catholique de Louvain, June 1998.
alpar@9 671
alpar@9 672 2. G. Andreello, A. Caprara, and M. Fischetti. Embedding cuts
alpar@9 673 in a Branch&Cut framework. Preliminary draft, October 2003.
alpar@9 674
alpar@9 675 MIR cuts can be generated on any level of the search tree that
alpar@9 676 makes the GLPK MIP solver to be a real branch-and-cut solver.
alpar@9 677
alpar@9 678 A bug was fixed in the routine lpx_write_cpxlp. If a variable
alpar@9 679 x has upper bound and no lower bound, it should appear in the
alpar@9 680 bounds section as "-inf <= x <= u", not as "x <= u". Thanks to
alpar@9 681 Enric Rodriguez <erodri@lsi.upc.edu> for the bug report.
alpar@9 682
alpar@9 683 GLPK 4.23 (release date: Oct 28, 2007)
alpar@9 684
alpar@9 685 The following new API routines were added:
alpar@9 686
alpar@9 687 glp_read_sol read basic solution from text file
alpar@9 688 glp_write_sol write basic solution to text file
alpar@9 689 glp_read_ipt read interior-point solution from text file
alpar@9 690 glp_write_ipt write interior-point solution to text file
alpar@9 691 glp_read_mip read MIP solution from text file
alpar@9 692 glp_write_mip write MIP solution to text file
alpar@9 693
alpar@9 694 For description of these routines and corresponding file
alpar@9 695 formats see Chapter "API Routines", Section "Utility routines"
alpar@9 696 in the reference manual included in the distribution.
alpar@9 697
alpar@9 698 Advanced API routine glp_free_env was added. It may be used by
alpar@9 699 the application program to free all resources allocated by GLPK
alpar@9 700 routines.
alpar@9 701
alpar@9 702 The following three new command-line options were added to the
alpar@9 703 solver glpsol:
alpar@9 704
alpar@9 705 --mipgap tol set relative MIP gap tolerance
alpar@9 706 -r filename read solution from filename
alpar@9 707 -w filename write solution to filename
alpar@9 708
alpar@9 709 GLPK 4.22 (release date: Sep 19, 2007)
alpar@9 710
alpar@9 711 This is a maintainer release.
alpar@9 712
alpar@9 713 A bug was fixed in the MIP preprocessor (ios_preprocess_node).
alpar@9 714 Thanks to Roberto Bagnara <bagnara@cs.unipr.it> (Department of
alpar@9 715 Mathematics, University of Parma, Italy) for the bug report.
alpar@9 716
alpar@9 717 A bug was fixed in the MIP preprocessor (col_implied_bounds),
alpar@9 718 due to which constraint coefficients with small magnitude could
alpar@9 719 lead to wrong implied bounds of structural variables.
alpar@9 720
alpar@9 721 A similar bug was fixed in the routine reduce_bounds.
alpar@9 722
alpar@9 723 A bug was fixed in the routines glp_set_mat_row and
alpar@9 724 glp_set_mat_col. (The bug appeared due to incorrect removing
alpar@9 725 zero elements from the row/column lists.)
alpar@9 726
alpar@9 727 A bug was fixed in the API routines lpx_read_mps and
alpar@9 728 lpx_read_freemps, due to which bounds of type LI specified in
alpar@9 729 BOUNDS section were incorrectly processed.
alpar@9 730
alpar@9 731 A call to standard function vsprintf was replaced by a call to
alpar@9 732 vsnprintf for security reasons. Many thanks to Peter T. Breuer
alpar@9 733 <ptb@inv.it.uc3m.es> and Rafael Laboissiere <rafael@debian.org>.
alpar@9 734
alpar@9 735 GLPK 4.21 (release date: Aug 28, 2007)
alpar@9 736
alpar@9 737 Additional reasons for calling the callback routine used in the
alpar@9 738 MIP solver (glp_intopt) were introduced. Currently the following
alpar@9 739 reasons are supported:
alpar@9 740
alpar@9 741 * request for subproblem selection
alpar@9 742 * request for preprocessing
alpar@9 743 * request for row generation
alpar@9 744 * request for heuristic solution
alpar@9 745 * request for cut generation
alpar@9 746 * request for branching
alpar@9 747 * better integer solution found
alpar@9 748
alpar@9 749 A basic preprocessing component used to improve subproblem
alpar@9 750 formulations by tightening bounds of variables was included in
alpar@9 751 the MIP solver. Depending on the control parameter pp_tech
alpar@9 752 passed to the routine glp_intopt the preprocessing can be
alpar@9 753 performed either on the root level or on all levels (default)
alpar@9 754 or can be disabled.
alpar@9 755
alpar@9 756 Backtracking heuristic used by default in the MIP solver was
alpar@9 757 changed to the "best local bound".
alpar@9 758
alpar@9 759 For more details see Chapter "Advanced API routines", Section
alpar@9 760 "Branch-and-bound interface routines" in a new edition of the
alpar@9 761 reference manual included in the distribution.
alpar@9 762
alpar@9 763 GLPK 4.20 (release date: Jul 26, 2007)
alpar@9 764
alpar@9 765 API routine lpx_integer was replaced by API routine glp_intopt,
alpar@9 766 which provides equivalent functionality and additionally allows
alpar@9 767 the application to control the solution process by means of the
alpar@9 768 user-written callback routine, which is called by the solver at
alpar@9 769 various points of the branch-and-bound algorithm. Besides, the
alpar@9 770 new MIP solver allows generating "lazy" constraints and cutting
alpar@9 771 planes on all levels of the branch-and-bound tree, not only on
alpar@9 772 the root level. The routine lpx_integer is also still available
alpar@9 773 for the backward compatibility.
alpar@9 774
alpar@9 775 The following new advanced API routines, which may be called
alpar@9 776 from the B&B callback routine, were included in the package:
alpar@9 777
alpar@9 778 glp_ios_reason determine reason for calling callback
alpar@9 779 routine
alpar@9 780 glp_ios_get_prob access the problem object
alpar@9 781 glp_ios_tree_size determine size of the branch-and-bound tree
alpar@9 782 glp_ios_curr_node determine current active subproblem
alpar@9 783 glp_ios_next_node determine next active subproblem
alpar@9 784 glp_ios_prev_node determine previous active subproblem
alpar@9 785 glp_ios_up_node determine parent subproblem
alpar@9 786 glp_ios_node_level determine subproblem level
alpar@9 787 glp_ios_node_bound determine subproblem local bound
alpar@9 788 glp_ios_mip_gap compute relative MIP gap
alpar@9 789 glp_ios_heur_sol provide solution found by heuristic
alpar@9 790 glp_ios_terminate terminate the solution process
alpar@9 791
alpar@9 792 For description of these routines see Chapter "Advanced API
alpar@9 793 routines", Section "Branch-and-bound interface routines" in a
alpar@9 794 new edition of the reference manual, which was included in the
alpar@9 795 distribution.
alpar@9 796
alpar@9 797 Old version of the integer optimization suite (IOS) as well as
alpar@9 798 TSP solver tspsol based on it are no longer supported and were
alpar@9 799 removed from the package.
alpar@9 800
alpar@9 801 A minor error in the MIP presolver was fixed; thanks to Graham
alpar@9 802 Rockwell <bionomicron@gmail.com> for the bug report.
alpar@9 803
alpar@9 804 GLPK 4.19 (release date: Jul 05, 2007)
alpar@9 805
alpar@9 806 The principal change is upgrading to GPLv3.
alpar@9 807
alpar@9 808 A serious bug in the routine glp_del_cols was fixed; thanks to
alpar@9 809 Cedric[FR] <fox2113@wanadoo.fr> for the bug report. The bug
alpar@9 810 appeared because on deleting non-basic columns the basis header
alpar@9 811 remained valid, however, contained invalid (old) column ordinal
alpar@9 812 numbers.
alpar@9 813
alpar@9 814 A new advanced API routine glp_mem_limit was added.
alpar@9 815
alpar@9 816 The case GLP_EBOUND was added to the routine lpx_simplex.
alpar@9 817 Thanks to Cameron Kellough <Cameron.Kellough@sri.com> for the
alpar@9 818 bug report.
alpar@9 819
alpar@9 820 An API routine lpx_write_pb to write the problem instance in
alpar@9 821 OPB (pseudo boolean) format format was added. Thanks to Oscar
alpar@9 822 Gustafsson <oscarg@isy.liu.se> for the contribution.
alpar@9 823
alpar@9 824 Two new options --wpb and --wnpb were added to glpsol to write
alpar@9 825 the problem instance in OPB format.
alpar@9 826
alpar@9 827 GLPK 4.18 (release date: Jun 25, 2007)
alpar@9 828
alpar@9 829 The following new API routines were added:
alpar@9 830
alpar@9 831 glp_set_rii set (change) row scale factor
alpar@9 832 glp_set_sjj set (change) column scale factor
alpar@9 833 glp_get_rii retrieve row scale factor
alpar@9 834 glp_get_sjj retrieve column scale factor
alpar@9 835 glp_simplex solve LP problem with the simplex method
alpar@9 836 (this routine replaces lpx_simplex, which is
alpar@9 837 also available for backward compatibility)
alpar@9 838 glp_init_smcp initialize simplex method control params
alpar@9 839 glp_bf_exists check if the basis factorization exists
alpar@9 840 glp_factorize compute the basis factorization
alpar@9 841 glp_bf_updated check if the basis factorization has been
alpar@9 842 updated
alpar@9 843 glp_get_bfcp retrieve basis factorization control params
alpar@9 844 glp_set_bfcp change basis factorization control params
alpar@9 845 glp_get_bhead retrieve the basis header information
alpar@9 846 glp_get_row_bind retrieve row index in the basis header
alpar@9 847 glp_get_col_bind retrieve column index in the basis header
alpar@9 848 glp_ftran perform forward transformation
alpar@9 849 glp_btran perform backward transformation
alpar@9 850
alpar@9 851 For description of all these routines see a new edition of the
alpar@9 852 reference manual included in the distribution.
alpar@9 853
alpar@9 854 Type names ulong_t and uldiv_t were changed to glp_ulong and
alpar@9 855 glp_uldiv to avoid conflicts with standard type names on some
alpar@9 856 platforms. Thanks to Boris Wirtz <Boris.Wirtz@uni-oldenburg.de>
alpar@9 857 for the bug report.
alpar@9 858
alpar@9 859 Some new examples in the MathProg language were added. Thanks
alpar@9 860 to Sebastian Nowozin <nowozin@gmail.com>.
alpar@9 861
alpar@9 862 GLPK 4.17 (release date: May 26, 2007)
alpar@9 863
alpar@9 864 API routines glp_set_mat_row, glp_set_mat_col, and glp_load_mat
alpar@9 865 were modified to allow zero constraint coefficients (which are
alpar@9 866 not stored in the constraint matrix). Note that constraint
alpar@9 867 coefficients with duplicate row/column indices are not allowed.
alpar@9 868
alpar@9 869 Another form of LP basis factorization was implemented in the
alpar@9 870 package. It is based on LU-factorization of an initial basis
alpar@9 871 and Schur complement to reflect changes in the basis. Currently
alpar@9 872 the implementation is incomplete and provides only updating the
alpar@9 873 factorization on replacing a column of the basis matrix. On API
alpar@9 874 level the user can set the control parameter LPX_K_BFTYPE to
alpar@9 875 choose between the folloiwng forms of LP basis factorization to
alpar@9 876 be used in the simplex method routines:
alpar@9 877 1) LU + Forrest-Tomlin update;
alpar@9 878 2) LU + Schur complement + Bartels-Golub update;
alpar@9 879 3) LU + Schur complement + Givens rotation update.
alpar@9 880 The GLPK implementation is similar to LUSOL/LUMOD developed by
alpar@9 881 Michael A. Saunders.
alpar@9 882
alpar@9 883 The user can choose the form of LP basis factorzation used by
alpar@9 884 the simplex method routines by specifying the folloiwng options
alpar@9 885 of glpsol: --luf, --cbg, --cgr.
alpar@9 886
alpar@9 887 GLPK 4.16 (release date: May 05, 2007)
alpar@9 888
alpar@9 889 A number of basic GLPK API routines, which now are in the
alpar@9 890 stable stable, were renamed to be prefixed with 'glp_'. Note
alpar@9 891 that all these routines are available via their old names
alpar@9 892 prefixed with 'lpx_' that keeps the downward compatibility with
alpar@9 893 older versions of the package.
alpar@9 894
alpar@9 895 Three new GLPK API routines were added to the package:
alpar@9 896 glp_version, glp_term_hook, and glp_mem_usage; for more details
alpar@9 897 see a new edition of the GLPK reference manual included in the
alpar@9 898 distribution. The routine glp_version reports the actual version
alpar@9 899 of the GLPK library and also can be used (along with the header
alpar@9 900 glpk.h) in Autotools specification files to check if the GLPK
alpar@9 901 library has been installed.
alpar@9 902
alpar@9 903 The header glpk.h was changed to conform to C++ environment.
alpar@9 904
alpar@9 905 GLPK 4.15 (release date: Feb 18, 2007)
alpar@9 906
alpar@9 907 Autotools specification files (configure.ac, Makefile.am) were
alpar@9 908 changed to use GNU Libtool. This allows building the static as
alpar@9 909 well as shared GLPK library.
alpar@9 910
alpar@9 911 GLPK 4.14 (release date: Feb 05, 2007)
alpar@9 912
alpar@9 913 Now GLPK conforms to ILP32, LLP64, and LP64 programming models
alpar@9 914 (the latter seems to be the ultimate choice regarding 64-bit
alpar@9 915 architectures). Note that GLPK itself is a 32-bit application,
alpar@9 916 and the conformity only means that the package works correctly
alpar@9 917 on all these arenae. Nevertheless, on 64-bit platforms it is
alpar@9 918 possible to use more than 4GB of memory, if necessary.
alpar@9 919
alpar@9 920 GLPK 4.13 (release date: Nov 13, 2006)
alpar@9 921
alpar@9 922 A tentative implementation of the "exact" simplex method based
alpar@9 923 on bignum (rational) arithmetic was included in the package.
alpar@9 924
alpar@9 925 On API level this new feature is available through the routine
alpar@9 926 lpx_exact, which is similar to the routine lpx_simplex.
alpar@9 927
alpar@9 928 In the solver glpsol this feature is available through two new
alpar@9 929 command-line options: --exact and --xcheck. If the '--exact'
alpar@9 930 option is specified, glpsol solves LP instance using the exact
alpar@9 931 simplex method; in case of MIP it is used to obtain optimal
alpar@9 932 solution of LP relaxation. If the --xcheck option is specified,
alpar@9 933 LP instance (or LP relaxation) is solved using the standard
alpar@9 934 (floating-point) simplex method, however, then glpsol calls the
alpar@9 935 exact simplex routine to make sure that the final LP basis is
alpar@9 936 exactly optimal, and if it is not, to perform some additional
alpar@9 937 simplex iterations in exact arithmetic.
alpar@9 938
alpar@9 939 GLPK 4.12 (release date: Nov 08, 2006)
alpar@9 940
alpar@9 941 A tentative implementation of some simplex method routines
alpar@9 942 based on exact (bignum) arithmetic was included in the package.
alpar@9 943 Currently these routines provide computing LU-factorization of
alpar@9 944 the basis matrix and computing components of basic solution.
alpar@9 945
alpar@9 946 These routines were used to implement a routine, which checks
alpar@9 947 primal and dual feasibility of basic solution exactly, i.e. in
alpar@9 948 rational numbers, without round-off errors. In glpsol this
alpar@9 949 feature is available through the command-line option --xcheck.
alpar@9 950
alpar@9 951 GLPK has its own low-level routines implementing operations on
alpar@9 952 integer and rational numbers that makes it independent on other
alpar@9 953 software packages. However, to attain a much better performance
alpar@9 954 it is highly recommended to install (before configuring GLPK)
alpar@9 955 the GNU Multiple Precision Arithmetic Library (GMP). Using GMP
alpar@9 956 makes computations 100-200 times faster.
alpar@9 957
alpar@9 958 GLPK 4.11 (release date: Jul 25, 2006)
alpar@9 959
alpar@9 960 Three new built-in functions in the modeling language were
alpar@9 961 implemented: card (cardinality of set), length (length of
alpar@9 962 character string), and substr (substring of character string).
alpar@9 963 Another improvement concerns the printf statement which now
alpar@9 964 allows redirecting its output to a specified file. These new
alpar@9 965 features are illustrated in example models crypto.mod and
alpar@9 966 graph.mod included in the distribution. For more details see
alpar@9 967 the document "Modeling Language GNU MathProg".
alpar@9 968
alpar@9 969 Four batch files (along with corresponding makefiles) were
alpar@9 970 included in the distribution to simplify building GLPK under
alpar@9 971 MS Windows; see them in subdirectory 'w32'.
alpar@9 972
alpar@9 973 GLPK 4.10 (release date: May 11, 2006)
alpar@9 974
alpar@9 975 Cutting planes of two new classes were implemented: mixed cover
alpar@9 976 cuts and clique cuts. On API level this feature can be enabled
alpar@9 977 by setting control parameter LPX_K_USECUTS passed to the routine
alpar@9 978 lpx_intopt. In glpsol this feature is available through the
alpar@9 979 command-line options --cover and --clique. For more details see
alpar@9 980 the reference manual.
alpar@9 981
alpar@9 982 Now the routines lpx_read_mps and lpx_read_freemps support LI
alpar@9 983 bound type. It is similar to LO, however, indicates the column
alpar@9 984 as of integer kind.
alpar@9 985
alpar@9 986 GLPK 4.9 (release date: Jan 17, 2006)
alpar@9 987
alpar@9 988 An advanced MIP solver was implemented. It includes:
alpar@9 989
alpar@9 990 - basic presolving technique (removing free, singleton and
alpar@9 991 redundant rows, improving bounds of columns, removing fixed
alpar@9 992 columns, reducing constraint coefficents);
alpar@9 993
alpar@9 994 - generating cutting planes to improve LP relaxation (currently
alpar@9 995 only Gomory's mixed integer cuts are implemented);
alpar@9 996
alpar@9 997 - using the branch-and-bound method to solve resultant MIP;
alpar@9 998
alpar@9 999 - recovering solution of the original MIP.
alpar@9 1000
alpar@9 1001 The solver is available on API level via the routine lpx_intopt
alpar@9 1002 (see the reference manual). It is similar to the routine
alpar@9 1003 lpx_integer, however, does not require initial solution of LP
alpar@9 1004 relaxation.
alpar@9 1005
alpar@9 1006 The solver is also available in the command-line utility glpsol
alpar@9 1007 via two options: --intopt (only presolving) and --cuts (assumes
alpar@9 1008 --intopt plus generating cuts).
alpar@9 1009
alpar@9 1010 Note that efficiency of the MIP solver strongly depends on the
alpar@9 1011 internal structure of the problem to be solved. For some hard
alpar@9 1012 instances it is very efficient, but for other instances it may
alpar@9 1013 be significantly worse than the standard branch-and-bound.
alpar@9 1014
alpar@9 1015 For some comparative benchmarks see doc/bench1.txt.
alpar@9 1016
alpar@9 1017 Well, what else...
alpar@9 1018
alpar@9 1019 Three built-in functions were added to MathProg: sin, cos, and
alpar@9 1020 atan (the latter allows one or two arguments).
alpar@9 1021
alpar@9 1022 Some bugs were fixed.
alpar@9 1023
alpar@9 1024 Several new examples in MathProg were included: color.mod
alpar@9 1025 (graph coloring problem), tsp.mod (traveling salesman problem),
alpar@9 1026 and pbn.mod (paint-by-numbers puzzle).
alpar@9 1027
alpar@9 1028 GLPK 4.8 (release date: Jan 12, 2005)
alpar@9 1029
alpar@9 1030 Core simplex method and interior-point method routines were
alpar@9 1031 re-implemented and now they use a new, "storage-by-rows" sparse
alpar@9 1032 matrix format (unlike previous versions where linked lists were
alpar@9 1033 used to represent sparse matrices). For details see ChangeLog.
alpar@9 1034
alpar@9 1035 Also a minor bug was fixed in API routine lpx_read_cpxlp.
alpar@9 1036
alpar@9 1037 GLPK 4.7 (release date: Aug 23, 2004)
alpar@9 1038
alpar@9 1039 Now GLPK supports free MPS format. Two new API routines
alpar@9 1040 lpx_read_freemps (to read problem data in free MPS format) and
alpar@9 1041 lpx_write_freemps (to write problem data in free MPS format)
alpar@9 1042 were added. This feature is also available in the solver glpsol
alpar@9 1043 via new command-line options --freemps and --wfreemps. For more
alpar@9 1044 details see the GLPK reference manual.
alpar@9 1045
alpar@9 1046 API routines lpx_read_cpxlp and lpx_write_cpxlp for reading and
alpar@9 1047 writing problem data in CPLEX LP format were re-implemented to
alpar@9 1048 allow long symbolic names (up to 255 characters).
alpar@9 1049
alpar@9 1050 The following three modules were temporarily removed from the
alpar@9 1051 GLPK distribution due to licensing problems: DELI (an interface
alpar@9 1052 module to Delphi), GLPKMEX (an interface module to Matlab), and
alpar@9 1053 JNI (an interface module to Java).
alpar@9 1054
alpar@9 1055 GLPK 4.6 (release date: Aug 04, 2004)
alpar@9 1056
alpar@9 1057 Three new statements were implemented in the GNU MathProg
alpar@9 1058 language: solve, printf, and for. Their detailed description can
alpar@9 1059 be found in the GLPK documentation included in the distribution.
alpar@9 1060 (See also a sample model, examples/queens.mod, which illustrates
alpar@9 1061 using these new statements.)
alpar@9 1062
alpar@9 1063 Two new API routines were added to the package: lpx_read_prob
alpar@9 1064 and lpx_write_prob. They allow reading/writing problem data in
alpar@9 1065 GNU LP low-level text format.
alpar@9 1066
alpar@9 1067 Three new command-line options were implemented in the LP/MIP
alpar@9 1068 solver glpsol: --glp (to read problem data in GNU LP format),
alpar@9 1069 --wglp (to write problem data in GNU LP format), and --name (to
alpar@9 1070 change problem name). Now glpsol also supports processing models
alpar@9 1071 where the new statements (see above) are used.
alpar@9 1072
alpar@9 1073 A new version of GLPKMEX, a Matlab MEX interface to GLPK, was
alpar@9 1074 included. For more details see contrib/glpkmex/ChangeLog.
alpar@9 1075
alpar@9 1076 GLPK 4.5 (release date: Jul 19, 2004)
alpar@9 1077
alpar@9 1078 The branch-and-bound solver was completely re-implemented.
alpar@9 1079
alpar@9 1080 Some modifications were made in memory allocation routines that
alpar@9 1081 allows using the package on 64-bit platforms.
alpar@9 1082
alpar@9 1083 For more details see ChangeLog.
alpar@9 1084
alpar@9 1085 GLPK 4.4 (release date: Jan 17, 2004)
alpar@9 1086
alpar@9 1087 All API routines were re-implemented using new data structures.
alpar@9 1088 The new implementation provides the same specifications and
alpar@9 1089 functionality of API routines as the old one, however, it has
alpar@9 1090 some important advantages, in particular:
alpar@9 1091 * linked lists are used everywhere that allows creating and
alpar@9 1092 modifying the problem object as efficiently as possible
alpar@9 1093 * all data stored in the problem object are non-scaled (even if
alpar@9 1094 the internal scaling is used) that prevents distortion of the
alpar@9 1095 original problem data
alpar@9 1096 * solution components obtained by the solver remain available
alpar@9 1097 even if the problem object has been modified
alpar@9 1098 * no solver-specific data are used in the new data structures
alpar@9 1099 that allows attaching any external lp/mip solver using GLPK
alpar@9 1100 API as an uniform interface
alpar@9 1101 Note that some API routines became obsolete being replaced by
alpar@9 1102 new, more convenient routines. These obsolete routines are kept
alpar@9 1103 for backward compatibility, however, they will be removed in
alpar@9 1104 the future. For more details please see ChangeLog and the GLPK
alpar@9 1105 Reference Manual.
alpar@9 1106
alpar@9 1107 New edition of the GLPK Reference Manual was included in the
alpar@9 1108 distribution.
alpar@9 1109
alpar@9 1110 GLPKMEX, a Matlab MEX interface to GLPK package, contributed by
alpar@9 1111 Nicolo Giorgetti <giorgetti@dii.unisi.it> was included in the
alpar@9 1112 distribution.
alpar@9 1113
alpar@9 1114 GLPK FAQ contributed by Harley Mackenzie <hjm@bigpond.com> was
alpar@9 1115 included in the distribution.
alpar@9 1116
alpar@9 1117 GLPK 4.3 (release date: Dec 12, 2003)
alpar@9 1118
alpar@9 1119 The bug, due to which the standard math library is not linked
alpar@9 1120 on building the package on some platforms, was fixed.
alpar@9 1121
alpar@9 1122 The following new built-in functions were added to the MathProg
alpar@9 1123 language: round, trunc, Irand224, Uniform01, Uniform, Normal01,
alpar@9 1124 Normal. For details see the language description.
alpar@9 1125
alpar@9 1126 The MathProg syntax was changed to allow writing 'subj to' that
alpar@9 1127 means 'subject to'.
alpar@9 1128
alpar@9 1129 The new api routine lpx_get_ray_info was added. It is intended
alpar@9 1130 to determine which (non-basic) variable causes unboundness. For
alpar@9 1131 details see the reference manual.
alpar@9 1132
alpar@9 1133 The module glpmps.c was changed to avoid compilation errors on
alpar@9 1134 building the package on Mac OS X.
alpar@9 1135
alpar@9 1136 Several typos was fixed and some new material was added to the
alpar@9 1137 GLPK documentation.
alpar@9 1138
alpar@9 1139 GLPK 4.2 (release date: Nov 14, 2003)
alpar@9 1140
alpar@9 1141 A preliminary implementation of the Integer Optimization Suite
alpar@9 1142 (IOS) was included in the package. The Branch-and-Cut Framework
alpar@9 1143 being completely superseded by IOS was removed from the package.
alpar@9 1144
alpar@9 1145 New API routine lpx_print_sens_bnds intended for bounds
alpar@9 1146 sensitivity analysis was contributed to GLPK by Brady Hunsaker
alpar@9 1147 <hunsaker@engr.pitt.edu>. This function is also available in
alpar@9 1148 the solver glpsol (via command-line option --bounds).
alpar@9 1149
alpar@9 1150 An improved version of GLPK JNI (Java Native Interface) was
alpar@9 1151 contributed by Chris Rosebrugh <cpr@pobox.com>.
alpar@9 1152
alpar@9 1153 GLPK DELI (Delphi Interface) was contributed by Ivo van Baren
alpar@9 1154 <i.van.baren@freeler.nl>.
alpar@9 1155
alpar@9 1156 Several makefiles were added to allow compiling GLPK on some
alpar@9 1157 non-GNU 32-bit platforms:
alpar@9 1158 * Windows single-threaded static library, Visual C++ 6.0
alpar@9 1159 * Windows multi-threaded dynamic library, Visual C++ 6.0
alpar@9 1160 * Windows single-threaded static library, Borland C++ 5.2
alpar@9 1161 * DOS single-threaded static library, Digital Mars C++ 7.50
alpar@9 1162
alpar@9 1163 And, of course, some bugs were fixed.
alpar@9 1164
alpar@9 1165 For more details see ChangeLog.
alpar@9 1166
alpar@9 1167 GLPK 4.1 (release date: Aug 23, 2003)
alpar@9 1168
alpar@9 1169 Some improvements were made in the lp/mip solver routines and
alpar@9 1170 several bugs were fixed in the model translator.
alpar@9 1171
alpar@9 1172 For more details see ChangeLog.
alpar@9 1173
alpar@9 1174 GLPK 4.0 (release date: May 06, 2003)
alpar@9 1175
alpar@9 1176 Now GLPK supports the GNU MathProg modeling language, which is
alpar@9 1177 a subset of the AMPL modeling language.
alpar@9 1178
alpar@9 1179 The document "GLPK: Modeling Language GNU MathProg" included in
alpar@9 1180 the distribution is a complete description of GNU MathProg. (See
alpar@9 1181 the files lang.latex, lang.dvi, and lang.ps in the subdirectory
alpar@9 1182 'doc'. See also some examples in the subdirectory 'sample'.)
alpar@9 1183
alpar@9 1184 New version of the solver glpsol, which supports models written
alpar@9 1185 in GNU MathProg, was implemented. (Brief instructions how to use
alpar@9 1186 glpsol can be found in the GNU MathProg documentation.)
alpar@9 1187
alpar@9 1188 The GLPK/L modeling language is no more supported. The reason is
alpar@9 1189 that GNU MathProg being much more powerful completely supersedes
alpar@9 1190 all features of GLPK/L.
alpar@9 1191
alpar@9 1192 GLPK 3.3 (release date: Mar 25, 2003)
alpar@9 1193
alpar@9 1194 LP PRESOLVER
alpar@9 1195 ------------
alpar@9 1196
alpar@9 1197 Now the routine lpx_simplex (which is a driver to the simplex
alpar@9 1198 method for solving LP) is provided with the built-in LP
alpar@9 1199 presolver, which is a program that transforms the original LP
alpar@9 1200 problem to an equivalent LP problem, which may be easier for
alpar@9 1201 solving with the simplex method than the original one. Once the
alpar@9 1202 transformed LP has been solver, the presolver transforms its
alpar@9 1203 basic solution back to a corresponding basic solution of the
alpar@9 1204 original problem. For details about this feature please see the
alpar@9 1205 GLPK reference manual.
alpar@9 1206
alpar@9 1207 Currently the LP presolver implements the following features:
alpar@9 1208 * removing empty rows;
alpar@9 1209 * removing empty columns;
alpar@9 1210 * removing free rows;
alpar@9 1211 * removing fixed columns;
alpar@9 1212 * removing row singletons, which have the form of equations;
alpar@9 1213 * removing row singletons, which have the form of inequalities;
alpar@9 1214 * removing column singletons, which are implied slack variables;
alpar@9 1215 * fixing and removing column singletons, which are implied free
alpar@9 1216 variables;
alpar@9 1217 * removing forcing rows that involves fixing and removing the
alpar@9 1218 corresponding columns;
alpar@9 1219 * checking for primal and dual infeasibilities.
alpar@9 1220
alpar@9 1221 The LP presolver is also used by default in the stand-alone
alpar@9 1222 program glpsol. In order *not* to use it, the option --nopresol
alpar@9 1223 should be specified in the command-line.
alpar@9 1224
alpar@9 1225 CHANGES IN GLPK/L
alpar@9 1226 -----------------
alpar@9 1227
alpar@9 1228 The syntax and semantics of the GLPK/L modeling language was
alpar@9 1229 changed to allow declaration of "interval" sets. This means that
alpar@9 1230 now the user can declare a set, for example, as:
alpar@9 1231
alpar@9 1232 set task = [8:11];
alpar@9 1233
alpar@9 1234 that is exactly equivalent to the following declaration:
alpar@9 1235
alpar@9 1236 set task = (task_8, task_9, task_10, task_11);
alpar@9 1237
alpar@9 1238 For details see the language description.
alpar@9 1239
alpar@9 1240 JAVA INTERFACE
alpar@9 1241 --------------
alpar@9 1242
alpar@9 1243 Now GLPK includes the package GLPK JNI (Java Native Interface)
alpar@9 1244 that implements Java binding for GLPK. It allows Java programs
alpar@9 1245 to utilize GLPK in solving LP and MIP problems. For details see
alpar@9 1246 a brief user's guide in the subdirectory contrib/java-binding.
alpar@9 1247 This package was developed and programmed by Yuri Victorovich
alpar@9 1248 <yuri@gjt.org>, who contributed it to GLPK.
alpar@9 1249
alpar@9 1250 GLPK 3.2.4 (release date: Feb 18, 2003)
alpar@9 1251
alpar@9 1252 This is a bug-fix release. For details see ChangeLog.
alpar@9 1253
alpar@9 1254 GLPK 3.2.3 (release date: Nov 11, 2002)
alpar@9 1255
alpar@9 1256 A new implementation of the api routine lpx_integer which now
alpar@9 1257 is based on the b&b driver (which is based on the implicit
alpar@9 1258 enumeration suite) was included in the package. This new
alpar@9 1259 implementation has exactly the same functionality as the old
alpar@9 1260 version, so all changes are transparent to the api user.
alpar@9 1261
alpar@9 1262 Four new api routines were included in the package:
alpar@9 1263 lpx_check_kkt checks Karush-Kuhn-Tucker optmality conditions;
alpar@9 1264 lpx_read_bas reads predifined basis in MPS format;
alpar@9 1265 lpx_write_bas writes current basis in MPS format;
alpar@9 1266 lpx_write_lpt writes problem data in CPLEX LP format.
alpar@9 1267
alpar@9 1268 Also other minor improvements were made (for details see the
alpar@9 1269 file 'ChangeLog').
alpar@9 1270
alpar@9 1271 GLPK 3.2.2 (release date: Oct 14, 2002)
alpar@9 1272
alpar@9 1273 The api routine lpx_read_lpt was included in the package. It
alpar@9 1274 is similar to the routine lpx_read_mps and intended to read
alpar@9 1275 LP/MIP data prepared in CPLEX LP format. Description of this
alpar@9 1276 format is given in the GLPK reference manual, a new edition of
alpar@9 1277 which was also included in the distribution (see the files
alpar@9 1278 'refman.latex', 'refman.dvi', 'refman.ps' in the subdirectory
alpar@9 1279 'doc'). In order to use data files in CPLEX LP format with the
alpar@9 1280 solver glpsol the option '--lpt' should be specified in the
alpar@9 1281 command line.
alpar@9 1282
alpar@9 1283 Several bugs were fixed and some minor improvements were made
alpar@9 1284 (for details see the file 'ChangeLog').
alpar@9 1285
alpar@9 1286 GLPK 3.2.1 (release date: Aug 12, 2002)
alpar@9 1287
alpar@9 1288 Now GLPK includes a preliminary implementation of the
alpar@9 1289 branch-and-cut framework, which is a set of data structures and
alpar@9 1290 routines intended for developing branch-and-cut methods for
alpar@9 1291 solving mixed-integer and combinatorial optimization problems.
alpar@9 1292
alpar@9 1293 Detailed decsription of the branch-and-cut framework is given in
alpar@9 1294 the document "GLPK: A Preliminary Implementation of the
alpar@9 1295 Branch-And-Cut Framework" included in the distribution (see the
alpar@9 1296 file 'brcut.txt' in the subdirectory 'doc').
alpar@9 1297
alpar@9 1298 In order to illustrate how the GLPK branch-and-cut framework
alpar@9 1299 can be used for solving a particular optimization problem there
alpar@9 1300 is an example included in the package. This is a stand-alone
alpar@9 1301 program, TSPSOL, which is intended for solving to optimality the
alpar@9 1302 symmetric Traveling Salesman Problem (TSP), a classical problem
alpar@9 1303 of the combinatorial optimization (see the file 'tspsol.c' in
alpar@9 1304 the subdirectory 'sample').
alpar@9 1305
alpar@9 1306 GLPK 3.2 (release date: Jul 15, 2002)
alpar@9 1307
alpar@9 1308 New edition of the document "GLPK: Reference Manual" was
alpar@9 1309 included (see the files 'refman.latex', 'refman.dvi', and
alpar@9 1310 'refman.ps' in the subdirectory 'doc').
alpar@9 1311
alpar@9 1312 New edition of the document "GLPK: Modeling Language GLPK/L" was
alpar@9 1313 included (see the files 'lang.latex', 'lang.dvi', and 'lang.ps'
alpar@9 1314 in the subdirectory 'doc').
alpar@9 1315
alpar@9 1316 The following new API routines were added to the package:
alpar@9 1317
alpar@9 1318 lpx_transform_row (transform explicitly specified row);
alpar@9 1319 lpx_transform_col (transform explicitly specified column);
alpar@9 1320 lpx_prim_ratio_test (perform primal ratio test);
alpar@9 1321 lpx_dual_ratio_test (perform dual ratio test);
alpar@9 1322 lpx_interior (solve LP problem using interior point method);
alpar@9 1323 lpx_get_ips_stat (query status of interior point solution);
alpar@9 1324 lpx_get_ips_row (obtain row interior point solution);
alpar@9 1325 lpx_get_ips_col (obtain column interior point solution);
alpar@9 1326 lpx_get_ips_obj (obtain interior point value of obj.func.);
alpar@9 1327 lpx_read_lpm (read LP/MIP model written in GLPK/L);
alpar@9 1328 lpx_write_mps (write problem data using MPS format);
alpar@9 1329 lpx_print_ips (print interior point solution).
alpar@9 1330
alpar@9 1331 Detailed description of all these new API routines are given in
alpar@9 1332 the new edition of the reference manual.
alpar@9 1333
alpar@9 1334 New version of the stand-alone solver glpsol (which is based on
alpar@9 1335 the new API) was implemented.
alpar@9 1336
alpar@9 1337 So long as the new API (introduced in glpk 3.0) now provides
alpar@9 1338 all the functions, which were provided by the old API, the old
alpar@9 1339 API routines were removed from the package at all.
alpar@9 1340
alpar@9 1341 GLPK 3.1 (release date: May 27, 2002)
alpar@9 1342
alpar@9 1343 A preliminary implementation of new API routines was completed
alpar@9 1344 and included in the package.
alpar@9 1345
alpar@9 1346 These new API routines provide much more flexible interaction
alpar@9 1347 between the application program, LP/MIP problem instances, and
alpar@9 1348 solver routines. Based on completely changed data structures
alpar@9 1349 they are, however, similar to the API routines and provide the
alpar@9 1350 same functionality. Please note that three routines, namely,
alpar@9 1351 solving LPs using interior point method, reading model written
alpar@9 1352 in the GLPK/L modeling language, and writing problem data in
alpar@9 1353 the MPS format, are not implemented in the new API, however,
alpar@9 1354 these routines are planned to be implemented in the next version
alpar@9 1355 of the package.
alpar@9 1356
alpar@9 1357 A description of the new API routines is given in the document
alpar@9 1358 "GLPK Reference Manual", a draft edition of which is included
alpar@9 1359 in the package (see the files 'refman.latex', 'refman.dvi', and
alpar@9 1360 'refman.ps' in the subdirectory 'doc').
alpar@9 1361
alpar@9 1362 Although the old API routines are kept in the package, they are
alpar@9 1363 no longer supported and will be removed in the future.
alpar@9 1364
alpar@9 1365 GLPK 3.0.8 (release date: May 13, 2002)
alpar@9 1366
alpar@9 1367 A preliminary implementation of new API routines was included
alpar@9 1368 in the package. These new API routines are intended to provide
alpar@9 1369 much more flexible interaction between the application program,
alpar@9 1370 LP/MIP problem and solver routines. See the document "New GLPK
alpar@9 1371 API Routines" (the file 'newapi.txt' in the subdirectory 'doc')
alpar@9 1372 also included in the package.
alpar@9 1373
alpar@9 1374 The api routines glp_simplex2, glp_call_ipm1, glp_call_bbm1 were
alpar@9 1375 renamed, respectively, to glp_simplex, glp_interior, glp_integer
alpar@9 1376 in order to reflect changes in implementation. The api routines
alpar@9 1377 glp_call_rsm1, glp_simplex1, glp_pivot_in, glp_pivout_out were
alpar@9 1378 removed from the package since they are completely supreseded by
alpar@9 1379 the new API routines (however, these routines still can be found
alpar@9 1380 in the subdirectory 'oldsrc'). Please consult a new edition of
alpar@9 1381 the document "GLPK User's Guide" about all these changes in the
alpar@9 1382 existing api routines.
alpar@9 1383
alpar@9 1384 The document "GLPK Library Reference" was removed from the
alpar@9 1385 package (into the subdirectory 'oldsrc') since it describes the
alpar@9 1386 obsolete library routines, most of which are no longer used.
alpar@9 1387
alpar@9 1388 GLPK 3.0.7 (release date: Apr 22, 2002)
alpar@9 1389
alpar@9 1390 A new, more efficient implementation of the primal/dual simplex
alpar@9 1391 method was included in the package. Due to some improvements the
alpar@9 1392 simplex-based solver allows solving many LP problems faster and
alpar@9 1393 provides more reliable results. Note that the new implementation
alpar@9 1394 is currently incomplete and available only via the api routine
alpar@9 1395 glp_simplex2.
alpar@9 1396
alpar@9 1397 All the changes are transparent on API level.
alpar@9 1398
alpar@9 1399 GLPK 3.0.6 (release date: Mar 28, 2002)
alpar@9 1400
alpar@9 1401 New version of LU-factorization and basis maintenance routines
alpar@9 1402 (based on Forrest-Tomlin updating technique) was implemented.
alpar@9 1403 Since these new routines functionally supersede some routines
alpar@9 1404 (which implement other forms of the basis matrix) and make them
alpar@9 1405 obsolete, the latter were removed from the package (they still
alpar@9 1406 can be found in the subdirectory 'oldsrc').
alpar@9 1407
alpar@9 1408 All the changes are transparent on API level.
alpar@9 1409
alpar@9 1410 GLPK 3.0.5 (release date: Jan 29, 2002)
alpar@9 1411
alpar@9 1412 New edition of the document "GLPK User's Guide" was included in
alpar@9 1413 the distribution. Now it describes all additional API routines,
alpar@9 1414 which were recently added to the package.
alpar@9 1415
alpar@9 1416 Structure of the package was re-organized in order to make its
alpar@9 1417 maintenance easier (all small files in the subdurectory 'source'
alpar@9 1418 were merged in bigger units). These changes are transparent for
alpar@9 1419 the user.
alpar@9 1420
alpar@9 1421 GLPK 3.0.4 (release date: Dec 10, 2001)
alpar@9 1422
alpar@9 1423 A new, more efficient implementation of the two-phase primal
alpar@9 1424 simplex method was included in the package. Due to some new
alpar@9 1425 features (an advanced initial basis, projected steepest edge,
alpar@9 1426 recursive updating values and reduced costs) the new LP solver
alpar@9 1427 is faster and numerically more stable than the old one.
alpar@9 1428
alpar@9 1429 The new LP solver is available as API routine glp_simplex2 and
alpar@9 1430 has the same purpose as API routine glp_call_rsm1. For detailed
alpar@9 1431 specification see the file 'newapi.txt' in the directory 'doc'.
alpar@9 1432
alpar@9 1433 Now the new LP solver is also used by default to solve an
alpar@9 1434 initial LP problem in the branch-and-bound routine glp_call_bbm1
alpar@9 1435 instead the routine rsm1_driver. Note that the branch-and-bound
alpar@9 1436 procedure itself is still based on rsm1_driver.
alpar@9 1437
alpar@9 1438 The new LP solver is also used as default solver in GLPSOL for
alpar@9 1439 solving LP and MIP problems. In order to choose the old solver
alpar@9 1440 the option '--old-sim' can be specified in the command line.
alpar@9 1441
alpar@9 1442 GLPK 3.0.3 (release date: Oct 03, 2001)
alpar@9 1443
alpar@9 1444 Some minor changes were made in the simplex method routines in
alpar@9 1445 order to improve numerical stability of the method.
alpar@9 1446
alpar@9 1447 GLPK 3.0.2 (release date: Sep 24, 2001)
alpar@9 1448
alpar@9 1449 A new implementation of the basis maintaining routines was
alpar@9 1450 included in the package. These routines, which are based on so
alpar@9 1451 called FHV-factorization (a variety of LU-factorization) of the
alpar@9 1452 basis matrix and Gustavson's data structures, allows performing
alpar@9 1453 the main operations faster at the expense of some worsening
alpar@9 1454 numerical accuracy.
alpar@9 1455
alpar@9 1456 AFI (Advanced Form of the Inverse), which is the form of the
alpar@9 1457 basis matrix based on FHV-factorization, is available via the
alpar@9 1458 parameter form = 3 (on API level) or via the option --afi (in
alpar@9 1459 GLPSOL solver).
alpar@9 1460
alpar@9 1461 GLPK 3.0.1 (release date: Aug 01, 2001)
alpar@9 1462
alpar@9 1463 Old GLPK API routines have been removed from the package.
alpar@9 1464
alpar@9 1465 New GLPK API routines were added:
alpar@9 1466
alpar@9 1467 - scaling routines;
alpar@9 1468
alpar@9 1469 - a routine for writing problem data in MPS format;
alpar@9 1470
alpar@9 1471 - a comprehensive driver to the simplex method;
alpar@9 1472
alpar@9 1473 - basis maintaining routines.
alpar@9 1474
alpar@9 1475 A description of the new API routines is given in the document
alpar@9 1476 "Additional GLPK API Routines". This document is included into
alpar@9 1477 the distribution in plain text format (see the file 'newapi.txt'
alpar@9 1478 in the subdirectory 'doc').
alpar@9 1479
alpar@9 1480 Now the distribution includes a non-trivial example of using
alpar@9 1481 GLPK as a base LP solver for Concorde, a well known program that
alpar@9 1482 solves Traveling Salesman Problem (TSP). For further details see
alpar@9 1483 comments in the file 'sample/lpglpk30.c'.
alpar@9 1484
alpar@9 1485 GLPK 3.0 (release date: Jul 19, 2001)
alpar@9 1486
alpar@9 1487 Now GLPK is provided with new API, which being more flexible
alpar@9 1488 can be used in more complex algorithmic schemes.
alpar@9 1489
alpar@9 1490 New edition of the document "GLPK User's Guide" is included in
alpar@9 1491 the distribution. Now it completely corresponds to the new GLPK
alpar@9 1492 API routines.
alpar@9 1493
alpar@9 1494 Old API routines are not removed yet from the package, however
alpar@9 1495 they became obsolete and therefore should not be used. Since now
alpar@9 1496 the header glpk.h corresponds to new API, in order to compile
alpar@9 1497 existing programs that use old GLPK API routines the statement
alpar@9 1498
alpar@9 1499 #define GLP_OLD_API
alpar@9 1500
alpar@9 1501 should be inserted before the statement
alpar@9 1502
alpar@9 1503 #include "glpk.h"
alpar@9 1504
alpar@9 1505 GLPK 2.4.1 (release date: Jun 14, 2001)
alpar@9 1506
alpar@9 1507 The document "Modeling language GLPK/L" is included into the
alpar@9 1508 distribution in texinfo format.
alpar@9 1509
alpar@9 1510 New edition of the document "GLPK User's Guide" is included in
alpar@9 1511 the distribution. Now it describes all additional API routines
alpar@9 1512 which were recently added to the package.
alpar@9 1513
alpar@9 1514 GLPK 2.4 (release date: May 10, 2001)
alpar@9 1515
alpar@9 1516 Now GLPK includes an implementation of a preliminary version
alpar@9 1517 of the GLPK/L modeling language. This language is intended for
alpar@9 1518 writing mathematcal programming models. The name GLPK/L is
alpar@9 1519 derived from GNU Linear Programming Kit Language.
alpar@9 1520
alpar@9 1521 A brief description of the GLPK/L language is given in the
alpar@9 1522 document "GLPK/L Modeling Language: A Brief Description". This
alpar@9 1523 document is included into the distribution in plain text format
alpar@9 1524 (see the file 'language.txt' in the subdirectory 'doc').
alpar@9 1525
alpar@9 1526 The language processor (which is a program that analyzes model
alpar@9 1527 description written in GLPK/L and translates it to internal data
alpar@9 1528 structures) is available as the GLPK API routine.
alpar@9 1529
alpar@9 1530 The stand-alone solver GLPSOL now is able: a) to process model
alpar@9 1531 descriptions written in the GLPK/L language; b) to solve pure LP
alpar@9 1532 problems using the interior point method (therefore the program
alpar@9 1533 GLPIPM was removed from the package).
alpar@9 1534
alpar@9 1535 GLPK 2.3 (release date: Apr 09, 2001)
alpar@9 1536
alpar@9 1537 New edition of the document "GLPK User's Guide" is included in
alpar@9 1538 the distribution. Now it describes all additional API routines
alpar@9 1539 which were recently added to the package.
alpar@9 1540
alpar@9 1541 The MIP solver was fully re-programmed in order to improve its
alpar@9 1542 robustness and performance. In particular, a basis recovering
alpar@9 1543 procedure was implemented (this procedure allows switching to
alpar@9 1544 the primal simplex method in case when the dual simplex method
alpar@9 1545 fails).
alpar@9 1546
alpar@9 1547 GLPK 2.2 (release date: Mar 15, 2001)
alpar@9 1548
alpar@9 1549 Now GLPK includes a tentative implementation of the
alpar@9 1550 branch-and-bound procedure based on the dual simplex method for
alpar@9 1551 mixed integer linear programming (MIP).
alpar@9 1552
alpar@9 1553 Complete description of this new feature of the package is given
alpar@9 1554 in the preliminary document "Mixed Integer Linear Programming
alpar@9 1555 Using GLPK Version 2.2 (Supplement to GLPK User's Guide)". This
alpar@9 1556 document is included into the distribution in plain text format
alpar@9 1557 (see the file 'mip.txt' in the subdirectory 'doc').
alpar@9 1558
alpar@9 1559 The MIP solver (glp_integer) can be used as GLPK API routine in
alpar@9 1560 the same way as the pure LP solver (glp_simplex).
alpar@9 1561
alpar@9 1562 The stand-alone program 'glpsol' is now able to solve LP as well
alpar@9 1563 as MIP problems.
alpar@9 1564
alpar@9 1565 Note that the current version of GLPK MIP solver is based on
alpar@9 1566 easiest heuristics for branching and backtrackng. Therefore the
alpar@9 1567 solver is fit mainly for MIP problems which are not very hard
alpar@9 1568 and have few integer variables.
alpar@9 1569
alpar@9 1570 GLPK 2.1 (release date: Feb 19, 2001)
alpar@9 1571
alpar@9 1572 The document "GLPK Implementation of the Revised Simplex Method"
alpar@9 1573 is included into the distribution. This document describes most
alpar@9 1574 of routines related to the revised simplex method.
alpar@9 1575
alpar@9 1576 GLPK 2.0 (release date: Jan 25, 2001)
alpar@9 1577
alpar@9 1578 Now GLPK includes a tentative implementation of the primal-dual
alpar@9 1579 interior point method for large-scale linear programming.
alpar@9 1580
alpar@9 1581 The interior point solver can be used as GLPK API routine in the
alpar@9 1582 same manner as the simplex method solver (glp_simplex):
alpar@9 1583
alpar@9 1584 ret = glp_interior();
alpar@9 1585
alpar@9 1586 Note that currently the interior point solver implemented in
alpar@9 1587 GLPK doesn't include many important features, in particular:
alpar@9 1588
alpar@9 1589 * it can't process dense columns; therefore if the problem has
alpar@9 1590 dense columns, the solving will be extremely inefficient;
alpar@9 1591
alpar@9 1592 * it has no special features against numerical unstability;
alpar@9 1593 some problems may cause premature termination of the solving
alpar@9 1594 when the matrix A*D*A' becomes ill-conditioned;
alpar@9 1595
alpar@9 1596 * it computes only values of primal (auxiliary and structural)
alpar@9 1597 variables and doesn't compute values of dual variables (i.e.
alpar@9 1598 reduced costs) which are just set to zero;
alpar@9 1599
alpar@9 1600 * it doesn't identify optimal basis corresponding to the found
alpar@9 1601 interior point solution; all variables in the found solution
alpar@9 1602 are just marked as basic variables.
alpar@9 1603
alpar@9 1604 GLPK also includes a stand-alone program 'glpipm' which is a
alpar@9 1605 demo based on the interior point method. It may be used in the
alpar@9 1606 same way as the program 'glpsol' that is based on the simplex
alpar@9 1607 method.