Context Navigation

glpios01.c @ 1:c445c931472f

Last change on this file since 1:c445c931472f 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: 52.1 KB

Rev	Line
[1]	1	/* glpios01.c */
	2
	3	/***********************************************************************
	4	* This code is part of GLPK (GNU Linear Programming Kit).
	5	*
	6	* Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
	7	* 2009, 2010 Andrew Makhorin, Department for Applied Informatics,
	8	* Moscow Aviation Institute, Moscow, Russia. All rights reserved.
	9	* E-mail: <mao@gnu.org>.
	10	*
	11	* GLPK is free software: you can redistribute it and/or modify it
	12	* under the terms of the GNU General Public License as published by
	13	* the Free Software Foundation, either version 3 of the License, or
	14	* (at your option) any later version.
	15	*
	16	* GLPK is distributed in the hope that it will be useful, but WITHOUT
	17	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
	18	* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
	19	* License for more details.
	20	*
	21	* You should have received a copy of the GNU General Public License
	22	* along with GLPK. If not, see <http://www.gnu.org/licenses/>.
	23	***********************************************************************/
	24
	25	#include "glpios.h"
	26
	27	/***********************************************************************
	28	* NAME
	29	*
	30	* ios_create_tree - create branch-and-bound tree
	31	*
	32	* SYNOPSIS
	33	*
	34	* #include "glpios.h"
	35	* glp_tree ios_create_tree(glp_prob mip, const glp_iocp *parm);
	36	*
	37	* DESCRIPTION
	38	*
	39	* The routine ios_create_tree creates the branch-and-bound tree.
	40	*
	41	* Being created the tree consists of the only root subproblem whose
	42	* reference number is 1. Note that initially the root subproblem is in
	43	* frozen state and therefore needs to be revived.
	44	*
	45	* RETURNS
	46	*
	47	* The routine returns a pointer to the tree created. */
	48
	49	static IOSNPD new_node(glp_tree tree, IOSNPD *parent);
	50
	51	glp_tree ios_create_tree(glp_prob mip, const glp_iocp *parm)
	52	{ int m = mip->m;
	53	int n = mip->n;
	54	glp_tree *tree;
	55	int i, j;
	56	xassert(mip->tree == NULL);
	57	mip->tree = tree = xmalloc(sizeof(glp_tree));
	58	tree->pool = dmp_create_pool();
	59	tree->n = n;
	60	/* save original problem components */
	61	tree->orig_m = m;
	62	tree->orig_type = xcalloc(1+m+n, sizeof(char));
	63	tree->orig_lb = xcalloc(1+m+n, sizeof(double));
	64	tree->orig_ub = xcalloc(1+m+n, sizeof(double));
	65	tree->orig_stat = xcalloc(1+m+n, sizeof(char));
	66	tree->orig_prim = xcalloc(1+m+n, sizeof(double));
	67	tree->orig_dual = xcalloc(1+m+n, sizeof(double));
	68	for (i = 1; i <= m; i++)
	69	{ GLPROW *row = mip->row[i];
	70	tree->orig_type[i] = (char)row->type;
	71	tree->orig_lb[i] = row->lb;
	72	tree->orig_ub[i] = row->ub;
	73	tree->orig_stat[i] = (char)row->stat;
	74	tree->orig_prim[i] = row->prim;
	75	tree->orig_dual[i] = row->dual;
	76	}
	77	for (j = 1; j <= n; j++)
	78	{ GLPCOL *col = mip->col[j];
	79	tree->orig_type[m+j] = (char)col->type;
	80	tree->orig_lb[m+j] = col->lb;
	81	tree->orig_ub[m+j] = col->ub;
	82	tree->orig_stat[m+j] = (char)col->stat;
	83	tree->orig_prim[m+j] = col->prim;
	84	tree->orig_dual[m+j] = col->dual;
	85	}
	86	tree->orig_obj = mip->obj_val;
	87	/* initialize the branch-and-bound tree */
	88	tree->nslots = 0;
	89	tree->avail = 0;
	90	tree->slot = NULL;
	91	tree->head = tree->tail = NULL;
	92	tree->a_cnt = tree->n_cnt = tree->t_cnt = 0;
	93	/* the root subproblem is not solved yet, so its final components
	94	are unknown so far */
	95	tree->root_m = 0;
	96	tree->root_type = NULL;
	97	tree->root_lb = tree->root_ub = NULL;
	98	tree->root_stat = NULL;
	99	/* the current subproblem does not exist yet */
	100	tree->curr = NULL;
	101	tree->mip = mip;
	102	/tree->solved = 0;/
	103	tree->non_int = xcalloc(1+n, sizeof(char));
	104	memset(&tree->non_int[1], 0, n);
	105	/* arrays to save parent subproblem components will be allocated
	106	later */
	107	tree->pred_m = tree->pred_max = 0;
	108	tree->pred_type = NULL;
	109	tree->pred_lb = tree->pred_ub = NULL;
	110	tree->pred_stat = NULL;
	111	/* cut generator */
	112	tree->local = ios_create_pool(tree);
	113	/tree->first_attempt = 1;/
	114	/tree->max_added_cuts = 0;/
	115	/tree->min_eff = 0.0;/
	116	/tree->miss = 0;/
	117	/tree->just_selected = 0;/
	118	tree->mir_gen = NULL;
	119	tree->clq_gen = NULL;
	120	/tree->round = 0;/
	121	#if 0
	122	/* create the conflict graph */
	123	tree->n_ref = xcalloc(1+n, sizeof(int));
	124	memset(&tree->n_ref[1], 0, n * sizeof(int));
	125	tree->c_ref = xcalloc(1+n, sizeof(int));
	126	memset(&tree->c_ref[1], 0, n * sizeof(int));
	127	tree->g = scg_create_graph(0);
	128	tree->j_ref = xcalloc(1+tree->g->n_max, sizeof(int));
	129	#endif
	130	/* pseudocost branching */
	131	tree->pcost = NULL;
	132	tree->iwrk = xcalloc(1+n, sizeof(int));
	133	tree->dwrk = xcalloc(1+n, sizeof(double));
	134	/* initialize control parameters */
	135	tree->parm = parm;
	136	tree->tm_beg = xtime();
	137	tree->tm_lag = xlset(0);
	138	tree->sol_cnt = 0;
	139	/* initialize advanced solver interface */
	140	tree->reason = 0;
	141	tree->reopt = 0;
	142	tree->reinv = 0;
	143	tree->br_var = 0;
	144	tree->br_sel = 0;
	145	tree->child = 0;
	146	tree->next_p = 0;
	147	/tree->btrack = NULL;/
	148	tree->stop = 0;
	149	/* create the root subproblem, which initially is identical to
	150	the original MIP */
	151	new_node(tree, NULL);
	152	return tree;
	153	}
	154
	155	/***********************************************************************
	156	* NAME
	157	*
	158	* ios_revive_node - revive specified subproblem
	159	*
	160	* SYNOPSIS
	161	*
	162	* #include "glpios.h"
	163	* void ios_revive_node(glp_tree *tree, int p);
	164	*
	165	* DESCRIPTION
	166	*
	167	* The routine ios_revive_node revives the specified subproblem, whose
	168	* reference number is p, and thereby makes it the current subproblem.
	169	* Note that the specified subproblem must be active. Besides, if the
	170	* current subproblem already exists, it must be frozen before reviving
	171	* another subproblem. */
	172
	173	void ios_revive_node(glp_tree *tree, int p)
	174	{ glp_prob *mip = tree->mip;
	175	IOSNPD node, root;
	176	/* obtain pointer to the specified subproblem */
	177	xassert(1 <= p && p <= tree->nslots);
	178	node = tree->slot[p].node;
	179	xassert(node != NULL);
	180	/* the specified subproblem must be active */
	181	xassert(node->count == 0);
	182	/* the current subproblem must not exist */
	183	xassert(tree->curr == NULL);
	184	/* the specified subproblem becomes current */
	185	tree->curr = node;
	186	/tree->solved = 0;/
	187	/* obtain pointer to the root subproblem */
	188	root = tree->slot[1].node;
	189	xassert(root != NULL);
	190	/* at this point problem object components correspond to the root
	191	subproblem, so if the root subproblem should be revived, there
	192	is nothing more to do */
	193	if (node == root) goto done;
	194	xassert(mip->m == tree->root_m);
	195	/* build path from the root to the current node */
	196	node->temp = NULL;
	197	for (node = node; node != NULL; node = node->up)
	198	{ if (node->up == NULL)
	199	xassert(node == root);
	200	else
	201	node->up->temp = node;
	202	}
	203	/* go down from the root to the current node and make necessary
	204	changes to restore components of the current subproblem */
	205	for (node = root; node != NULL; node = node->temp)
	206	{ int m = mip->m;
	207	int n = mip->n;
	208	/* if the current node is reached, the problem object at this
	209	point corresponds to its parent, so save attributes of rows
	210	and columns for the parent subproblem */
	211	if (node->temp == NULL)
	212	{ int i, j;
	213	tree->pred_m = m;
	214	/* allocate/reallocate arrays, if necessary */
	215	if (tree->pred_max < m + n)
	216	{ int new_size = m + n + 100;
	217	if (tree->pred_type != NULL) xfree(tree->pred_type);
	218	if (tree->pred_lb != NULL) xfree(tree->pred_lb);
	219	if (tree->pred_ub != NULL) xfree(tree->pred_ub);
	220	if (tree->pred_stat != NULL) xfree(tree->pred_stat);
	221	tree->pred_max = new_size;
	222	tree->pred_type = xcalloc(1+new_size, sizeof(char));
	223	tree->pred_lb = xcalloc(1+new_size, sizeof(double));
	224	tree->pred_ub = xcalloc(1+new_size, sizeof(double));
	225	tree->pred_stat = xcalloc(1+new_size, sizeof(char));
	226	}
	227	/* save row attributes */
	228	for (i = 1; i <= m; i++)
	229	{ GLPROW *row = mip->row[i];
	230	tree->pred_type[i] = (char)row->type;
	231	tree->pred_lb[i] = row->lb;
	232	tree->pred_ub[i] = row->ub;
	233	tree->pred_stat[i] = (char)row->stat;
	234	}
	235	/* save column attributes */
	236	for (j = 1; j <= n; j++)
	237	{ GLPCOL *col = mip->col[j];
	238	tree->pred_type[mip->m+j] = (char)col->type;
	239	tree->pred_lb[mip->m+j] = col->lb;
	240	tree->pred_ub[mip->m+j] = col->ub;
	241	tree->pred_stat[mip->m+j] = (char)col->stat;
	242	}
	243	}
	244	/* change bounds of rows and columns */
	245	{ IOSBND *b;
	246	for (b = node->b_ptr; b != NULL; b = b->next)
	247	{ if (b->k <= m)
	248	glp_set_row_bnds(mip, b->k, b->type, b->lb, b->ub);
	249	else
	250	glp_set_col_bnds(mip, b->k-m, b->type, b->lb, b->ub);
	251	}
	252	}
	253	/* change statuses of rows and columns */
	254	{ IOSTAT *s;
	255	for (s = node->s_ptr; s != NULL; s = s->next)
	256	{ if (s->k <= m)
	257	glp_set_row_stat(mip, s->k, s->stat);
	258	else
	259	glp_set_col_stat(mip, s->k-m, s->stat);
	260	}
	261	}
	262	/* add new rows */
	263	if (node->r_ptr != NULL)
	264	{ IOSROW *r;
	265	IOSAIJ *a;
	266	int i, len, *ind;
	267	double *val;
	268	ind = xcalloc(1+n, sizeof(int));
	269	val = xcalloc(1+n, sizeof(double));
	270	for (r = node->r_ptr; r != NULL; r = r->next)
	271	{ i = glp_add_rows(mip, 1);
	272	glp_set_row_name(mip, i, r->name);
	273	#if 1 /* 20/IX-2008 */
	274	xassert(mip->row[i]->level == 0);
	275	mip->row[i]->level = node->level;
	276	mip->row[i]->origin = r->origin;
	277	mip->row[i]->klass = r->klass;
	278	#endif
	279	glp_set_row_bnds(mip, i, r->type, r->lb, r->ub);
	280	len = 0;
	281	for (a = r->ptr; a != NULL; a = a->next)
	282	len++, ind[len] = a->j, val[len] = a->val;
	283	glp_set_mat_row(mip, i, len, ind, val);
	284	glp_set_rii(mip, i, r->rii);
	285	glp_set_row_stat(mip, i, r->stat);
	286	}
	287	xfree(ind);
	288	xfree(val);
	289	}
	290	#if 0
	291	/* add new edges to the conflict graph */
	292	/* add new cliques to the conflict graph */
	293	/* (not implemented yet) */
	294	xassert(node->own_nn == 0);
	295	xassert(node->own_nc == 0);
	296	xassert(node->e_ptr == NULL);
	297	#endif
	298	}
	299	/* the specified subproblem has been revived */
	300	node = tree->curr;
	301	/* delete its bound change list */
	302	while (node->b_ptr != NULL)
	303	{ IOSBND *b;
	304	b = node->b_ptr;
	305	node->b_ptr = b->next;
	306	dmp_free_atom(tree->pool, b, sizeof(IOSBND));
	307	}
	308	/* delete its status change list */
	309	while (node->s_ptr != NULL)
	310	{ IOSTAT *s;
	311	s = node->s_ptr;
	312	node->s_ptr = s->next;
	313	dmp_free_atom(tree->pool, s, sizeof(IOSTAT));
	314	}
	315	#if 1 /* 20/XI-2009 */
	316	/* delete its row addition list (additional rows may appear, for
	317	example, due to branching on GUB constraints */
	318	while (node->r_ptr != NULL)
	319	{ IOSROW *r;
	320	r = node->r_ptr;
	321	node->r_ptr = r->next;
	322	xassert(r->name == NULL);
	323	while (r->ptr != NULL)
	324	{ IOSAIJ *a;
	325	a = r->ptr;
	326	r->ptr = a->next;
	327	dmp_free_atom(tree->pool, a, sizeof(IOSAIJ));
	328	}
	329	dmp_free_atom(tree->pool, r, sizeof(IOSROW));
	330	}
	331	#endif
	332	done: return;
	333	}
	334
	335	/***********************************************************************
	336	* NAME
	337	*
	338	* ios_freeze_node - freeze current subproblem
	339	*
	340	* SYNOPSIS
	341	*
	342	* #include "glpios.h"
	343	* void ios_freeze_node(glp_tree *tree);
	344	*
	345	* DESCRIPTION
	346	*
	347	* The routine ios_freeze_node freezes the current subproblem. */
	348
	349	void ios_freeze_node(glp_tree *tree)
	350	{ glp_prob *mip = tree->mip;
	351	int m = mip->m;
	352	int n = mip->n;
	353	IOSNPD *node;
	354	/* obtain pointer to the current subproblem */
	355	node = tree->curr;
	356	xassert(node != NULL);
	357	if (node->up == NULL)
	358	{ /* freeze the root subproblem */
	359	int k;
	360	xassert(node->p == 1);
	361	xassert(tree->root_m == 0);
	362	xassert(tree->root_type == NULL);
	363	xassert(tree->root_lb == NULL);
	364	xassert(tree->root_ub == NULL);
	365	xassert(tree->root_stat == NULL);
	366	tree->root_m = m;
	367	tree->root_type = xcalloc(1+m+n, sizeof(char));
	368	tree->root_lb = xcalloc(1+m+n, sizeof(double));
	369	tree->root_ub = xcalloc(1+m+n, sizeof(double));
	370	tree->root_stat = xcalloc(1+m+n, sizeof(char));
	371	for (k = 1; k <= m+n; k++)
	372	{ if (k <= m)
	373	{ GLPROW *row = mip->row[k];
	374	tree->root_type[k] = (char)row->type;
	375	tree->root_lb[k] = row->lb;
	376	tree->root_ub[k] = row->ub;
	377	tree->root_stat[k] = (char)row->stat;
	378	}
	379	else
	380	{ GLPCOL *col = mip->col[k-m];
	381	tree->root_type[k] = (char)col->type;
	382	tree->root_lb[k] = col->lb;
	383	tree->root_ub[k] = col->ub;
	384	tree->root_stat[k] = (char)col->stat;
	385	}
	386	}
	387	}
	388	else
	389	{ /* freeze non-root subproblem */
	390	int root_m = tree->root_m;
	391	int pred_m = tree->pred_m;
	392	int i, j, k;
	393	xassert(pred_m <= m);
	394	/* build change lists for rows and columns which exist in the
	395	parent subproblem */
	396	xassert(node->b_ptr == NULL);
	397	xassert(node->s_ptr == NULL);
	398	for (k = 1; k <= pred_m + n; k++)
	399	{ int pred_type, pred_stat, type, stat;
	400	double pred_lb, pred_ub, lb, ub;
	401	/* determine attributes in the parent subproblem */
	402	pred_type = tree->pred_type[k];
	403	pred_lb = tree->pred_lb[k];
	404	pred_ub = tree->pred_ub[k];
	405	pred_stat = tree->pred_stat[k];
	406	/* determine attributes in the current subproblem */
	407	if (k <= pred_m)
	408	{ GLPROW *row = mip->row[k];
	409	type = row->type;
	410	lb = row->lb;
	411	ub = row->ub;
	412	stat = row->stat;
	413	}
	414	else
	415	{ GLPCOL *col = mip->col[k - pred_m];
	416	type = col->type;
	417	lb = col->lb;
	418	ub = col->ub;
	419	stat = col->stat;
	420	}
	421	/* save type and bounds of a row/column, if changed */
	422	if (!(pred_type == type && pred_lb == lb && pred_ub == ub))
	423	{ IOSBND *b;
	424	b = dmp_get_atom(tree->pool, sizeof(IOSBND));
	425	b->k = k;
	426	b->type = (unsigned char)type;
	427	b->lb = lb;
	428	b->ub = ub;
	429	b->next = node->b_ptr;
	430	node->b_ptr = b;
	431	}
	432	/* save status of a row/column, if changed */
	433	if (pred_stat != stat)
	434	{ IOSTAT *s;
	435	s = dmp_get_atom(tree->pool, sizeof(IOSTAT));
	436	s->k = k;
	437	s->stat = (unsigned char)stat;
	438	s->next = node->s_ptr;
	439	node->s_ptr = s;
	440	}
	441	}
	442	/* save new rows added to the current subproblem */
	443	xassert(node->r_ptr == NULL);
	444	if (pred_m < m)
	445	{ int i, len, *ind;
	446	double *val;
	447	ind = xcalloc(1+n, sizeof(int));
	448	val = xcalloc(1+n, sizeof(double));
	449	for (i = m; i > pred_m; i--)
	450	{ GLPROW *row = mip->row[i];
	451	IOSROW *r;
	452	const char *name;
	453	r = dmp_get_atom(tree->pool, sizeof(IOSROW));
	454	name = glp_get_row_name(mip, i);
	455	if (name == NULL)
	456	r->name = NULL;
	457	else
	458	{ r->name = dmp_get_atom(tree->pool, strlen(name)+1);
	459	strcpy(r->name, name);
	460	}
	461	#if 1 /* 20/IX-2008 */
	462	r->origin = row->origin;
	463	r->klass = row->klass;
	464	#endif
	465	r->type = (unsigned char)row->type;
	466	r->lb = row->lb;
	467	r->ub = row->ub;
	468	r->ptr = NULL;
	469	len = glp_get_mat_row(mip, i, ind, val);
	470	for (k = 1; k <= len; k++)
	471	{ IOSAIJ *a;
	472	a = dmp_get_atom(tree->pool, sizeof(IOSAIJ));
	473	a->j = ind[k];
	474	a->val = val[k];
	475	a->next = r->ptr;
	476	r->ptr = a;
	477	}
	478	r->rii = row->rii;
	479	r->stat = (unsigned char)row->stat;
	480	r->next = node->r_ptr;
	481	node->r_ptr = r;
	482	}
	483	xfree(ind);
	484	xfree(val);
	485	}
	486	/* remove all rows missing in the root subproblem */
	487	if (m != root_m)
	488	{ int nrs, *num;
	489	nrs = m - root_m;
	490	xassert(nrs > 0);
	491	num = xcalloc(1+nrs, sizeof(int));
	492	for (i = 1; i <= nrs; i++) num[i] = root_m + i;
	493	glp_del_rows(mip, nrs, num);
	494	xfree(num);
	495	}
	496	m = mip->m;
	497	/* and restore attributes of all rows and columns for the root
	498	subproblem */
	499	xassert(m == root_m);
	500	for (i = 1; i <= m; i++)
	501	{ glp_set_row_bnds(mip, i, tree->root_type[i],
	502	tree->root_lb[i], tree->root_ub[i]);
	503	glp_set_row_stat(mip, i, tree->root_stat[i]);
	504	}
	505	for (j = 1; j <= n; j++)
	506	{ glp_set_col_bnds(mip, j, tree->root_type[m+j],
	507	tree->root_lb[m+j], tree->root_ub[m+j]);
	508	glp_set_col_stat(mip, j, tree->root_stat[m+j]);
	509	}
	510	#if 1
	511	/* remove all edges and cliques missing in the conflict graph
	512	for the root subproblem */
	513	/* (not implemented yet) */
	514	#endif
	515	}
	516	/* the current subproblem has been frozen */
	517	tree->curr = NULL;
	518	return;
	519	}
	520
	521	/***********************************************************************
	522	* NAME
	523	*
	524	* ios_clone_node - clone specified subproblem
	525	*
	526	* SYNOPSIS
	527	*
	528	* #include "glpios.h"
	529	* void ios_clone_node(glp_tree *tree, int p, int nnn, int ref[]);
	530	*
	531	* DESCRIPTION
	532	*
	533	* The routine ios_clone_node clones the specified subproblem, whose
	534	* reference number is p, creating its nnn exact copies. Note that the
	535	* specified subproblem must be active and must be in the frozen state
	536	* (i.e. it must not be the current subproblem).
	537	*
	538	* Each clone, an exact copy of the specified subproblem, becomes a new
	539	* active subproblem added to the end of the active list. After cloning
	540	* the specified subproblem becomes inactive.
	541	*
	542	* The reference numbers of clone subproblems are stored to locations
	543	* ref[1], ..., ref[nnn]. */
	544
	545	static int get_slot(glp_tree *tree)
	546	{ int p;
	547	/* if no free slots are available, increase the room */
	548	if (tree->avail == 0)
	549	{ int nslots = tree->nslots;
	550	IOSLOT *save = tree->slot;
	551	if (nslots == 0)
	552	tree->nslots = 20;
	553	else
	554	{ tree->nslots = nslots + nslots;
	555	xassert(tree->nslots > nslots);
	556	}
	557	tree->slot = xcalloc(1+tree->nslots, sizeof(IOSLOT));
	558	if (save != NULL)
	559	{ memcpy(&tree->slot[1], &save[1], nslots * sizeof(IOSLOT));
	560	xfree(save);
	561	}
	562	/* push more free slots into the stack */
	563	for (p = tree->nslots; p > nslots; p--)
	564	{ tree->slot[p].node = NULL;
	565	tree->slot[p].next = tree->avail;
	566	tree->avail = p;
	567	}
	568	}
	569	/* pull a free slot from the stack */
	570	p = tree->avail;
	571	tree->avail = tree->slot[p].next;
	572	xassert(tree->slot[p].node == NULL);
	573	tree->slot[p].next = 0;
	574	return p;
	575	}
	576
	577	static IOSNPD new_node(glp_tree tree, IOSNPD *parent)
	578	{ IOSNPD *node;
	579	int p;
	580	/* pull a free slot for the new node */
	581	p = get_slot(tree);
	582	/* create descriptor of the new subproblem */
	583	node = dmp_get_atom(tree->pool, sizeof(IOSNPD));
	584	tree->slot[p].node = node;
	585	node->p = p;
	586	node->up = parent;
	587	node->level = (parent == NULL ? 0 : parent->level + 1);
	588	node->count = 0;
	589	node->b_ptr = NULL;
	590	node->s_ptr = NULL;
	591	node->r_ptr = NULL;
	592	node->solved = 0;
	593	#if 0
	594	node->own_nn = node->own_nc = 0;
	595	node->e_ptr = NULL;
	596	#endif
	597	#if 1 /* 04/X-2008 */
	598	node->lp_obj = (parent == NULL ? (tree->mip->dir == GLP_MIN ?
	599	-DBL_MAX : +DBL_MAX) : parent->lp_obj);
	600	#endif
	601	node->bound = (parent == NULL ? (tree->mip->dir == GLP_MIN ?
	602	-DBL_MAX : +DBL_MAX) : parent->bound);
	603	node->br_var = 0;
	604	node->br_val = 0.0;
	605	node->ii_cnt = 0;
	606	node->ii_sum = 0.0;
	607	#if 1 /* 30/XI-2009 */
	608	node->changed = 0;
	609	#endif
	610	if (tree->parm->cb_size == 0)
	611	node->data = NULL;
	612	else
	613	{ node->data = dmp_get_atom(tree->pool, tree->parm->cb_size);
	614	memset(node->data, 0, tree->parm->cb_size);
	615	}
	616	node->temp = NULL;
	617	node->prev = tree->tail;
	618	node->next = NULL;
	619	/* add the new subproblem to the end of the active list */
	620	if (tree->head == NULL)
	621	tree->head = node;
	622	else
	623	tree->tail->next = node;
	624	tree->tail = node;
	625	tree->a_cnt++;
	626	tree->n_cnt++;
	627	tree->t_cnt++;
	628	/* increase the number of child subproblems */
	629	if (parent == NULL)
	630	xassert(p == 1);
	631	else
	632	parent->count++;
	633	return node;
	634	}
	635
	636	void ios_clone_node(glp_tree *tree, int p, int nnn, int ref[])
	637	{ IOSNPD *node;
	638	int k;
	639	/* obtain pointer to the subproblem to be cloned */
	640	xassert(1 <= p && p <= tree->nslots);
	641	node = tree->slot[p].node;
	642	xassert(node != NULL);
	643	/* the specified subproblem must be active */
	644	xassert(node->count == 0);
	645	/* and must be in the frozen state */
	646	xassert(tree->curr != node);
	647	/* remove the specified subproblem from the active list, because
	648	it becomes inactive */
	649	if (node->prev == NULL)
	650	tree->head = node->next;
	651	else
	652	node->prev->next = node->next;
	653	if (node->next == NULL)
	654	tree->tail = node->prev;
	655	else
	656	node->next->prev = node->prev;
	657	node->prev = node->next = NULL;
	658	tree->a_cnt--;
	659	/* create clone subproblems */
	660	xassert(nnn > 0);
	661	for (k = 1; k <= nnn; k++)
	662	ref[k] = new_node(tree, node)->p;
	663	return;
	664	}
	665
	666	/***********************************************************************
	667	* NAME
	668	*
	669	* ios_delete_node - delete specified subproblem
	670	*
	671	* SYNOPSIS
	672	*
	673	* #include "glpios.h"
	674	* void ios_delete_node(glp_tree *tree, int p);
	675	*
	676	* DESCRIPTION
	677	*
	678	* The routine ios_delete_node deletes the specified subproblem, whose
	679	* reference number is p. The subproblem must be active and must be in
	680	* the frozen state (i.e. it must not be the current subproblem).
	681	*
	682	* Note that deletion is performed recursively, i.e. if a subproblem to
	683	* be deleted is the only child of its parent, the parent subproblem is
	684	* also deleted, etc. */
	685
	686	void ios_delete_node(glp_tree *tree, int p)
	687	{ IOSNPD node, temp;
	688	/* obtain pointer to the subproblem to be deleted */
	689	xassert(1 <= p && p <= tree->nslots);
	690	node = tree->slot[p].node;
	691	xassert(node != NULL);
	692	/* the specified subproblem must be active */
	693	xassert(node->count == 0);
	694	/* and must be in the frozen state */
	695	xassert(tree->curr != node);
	696	/* remove the specified subproblem from the active list, because
	697	it is gone from the tree */
	698	if (node->prev == NULL)
	699	tree->head = node->next;
	700	else
	701	node->prev->next = node->next;
	702	if (node->next == NULL)
	703	tree->tail = node->prev;
	704	else
	705	node->next->prev = node->prev;
	706	node->prev = node->next = NULL;
	707	tree->a_cnt--;
	708	loop: /* recursive deletion starts here */
	709	/* delete the bound change list */
	710	{ IOSBND *b;
	711	while (node->b_ptr != NULL)
	712	{ b = node->b_ptr;
	713	node->b_ptr = b->next;
	714	dmp_free_atom(tree->pool, b, sizeof(IOSBND));
	715	}
	716	}
	717	/* delete the status change list */
	718	{ IOSTAT *s;
	719	while (node->s_ptr != NULL)
	720	{ s = node->s_ptr;
	721	node->s_ptr = s->next;
	722	dmp_free_atom(tree->pool, s, sizeof(IOSTAT));
	723	}
	724	}
	725	/* delete the row addition list */
	726	while (node->r_ptr != NULL)
	727	{ IOSROW *r;
	728	r = node->r_ptr;
	729	if (r->name != NULL)
	730	dmp_free_atom(tree->pool, r->name, strlen(r->name)+1);
	731	while (r->ptr != NULL)
	732	{ IOSAIJ *a;
	733	a = r->ptr;
	734	r->ptr = a->next;
	735	dmp_free_atom(tree->pool, a, sizeof(IOSAIJ));
	736	}
	737	node->r_ptr = r->next;
	738	dmp_free_atom(tree->pool, r, sizeof(IOSROW));
	739	}
	740	#if 0
	741	/* delete the edge addition list */
	742	/* delete the clique addition list */
	743	/* (not implemented yet) */
	744	xassert(node->own_nn == 0);
	745	xassert(node->own_nc == 0);
	746	xassert(node->e_ptr == NULL);
	747	#endif
	748	/* free application-specific data */
	749	if (tree->parm->cb_size == 0)
	750	xassert(node->data == NULL);
	751	else
	752	dmp_free_atom(tree->pool, node->data, tree->parm->cb_size);
	753	/* free the corresponding node slot */
	754	p = node->p;
	755	xassert(tree->slot[p].node == node);
	756	tree->slot[p].node = NULL;
	757	tree->slot[p].next = tree->avail;
	758	tree->avail = p;
	759	/* save pointer to the parent subproblem */
	760	temp = node->up;
	761	/* delete the subproblem descriptor */
	762	dmp_free_atom(tree->pool, node, sizeof(IOSNPD));
	763	tree->n_cnt--;
	764	/* take pointer to the parent subproblem */
	765	node = temp;
	766	if (node != NULL)
	767	{ /* the parent subproblem exists; decrease the number of its
	768	child subproblems */
	769	xassert(node->count > 0);
	770	node->count--;
	771	/* if now the parent subproblem has no childs, it also must be
	772	deleted */
	773	if (node->count == 0) goto loop;
	774	}
	775	return;
	776	}
	777
	778	/***********************************************************************
	779	* NAME
	780	*
	781	* ios_delete_tree - delete branch-and-bound tree
	782	*
	783	* SYNOPSIS
	784	*
	785	* #include "glpios.h"
	786	* void ios_delete_tree(glp_tree *tree);
	787	*
	788	* DESCRIPTION
	789	*
	790	* The routine ios_delete_tree deletes the branch-and-bound tree, which
	791	* the parameter tree points to, and frees all the memory allocated to
	792	* this program object.
	793	*
	794	* On exit components of the problem object are restored to correspond
	795	* to the original MIP passed to the routine ios_create_tree. */
	796
	797	void ios_delete_tree(glp_tree *tree)
	798	{ glp_prob *mip = tree->mip;
	799	int i, j;
	800	int m = mip->m;
	801	int n = mip->n;
	802	xassert(mip->tree == tree);
	803	/* remove all additional rows */
	804	if (m != tree->orig_m)
	805	{ int nrs, *num;
	806	nrs = m - tree->orig_m;
	807	xassert(nrs > 0);
	808	num = xcalloc(1+nrs, sizeof(int));
	809	for (i = 1; i <= nrs; i++) num[i] = tree->orig_m + i;
	810	glp_del_rows(mip, nrs, num);
	811	xfree(num);
	812	}
	813	m = tree->orig_m;
	814	/* restore original attributes of rows and columns */
	815	xassert(m == tree->orig_m);
	816	xassert(n == tree->n);
	817	for (i = 1; i <= m; i++)
	818	{ glp_set_row_bnds(mip, i, tree->orig_type[i],
	819	tree->orig_lb[i], tree->orig_ub[i]);
	820	glp_set_row_stat(mip, i, tree->orig_stat[i]);
	821	mip->row[i]->prim = tree->orig_prim[i];
	822	mip->row[i]->dual = tree->orig_dual[i];
	823	}
	824	for (j = 1; j <= n; j++)
	825	{ glp_set_col_bnds(mip, j, tree->orig_type[m+j],
	826	tree->orig_lb[m+j], tree->orig_ub[m+j]);
	827	glp_set_col_stat(mip, j, tree->orig_stat[m+j]);
	828	mip->col[j]->prim = tree->orig_prim[m+j];
	829	mip->col[j]->dual = tree->orig_dual[m+j];
	830	}
	831	mip->pbs_stat = mip->dbs_stat = GLP_FEAS;
	832	mip->obj_val = tree->orig_obj;
	833	/* delete the branch-and-bound tree */
	834	xassert(tree->local != NULL);
	835	ios_delete_pool(tree, tree->local);
	836	dmp_delete_pool(tree->pool);
	837	xfree(tree->orig_type);
	838	xfree(tree->orig_lb);
	839	xfree(tree->orig_ub);
	840	xfree(tree->orig_stat);
	841	xfree(tree->orig_prim);
	842	xfree(tree->orig_dual);
	843	xfree(tree->slot);
	844	if (tree->root_type != NULL) xfree(tree->root_type);
	845	if (tree->root_lb != NULL) xfree(tree->root_lb);
	846	if (tree->root_ub != NULL) xfree(tree->root_ub);
	847	if (tree->root_stat != NULL) xfree(tree->root_stat);
	848	xfree(tree->non_int);
	849	#if 0
	850	xfree(tree->n_ref);
	851	xfree(tree->c_ref);
	852	xfree(tree->j_ref);
	853	#endif
	854	if (tree->pcost != NULL) ios_pcost_free(tree);
	855	xfree(tree->iwrk);
	856	xfree(tree->dwrk);
	857	#if 0
	858	scg_delete_graph(tree->g);
	859	#endif
	860	if (tree->pred_type != NULL) xfree(tree->pred_type);
	861	if (tree->pred_lb != NULL) xfree(tree->pred_lb);
	862	if (tree->pred_ub != NULL) xfree(tree->pred_ub);
	863	if (tree->pred_stat != NULL) xfree(tree->pred_stat);
	864	#if 0
	865	xassert(tree->cut_gen == NULL);
	866	#endif
	867	xassert(tree->mir_gen == NULL);
	868	xassert(tree->clq_gen == NULL);
	869	xfree(tree);
	870	mip->tree = NULL;
	871	return;
	872	}
	873
	874	/***********************************************************************
	875	* NAME
	876	*
	877	* ios_eval_degrad - estimate obj. degrad. for down- and up-branches
	878	*
	879	* SYNOPSIS
	880	*
	881	* #include "glpios.h"
	882	* void ios_eval_degrad(glp_tree tree, int j, double dn, double *up);
	883	*
	884	* DESCRIPTION
	885	*
	886	* Given optimal basis to LP relaxation of the current subproblem the
	887	* routine ios_eval_degrad performs the dual ratio test to compute the
	888	* objective values in the adjacent basis for down- and up-branches,
	889	* which are stored in locations dn and up, assuming that x[j] is a
	890	* variable chosen to branch upon. */
	891
	892	void ios_eval_degrad(glp_tree tree, int j, double dn, double *up)
	893	{ glp_prob *mip = tree->mip;
	894	int m = mip->m, n = mip->n;
	895	int len, kase, k, t, stat;
	896	double alfa, beta, gamma, delta, dz;
	897	int *ind = tree->iwrk;
	898	double *val = tree->dwrk;
	899	/* current basis must be optimal */
	900	xassert(glp_get_status(mip) == GLP_OPT);
	901	/* basis factorization must exist */
	902	xassert(glp_bf_exists(mip));
	903	/* obtain (fractional) value of x[j] in optimal basic solution
	904	to LP relaxation of the current subproblem */
	905	xassert(1 <= j && j <= n);
	906	beta = mip->col[j]->prim;
	907	/* since the value of x[j] is fractional, it is basic; compute
	908	corresponding row of the simplex table */
	909	len = lpx_eval_tab_row(mip, m+j, ind, val);
	910	/* kase < 0 means down-branch; kase > 0 means up-branch */
	911	for (kase = -1; kase <= +1; kase += 2)
	912	{ /* for down-branch we introduce new upper bound floor(beta)
	913	for x[j]; similarly, for up-branch we introduce new lower
	914	bound ceil(beta) for x[j]; in the current basis this new
	915	upper/lower bound is violated, so in the adjacent basis
	916	x[j] will leave the basis and go to its new upper/lower
	917	bound; we need to know which non-basic variable x[k] should
	918	enter the basis to keep dual feasibility */
	919	#if 0 /* 23/XI-2009 */
	920	k = lpx_dual_ratio_test(mip, len, ind, val, kase, 1e-7);
	921	#else
	922	k = lpx_dual_ratio_test(mip, len, ind, val, kase, 1e-9);
	923	#endif
	924	/* if no variable has been chosen, current basis being primal
	925	infeasible due to the new upper/lower bound of x[j] is dual
	926	unbounded, therefore, LP relaxation to corresponding branch
	927	has no primal feasible solution */
	928	if (k == 0)
	929	{ if (mip->dir == GLP_MIN)
	930	{ if (kase < 0)
	931	*dn = +DBL_MAX;
	932	else
	933	*up = +DBL_MAX;
	934	}
	935	else if (mip->dir == GLP_MAX)
	936	{ if (kase < 0)
	937	*dn = -DBL_MAX;
	938	else
	939	*up = -DBL_MAX;
	940	}
	941	else
	942	xassert(mip != mip);
	943	continue;
	944	}
	945	xassert(1 <= k && k <= m+n);
	946	/* row of the simplex table corresponding to specified basic
	947	variable x[j] is the following:
	948	x[j] = ... + alfa * x[k] + ... ;
	949	we need to know influence coefficient, alfa, at non-basic
	950	variable x[k] chosen with the dual ratio test */
	951	for (t = 1; t <= len; t++)
	952	if (ind[t] == k) break;
	953	xassert(1 <= t && t <= len);
	954	alfa = val[t];
	955	/* determine status and reduced cost of variable x[k] */
	956	if (k <= m)
	957	{ stat = mip->row[k]->stat;
	958	gamma = mip->row[k]->dual;
	959	}
	960	else
	961	{ stat = mip->col[k-m]->stat;
	962	gamma = mip->col[k-m]->dual;
	963	}
	964	/* x[k] cannot be basic or fixed non-basic */
	965	xassert(stat == GLP_NL \|\| stat == GLP_NU \|\| stat == GLP_NF);
	966	/* if the current basis is dual degenerative, some reduced
	967	costs, which are close to zero, may have wrong sign due to
	968	round-off errors, so correct the sign of gamma */
	969	if (mip->dir == GLP_MIN)
	970	{ if (stat == GLP_NL && gamma < 0.0 \|\|
	971	stat == GLP_NU && gamma > 0.0 \|\|
	972	stat == GLP_NF) gamma = 0.0;
	973	}
	974	else if (mip->dir == GLP_MAX)
	975	{ if (stat == GLP_NL && gamma > 0.0 \|\|
	976	stat == GLP_NU && gamma < 0.0 \|\|
	977	stat == GLP_NF) gamma = 0.0;
	978	}
	979	else
	980	xassert(mip != mip);
	981	/* determine the change of x[j] in the adjacent basis:
	982	delta x[j] = new x[j] - old x[j] */
	983	delta = (kase < 0 ? floor(beta) : ceil(beta)) - beta;
	984	/* compute the change of x[k] in the adjacent basis:
	985	delta x[k] = new x[k] - old x[k] = delta x[j] / alfa */
	986	delta /= alfa;
	987	/* compute the change of the objective in the adjacent basis:
	988	delta z = new z - old z = gamma * delta x[k] */
	989	dz = gamma * delta;
	990	if (mip->dir == GLP_MIN)
	991	xassert(dz >= 0.0);
	992	else if (mip->dir == GLP_MAX)
	993	xassert(dz <= 0.0);
	994	else
	995	xassert(mip != mip);
	996	/* compute the new objective value in the adjacent basis:
	997	new z = old z + delta z */
	998	if (kase < 0)
	999	*dn = mip->obj_val + dz;
	1000	else
	1001	*up = mip->obj_val + dz;
	1002	}
	1003	/*xprintf("obj = %g; dn = %g; up = %g\n",
	1004	mip->obj_val, dn, up);*/
	1005	return;
	1006	}
	1007
	1008	/***********************************************************************
	1009	* NAME
	1010	*
	1011	* ios_round_bound - improve local bound by rounding
	1012	*
	1013	* SYNOPSIS
	1014	*
	1015	* #include "glpios.h"
	1016	* double ios_round_bound(glp_tree *tree, double bound);
	1017	*
	1018	* RETURNS
	1019	*
	1020	* For the given local bound for any integer feasible solution to the
	1021	* current subproblem the routine ios_round_bound returns an improved
	1022	* local bound for the same integer feasible solution.
	1023	*
	1024	* BACKGROUND
	1025	*
	1026	* Let the current subproblem has the following objective function:
	1027	*
	1028	* z = sum c[j] * x[j] + s >= b, (1)
	1029	* j in J
	1030	*
	1031	* where J = {j: c[j] is non-zero and integer, x[j] is integer}, s is
	1032	* the sum of terms corresponding to fixed variables, b is an initial
	1033	* local bound (minimization).
	1034	*
	1035	* From (1) it follows that:
	1036	*
	1037	* d * sum (c[j] / d) * x[j] + s >= b, (2)
	1038	* j in J
	1039	*
	1040	* or, equivalently,
	1041	*
	1042	* sum (c[j] / d) * x[j] >= (b - s) / d = h, (3)
	1043	* j in J
	1044	*
	1045	* where d = gcd(c[j]). Since the left-hand side of (3) is integer,
	1046	* h = (b - s) / d can be rounded up to the nearest integer:
	1047	*
	1048	* h' = ceil(h) = (b' - s) / d, (4)
	1049	*
	1050	* that gives an rounded, improved local bound:
	1051	*
	1052	* b' = d * h' + s. (5)
	1053	*
	1054	* In case of maximization '>=' in (1) should be replaced by '<=' that
	1055	* leads to the following formula:
	1056	*
	1057	* h' = floor(h) = (b' - s) / d, (6)
	1058	*
	1059	* which should used in the same way as (4).
	1060	*
	1061	* NOTE: If b is a valid local bound for a child of the current
	1062	* subproblem, b' is also valid for that child subproblem. */
	1063
	1064	double ios_round_bound(glp_tree *tree, double bound)
	1065	{ glp_prob *mip = tree->mip;
	1066	int n = mip->n;
	1067	int d, j, nn, *c = tree->iwrk;
	1068	double s, h;
	1069	/* determine c[j] and compute s */
	1070	nn = 0, s = mip->c0, d = 0;
	1071	for (j = 1; j <= n; j++)
	1072	{ GLPCOL *col = mip->col[j];
	1073	if (col->coef == 0.0) continue;
	1074	if (col->type == GLP_FX)
	1075	{ /* fixed variable */
	1076	s += col->coef * col->prim;
	1077	}
	1078	else
	1079	{ /* non-fixed variable */
	1080	if (col->kind != GLP_IV) goto skip;
	1081	if (col->coef != floor(col->coef)) goto skip;
	1082	if (fabs(col->coef) <= (double)INT_MAX)
	1083	c[++nn] = (int)fabs(col->coef);
	1084	else
	1085	d = 1;
	1086	}
	1087	}
	1088	/* compute d = gcd(c[1],...c[nn]) */
	1089	if (d == 0)
	1090	{ if (nn == 0) goto skip;
	1091	d = gcdn(nn, c);
	1092	}
	1093	xassert(d > 0);
	1094	/* compute new local bound */
	1095	if (mip->dir == GLP_MIN)
	1096	{ if (bound != +DBL_MAX)
	1097	{ h = (bound - s) / (double)d;
	1098	if (h >= floor(h) + 0.001)
	1099	{ /* round up */
	1100	h = ceil(h);
	1101	/xprintf("d = %d; old = %g; ", d, bound);/
	1102	bound = (double)d * h + s;
	1103	/xprintf("new = %g\n", bound);/
	1104	}
	1105	}
	1106	}
	1107	else if (mip->dir == GLP_MAX)
	1108	{ if (bound != -DBL_MAX)
	1109	{ h = (bound - s) / (double)d;
	1110	if (h <= ceil(h) - 0.001)
	1111	{ /* round down */
	1112	h = floor(h);
	1113	bound = (double)d * h + s;
	1114	}
	1115	}
	1116	}
	1117	else
	1118	xassert(mip != mip);
	1119	skip: return bound;
	1120	}
	1121
	1122	/***********************************************************************
	1123	* NAME
	1124	*
	1125	* ios_is_hopeful - check if subproblem is hopeful
	1126	*
	1127	* SYNOPSIS
	1128	*
	1129	* #include "glpios.h"
	1130	* int ios_is_hopeful(glp_tree *tree, double bound);
	1131	*
	1132	* DESCRIPTION
	1133	*
	1134	* Given the local bound of a subproblem the routine ios_is_hopeful
	1135	* checks if the subproblem can have an integer optimal solution which
	1136	* is better than the best one currently known.
	1137	*
	1138	* RETURNS
	1139	*
	1140	* If the subproblem can have a better integer optimal solution, the
	1141	* routine returns non-zero; otherwise, if the corresponding branch can
	1142	* be pruned, the routine returns zero. */
	1143
	1144	int ios_is_hopeful(glp_tree *tree, double bound)
	1145	{ glp_prob *mip = tree->mip;
	1146	int ret = 1;
	1147	double eps;
	1148	if (mip->mip_stat == GLP_FEAS)
	1149	{ eps = tree->parm->tol_obj * (1.0 + fabs(mip->mip_obj));
	1150	switch (mip->dir)
	1151	{ case GLP_MIN:
	1152	if (bound >= mip->mip_obj - eps) ret = 0;
	1153	break;
	1154	case GLP_MAX:
	1155	if (bound <= mip->mip_obj + eps) ret = 0;
	1156	break;
	1157	default:
	1158	xassert(mip != mip);
	1159	}
	1160	}
	1161	else
	1162	{ switch (mip->dir)
	1163	{ case GLP_MIN:
	1164	if (bound == +DBL_MAX) ret = 0;
	1165	break;
	1166	case GLP_MAX:
	1167	if (bound == -DBL_MAX) ret = 0;
	1168	break;
	1169	default:
	1170	xassert(mip != mip);
	1171	}
	1172	}
	1173	return ret;
	1174	}
	1175
	1176	/***********************************************************************
	1177	* NAME
	1178	*
	1179	* ios_best_node - find active node with best local bound
	1180	*
	1181	* SYNOPSIS
	1182	*
	1183	* #include "glpios.h"
	1184	* int ios_best_node(glp_tree *tree);
	1185	*
	1186	* DESCRIPTION
	1187	*
	1188	* The routine ios_best_node finds an active node whose local bound is
	1189	* best among other active nodes.
	1190	*
	1191	* It is understood that the integer optimal solution of the original
	1192	* mip problem cannot be better than the best bound, so the best bound
	1193	* is an lower (minimization) or upper (maximization) global bound for
	1194	* the original problem.
	1195	*
	1196	* RETURNS
	1197	*
	1198	* The routine ios_best_node returns the subproblem reference number
	1199	* for the best node. However, if the tree is empty, it returns zero. */
	1200
	1201	int ios_best_node(glp_tree *tree)
	1202	{ IOSNPD node, best = NULL;
	1203	switch (tree->mip->dir)
	1204	{ case GLP_MIN:
	1205	/* minimization */
	1206	for (node = tree->head; node != NULL; node = node->next)
	1207	if (best == NULL \|\| best->bound > node->bound)
	1208	best = node;
	1209	break;
	1210	case GLP_MAX:
	1211	/* maximization */
	1212	for (node = tree->head; node != NULL; node = node->next)
	1213	if (best == NULL \|\| best->bound < node->bound)
	1214	best = node;
	1215	break;
	1216	default:
	1217	xassert(tree != tree);
	1218	}
	1219	return best == NULL ? 0 : best->p;
	1220	}
	1221
	1222	/***********************************************************************
	1223	* NAME
	1224	*
	1225	* ios_relative_gap - compute relative mip gap
	1226	*
	1227	* SYNOPSIS
	1228	*
	1229	* #include "glpios.h"
	1230	* double ios_relative_gap(glp_tree *tree);
	1231	*
	1232	* DESCRIPTION
	1233	*
	1234	* The routine ios_relative_gap computes the relative mip gap using the
	1235	* formula:
	1236	*
	1237	* gap = \|best_mip - best_bnd\| / (\|best_mip\| + DBL_EPSILON),
	1238	*
	1239	* where best_mip is the best integer feasible solution found so far,
	1240	* best_bnd is the best (global) bound. If no integer feasible solution
	1241	* has been found yet, rel_gap is set to DBL_MAX.
	1242	*
	1243	* RETURNS
	1244	*
	1245	* The routine ios_relative_gap returns the relative mip gap. */
	1246
	1247	double ios_relative_gap(glp_tree *tree)
	1248	{ glp_prob *mip = tree->mip;
	1249	int p;
	1250	double best_mip, best_bnd, gap;
	1251	if (mip->mip_stat == GLP_FEAS)
	1252	{ best_mip = mip->mip_obj;
	1253	p = ios_best_node(tree);
	1254	if (p == 0)
	1255	{ /* the tree is empty */
	1256	gap = 0.0;
	1257	}
	1258	else
	1259	{ best_bnd = tree->slot[p].node->bound;
	1260	gap = fabs(best_mip - best_bnd) / (fabs(best_mip) +
	1261	DBL_EPSILON);
	1262	}
	1263	}
	1264	else
	1265	{ /* no integer feasible solution has been found yet */
	1266	gap = DBL_MAX;
	1267	}
	1268	return gap;
	1269	}
	1270
	1271	/***********************************************************************
	1272	* NAME
	1273	*
	1274	* ios_solve_node - solve LP relaxation of current subproblem
	1275	*
	1276	* SYNOPSIS
	1277	*
	1278	* #include "glpios.h"
	1279	* int ios_solve_node(glp_tree *tree);
	1280	*
	1281	* DESCRIPTION
	1282	*
	1283	* The routine ios_solve_node re-optimizes LP relaxation of the current
	1284	* subproblem using the dual simplex method.
	1285	*
	1286	* RETURNS
	1287	*
	1288	* The routine returns the code which is reported by glp_simplex. */
	1289
	1290	int ios_solve_node(glp_tree *tree)
	1291	{ glp_prob *mip = tree->mip;
	1292	glp_smcp parm;
	1293	int ret;
	1294	/* the current subproblem must exist */
	1295	xassert(tree->curr != NULL);
	1296	/* set some control parameters */
	1297	glp_init_smcp(&parm);
	1298	switch (tree->parm->msg_lev)
	1299	{ case GLP_MSG_OFF:
	1300	parm.msg_lev = GLP_MSG_OFF; break;
	1301	case GLP_MSG_ERR:
	1302	parm.msg_lev = GLP_MSG_ERR; break;
	1303	case GLP_MSG_ON:
	1304	case GLP_MSG_ALL:
	1305	parm.msg_lev = GLP_MSG_ON; break;
	1306	case GLP_MSG_DBG:
	1307	parm.msg_lev = GLP_MSG_ALL; break;
	1308	default:
	1309	xassert(tree != tree);
	1310	}
	1311	parm.meth = GLP_DUALP;
	1312	if (tree->parm->msg_lev < GLP_MSG_DBG)
	1313	parm.out_dly = tree->parm->out_dly;
	1314	else
	1315	parm.out_dly = 0;
	1316	/* if the incumbent objective value is already known, use it to
	1317	prematurely terminate the dual simplex search */
	1318	if (mip->mip_stat == GLP_FEAS)
	1319	{ switch (tree->mip->dir)
	1320	{ case GLP_MIN:
	1321	parm.obj_ul = mip->mip_obj;
	1322	break;
	1323	case GLP_MAX:
	1324	parm.obj_ll = mip->mip_obj;
	1325	break;
	1326	default:
	1327	xassert(mip != mip);
	1328	}
	1329	}
	1330	/* try to solve/re-optimize the LP relaxation */
	1331	ret = glp_simplex(mip, &parm);
	1332	tree->curr->solved++;
	1333	#if 0
	1334	xprintf("ret = %d; status = %d; pbs = %d; dbs = %d; some = %d\n",
	1335	ret, glp_get_status(mip), mip->pbs_stat, mip->dbs_stat,
	1336	mip->some);
	1337	lpx_print_sol(mip, "sol");
	1338	#endif
	1339	return ret;
	1340	}
	1341
	1342	/**********************************************************************/
	1343
	1344	IOSPOOL ios_create_pool(glp_tree tree)
	1345	{ /* create cut pool */
	1346	IOSPOOL *pool;
	1347	#if 0
	1348	pool = dmp_get_atom(tree->pool, sizeof(IOSPOOL));
	1349	#else
	1350	xassert(tree == tree);
	1351	pool = xmalloc(sizeof(IOSPOOL));
	1352	#endif
	1353	pool->size = 0;
	1354	pool->head = pool->tail = NULL;
	1355	pool->ord = 0, pool->curr = NULL;
	1356	return pool;
	1357	}
	1358
	1359	int ios_add_row(glp_tree tree, IOSPOOL pool,
	1360	const char *name, int klass, int flags, int len, const int ind[],
	1361	const double val[], int type, double rhs)
	1362	{ /* add row (constraint) to the cut pool */
	1363	IOSCUT *cut;
	1364	IOSAIJ *aij;
	1365	int k;
	1366	xassert(pool != NULL);
	1367	cut = dmp_get_atom(tree->pool, sizeof(IOSCUT));
	1368	if (name == NULL \|\| name[0] == '\0')
	1369	cut->name = NULL;
	1370	else
	1371	{ for (k = 0; name[k] != '\0'; k++)
	1372	{ if (k == 256)
	1373	xerror("glp_ios_add_row: cut name too long\n");
	1374	if (iscntrl((unsigned char)name[k]))
	1375	xerror("glp_ios_add_row: cut name contains invalid chara"
	1376	"cter(s)\n");
	1377	}
	1378	cut->name = dmp_get_atom(tree->pool, strlen(name)+1);
	1379	strcpy(cut->name, name);
	1380	}
	1381	if (!(0 <= klass && klass <= 255))
	1382	xerror("glp_ios_add_row: klass = %d; invalid cut class\n",
	1383	klass);
	1384	cut->klass = (unsigned char)klass;
	1385	if (flags != 0)
	1386	xerror("glp_ios_add_row: flags = %d; invalid cut flags\n",
	1387	flags);
	1388	cut->ptr = NULL;
	1389	if (!(0 <= len && len <= tree->n))
	1390	xerror("glp_ios_add_row: len = %d; invalid cut length\n",
	1391	len);
	1392	for (k = 1; k <= len; k++)
	1393	{ aij = dmp_get_atom(tree->pool, sizeof(IOSAIJ));
	1394	if (!(1 <= ind[k] && ind[k] <= tree->n))
	1395	xerror("glp_ios_add_row: ind[%d] = %d; column index out of "
	1396	"range\n", k, ind[k]);
	1397	aij->j = ind[k];
	1398	aij->val = val[k];
	1399	aij->next = cut->ptr;
	1400	cut->ptr = aij;
	1401	}
	1402	if (!(type == GLP_LO \|\| type == GLP_UP \|\| type == GLP_FX))
	1403	xerror("glp_ios_add_row: type = %d; invalid cut type\n",
	1404	type);
	1405	cut->type = (unsigned char)type;
	1406	cut->rhs = rhs;
	1407	cut->prev = pool->tail;
	1408	cut->next = NULL;
	1409	if (cut->prev == NULL)
	1410	pool->head = cut;
	1411	else
	1412	cut->prev->next = cut;
	1413	pool->tail = cut;
	1414	pool->size++;
	1415	return pool->size;
	1416	}
	1417
	1418	IOSCUT ios_find_row(IOSPOOL pool, int i)
	1419	{ /* find row (constraint) in the cut pool */
	1420	/* (smart linear search) */
	1421	xassert(pool != NULL);
	1422	xassert(1 <= i && i <= pool->size);
	1423	if (pool->ord == 0)
	1424	{ xassert(pool->curr == NULL);
	1425	pool->ord = 1;
	1426	pool->curr = pool->head;
	1427	}
	1428	xassert(pool->curr != NULL);
	1429	if (i < pool->ord)
	1430	{ if (i < pool->ord - i)
	1431	{ pool->ord = 1;
	1432	pool->curr = pool->head;
	1433	while (pool->ord != i)
	1434	{ pool->ord++;
	1435	xassert(pool->curr != NULL);
	1436	pool->curr = pool->curr->next;
	1437	}
	1438	}
	1439	else
	1440	{ while (pool->ord != i)
	1441	{ pool->ord--;
	1442	xassert(pool->curr != NULL);
	1443	pool->curr = pool->curr->prev;
	1444	}
	1445	}
	1446	}
	1447	else if (i > pool->ord)
	1448	{ if (i - pool->ord < pool->size - i)
	1449	{ while (pool->ord != i)
	1450	{ pool->ord++;
	1451	xassert(pool->curr != NULL);
	1452	pool->curr = pool->curr->next;
	1453	}
	1454	}
	1455	else
	1456	{ pool->ord = pool->size;
	1457	pool->curr = pool->tail;
	1458	while (pool->ord != i)
	1459	{ pool->ord--;
	1460	xassert(pool->curr != NULL);
	1461	pool->curr = pool->curr->prev;
	1462	}
	1463	}
	1464	}
	1465	xassert(pool->ord == i);
	1466	xassert(pool->curr != NULL);
	1467	return pool->curr;
	1468	}
	1469
	1470	void ios_del_row(glp_tree tree, IOSPOOL pool, int i)
	1471	{ /* remove row (constraint) from the cut pool */
	1472	IOSCUT *cut;
	1473	IOSAIJ *aij;
	1474	xassert(pool != NULL);
	1475	if (!(1 <= i && i <= pool->size))
	1476	xerror("glp_ios_del_row: i = %d; cut number out of range\n",
	1477	i);
	1478	cut = ios_find_row(pool, i);
	1479	xassert(pool->curr == cut);
	1480	if (cut->next != NULL)
	1481	pool->curr = cut->next;
	1482	else if (cut->prev != NULL)
	1483	pool->ord--, pool->curr = cut->prev;
	1484	else
	1485	pool->ord = 0, pool->curr = NULL;
	1486	if (cut->name != NULL)
	1487	dmp_free_atom(tree->pool, cut->name, strlen(cut->name)+1);
	1488	if (cut->prev == NULL)
	1489	{ xassert(pool->head == cut);
	1490	pool->head = cut->next;
	1491	}
	1492	else
	1493	{ xassert(cut->prev->next == cut);
	1494	cut->prev->next = cut->next;
	1495	}
	1496	if (cut->next == NULL)
	1497	{ xassert(pool->tail == cut);
	1498	pool->tail = cut->prev;
	1499	}
	1500	else
	1501	{ xassert(cut->next->prev == cut);
	1502	cut->next->prev = cut->prev;
	1503	}
	1504	while (cut->ptr != NULL)
	1505	{ aij = cut->ptr;
	1506	cut->ptr = aij->next;
	1507	dmp_free_atom(tree->pool, aij, sizeof(IOSAIJ));
	1508	}
	1509	dmp_free_atom(tree->pool, cut, sizeof(IOSCUT));
	1510	pool->size--;
	1511	return;
	1512	}
	1513
	1514	void ios_clear_pool(glp_tree tree, IOSPOOL pool)
	1515	{ /* remove all rows (constraints) from the cut pool */
	1516	xassert(pool != NULL);
	1517	while (pool->head != NULL)
	1518	{ IOSCUT *cut = pool->head;
	1519	pool->head = cut->next;
	1520	if (cut->name != NULL)
	1521	dmp_free_atom(tree->pool, cut->name, strlen(cut->name)+1);
	1522	while (cut->ptr != NULL)
	1523	{ IOSAIJ *aij = cut->ptr;
	1524	cut->ptr = aij->next;
	1525	dmp_free_atom(tree->pool, aij, sizeof(IOSAIJ));
	1526	}
	1527	dmp_free_atom(tree->pool, cut, sizeof(IOSCUT));
	1528	}
	1529	pool->size = 0;
	1530	pool->head = pool->tail = NULL;
	1531	pool->ord = 0, pool->curr = NULL;
	1532	return;
	1533	}
	1534
	1535	void ios_delete_pool(glp_tree tree, IOSPOOL pool)
	1536	{ /* delete cut pool */
	1537	xassert(pool != NULL);
	1538	ios_clear_pool(tree, pool);
	1539	xfree(pool);
	1540	return;
	1541	}
	1542
	1543	/**********************************************************************/
	1544
	1545	#if 0
	1546	static int refer_to_node(glp_tree *tree, int j)
	1547	{ /* determine node number corresponding to binary variable x[j] or
	1548	its complement */
	1549	glp_prob *mip = tree->mip;
	1550	int n = mip->n;
	1551	int *ref;
	1552	if (j > 0)
	1553	ref = tree->n_ref;
	1554	else
	1555	ref = tree->c_ref, j = - j;
	1556	xassert(1 <= j && j <= n);
	1557	if (ref[j] == 0)
	1558	{ /* new node is needed */
	1559	SCG *g = tree->g;
	1560	int n_max = g->n_max;
	1561	ref[j] = scg_add_nodes(g, 1);
	1562	if (g->n_max > n_max)
	1563	{ int *save = tree->j_ref;
	1564	tree->j_ref = xcalloc(1+g->n_max, sizeof(int));
	1565	memcpy(&tree->j_ref[1], &save[1], g->n * sizeof(int));
	1566	xfree(save);
	1567	}
	1568	xassert(ref[j] == g->n);
	1569	tree->j_ref[ref[j]] = j;
	1570	xassert(tree->curr != NULL);
	1571	if (tree->curr->level > 0) tree->curr->own_nn++;
	1572	}
	1573	return ref[j];
	1574	}
	1575	#endif
	1576
	1577	#if 0
	1578	void ios_add_edge(glp_tree *tree, int j1, int j2)
	1579	{ /* add new edge to the conflict graph */
	1580	glp_prob *mip = tree->mip;
	1581	int n = mip->n;
	1582	SCGRIB *e;
	1583	int first, i1, i2;
	1584	xassert(-n <= j1 && j1 <= +n && j1 != 0);
	1585	xassert(-n <= j2 && j2 <= +n && j2 != 0);
	1586	xassert(j1 != j2);
	1587	/* determine number of the first node, which was added for the
	1588	current subproblem */
	1589	xassert(tree->curr != NULL);
	1590	first = tree->g->n - tree->curr->own_nn + 1;
	1591	/* determine node numbers for both endpoints */
	1592	i1 = refer_to_node(tree, j1);
	1593	i2 = refer_to_node(tree, j2);
	1594	/* add edge (i1,i2) to the conflict graph */
	1595	e = scg_add_edge(tree->g, i1, i2);
	1596	/* if the current subproblem is not the root and both endpoints
	1597	were created on some previous levels, save the edge */
	1598	if (tree->curr->level > 0 && i1 < first && i2 < first)
	1599	{ IOSRIB *rib;
	1600	rib = dmp_get_atom(tree->pool, sizeof(IOSRIB));
	1601	rib->j1 = j1;
	1602	rib->j2 = j2;
	1603	rib->e = e;
	1604	rib->next = tree->curr->e_ptr;
	1605	tree->curr->e_ptr = rib;
	1606	}
	1607	return;
	1608	}
	1609	#endif
	1610
	1611	/* eof */

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

Context Navigation

source: glpk-cmake/src/glpios01.c @ 1:c445c931472f

Download in other formats: