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