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