COIN-OR::LEMON - Graph Library

source: lemon-project-template-glpk/deps/glpk/src/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
49static IOSNPD *new_node(glp_tree *tree, IOSNPD *parent);
50
51glp_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
173void 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
332done: 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
349void 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
545static 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
577static 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
636void 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
686void 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--;
708loop: /* 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
797void 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
892void 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
1064double 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);
1119skip: 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
1144int 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
1201int 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
1247double 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
1290int 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
1344IOSPOOL *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
1359int 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
1418IOSCUT *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
1470void 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
1514void 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
1535void 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
1546static 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
1578void 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.