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