Context Navigation

source: glpk-cmake/NEWS @ 2:4c8956a7bdf4

Last change on this file since 2:4c8956a7bdf4 was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 14 years ago

Import glpk-4.45

Generated files and doc/notes are removed

File size: 68.0 KB

Line
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 ADA' 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.

Note: See TracBrowser for help on using the repository browser.

Download in other formats:

Original Format