lemon-project-template-glpk

comparison deps/glpk/NEWS @ 11:4fc6ad2fb8a6

Test GLPK in src/main.cc
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 21:43:29 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:bd6dc4495aea
1 GLPK 4.47 (release date: Sep 09, 2011)
2
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).
12
13 The following two options were added to glpsol:
14
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)
19
20 --objbnd bound add inequality obj <= bound (minimization) or
21 obj >= bound (maximization) to 0-1 feasibility
22 problem (this option assumes --minisat)
23
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/.
30
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.
34
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.
38
39 GLPK 4.46 (release date: Aug 09, 2011)
40
41 The following new API routines were added:
42
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
47
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.
54
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).
58
59 The following new glpsol command-line options were added:
60
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
67
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.
72
73 Some bugs were fixed in the SQL table driver. Thanks to Xypron
74 <xypron.glpk@gmx.de>.
75
76 GLPK 4.45 (release date: Dec 05, 2010)
77
78 This is a bug-fix release.
79
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.
84
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):
88
89 GLPK: Reference Manual
90
91 GLPK: Graph and Network Routines
92
93 Modeling Language GNU MathProg: Language Reference
94
95 GLPK 4.44 (release date: Jun 03, 2010)
96
97 The following suffixes for variables and constraints were
98 implemented in the MathProg language:
99
100 .lb (lower bound),
101 .ub (upper bound),
102 .status (status in the solution),
103 .val (primal value), and
104 .dual (dual value).
105
106 Thanks to Xypron <xypron.glpk@gmx.de> for draft implementation
107 and testing.
108
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.
113
114 The API routine glp_cpp to solve the Critical Path Problem was
115 added and documented.
116
117 GLPK 4.43 (release date: Feb 20, 2010)
118
119 This is a maintainer release.
120
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.
125
126 The SQL table driver was improved to process NULL data. Thanks
127 to Xypron <xypron.glpk@gmx.de>.
128
129 Some bugs were fixed in the LP/MIP preprocessor.
130
131 GLPK 4.42 (release date: Jan 13, 2010)
132
133 The following new API routines were added:
134
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)
146
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.)
152
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)
159
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.
164
165 GLPK 4.41 (release date: Dec 21, 2009)
166
167 The following new API routies were added:
168
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
173
174 For description of these new routines see a new edition of the
175 reference manual included in the distribution.
176
177 The following API routines are deprecated: lpx_transform_row,
178 lpx_transform_col, lpx_prim_ratio_test, lpx_dual_ratio_test.
179
180 Some improvements were made in the MIP solver (glp_intopt).
181
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>.
185
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).
191
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.
195
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.
199
200 GLPK 4.40 (release date: Nov 03, 2009)
201
202 The following new API routines were added:
203
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
212
213 For description of these new routines see a new edition of the
214 reference manual included in the distribution.
215
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.
221
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.
226
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.
230
231 A bug was fixed and some improvements were made in the FPUMP
232 heuristic module. Thanks to Xypron <xypron.glpk@gmx.de>.
233
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.
237
238 GLPK 4.39 (release date: Jul 26, 2009)
239
240 The following new API routines were added:
241
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
258
259 Also were added some API routines to read plain data files.
260
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.
265
266 For description of these new routines see a new edition of the
267 reference manual included in the distribution.
268
269 The 'xfree(NULL)' bug was fixed in the AMD routines. Thanks to
270 Niels Klitgord <niels@bu.edu> for bug report.
271
272 The message "Crashing..." was changed to "Constructing initial
273 basis..." due to suggestion by Thomas Kahle <tom111@gmx.de>.
274
275 Some typos were corrected in glpsol output messages. Thanks to
276 Xypron <xypron.glpk@gmx.de> for patch.
277
278 GLPK 4.38 (release date: May 02, 2009)
279
280 API routines glp_read_mps and glp_write_mps were improved.
281
282 Some improvements were made in the dual simplex routines.
283
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.
288
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.
292
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.
295
296 GLPK 4.37 (release date: Mar 29, 2009)
297
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.
304
305 The following new API routines were added:
306
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
315
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).
319
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.
323
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.
329
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.
333
334 GLPK 4.36 (release date: Feb 06, 2009)
335
336 The following new API routines were added to the package:
337
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
342
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.
346
347 The following two new command-line options were added to the
348 solver glpsol:
349
350 --mincost read min-cost flow data in DIMACS format
351 --maxflow read maximum flow data in DIMACS format
352
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.
357
358 A minor defect was fixed in the routine glp_write_lp.
359 Thanks to Sebastien Briais <sbriais@free.fr> for bug report.
360
361 A minor bug was fixed in the SQL module.
362 Thanks to Xypron <xypron.glpk@gmx.de> for patch.
363
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.
367
368 GLPK 4.35 (release date: Jan 09, 2009)
369
370 The following new API routines were added to the package:
371
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
391
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.
395
396 A minor change were made in the internal routine xputc. Thanks
397 to Luiz Bettoni <bettoni@cpgei.ct.utfpr.edu.br> for suggestion.
398
399 A minor bug was fixed in the internal routine mpl_fn_time2str.
400 Thanks to Stefan Vigerske <stefan@vigerske.de> for bug report.
401
402 GLPK 4.34 (release date: Dec 04, 2008)
403
404 The GNU MathProg modeling language was supplemented with three
405 new built-in functions:
406
407 gmtime obtaining current calendar time
408 str2time converting character string to calendar time
409 time2str converting calendar time to character string
410
411 (Thanks to Xypron <xypron.glpk@gmx.de>.)
412
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.
416
417 A bug was fixed in the MIP solver. Thanks to Nigel Galloway
418 <nigel_galloway@operamail.com> for bug report.
419
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.
423
424 GLPK 4.33 (release date: Oct 30, 2008)
425
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)
434
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.)
445
446 For description of all these new API routines see the reference
447 manual included in the distribution.
448
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.
453
454 Some bugs were fixed in the SQL table driver. Thanks to Xypron
455 <xypron.glpk@gmx.de>.
456
457 GLPK 4.32 (release date: Oct 03, 2008)
458
459 The following new features were included in the MIP solver
460 (the API routine glp_intopt):
461
462 * MIP presolver
463 * mixed cover cut generator
464 * clique cut generator
465 * Euclidean reduction of the objective value
466
467 Due to changes the routine glp_intopt may additionally return
468 GLP_ENOPFS, GLP_ENODFS, and GLP_EMIPGAP.
469
470 The API routines lpx_integer are lpx_intopt are deprecated,
471 since they are completely superseded by glp_intopt.
472
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
479
480 For description of these new routines see the reference manual
481 included in the distribution.
482
483 The stand-alone solver glpsol was changed to allow multiple
484 data files.
485
486 A new edition of the supplement "Using Data Tables in the GNU
487 MathProg Modeling Language" was included.
488
489 As usual, some bugs were fixed (in the MathProg translator).
490 Thanks to Xypron <xypron.glpk@gmx.de>.
491
492 GLPK 4.31 (release date: Sep 02, 2008)
493
494 The core LP solver based on the dual simplex method was
495 re-implemented and now it provides both phases I and II.
496
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
502
503 For description of these new routines see the reference manual
504 included in the distribution.
505
506 The following API routines are deprecated:
507 lpx_scale_prob, lpx_std_basis, lpx_adv_basis, lpx_cpx_basis.
508
509 Necessary changes were made in memory allocation routines to
510 resolve portability issues for 64-bit platforms.
511
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.
515
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.
520
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).
523
524 GLPK 4.30 (release date: Aug 13, 2008)
525
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.
530
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.
534
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.
538
539 GLPK 4.29 (release date: Jul 06, 2008)
540
541 The configure script was changed to disable all optional
542 features by default. For details please see file INSTALL.
543
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
550
551 For description of these new routines see the reference manual
552 included in the distribution.
553
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.
557
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.
561
562 GLPK 4.28 (release date: Mar 25, 2008)
563
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.
573
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).
581
582 The `configure' script was re-implemented. Now it supports the
583 following specific options:
584
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
599
600 For more details please see file INSTALL.
601
602 GLPK 4.27 (release date: Mar 02, 2008)
603
604 Three new table drivers were added to the MathProg translator:
605
606 xBASE built-in table driver, which allows reading and writing
607 data in .dbf format (only C and N fields are supported);
608
609 MySQL table driver, which provides connection to a MySQL
610 database;
611
612 iODBC table driver, which provides connection to a database
613 through ODBC.
614
615 The MySQL and iODBC table drivers were contributed to GLPK by
616 Heinrich Schuchardt <heinrich.schuchardt@gmx.de>.
617
618 The table driver is a program module which allows transmitting
619 data between MathProg model objects and external data tables.
620
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.
626
627 GLPK 4.26 (release date: Feb 17, 2008)
628
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.
633
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.
637
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.
642
643 Detailed description of the table statement and CSV format can
644 be found in file doc/tables.txt, included in the distribution.
645
646 GLPK 4.25 (release date: Dec 19, 2007)
647
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.
655
656 GLPK 4.24 (release date: Nov 21, 2007)
657
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.
665
666 The implementation is mainly based on the following two papers:
667
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.
671
672 2. G. Andreello, A. Caprara, and M. Fischetti. Embedding cuts
673 in a Branch&Cut framework. Preliminary draft, October 2003.
674
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.
677
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.
682
683 GLPK 4.23 (release date: Oct 28, 2007)
684
685 The following new API routines were added:
686
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
693
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.
697
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.
701
702 The following three new command-line options were added to the
703 solver glpsol:
704
705 --mipgap tol set relative MIP gap tolerance
706 -r filename read solution from filename
707 -w filename write solution to filename
708
709 GLPK 4.22 (release date: Sep 19, 2007)
710
711 This is a maintainer release.
712
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.
716
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.
720
721 A similar bug was fixed in the routine reduce_bounds.
722
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.)
726
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.
730
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>.
734
735 GLPK 4.21 (release date: Aug 28, 2007)
736
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:
740
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
748
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.
755
756 Backtracking heuristic used by default in the MIP solver was
757 changed to the "best local bound".
758
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.
762
763 GLPK 4.20 (release date: Jul 26, 2007)
764
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.
774
775 The following new advanced API routines, which may be called
776 from the B&B callback routine, were included in the package:
777
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
791
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.
796
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.
800
801 A minor error in the MIP presolver was fixed; thanks to Graham
802 Rockwell <bionomicron@gmail.com> for the bug report.
803
804 GLPK 4.19 (release date: Jul 05, 2007)
805
806 The principal change is upgrading to GPLv3.
807
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.
813
814 A new advanced API routine glp_mem_limit was added.
815
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.
819
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.
823
824 Two new options --wpb and --wnpb were added to glpsol to write
825 the problem instance in OPB format.
826
827 GLPK 4.18 (release date: Jun 25, 2007)
828
829 The following new API routines were added:
830
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
850
851 For description of all these routines see a new edition of the
852 reference manual included in the distribution.
853
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.
858
859 Some new examples in the MathProg language were added. Thanks
860 to Sebastian Nowozin <nowozin@gmail.com>.
861
862 GLPK 4.17 (release date: May 26, 2007)
863
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.
868
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.
882
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.
886
887 GLPK 4.16 (release date: May 05, 2007)
888
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.
894
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.
902
903 The header glpk.h was changed to conform to C++ environment.
904
905 GLPK 4.15 (release date: Feb 18, 2007)
906
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.
910
911 GLPK 4.14 (release date: Feb 05, 2007)
912
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.
919
920 GLPK 4.13 (release date: Nov 13, 2006)
921
922 A tentative implementation of the "exact" simplex method based
923 on bignum (rational) arithmetic was included in the package.
924
925 On API level this new feature is available through the routine
926 lpx_exact, which is similar to the routine lpx_simplex.
927
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.
938
939 GLPK 4.12 (release date: Nov 08, 2006)
940
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.
945
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.
950
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.
957
958 GLPK 4.11 (release date: Jul 25, 2006)
959
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".
968
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'.
972
973 GLPK 4.10 (release date: May 11, 2006)
974
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.
981
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.
985
986 GLPK 4.9 (release date: Jan 17, 2006)
987
988 An advanced MIP solver was implemented. It includes:
989
990 - basic presolving technique (removing free, singleton and
991 redundant rows, improving bounds of columns, removing fixed
992 columns, reducing constraint coefficents);
993
994 - generating cutting planes to improve LP relaxation (currently
995 only Gomory's mixed integer cuts are implemented);
996
997 - using the branch-and-bound method to solve resultant MIP;
998
999 - recovering solution of the original MIP.
1000
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.
1005
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).
1009
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.
1014
1015 For some comparative benchmarks see doc/bench1.txt.
1016
1017 Well, what else...
1018
1019 Three built-in functions were added to MathProg: sin, cos, and
1020 atan (the latter allows one or two arguments).
1021
1022 Some bugs were fixed.
1023
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).
1027
1028 GLPK 4.8 (release date: Jan 12, 2005)
1029
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.
1034
1035 Also a minor bug was fixed in API routine lpx_read_cpxlp.
1036
1037 GLPK 4.7 (release date: Aug 23, 2004)
1038
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.
1045
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).
1049
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).
1054
1055 GLPK 4.6 (release date: Aug 04, 2004)
1056
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.)
1062
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.
1066
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.
1072
1073 A new version of GLPKMEX, a Matlab MEX interface to GLPK, was
1074 included. For more details see contrib/glpkmex/ChangeLog.
1075
1076 GLPK 4.5 (release date: Jul 19, 2004)
1077
1078 The branch-and-bound solver was completely re-implemented.
1079
1080 Some modifications were made in memory allocation routines that
1081 allows using the package on 64-bit platforms.
1082
1083 For more details see ChangeLog.
1084
1085 GLPK 4.4 (release date: Jan 17, 2004)
1086
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.
1106
1107 New edition of the GLPK Reference Manual was included in the
1108 distribution.
1109
1110 GLPKMEX, a Matlab MEX interface to GLPK package, contributed by
1111 Nicolo Giorgetti <giorgetti@dii.unisi.it> was included in the
1112 distribution.
1113
1114 GLPK FAQ contributed by Harley Mackenzie <hjm@bigpond.com> was
1115 included in the distribution.
1116
1117 GLPK 4.3 (release date: Dec 12, 2003)
1118
1119 The bug, due to which the standard math library is not linked
1120 on building the package on some platforms, was fixed.
1121
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.
1125
1126 The MathProg syntax was changed to allow writing 'subj to' that
1127 means 'subject to'.
1128
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.
1132
1133 The module glpmps.c was changed to avoid compilation errors on
1134 building the package on Mac OS X.
1135
1136 Several typos was fixed and some new material was added to the
1137 GLPK documentation.
1138
1139 GLPK 4.2 (release date: Nov 14, 2003)
1140
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.
1144
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).
1149
1150 An improved version of GLPK JNI (Java Native Interface) was
1151 contributed by Chris Rosebrugh <cpr@pobox.com>.
1152
1153 GLPK DELI (Delphi Interface) was contributed by Ivo van Baren
1154 <i.van.baren@freeler.nl>.
1155
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
1162
1163 And, of course, some bugs were fixed.
1164
1165 For more details see ChangeLog.
1166
1167 GLPK 4.1 (release date: Aug 23, 2003)
1168
1169 Some improvements were made in the lp/mip solver routines and
1170 several bugs were fixed in the model translator.
1171
1172 For more details see ChangeLog.
1173
1174 GLPK 4.0 (release date: May 06, 2003)
1175
1176 Now GLPK supports the GNU MathProg modeling language, which is
1177 a subset of the AMPL modeling language.
1178
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'.)
1183
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.)
1187
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.
1191
1192 GLPK 3.3 (release date: Mar 25, 2003)
1193
1194 LP PRESOLVER
1195 ------------
1196
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.
1206
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.
1220
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.
1224
1225 CHANGES IN GLPK/L
1226 -----------------
1227
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:
1231
1232 set task = [8:11];
1233
1234 that is exactly equivalent to the following declaration:
1235
1236 set task = (task_8, task_9, task_10, task_11);
1237
1238 For details see the language description.
1239
1240 JAVA INTERFACE
1241 --------------
1242
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.
1249
1250 GLPK 3.2.4 (release date: Feb 18, 2003)
1251
1252 This is a bug-fix release. For details see ChangeLog.
1253
1254 GLPK 3.2.3 (release date: Nov 11, 2002)
1255
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.
1261
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.
1267
1268 Also other minor improvements were made (for details see the
1269 file 'ChangeLog').
1270
1271 GLPK 3.2.2 (release date: Oct 14, 2002)
1272
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.
1282
1283 Several bugs were fixed and some minor improvements were made
1284 (for details see the file 'ChangeLog').
1285
1286 GLPK 3.2.1 (release date: Aug 12, 2002)
1287
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.
1292
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').
1297
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').
1305
1306 GLPK 3.2 (release date: Jul 15, 2002)
1307
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').
1311
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').
1315
1316 The following new API routines were added to the package:
1317
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).
1330
1331 Detailed description of all these new API routines are given in
1332 the new edition of the reference manual.
1333
1334 New version of the stand-alone solver glpsol (which is based on
1335 the new API) was implemented.
1336
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.
1340
1341 GLPK 3.1 (release date: May 27, 2002)
1342
1343 A preliminary implementation of new API routines was completed
1344 and included in the package.
1345
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.
1356
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').
1361
1362 Although the old API routines are kept in the package, they are
1363 no longer supported and will be removed in the future.
1364
1365 GLPK 3.0.8 (release date: May 13, 2002)
1366
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.
1373
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.
1383
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.
1387
1388 GLPK 3.0.7 (release date: Apr 22, 2002)
1389
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.
1396
1397 All the changes are transparent on API level.
1398
1399 GLPK 3.0.6 (release date: Mar 28, 2002)
1400
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').
1407
1408 All the changes are transparent on API level.
1409
1410 GLPK 3.0.5 (release date: Jan 29, 2002)
1411
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.
1415
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.
1420
1421 GLPK 3.0.4 (release date: Dec 10, 2001)
1422
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.
1428
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'.
1432
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.
1437
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.
1441
1442 GLPK 3.0.3 (release date: Oct 03, 2001)
1443
1444 Some minor changes were made in the simplex method routines in
1445 order to improve numerical stability of the method.
1446
1447 GLPK 3.0.2 (release date: Sep 24, 2001)
1448
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.
1455
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).
1460
1461 GLPK 3.0.1 (release date: Aug 01, 2001)
1462
1463 Old GLPK API routines have been removed from the package.
1464
1465 New GLPK API routines were added:
1466
1467 - scaling routines;
1468
1469 - a routine for writing problem data in MPS format;
1470
1471 - a comprehensive driver to the simplex method;
1472
1473 - basis maintaining routines.
1474
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').
1479
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'.
1484
1485 GLPK 3.0 (release date: Jul 19, 2001)
1486
1487 Now GLPK is provided with new API, which being more flexible
1488 can be used in more complex algorithmic schemes.
1489
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.
1493
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
1498
1499 #define GLP_OLD_API
1500
1501 should be inserted before the statement
1502
1503 #include "glpk.h"
1504
1505 GLPK 2.4.1 (release date: Jun 14, 2001)
1506
1507 The document "Modeling language GLPK/L" is included into the
1508 distribution in texinfo format.
1509
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.
1513
1514 GLPK 2.4 (release date: May 10, 2001)
1515
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.
1520
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').
1525
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.
1529
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).
1534
1535 GLPK 2.3 (release date: Apr 09, 2001)
1536
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.
1540
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).
1546
1547 GLPK 2.2 (release date: Mar 15, 2001)
1548
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).
1552
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').
1558
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).
1561
1562 The stand-alone program 'glpsol' is now able to solve LP as well
1563 as MIP problems.
1564
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.
1569
1570 GLPK 2.1 (release date: Feb 19, 2001)
1571
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.
1575
1576 GLPK 2.0 (release date: Jan 25, 2001)
1577
1578 Now GLPK includes a tentative implementation of the primal-dual
1579 interior point method for large-scale linear programming.
1580
1581 The interior point solver can be used as GLPK API routine in the
1582 same manner as the simplex method solver (glp_simplex):
1583
1584 ret = glp_interior();
1585
1586 Note that currently the interior point solver implemented in
1587 GLPK doesn't include many important features, in particular:
1588
1589 * it can't process dense columns; therefore if the problem has
1590 dense columns, the solving will be extremely inefficient;
1591
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;
1595
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;
1599
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.
1603
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.