Context Navigation

← Previous Revision
Next Revision →
Blame
Revision Log

glpios01.c

subpack-glpk

Last change on this file was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 13 years ago
Import GLPK 4.47
File size: 52.1 KB

Line
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, 2011 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: lemon-project-template-glpk/deps/glpk/src/glpios01.c

Download in other formats: