Context Navigation

← Previous Revision
Next Revision →
Normal
Revision Log

source: glpk-cmake/NEWS

Last change on this file 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

Rev	Line
[1]	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