/* glpios01.c */

 /***********************************************************************

 *  This code is part of GLPK (GNU Linear Programming Kit).

 *

 *  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,

 *  2009, 2010 Andrew Makhorin, Department for Applied Informatics,

 *  Moscow Aviation Institute, Moscow, Russia. All rights reserved.

 *  E-mail: <mao@gnu.org>.

 *

 *  GLPK is free software: you can redistribute it and/or modify it

 *  under the terms of the GNU General Public License as published by

 *  the Free Software Foundation, either version 3 of the License, or

 *  (at your option) any later version.

 *

 *  GLPK is distributed in the hope that it will be useful, but WITHOUT

 *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY

 *  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public

 *  License for more details.

 *

 *  You should have received a copy of the GNU General Public License

 *  along with GLPK. If not, see <http://www.gnu.org/licenses/>.

 ***********************************************************************/

 #include "glpios.h"

 /***********************************************************************

 *  NAME

 *

 *  ios_create_tree - create branch-and-bound tree

 *

 *  SYNOPSIS

 *

 *  #include "glpios.h"

 *  glp_tree *ios_create_tree(glp_prob *mip, const glp_iocp *parm);

 *

 *  DESCRIPTION

 *

 *  The routine ios_create_tree creates the branch-and-bound tree.

 *

 *  Being created the tree consists of the only root subproblem whose

 *  reference number is 1. Note that initially the root subproblem is in

 *  frozen state and therefore needs to be revived.

 *

 *  RETURNS

 *

 *  The routine returns a pointer to the tree created. */

 static IOSNPD *new_node(glp_tree *tree, IOSNPD *parent);

 glp_tree *ios_create_tree(glp_prob *mip, const glp_iocp *parm)

 {     int m = mip->m;

       int n = mip->n;

       glp_tree *tree;

       int i, j;

       xassert(mip->tree == NULL);

       mip->tree = tree = xmalloc(sizeof(glp_tree));

       tree->pool = dmp_create_pool();

       tree->n = n;

       /* save original problem components */

       tree->orig_m = m;

       tree->orig_type = xcalloc(1+m+n, sizeof(char));

       tree->orig_lb = xcalloc(1+m+n, sizeof(double));

       tree->orig_ub = xcalloc(1+m+n, sizeof(double));

       tree->orig_stat = xcalloc(1+m+n, sizeof(char));

       tree->orig_prim = xcalloc(1+m+n, sizeof(double));

       tree->orig_dual = xcalloc(1+m+n, sizeof(double));

       for (i = 1; i <= m; i++)

       {  GLPROW *row = mip->row[i];

          tree->orig_type[i] = (char)row->type;

          tree->orig_lb[i] = row->lb;

          tree->orig_ub[i] = row->ub;

          tree->orig_stat[i] = (char)row->stat;

          tree->orig_prim[i] = row->prim;

          tree->orig_dual[i] = row->dual;

       }

       for (j = 1; j <= n; j++)

       {  GLPCOL *col = mip->col[j];

          tree->orig_type[m+j] = (char)col->type;

          tree->orig_lb[m+j] = col->lb;

          tree->orig_ub[m+j] = col->ub;

          tree->orig_stat[m+j] = (char)col->stat;

          tree->orig_prim[m+j] = col->prim;

          tree->orig_dual[m+j] = col->dual;

       }

       tree->orig_obj = mip->obj_val;

       /* initialize the branch-and-bound tree */

       tree->nslots = 0;

       tree->avail = 0;

       tree->slot = NULL;

       tree->head = tree->tail = NULL;

       tree->a_cnt = tree->n_cnt = tree->t_cnt = 0;

       /* the root subproblem is not solved yet, so its final components

          are unknown so far */

       tree->root_m = 0;

       tree->root_type = NULL;

       tree->root_lb = tree->root_ub = NULL;

       tree->root_stat = NULL;

       /* the current subproblem does not exist yet */

       tree->curr = NULL;

       tree->mip = mip;

       /*tree->solved = 0;*/

       tree->non_int = xcalloc(1+n, sizeof(char));

       memset(&tree->non_int[1], 0, n);

       /* arrays to save parent subproblem components will be allocated

          later */

       tree->pred_m = tree->pred_max = 0;

       tree->pred_type = NULL;

       tree->pred_lb = tree->pred_ub = NULL;

       tree->pred_stat = NULL;

       /* cut generator */

       tree->local = ios_create_pool(tree);

       /*tree->first_attempt = 1;*/

       /*tree->max_added_cuts = 0;*/

       /*tree->min_eff = 0.0;*/

       /*tree->miss = 0;*/

       /*tree->just_selected = 0;*/

       tree->mir_gen = NULL;

       tree->clq_gen = NULL;

       /*tree->round = 0;*/

 #if 0

       /* create the conflict graph */

       tree->n_ref = xcalloc(1+n, sizeof(int));

       memset(&tree->n_ref[1], 0, n * sizeof(int));

       tree->c_ref = xcalloc(1+n, sizeof(int));

       memset(&tree->c_ref[1], 0, n * sizeof(int));

       tree->g = scg_create_graph(0);

       tree->j_ref = xcalloc(1+tree->g->n_max, sizeof(int));

 #endif

       /* pseudocost branching */

       tree->pcost = NULL;

       tree->iwrk = xcalloc(1+n, sizeof(int));

       tree->dwrk = xcalloc(1+n, sizeof(double));

       /* initialize control parameters */

       tree->parm = parm;

       tree->tm_beg = xtime();

       tree->tm_lag = xlset(0);

       tree->sol_cnt = 0;

       /* initialize advanced solver interface */

       tree->reason = 0;

       tree->reopt = 0;

       tree->reinv = 0;

       tree->br_var = 0;

       tree->br_sel = 0;

       tree->child = 0;

       tree->next_p = 0;

       /*tree->btrack = NULL;*/

       tree->stop = 0;

       /* create the root subproblem, which initially is identical to

          the original MIP */

       new_node(tree, NULL);

       return tree;

 }

 /***********************************************************************

 *  NAME

 *

 *  ios_revive_node - revive specified subproblem

 *

 *  SYNOPSIS

 *

 *  #include "glpios.h"

 *  void ios_revive_node(glp_tree *tree, int p);

 *

 *  DESCRIPTION

 *

 *  The routine ios_revive_node revives the specified subproblem, whose

 *  reference number is p, and thereby makes it the current subproblem.

 *  Note that the specified subproblem must be active. Besides, if the

 *  current subproblem already exists, it must be frozen before reviving

 *  another subproblem. */

 void ios_revive_node(glp_tree *tree, int p)

 {     glp_prob *mip = tree->mip;

       IOSNPD *node, *root;

       /* obtain pointer to the specified subproblem */

       xassert(1 <= p && p <= tree->nslots);

       node = tree->slot[p].node;

       xassert(node != NULL);

       /* the specified subproblem must be active */

       xassert(node->count == 0);

       /* the current subproblem must not exist */

       xassert(tree->curr == NULL);

       /* the specified subproblem becomes current */

       tree->curr = node;

       /*tree->solved = 0;*/

       /* obtain pointer to the root subproblem */

       root = tree->slot[1].node;

       xassert(root != NULL);

       /* at this point problem object components correspond to the root

          subproblem, so if the root subproblem should be revived, there

          is nothing more to do */

       if (node == root) goto done;

       xassert(mip->m == tree->root_m);

       /* build path from the root to the current node */

       node->temp = NULL;

       for (node = node; node != NULL; node = node->up)

       {  if (node->up == NULL)

             xassert(node == root);

          else

             node->up->temp = node;

       }

       /* go down from the root to the current node and make necessary

          changes to restore components of the current subproblem */

       for (node = root; node != NULL; node = node->temp)

       {  int m = mip->m;

          int n = mip->n;

          /* if the current node is reached, the problem object at this

             point corresponds to its parent, so save attributes of rows

             and columns for the parent subproblem */

          if (node->temp == NULL)

          {  int i, j;

             tree->pred_m = m;

             /* allocate/reallocate arrays, if necessary */

             if (tree->pred_max < m + n)

             {  int new_size = m + n + 100;

                if (tree->pred_type != NULL) xfree(tree->pred_type);

                if (tree->pred_lb != NULL) xfree(tree->pred_lb);

                if (tree->pred_ub != NULL) xfree(tree->pred_ub);

                if (tree->pred_stat != NULL) xfree(tree->pred_stat);

                tree->pred_max = new_size;

                tree->pred_type = xcalloc(1+new_size, sizeof(char));

                tree->pred_lb = xcalloc(1+new_size, sizeof(double));

                tree->pred_ub = xcalloc(1+new_size, sizeof(double));

                tree->pred_stat = xcalloc(1+new_size, sizeof(char));

             }

             /* save row attributes */

             for (i = 1; i <= m; i++)

             {  GLPROW *row = mip->row[i];

                tree->pred_type[i] = (char)row->type;

                tree->pred_lb[i] = row->lb;

                tree->pred_ub[i] = row->ub;

                tree->pred_stat[i] = (char)row->stat;

             }

             /* save column attributes */

             for (j = 1; j <= n; j++)

             {  GLPCOL *col = mip->col[j];

                tree->pred_type[mip->m+j] = (char)col->type;

                tree->pred_lb[mip->m+j] = col->lb;

                tree->pred_ub[mip->m+j] = col->ub;

                tree->pred_stat[mip->m+j] = (char)col->stat;

             }

          }

          /* change bounds of rows and columns */

          {  IOSBND *b;

             for (b = node->b_ptr; b != NULL; b = b->next)

             {  if (b->k <= m)

                   glp_set_row_bnds(mip, b->k, b->type, b->lb, b->ub);

                else

                   glp_set_col_bnds(mip, b->k-m, b->type, b->lb, b->ub);

             }

          }

          /* change statuses of rows and columns */

          {  IOSTAT *s;

             for (s = node->s_ptr; s != NULL; s = s->next)

             {  if (s->k <= m)

                   glp_set_row_stat(mip, s->k, s->stat);

                else

                   glp_set_col_stat(mip, s->k-m, s->stat);

             }

          }

          /* add new rows */

          if (node->r_ptr != NULL)

          {  IOSROW *r;

             IOSAIJ *a;

             int i, len, *ind;

             double *val;

             ind = xcalloc(1+n, sizeof(int));

             val = xcalloc(1+n, sizeof(double));

             for (r = node->r_ptr; r != NULL; r = r->next)

             {  i = glp_add_rows(mip, 1);

                glp_set_row_name(mip, i, r->name);

 #if 1 /* 20/IX-2008 */

                xassert(mip->row[i]->level == 0);

                mip->row[i]->level = node->level;

                mip->row[i]->origin = r->origin;

                mip->row[i]->klass = r->klass;

 #endif

                glp_set_row_bnds(mip, i, r->type, r->lb, r->ub);

                len = 0;

                for (a = r->ptr; a != NULL; a = a->next)

                   len++, ind[len] = a->j, val[len] = a->val;

                glp_set_mat_row(mip, i, len, ind, val);

                glp_set_rii(mip, i, r->rii);

                glp_set_row_stat(mip, i, r->stat);

             }

             xfree(ind);

             xfree(val);

          }

 #if 0

          /* add new edges to the conflict graph */

          /* add new cliques to the conflict graph */

          /* (not implemented yet) */

          xassert(node->own_nn == 0);

          xassert(node->own_nc == 0);

          xassert(node->e_ptr == NULL);

 #endif

       }

       /* the specified subproblem has been revived */

       node = tree->curr;

       /* delete its bound change list */

       while (node->b_ptr != NULL)

       {  IOSBND *b;

          b = node->b_ptr;

          node->b_ptr = b->next;

          dmp_free_atom(tree->pool, b, sizeof(IOSBND));

       }

       /* delete its status change list */

       while (node->s_ptr != NULL)

       {  IOSTAT *s;

          s = node->s_ptr;

          node->s_ptr = s->next;

          dmp_free_atom(tree->pool, s, sizeof(IOSTAT));

       }

 #if 1 /* 20/XI-2009 */

       /* delete its row addition list (additional rows may appear, for

          example, due to branching on GUB constraints */

       while (node->r_ptr != NULL)

       {  IOSROW *r;

          r = node->r_ptr;

          node->r_ptr = r->next;

          xassert(r->name == NULL);

          while (r->ptr != NULL)

          {  IOSAIJ *a;

             a = r->ptr;

             r->ptr = a->next;

             dmp_free_atom(tree->pool, a, sizeof(IOSAIJ));

          }

          dmp_free_atom(tree->pool, r, sizeof(IOSROW));

       }

 #endif

 done: return;

 }

 /***********************************************************************

 *  NAME

 *

 *  ios_freeze_node - freeze current subproblem

 *

 *  SYNOPSIS

 *

 *  #include "glpios.h"

 *  void ios_freeze_node(glp_tree *tree);

 *

 *  DESCRIPTION

 *

 *  The routine ios_freeze_node freezes the current subproblem. */

 void ios_freeze_node(glp_tree *tree)

 {     glp_prob *mip = tree->mip;

       int m = mip->m;

       int n = mip->n;

       IOSNPD *node;

       /* obtain pointer to the current subproblem */

       node = tree->curr;

       xassert(node != NULL);

       if (node->up == NULL)

       {  /* freeze the root subproblem */

          int k;

          xassert(node->p == 1);

          xassert(tree->root_m == 0);

          xassert(tree->root_type == NULL);

          xassert(tree->root_lb == NULL);

          xassert(tree->root_ub == NULL);

          xassert(tree->root_stat == NULL);

          tree->root_m = m;

          tree->root_type = xcalloc(1+m+n, sizeof(char));

          tree->root_lb = xcalloc(1+m+n, sizeof(double));

          tree->root_ub = xcalloc(1+m+n, sizeof(double));

          tree->root_stat = xcalloc(1+m+n, sizeof(char));

          for (k = 1; k <= m+n; k++)

          {  if (k <= m)

             {  GLPROW *row = mip->row[k];

                tree->root_type[k] = (char)row->type;

                tree->root_lb[k] = row->lb;

                tree->root_ub[k] = row->ub;

                tree->root_stat[k] = (char)row->stat;

             }

             else

             {  GLPCOL *col = mip->col[k-m];

                tree->root_type[k] = (char)col->type;

                tree->root_lb[k] = col->lb;

                tree->root_ub[k] = col->ub;

                tree->root_stat[k] = (char)col->stat;

             }

          }

       }

       else

       {  /* freeze non-root subproblem */

          int root_m = tree->root_m;

          int pred_m = tree->pred_m;

          int i, j, k;

          xassert(pred_m <= m);

          /* build change lists for rows and columns which exist in the

             parent subproblem */

          xassert(node->b_ptr == NULL);

          xassert(node->s_ptr == NULL);

          for (k = 1; k <= pred_m + n; k++)

          {  int pred_type, pred_stat, type, stat;

             double pred_lb, pred_ub, lb, ub;

             /* determine attributes in the parent subproblem */

             pred_type = tree->pred_type[k];

             pred_lb = tree->pred_lb[k];

             pred_ub = tree->pred_ub[k];

             pred_stat = tree->pred_stat[k];

             /* determine attributes in the current subproblem */

             if (k <= pred_m)

             {  GLPROW *row = mip->row[k];

                type = row->type;

                lb = row->lb;

                ub = row->ub;

                stat = row->stat;

             }

             else

             {  GLPCOL *col = mip->col[k - pred_m];

                type = col->type;

                lb = col->lb;

                ub = col->ub;

                stat = col->stat;

             }

             /* save type and bounds of a row/column, if changed */

             if (!(pred_type == type && pred_lb == lb && pred_ub == ub))

             {  IOSBND *b;

                b = dmp_get_atom(tree->pool, sizeof(IOSBND));

                b->k = k;

                b->type = (unsigned char)type;

                b->lb = lb;

                b->ub = ub;

                b->next = node->b_ptr;

                node->b_ptr = b;

             }

             /* save status of a row/column, if changed */

             if (pred_stat != stat)

             {  IOSTAT *s;

                s = dmp_get_atom(tree->pool, sizeof(IOSTAT));

                s->k = k;

                s->stat = (unsigned char)stat;

                s->next = node->s_ptr;

                node->s_ptr = s;

             }

          }

          /* save new rows added to the current subproblem */

          xassert(node->r_ptr == NULL);

          if (pred_m < m)

          {  int i, len, *ind;

             double *val;

             ind = xcalloc(1+n, sizeof(int));

             val = xcalloc(1+n, sizeof(double));

             for (i = m; i > pred_m; i--)

             {  GLPROW *row = mip->row[i];

                IOSROW *r;

                const char *name;

                r = dmp_get_atom(tree->pool, sizeof(IOSROW));

                name = glp_get_row_name(mip, i);

                if (name == NULL)

                   r->name = NULL;

                else

                {  r->name = dmp_get_atom(tree->pool, strlen(name)+1);

                   strcpy(r->name, name);

                }

 #if 1 /* 20/IX-2008 */

                r->origin = row->origin;

                r->klass = row->klass;

 #endif

                r->type = (unsigned char)row->type;

                r->lb = row->lb;

                r->ub = row->ub;

                r->ptr = NULL;

                len = glp_get_mat_row(mip, i, ind, val);

                for (k = 1; k <= len; k++)

                {  IOSAIJ *a;

                   a = dmp_get_atom(tree->pool, sizeof(IOSAIJ));

                   a->j = ind[k];

                   a->val = val[k];

                   a->next = r->ptr;

                   r->ptr = a;

                }

                r->rii = row->rii;

                r->stat = (unsigned char)row->stat;

                r->next = node->r_ptr;

                node->r_ptr = r;

             }

             xfree(ind);

             xfree(val);

          }

          /* remove all rows missing in the root subproblem */

          if (m != root_m)

          {  int nrs, *num;

             nrs = m - root_m;

             xassert(nrs > 0);

             num = xcalloc(1+nrs, sizeof(int));

             for (i = 1; i <= nrs; i++) num[i] = root_m + i;

             glp_del_rows(mip, nrs, num);

             xfree(num);

          }

          m = mip->m;

          /* and restore attributes of all rows and columns for the root

             subproblem */

          xassert(m == root_m);

          for (i = 1; i <= m; i++)

          {  glp_set_row_bnds(mip, i, tree->root_type[i],

                tree->root_lb[i], tree->root_ub[i]);

             glp_set_row_stat(mip, i, tree->root_stat[i]);

          }

          for (j = 1; j <= n; j++)

          {  glp_set_col_bnds(mip, j, tree->root_type[m+j],

                tree->root_lb[m+j], tree->root_ub[m+j]);

             glp_set_col_stat(mip, j, tree->root_stat[m+j]);

          }

 #if 1

          /* remove all edges and cliques missing in the conflict graph

             for the root subproblem */

          /* (not implemented yet) */

 #endif

       }

       /* the current subproblem has been frozen */

       tree->curr = NULL;

       return;

 }

 /***********************************************************************

 *  NAME

 *

 *  ios_clone_node - clone specified subproblem

 *

 *  SYNOPSIS

 *

 *  #include "glpios.h"

 *  void ios_clone_node(glp_tree *tree, int p, int nnn, int ref[]);

 *

 *  DESCRIPTION

 *

 *  The routine ios_clone_node clones the specified subproblem, whose

 *  reference number is p, creating its nnn exact copies. Note that the

 *  specified subproblem must be active and must be in the frozen state

 *  (i.e. it must not be the current subproblem).

 *

 *  Each clone, an exact copy of the specified subproblem, becomes a new

 *  active subproblem added to the end of the active list. After cloning

 *  the specified subproblem becomes inactive.

 *

 *  The reference numbers of clone subproblems are stored to locations

 *  ref[1], ..., ref[nnn]. */

 static int get_slot(glp_tree *tree)

 {     int p;

       /* if no free slots are available, increase the room */

       if (tree->avail == 0)

       {  int nslots = tree->nslots;

          IOSLOT *save = tree->slot;

          if (nslots == 0)

             tree->nslots = 20;

          else

          {  tree->nslots = nslots + nslots;

             xassert(tree->nslots > nslots);

          }

          tree->slot = xcalloc(1+tree->nslots, sizeof(IOSLOT));

          if (save != NULL)

          {  memcpy(&tree->slot[1], &save[1], nslots * sizeof(IOSLOT));

             xfree(save);

          }

          /* push more free slots into the stack */

          for (p = tree->nslots; p > nslots; p--)

          {  tree->slot[p].node = NULL;

             tree->slot[p].next = tree->avail;

             tree->avail = p;

          }

       }

       /* pull a free slot from the stack */

       p = tree->avail;

       tree->avail = tree->slot[p].next;

       xassert(tree->slot[p].node == NULL);

       tree->slot[p].next = 0;

       return p;

 }

 static IOSNPD *new_node(glp_tree *tree, IOSNPD *parent)

 {     IOSNPD *node;

       int p;

       /* pull a free slot for the new node */

       p = get_slot(tree);

       /* create descriptor of the new subproblem */

       node = dmp_get_atom(tree->pool, sizeof(IOSNPD));

       tree->slot[p].node = node;

       node->p = p;

       node->up = parent;

       node->level = (parent == NULL ? 0 : parent->level + 1);

       node->count = 0;

       node->b_ptr = NULL;

       node->s_ptr = NULL;

       node->r_ptr = NULL;

       node->solved = 0;

 #if 0

       node->own_nn = node->own_nc = 0;

       node->e_ptr = NULL;

 #endif

 #if 1 /* 04/X-2008 */

       node->lp_obj = (parent == NULL ? (tree->mip->dir == GLP_MIN ?

          -DBL_MAX : +DBL_MAX) : parent->lp_obj);

 #endif

       node->bound = (parent == NULL ? (tree->mip->dir == GLP_MIN ?

          -DBL_MAX : +DBL_MAX) : parent->bound);

       node->br_var = 0;

       node->br_val = 0.0;

       node->ii_cnt = 0;

       node->ii_sum = 0.0;

 #if 1 /* 30/XI-2009 */

       node->changed = 0;

 #endif

       if (tree->parm->cb_size == 0)

          node->data = NULL;

       else

       {  node->data = dmp_get_atom(tree->pool, tree->parm->cb_size);

          memset(node->data, 0, tree->parm->cb_size);

       }

       node->temp = NULL;

       node->prev = tree->tail;

       node->next = NULL;

       /* add the new subproblem to the end of the active list */

       if (tree->head == NULL)

          tree->head = node;

       else

          tree->tail->next = node;

       tree->tail = node;

       tree->a_cnt++;

       tree->n_cnt++;

       tree->t_cnt++;

       /* increase the number of child subproblems */

       if (parent == NULL)

          xassert(p == 1);

       else

          parent->count++;

       return node;

 }

 void ios_clone_node(glp_tree *tree, int p, int nnn, int ref[])

 {     IOSNPD *node;

       int k;

       /* obtain pointer to the subproblem to be cloned */

       xassert(1 <= p && p <= tree->nslots);

       node = tree->slot[p].node;

       xassert(node != NULL);

       /* the specified subproblem must be active */

       xassert(node->count == 0);

       /* and must be in the frozen state */

       xassert(tree->curr != node);

       /* remove the specified subproblem from the active list, because

          it becomes inactive */

       if (node->prev == NULL)

          tree->head = node->next;

       else

          node->prev->next = node->next;

       if (node->next == NULL)

          tree->tail = node->prev;

       else

          node->next->prev = node->prev;

       node->prev = node->next = NULL;

       tree->a_cnt--;

       /* create clone subproblems */

       xassert(nnn > 0);

       for (k = 1; k <= nnn; k++)

          ref[k] = new_node(tree, node)->p;

       return;

 }

 /***********************************************************************

 *  NAME

 *

 *  ios_delete_node - delete specified subproblem

 *

 *  SYNOPSIS

 *

 *  #include "glpios.h"

 *  void ios_delete_node(glp_tree *tree, int p);

 *

 *  DESCRIPTION

 *

 *  The routine ios_delete_node deletes the specified subproblem, whose

 *  reference number is p. The subproblem must be active and must be in

 *  the frozen state (i.e. it must not be the current subproblem).

 *

 *  Note that deletion is performed recursively, i.e. if a subproblem to

 *  be deleted is the only child of its parent, the parent subproblem is

 *  also deleted, etc. */

 void ios_delete_node(glp_tree *tree, int p)

 {     IOSNPD *node, *temp;

       /* obtain pointer to the subproblem to be deleted */

       xassert(1 <= p && p <= tree->nslots);

       node = tree->slot[p].node;

       xassert(node != NULL);

       /* the specified subproblem must be active */

       xassert(node->count == 0);

       /* and must be in the frozen state */

       xassert(tree->curr != node);

       /* remove the specified subproblem from the active list, because

          it is gone from the tree */

       if (node->prev == NULL)

          tree->head = node->next;

       else

          node->prev->next = node->next;

       if (node->next == NULL)

          tree->tail = node->prev;

       else

          node->next->prev = node->prev;

       node->prev = node->next = NULL;

       tree->a_cnt--;

 loop: /* recursive deletion starts here */

       /* delete the bound change list */

       {  IOSBND *b;

          while (node->b_ptr != NULL)

          {  b = node->b_ptr;

             node->b_ptr = b->next;

             dmp_free_atom(tree->pool, b, sizeof(IOSBND));

          }

       }

       /* delete the status change list */

       {  IOSTAT *s;

          while (node->s_ptr != NULL)

          {  s = node->s_ptr;

             node->s_ptr = s->next;

             dmp_free_atom(tree->pool, s, sizeof(IOSTAT));

          }

       }

       /* delete the row addition list */

       while (node->r_ptr != NULL)

       {  IOSROW *r;

          r = node->r_ptr;

          if (r->name != NULL)

             dmp_free_atom(tree->pool, r->name, strlen(r->name)+1);

          while (r->ptr != NULL)

          {  IOSAIJ *a;

             a = r->ptr;

             r->ptr = a->next;

             dmp_free_atom(tree->pool, a, sizeof(IOSAIJ));

          }

          node->r_ptr = r->next;

          dmp_free_atom(tree->pool, r, sizeof(IOSROW));

       }

 #if 0

       /* delete the edge addition list */

       /* delete the clique addition list */

       /* (not implemented yet) */

       xassert(node->own_nn == 0);

       xassert(node->own_nc == 0);

       xassert(node->e_ptr == NULL);

 #endif

       /* free application-specific data */

       if (tree->parm->cb_size == 0)

          xassert(node->data == NULL);

       else

          dmp_free_atom(tree->pool, node->data, tree->parm->cb_size);

       /* free the corresponding node slot */

       p = node->p;

       xassert(tree->slot[p].node == node);

       tree->slot[p].node = NULL;

       tree->slot[p].next = tree->avail;

       tree->avail = p;

       /* save pointer to the parent subproblem */

       temp = node->up;

       /* delete the subproblem descriptor */

       dmp_free_atom(tree->pool, node, sizeof(IOSNPD));

       tree->n_cnt--;

       /* take pointer to the parent subproblem */

       node = temp;

       if (node != NULL)

       {  /* the parent subproblem exists; decrease the number of its

             child subproblems */

          xassert(node->count > 0);

          node->count--;

          /* if now the parent subproblem has no childs, it also must be

             deleted */

          if (node->count == 0) goto loop;

       }

       return;

 }

 /***********************************************************************

 *  NAME

 *

 *  ios_delete_tree - delete branch-and-bound tree

 *

 *  SYNOPSIS

 *

 *  #include "glpios.h"

 *  void ios_delete_tree(glp_tree *tree);

 *

 *  DESCRIPTION

 *

 *  The routine ios_delete_tree deletes the branch-and-bound tree, which

 *  the parameter tree points to, and frees all the memory allocated to

 *  this program object.

 *

 *  On exit components of the problem object are restored to correspond

 *  to the original MIP passed to the routine ios_create_tree. */

 void ios_delete_tree(glp_tree *tree)

 {     glp_prob *mip = tree->mip;

       int i, j;

       int m = mip->m;

       int n = mip->n;

       xassert(mip->tree == tree);

       /* remove all additional rows */

       if (m != tree->orig_m)

       {  int nrs, *num;

          nrs = m - tree->orig_m;

          xassert(nrs > 0);

          num = xcalloc(1+nrs, sizeof(int));

          for (i = 1; i <= nrs; i++) num[i] = tree->orig_m + i;

          glp_del_rows(mip, nrs, num);

          xfree(num);

       }

       m = tree->orig_m;

       /* restore original attributes of rows and columns */

       xassert(m == tree->orig_m);

       xassert(n == tree->n);

       for (i = 1; i <= m; i++)

       {  glp_set_row_bnds(mip, i, tree->orig_type[i],

             tree->orig_lb[i], tree->orig_ub[i]);

          glp_set_row_stat(mip, i, tree->orig_stat[i]);

          mip->row[i]->prim = tree->orig_prim[i];

          mip->row[i]->dual = tree->orig_dual[i];

       }

       for (j = 1; j <= n; j++)

       {  glp_set_col_bnds(mip, j, tree->orig_type[m+j],

             tree->orig_lb[m+j], tree->orig_ub[m+j]);

          glp_set_col_stat(mip, j, tree->orig_stat[m+j]);

          mip->col[j]->prim = tree->orig_prim[m+j];

          mip->col[j]->dual = tree->orig_dual[m+j];

       }

       mip->pbs_stat = mip->dbs_stat = GLP_FEAS;

       mip->obj_val = tree->orig_obj;

       /* delete the branch-and-bound tree */

       xassert(tree->local != NULL);

       ios_delete_pool(tree, tree->local);

       dmp_delete_pool(tree->pool);

       xfree(tree->orig_type);

       xfree(tree->orig_lb);

       xfree(tree->orig_ub);

       xfree(tree->orig_stat);

       xfree(tree->orig_prim);

       xfree(tree->orig_dual);

       xfree(tree->slot);

       if (tree->root_type != NULL) xfree(tree->root_type);

       if (tree->root_lb != NULL) xfree(tree->root_lb);

       if (tree->root_ub != NULL) xfree(tree->root_ub);

       if (tree->root_stat != NULL) xfree(tree->root_stat);

       xfree(tree->non_int);

 #if 0

       xfree(tree->n_ref);

       xfree(tree->c_ref);

       xfree(tree->j_ref);

 #endif

       if (tree->pcost != NULL) ios_pcost_free(tree);

       xfree(tree->iwrk);

       xfree(tree->dwrk);

 #if 0

       scg_delete_graph(tree->g);

 #endif

       if (tree->pred_type != NULL) xfree(tree->pred_type);

       if (tree->pred_lb != NULL) xfree(tree->pred_lb);

       if (tree->pred_ub != NULL) xfree(tree->pred_ub);

       if (tree->pred_stat != NULL) xfree(tree->pred_stat);

 #if 0

       xassert(tree->cut_gen == NULL);

 #endif

       xassert(tree->mir_gen == NULL);

       xassert(tree->clq_gen == NULL);

       xfree(tree);

       mip->tree = NULL;

       return;

 }

 /***********************************************************************

 *  NAME

 *

 *  ios_eval_degrad - estimate obj. degrad. for down- and up-branches

 *

 *  SYNOPSIS

 *

 *  #include "glpios.h"

 *  void ios_eval_degrad(glp_tree *tree, int j, double *dn, double *up);

 *

 *  DESCRIPTION

 *

 *  Given optimal basis to LP relaxation of the current subproblem the

 *  routine ios_eval_degrad performs the dual ratio test to compute the

 *  objective values in the adjacent basis for down- and up-branches,

 *  which are stored in locations *dn and *up, assuming that x[j] is a

 *  variable chosen to branch upon. */

 void ios_eval_degrad(glp_tree *tree, int j, double *dn, double *up)

 {     glp_prob *mip = tree->mip;

       int m = mip->m, n = mip->n;

       int len, kase, k, t, stat;

       double alfa, beta, gamma, delta, dz;

       int *ind = tree->iwrk;

       double *val = tree->dwrk;

       /* current basis must be optimal */

       xassert(glp_get_status(mip) == GLP_OPT);

       /* basis factorization must exist */

       xassert(glp_bf_exists(mip));

       /* obtain (fractional) value of x[j] in optimal basic solution

          to LP relaxation of the current subproblem */

       xassert(1 <= j && j <= n);

       beta = mip->col[j]->prim;

       /* since the value of x[j] is fractional, it is basic; compute

          corresponding row of the simplex table */

       len = lpx_eval_tab_row(mip, m+j, ind, val);

       /* kase < 0 means down-branch; kase > 0 means up-branch */

       for (kase = -1; kase <= +1; kase += 2)

       {  /* for down-branch we introduce new upper bound floor(beta)

             for x[j]; similarly, for up-branch we introduce new lower

             bound ceil(beta) for x[j]; in the current basis this new

             upper/lower bound is violated, so in the adjacent basis

             x[j] will leave the basis and go to its new upper/lower

             bound; we need to know which non-basic variable x[k] should

             enter the basis to keep dual feasibility */

 #if 0 /* 23/XI-2009 */

          k = lpx_dual_ratio_test(mip, len, ind, val, kase, 1e-7);

 #else

          k = lpx_dual_ratio_test(mip, len, ind, val, kase, 1e-9);

 #endif

          /* if no variable has been chosen, current basis being primal

             infeasible due to the new upper/lower bound of x[j] is dual

             unbounded, therefore, LP relaxation to corresponding branch

             has no primal feasible solution */

          if (k == 0)

          {  if (mip->dir == GLP_MIN)

             {  if (kase < 0)

                   *dn = +DBL_MAX;

                else

                   *up = +DBL_MAX;

             }

             else if (mip->dir == GLP_MAX)

             {  if (kase < 0)

                   *dn = -DBL_MAX;

                else

                   *up = -DBL_MAX;

             }

             else

                xassert(mip != mip);

             continue;

          }

          xassert(1 <= k && k <= m+n);

          /* row of the simplex table corresponding to specified basic

             variable x[j] is the following:

                x[j] = ... + alfa * x[k] + ... ;

             we need to know influence coefficient, alfa, at non-basic

             variable x[k] chosen with the dual ratio test */

          for (t = 1; t <= len; t++)

             if (ind[t] == k) break;

          xassert(1 <= t && t <= len);

          alfa = val[t];

          /* determine status and reduced cost of variable x[k] */

          if (k <= m)

          {  stat = mip->row[k]->stat;

             gamma = mip->row[k]->dual;

          }

          else

          {  stat = mip->col[k-m]->stat;

             gamma = mip->col[k-m]->dual;

          }

          /* x[k] cannot be basic or fixed non-basic */

          xassert(stat == GLP_NL || stat == GLP_NU || stat == GLP_NF);

          /* if the current basis is dual degenerative, some reduced

             costs, which are close to zero, may have wrong sign due to

             round-off errors, so correct the sign of gamma */

          if (mip->dir == GLP_MIN)

          {  if (stat == GLP_NL && gamma < 0.0 ||

                 stat == GLP_NU && gamma > 0.0 ||

                 stat == GLP_NF) gamma = 0.0;

          }

          else if (mip->dir == GLP_MAX)

          {  if (stat == GLP_NL && gamma > 0.0 ||

                 stat == GLP_NU && gamma < 0.0 ||

                 stat == GLP_NF) gamma = 0.0;

          }

          else

             xassert(mip != mip);

          /* determine the change of x[j] in the adjacent basis:

             delta x[j] = new x[j] - old x[j] */

          delta = (kase < 0 ? floor(beta) : ceil(beta)) - beta;

          /* compute the change of x[k] in the adjacent basis:

             delta x[k] = new x[k] - old x[k] = delta x[j] / alfa */

          delta /= alfa;

          /* compute the change of the objective in the adjacent basis:

             delta z = new z - old z = gamma * delta x[k] */

          dz = gamma * delta;

          if (mip->dir == GLP_MIN)

             xassert(dz >= 0.0);

          else if (mip->dir == GLP_MAX)

             xassert(dz <= 0.0);

          else

             xassert(mip != mip);

          /* compute the new objective value in the adjacent basis:

             new z = old z + delta z */

          if (kase < 0)

             *dn = mip->obj_val + dz;

          else

             *up = mip->obj_val + dz;

       }

       /*xprintf("obj = %g; dn = %g; up = %g\n",

          mip->obj_val, *dn, *up);*/

       return;

 }

 /***********************************************************************

 *  NAME

 *

 *  ios_round_bound - improve local bound by rounding

 *

 *  SYNOPSIS

 *

 *  #include "glpios.h"

 *  double ios_round_bound(glp_tree *tree, double bound);

 *

 *  RETURNS

 *

 *  For the given local bound for any integer feasible solution to the

 *  current subproblem the routine ios_round_bound returns an improved

 *  local bound for the same integer feasible solution.

 *

 *  BACKGROUND

 *

 *  Let the current subproblem has the following objective function:

 *

 *     z =   sum  c[j] * x[j] + s >= b,                               (1)

 *         j in J

 *

 *  where J = {j: c[j] is non-zero and integer, x[j] is integer}, s is

 *  the sum of terms corresponding to fixed variables, b is an initial

 *  local bound (minimization).

 *

 *  From (1) it follows that:

 *

 *     d *  sum  (c[j] / d) * x[j] + s >= b,                          (2)

 *        j in J

 *

 *  or, equivalently,

 *

 *     sum  (c[j] / d) * x[j] >= (b - s) / d = h,                     (3)

 *   j in J

 *

 *  where d = gcd(c[j]). Since the left-hand side of (3) is integer,

 *  h = (b - s) / d can be rounded up to the nearest integer:

 *

 *     h' = ceil(h) = (b' - s) / d,                                   (4)

 *

 *  that gives an rounded, improved local bound:

 *

 *     b' = d * h' + s.                                               (5)

 *

 *  In case of maximization '>=' in (1) should be replaced by '<=' that

 *  leads to the following formula:

 *

 *     h' = floor(h) = (b' - s) / d,                                  (6)

 *

 *  which should used in the same way as (4).

 *

 *  NOTE: If b is a valid local bound for a child of the current

 *        subproblem, b' is also valid for that child subproblem. */

 double ios_round_bound(glp_tree *tree, double bound)

 {     glp_prob *mip = tree->mip;

       int n = mip->n;

       int d, j, nn, *c = tree->iwrk;

       double s, h;

       /* determine c[j] and compute s */

       nn = 0, s = mip->c0, d = 0;

       for (j = 1; j <= n; j++)

       {  GLPCOL *col = mip->col[j];

          if (col->coef == 0.0) continue;

          if (col->type == GLP_FX)

          {  /* fixed variable */

             s += col->coef * col->prim;

          }

          else

          {  /* non-fixed variable */

             if (col->kind != GLP_IV) goto skip;

             if (col->coef != floor(col->coef)) goto skip;

             if (fabs(col->coef) <= (double)INT_MAX)

                c[++nn] = (int)fabs(col->coef);

             else

                d = 1;

          }

       }

       /* compute d = gcd(c[1],...c[nn]) */

       if (d == 0)

       {  if (nn == 0) goto skip;

          d = gcdn(nn, c);

       }

       xassert(d > 0);

       /* compute new local bound */

       if (mip->dir == GLP_MIN)

       {  if (bound != +DBL_MAX)

          {  h = (bound - s) / (double)d;

             if (h >= floor(h) + 0.001)

             {  /* round up */

                h = ceil(h);

                /*xprintf("d = %d; old = %g; ", d, bound);*/

                bound = (double)d * h + s;

                /*xprintf("new = %g\n", bound);*/

             }

          }

       }

       else if (mip->dir == GLP_MAX)

       {  if (bound != -DBL_MAX)

          {  h = (bound - s) / (double)d;

             if (h <= ceil(h) - 0.001)

             {  /* round down */

                h = floor(h);

                bound = (double)d * h + s;

             }

          }

       }

       else

          xassert(mip != mip);

 skip: return bound;

 }

 /***********************************************************************

 *  NAME

 *

 *  ios_is_hopeful - check if subproblem is hopeful

 *

 *  SYNOPSIS

 *

 *  #include "glpios.h"

 *  int ios_is_hopeful(glp_tree *tree, double bound);

 *

 *  DESCRIPTION

 *

 *  Given the local bound of a subproblem the routine ios_is_hopeful

 *  checks if the subproblem can have an integer optimal solution which

 *  is better than the best one currently known.