alpar@1: /* glpios01.c */
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  This code is part of GLPK (GNU Linear Programming Kit).
alpar@1: *
alpar@1: *  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@1: *  2009, 2010 Andrew Makhorin, Department for Applied Informatics,
alpar@1: *  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@1: *  E-mail: <mao@gnu.org>.
alpar@1: *
alpar@1: *  GLPK is free software: you can redistribute it and/or modify it
alpar@1: *  under the terms of the GNU General Public License as published by
alpar@1: *  the Free Software Foundation, either version 3 of the License, or
alpar@1: *  (at your option) any later version.
alpar@1: *
alpar@1: *  GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@1: *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@1: *  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@1: *  License for more details.
alpar@1: *
alpar@1: *  You should have received a copy of the GNU General Public License
alpar@1: *  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@1: ***********************************************************************/
alpar@1: 
alpar@1: #include "glpios.h"
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  ios_create_tree - create branch-and-bound tree
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "glpios.h"
alpar@1: *  glp_tree *ios_create_tree(glp_prob *mip, const glp_iocp *parm);
alpar@1: *
alpar@1: *  DESCRIPTION
alpar@1: *
alpar@1: *  The routine ios_create_tree creates the branch-and-bound tree.
alpar@1: *
alpar@1: *  Being created the tree consists of the only root subproblem whose
alpar@1: *  reference number is 1. Note that initially the root subproblem is in
alpar@1: *  frozen state and therefore needs to be revived.
alpar@1: *
alpar@1: *  RETURNS
alpar@1: *
alpar@1: *  The routine returns a pointer to the tree created. */
alpar@1: 
alpar@1: static IOSNPD *new_node(glp_tree *tree, IOSNPD *parent);
alpar@1: 
alpar@1: glp_tree *ios_create_tree(glp_prob *mip, const glp_iocp *parm)
alpar@1: {     int m = mip->m;
alpar@1:       int n = mip->n;
alpar@1:       glp_tree *tree;
alpar@1:       int i, j;
alpar@1:       xassert(mip->tree == NULL);
alpar@1:       mip->tree = tree = xmalloc(sizeof(glp_tree));
alpar@1:       tree->pool = dmp_create_pool();
alpar@1:       tree->n = n;
alpar@1:       /* save original problem components */
alpar@1:       tree->orig_m = m;
alpar@1:       tree->orig_type = xcalloc(1+m+n, sizeof(char));
alpar@1:       tree->orig_lb = xcalloc(1+m+n, sizeof(double));
alpar@1:       tree->orig_ub = xcalloc(1+m+n, sizeof(double));
alpar@1:       tree->orig_stat = xcalloc(1+m+n, sizeof(char));
alpar@1:       tree->orig_prim = xcalloc(1+m+n, sizeof(double));
alpar@1:       tree->orig_dual = xcalloc(1+m+n, sizeof(double));
alpar@1:       for (i = 1; i <= m; i++)
alpar@1:       {  GLPROW *row = mip->row[i];
alpar@1:          tree->orig_type[i] = (char)row->type;
alpar@1:          tree->orig_lb[i] = row->lb;
alpar@1:          tree->orig_ub[i] = row->ub;
alpar@1:          tree->orig_stat[i] = (char)row->stat;
alpar@1:          tree->orig_prim[i] = row->prim;
alpar@1:          tree->orig_dual[i] = row->dual;
alpar@1:       }
alpar@1:       for (j = 1; j <= n; j++)
alpar@1:       {  GLPCOL *col = mip->col[j];
alpar@1:          tree->orig_type[m+j] = (char)col->type;
alpar@1:          tree->orig_lb[m+j] = col->lb;
alpar@1:          tree->orig_ub[m+j] = col->ub;
alpar@1:          tree->orig_stat[m+j] = (char)col->stat;
alpar@1:          tree->orig_prim[m+j] = col->prim;
alpar@1:          tree->orig_dual[m+j] = col->dual;
alpar@1:       }
alpar@1:       tree->orig_obj = mip->obj_val;
alpar@1:       /* initialize the branch-and-bound tree */
alpar@1:       tree->nslots = 0;
alpar@1:       tree->avail = 0;
alpar@1:       tree->slot = NULL;
alpar@1:       tree->head = tree->tail = NULL;
alpar@1:       tree->a_cnt = tree->n_cnt = tree->t_cnt = 0;
alpar@1:       /* the root subproblem is not solved yet, so its final components
alpar@1:          are unknown so far */
alpar@1:       tree->root_m = 0;
alpar@1:       tree->root_type = NULL;
alpar@1:       tree->root_lb = tree->root_ub = NULL;
alpar@1:       tree->root_stat = NULL;
alpar@1:       /* the current subproblem does not exist yet */
alpar@1:       tree->curr = NULL;
alpar@1:       tree->mip = mip;
alpar@1:       /*tree->solved = 0;*/
alpar@1:       tree->non_int = xcalloc(1+n, sizeof(char));
alpar@1:       memset(&tree->non_int[1], 0, n);
alpar@1:       /* arrays to save parent subproblem components will be allocated
alpar@1:          later */
alpar@1:       tree->pred_m = tree->pred_max = 0;
alpar@1:       tree->pred_type = NULL;
alpar@1:       tree->pred_lb = tree->pred_ub = NULL;
alpar@1:       tree->pred_stat = NULL;
alpar@1:       /* cut generator */
alpar@1:       tree->local = ios_create_pool(tree);
alpar@1:       /*tree->first_attempt = 1;*/
alpar@1:       /*tree->max_added_cuts = 0;*/
alpar@1:       /*tree->min_eff = 0.0;*/
alpar@1:       /*tree->miss = 0;*/
alpar@1:       /*tree->just_selected = 0;*/
alpar@1:       tree->mir_gen = NULL;
alpar@1:       tree->clq_gen = NULL;
alpar@1:       /*tree->round = 0;*/
alpar@1: #if 0
alpar@1:       /* create the conflict graph */
alpar@1:       tree->n_ref = xcalloc(1+n, sizeof(int));
alpar@1:       memset(&tree->n_ref[1], 0, n * sizeof(int));
alpar@1:       tree->c_ref = xcalloc(1+n, sizeof(int));
alpar@1:       memset(&tree->c_ref[1], 0, n * sizeof(int));
alpar@1:       tree->g = scg_create_graph(0);
alpar@1:       tree->j_ref = xcalloc(1+tree->g->n_max, sizeof(int));
alpar@1: #endif
alpar@1:       /* pseudocost branching */
alpar@1:       tree->pcost = NULL;
alpar@1:       tree->iwrk = xcalloc(1+n, sizeof(int));
alpar@1:       tree->dwrk = xcalloc(1+n, sizeof(double));
alpar@1:       /* initialize control parameters */
alpar@1:       tree->parm = parm;
alpar@1:       tree->tm_beg = xtime();
alpar@1:       tree->tm_lag = xlset(0);
alpar@1:       tree->sol_cnt = 0;
alpar@1:       /* initialize advanced solver interface */
alpar@1:       tree->reason = 0;
alpar@1:       tree->reopt = 0;
alpar@1:       tree->reinv = 0;
alpar@1:       tree->br_var = 0;
alpar@1:       tree->br_sel = 0;
alpar@1:       tree->child = 0;
alpar@1:       tree->next_p = 0;
alpar@1:       /*tree->btrack = NULL;*/
alpar@1:       tree->stop = 0;
alpar@1:       /* create the root subproblem, which initially is identical to
alpar@1:          the original MIP */
alpar@1:       new_node(tree, NULL);
alpar@1:       return tree;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  ios_revive_node - revive specified subproblem
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "glpios.h"
alpar@1: *  void ios_revive_node(glp_tree *tree, int p);
alpar@1: *
alpar@1: *  DESCRIPTION
alpar@1: *
alpar@1: *  The routine ios_revive_node revives the specified subproblem, whose
alpar@1: *  reference number is p, and thereby makes it the current subproblem.
alpar@1: *  Note that the specified subproblem must be active. Besides, if the
alpar@1: *  current subproblem already exists, it must be frozen before reviving
alpar@1: *  another subproblem. */
alpar@1: 
alpar@1: void ios_revive_node(glp_tree *tree, int p)
alpar@1: {     glp_prob *mip = tree->mip;
alpar@1:       IOSNPD *node, *root;
alpar@1:       /* obtain pointer to the specified subproblem */
alpar@1:       xassert(1 <= p && p <= tree->nslots);
alpar@1:       node = tree->slot[p].node;
alpar@1:       xassert(node != NULL);
alpar@1:       /* the specified subproblem must be active */
alpar@1:       xassert(node->count == 0);
alpar@1:       /* the current subproblem must not exist */
alpar@1:       xassert(tree->curr == NULL);
alpar@1:       /* the specified subproblem becomes current */
alpar@1:       tree->curr = node;
alpar@1:       /*tree->solved = 0;*/
alpar@1:       /* obtain pointer to the root subproblem */
alpar@1:       root = tree->slot[1].node;
alpar@1:       xassert(root != NULL);
alpar@1:       /* at this point problem object components correspond to the root
alpar@1:          subproblem, so if the root subproblem should be revived, there
alpar@1:          is nothing more to do */
alpar@1:       if (node == root) goto done;
alpar@1:       xassert(mip->m == tree->root_m);
alpar@1:       /* build path from the root to the current node */
alpar@1:       node->temp = NULL;
alpar@1:       for (node = node; node != NULL; node = node->up)
alpar@1:       {  if (node->up == NULL)
alpar@1:             xassert(node == root);
alpar@1:          else
alpar@1:             node->up->temp = node;
alpar@1:       }
alpar@1:       /* go down from the root to the current node and make necessary
alpar@1:          changes to restore components of the current subproblem */
alpar@1:       for (node = root; node != NULL; node = node->temp)
alpar@1:       {  int m = mip->m;
alpar@1:          int n = mip->n;
alpar@1:          /* if the current node is reached, the problem object at this
alpar@1:             point corresponds to its parent, so save attributes of rows
alpar@1:             and columns for the parent subproblem */
alpar@1:          if (node->temp == NULL)
alpar@1:          {  int i, j;
alpar@1:             tree->pred_m = m;
alpar@1:             /* allocate/reallocate arrays, if necessary */
alpar@1:             if (tree->pred_max < m + n)
alpar@1:             {  int new_size = m + n + 100;
alpar@1:                if (tree->pred_type != NULL) xfree(tree->pred_type);
alpar@1:                if (tree->pred_lb != NULL) xfree(tree->pred_lb);
alpar@1:                if (tree->pred_ub != NULL) xfree(tree->pred_ub);
alpar@1:                if (tree->pred_stat != NULL) xfree(tree->pred_stat);
alpar@1:                tree->pred_max = new_size;
alpar@1:                tree->pred_type = xcalloc(1+new_size, sizeof(char));
alpar@1:                tree->pred_lb = xcalloc(1+new_size, sizeof(double));
alpar@1:                tree->pred_ub = xcalloc(1+new_size, sizeof(double));
alpar@1:                tree->pred_stat = xcalloc(1+new_size, sizeof(char));
alpar@1:             }
alpar@1:             /* save row attributes */
alpar@1:             for (i = 1; i <= m; i++)
alpar@1:             {  GLPROW *row = mip->row[i];
alpar@1:                tree->pred_type[i] = (char)row->type;
alpar@1:                tree->pred_lb[i] = row->lb;
alpar@1:                tree->pred_ub[i] = row->ub;
alpar@1:                tree->pred_stat[i] = (char)row->stat;
alpar@1:             }
alpar@1:             /* save column attributes */
alpar@1:             for (j = 1; j <= n; j++)
alpar@1:             {  GLPCOL *col = mip->col[j];
alpar@1:                tree->pred_type[mip->m+j] = (char)col->type;
alpar@1:                tree->pred_lb[mip->m+j] = col->lb;
alpar@1:                tree->pred_ub[mip->m+j] = col->ub;
alpar@1:                tree->pred_stat[mip->m+j] = (char)col->stat;
alpar@1:             }
alpar@1:          }
alpar@1:          /* change bounds of rows and columns */
alpar@1:          {  IOSBND *b;
alpar@1:             for (b = node->b_ptr; b != NULL; b = b->next)
alpar@1:             {  if (b->k <= m)
alpar@1:                   glp_set_row_bnds(mip, b->k, b->type, b->lb, b->ub);
alpar@1:                else
alpar@1:                   glp_set_col_bnds(mip, b->k-m, b->type, b->lb, b->ub);
alpar@1:             }
alpar@1:          }
alpar@1:          /* change statuses of rows and columns */
alpar@1:          {  IOSTAT *s;
alpar@1:             for (s = node->s_ptr; s != NULL; s = s->next)
alpar@1:             {  if (s->k <= m)
alpar@1:                   glp_set_row_stat(mip, s->k, s->stat);
alpar@1:                else
alpar@1:                   glp_set_col_stat(mip, s->k-m, s->stat);
alpar@1:             }
alpar@1:          }
alpar@1:          /* add new rows */
alpar@1:          if (node->r_ptr != NULL)
alpar@1:          {  IOSROW *r;
alpar@1:             IOSAIJ *a;
alpar@1:             int i, len, *ind;
alpar@1:             double *val;
alpar@1:             ind = xcalloc(1+n, sizeof(int));
alpar@1:             val = xcalloc(1+n, sizeof(double));
alpar@1:             for (r = node->r_ptr; r != NULL; r = r->next)
alpar@1:             {  i = glp_add_rows(mip, 1);
alpar@1:                glp_set_row_name(mip, i, r->name);
alpar@1: #if 1 /* 20/IX-2008 */
alpar@1:                xassert(mip->row[i]->level == 0);
alpar@1:                mip->row[i]->level = node->level;
alpar@1:                mip->row[i]->origin = r->origin;
alpar@1:                mip->row[i]->klass = r->klass;
alpar@1: #endif
alpar@1:                glp_set_row_bnds(mip, i, r->type, r->lb, r->ub);
alpar@1:                len = 0;
alpar@1:                for (a = r->ptr; a != NULL; a = a->next)
alpar@1:                   len++, ind[len] = a->j, val[len] = a->val;
alpar@1:                glp_set_mat_row(mip, i, len, ind, val);
alpar@1:                glp_set_rii(mip, i, r->rii);
alpar@1:                glp_set_row_stat(mip, i, r->stat);
alpar@1:             }
alpar@1:             xfree(ind);
alpar@1:             xfree(val);
alpar@1:          }
alpar@1: #if 0
alpar@1:          /* add new edges to the conflict graph */
alpar@1:          /* add new cliques to the conflict graph */
alpar@1:          /* (not implemented yet) */
alpar@1:          xassert(node->own_nn == 0);
alpar@1:          xassert(node->own_nc == 0);
alpar@1:          xassert(node->e_ptr == NULL);
alpar@1: #endif
alpar@1:       }
alpar@1:       /* the specified subproblem has been revived */
alpar@1:       node = tree->curr;
alpar@1:       /* delete its bound change list */
alpar@1:       while (node->b_ptr != NULL)
alpar@1:       {  IOSBND *b;
alpar@1:          b = node->b_ptr;
alpar@1:          node->b_ptr = b->next;
alpar@1:          dmp_free_atom(tree->pool, b, sizeof(IOSBND));
alpar@1:       }
alpar@1:       /* delete its status change list */
alpar@1:       while (node->s_ptr != NULL)
alpar@1:       {  IOSTAT *s;
alpar@1:          s = node->s_ptr;
alpar@1:          node->s_ptr = s->next;
alpar@1:          dmp_free_atom(tree->pool, s, sizeof(IOSTAT));
alpar@1:       }
alpar@1: #if 1 /* 20/XI-2009 */
alpar@1:       /* delete its row addition list (additional rows may appear, for
alpar@1:          example, due to branching on GUB constraints */
alpar@1:       while (node->r_ptr != NULL)
alpar@1:       {  IOSROW *r;
alpar@1:          r = node->r_ptr;
alpar@1:          node->r_ptr = r->next;
alpar@1:          xassert(r->name == NULL);
alpar@1:          while (r->ptr != NULL)
alpar@1:          {  IOSAIJ *a;
alpar@1:             a = r->ptr;
alpar@1:             r->ptr = a->next;
alpar@1:             dmp_free_atom(tree->pool, a, sizeof(IOSAIJ));
alpar@1:          }
alpar@1:          dmp_free_atom(tree->pool, r, sizeof(IOSROW));
alpar@1:       }
alpar@1: #endif
alpar@1: done: return;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  ios_freeze_node - freeze current subproblem
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "glpios.h"
alpar@1: *  void ios_freeze_node(glp_tree *tree);
alpar@1: *
alpar@1: *  DESCRIPTION
alpar@1: *
alpar@1: *  The routine ios_freeze_node freezes the current subproblem. */
alpar@1: 
alpar@1: void ios_freeze_node(glp_tree *tree)
alpar@1: {     glp_prob *mip = tree->mip;
alpar@1:       int m = mip->m;
alpar@1:       int n = mip->n;
alpar@1:       IOSNPD *node;
alpar@1:       /* obtain pointer to the current subproblem */
alpar@1:       node = tree->curr;
alpar@1:       xassert(node != NULL);
alpar@1:       if (node->up == NULL)
alpar@1:       {  /* freeze the root subproblem */
alpar@1:          int k;
alpar@1:          xassert(node->p == 1);
alpar@1:          xassert(tree->root_m == 0);
alpar@1:          xassert(tree->root_type == NULL);
alpar@1:          xassert(tree->root_lb == NULL);
alpar@1:          xassert(tree->root_ub == NULL);
alpar@1:          xassert(tree->root_stat == NULL);
alpar@1:          tree->root_m = m;
alpar@1:          tree->root_type = xcalloc(1+m+n, sizeof(char));
alpar@1:          tree->root_lb = xcalloc(1+m+n, sizeof(double));
alpar@1:          tree->root_ub = xcalloc(1+m+n, sizeof(double));
alpar@1:          tree->root_stat = xcalloc(1+m+n, sizeof(char));
alpar@1:          for (k = 1; k <= m+n; k++)
alpar@1:          {  if (k <= m)
alpar@1:             {  GLPROW *row = mip->row[k];
alpar@1:                tree->root_type[k] = (char)row->type;
alpar@1:                tree->root_lb[k] = row->lb;
alpar@1:                tree->root_ub[k] = row->ub;
alpar@1:                tree->root_stat[k] = (char)row->stat;
alpar@1:             }
alpar@1:             else
alpar@1:             {  GLPCOL *col = mip->col[k-m];
alpar@1:                tree->root_type[k] = (char)col->type;
alpar@1:                tree->root_lb[k] = col->lb;
alpar@1:                tree->root_ub[k] = col->ub;
alpar@1:                tree->root_stat[k] = (char)col->stat;
alpar@1:             }
alpar@1:          }
alpar@1:       }
alpar@1:       else
alpar@1:       {  /* freeze non-root subproblem */
alpar@1:          int root_m = tree->root_m;
alpar@1:          int pred_m = tree->pred_m;
alpar@1:          int i, j, k;
alpar@1:          xassert(pred_m <= m);
alpar@1:          /* build change lists for rows and columns which exist in the
alpar@1:             parent subproblem */
alpar@1:          xassert(node->b_ptr == NULL);
alpar@1:          xassert(node->s_ptr == NULL);
alpar@1:          for (k = 1; k <= pred_m + n; k++)
alpar@1:          {  int pred_type, pred_stat, type, stat;
alpar@1:             double pred_lb, pred_ub, lb, ub;
alpar@1:             /* determine attributes in the parent subproblem */
alpar@1:             pred_type = tree->pred_type[k];
alpar@1:             pred_lb = tree->pred_lb[k];
alpar@1:             pred_ub = tree->pred_ub[k];
alpar@1:             pred_stat = tree->pred_stat[k];
alpar@1:             /* determine attributes in the current subproblem */
alpar@1:             if (k <= pred_m)
alpar@1:             {  GLPROW *row = mip->row[k];
alpar@1:                type = row->type;
alpar@1:                lb = row->lb;
alpar@1:                ub = row->ub;
alpar@1:                stat = row->stat;
alpar@1:             }
alpar@1:             else
alpar@1:             {  GLPCOL *col = mip->col[k - pred_m];
alpar@1:                type = col->type;
alpar@1:                lb = col->lb;
alpar@1:                ub = col->ub;
alpar@1:                stat = col->stat;
alpar@1:             }
alpar@1:             /* save type and bounds of a row/column, if changed */
alpar@1:             if (!(pred_type == type && pred_lb == lb && pred_ub == ub))
alpar@1:             {  IOSBND *b;
alpar@1:                b = dmp_get_atom(tree->pool, sizeof(IOSBND));
alpar@1:                b->k = k;
alpar@1:                b->type = (unsigned char)type;
alpar@1:                b->lb = lb;
alpar@1:                b->ub = ub;
alpar@1:                b->next = node->b_ptr;
alpar@1:                node->b_ptr = b;
alpar@1:             }
alpar@1:             /* save status of a row/column, if changed */
alpar@1:             if (pred_stat != stat)
alpar@1:             {  IOSTAT *s;
alpar@1:                s = dmp_get_atom(tree->pool, sizeof(IOSTAT));
alpar@1:                s->k = k;
alpar@1:                s->stat = (unsigned char)stat;
alpar@1:                s->next = node->s_ptr;
alpar@1:                node->s_ptr = s;
alpar@1:             }
alpar@1:          }
alpar@1:          /* save new rows added to the current subproblem */
alpar@1:          xassert(node->r_ptr == NULL);
alpar@1:          if (pred_m < m)
alpar@1:          {  int i, len, *ind;
alpar@1:             double *val;
alpar@1:             ind = xcalloc(1+n, sizeof(int));
alpar@1:             val = xcalloc(1+n, sizeof(double));
alpar@1:             for (i = m; i > pred_m; i--)
alpar@1:             {  GLPROW *row = mip->row[i];
alpar@1:                IOSROW *r;
alpar@1:                const char *name;
alpar@1:                r = dmp_get_atom(tree->pool, sizeof(IOSROW));
alpar@1:                name = glp_get_row_name(mip, i);
alpar@1:                if (name == NULL)
alpar@1:                   r->name = NULL;
alpar@1:                else
alpar@1:                {  r->name = dmp_get_atom(tree->pool, strlen(name)+1);
alpar@1:                   strcpy(r->name, name);
alpar@1:                }
alpar@1: #if 1 /* 20/IX-2008 */
alpar@1:                r->origin = row->origin;
alpar@1:                r->klass = row->klass;
alpar@1: #endif
alpar@1:                r->type = (unsigned char)row->type;
alpar@1:                r->lb = row->lb;
alpar@1:                r->ub = row->ub;
alpar@1:                r->ptr = NULL;
alpar@1:                len = glp_get_mat_row(mip, i, ind, val);
alpar@1:                for (k = 1; k <= len; k++)
alpar@1:                {  IOSAIJ *a;
alpar@1:                   a = dmp_get_atom(tree->pool, sizeof(IOSAIJ));
alpar@1:                   a->j = ind[k];
alpar@1:                   a->val = val[k];
alpar@1:                   a->next = r->ptr;
alpar@1:                   r->ptr = a;
alpar@1:                }
alpar@1:                r->rii = row->rii;
alpar@1:                r->stat = (unsigned char)row->stat;
alpar@1:                r->next = node->r_ptr;
alpar@1:                node->r_ptr = r;
alpar@1:             }
alpar@1:             xfree(ind);
alpar@1:             xfree(val);
alpar@1:          }
alpar@1:          /* remove all rows missing in the root subproblem */
alpar@1:          if (m != root_m)
alpar@1:          {  int nrs, *num;
alpar@1:             nrs = m - root_m;
alpar@1:             xassert(nrs > 0);
alpar@1:             num = xcalloc(1+nrs, sizeof(int));
alpar@1:             for (i = 1; i <= nrs; i++) num[i] = root_m + i;
alpar@1:             glp_del_rows(mip, nrs, num);
alpar@1:             xfree(num);
alpar@1:          }
alpar@1:          m = mip->m;
alpar@1:          /* and restore attributes of all rows and columns for the root
alpar@1:             subproblem */
alpar@1:          xassert(m == root_m);
alpar@1:          for (i = 1; i <= m; i++)
alpar@1:          {  glp_set_row_bnds(mip, i, tree->root_type[i],
alpar@1:                tree->root_lb[i], tree->root_ub[i]);
alpar@1:             glp_set_row_stat(mip, i, tree->root_stat[i]);
alpar@1:          }
alpar@1:          for (j = 1; j <= n; j++)
alpar@1:          {  glp_set_col_bnds(mip, j, tree->root_type[m+j],
alpar@1:                tree->root_lb[m+j], tree->root_ub[m+j]);
alpar@1:             glp_set_col_stat(mip, j, tree->root_stat[m+j]);
alpar@1:          }
alpar@1: #if 1
alpar@1:          /* remove all edges and cliques missing in the conflict graph
alpar@1:             for the root subproblem */
alpar@1:          /* (not implemented yet) */
alpar@1: #endif
alpar@1:       }
alpar@1:       /* the current subproblem has been frozen */
alpar@1:       tree->curr = NULL;
alpar@1:       return;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  ios_clone_node - clone specified subproblem
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "glpios.h"
alpar@1: *  void ios_clone_node(glp_tree *tree, int p, int nnn, int ref[]);
alpar@1: *
alpar@1: *  DESCRIPTION
alpar@1: *
alpar@1: *  The routine ios_clone_node clones the specified subproblem, whose
alpar@1: *  reference number is p, creating its nnn exact copies. Note that the
alpar@1: *  specified subproblem must be active and must be in the frozen state
alpar@1: *  (i.e. it must not be the current subproblem).
alpar@1: *
alpar@1: *  Each clone, an exact copy of the specified subproblem, becomes a new
alpar@1: *  active subproblem added to the end of the active list. After cloning
alpar@1: *  the specified subproblem becomes inactive.
alpar@1: *
alpar@1: *  The reference numbers of clone subproblems are stored to locations
alpar@1: *  ref[1], ..., ref[nnn]. */
alpar@1: 
alpar@1: static int get_slot(glp_tree *tree)
alpar@1: {     int p;
alpar@1:       /* if no free slots are available, increase the room */
alpar@1:       if (tree->avail == 0)
alpar@1:       {  int nslots = tree->nslots;
alpar@1:          IOSLOT *save = tree->slot;
alpar@1:          if (nslots == 0)
alpar@1:             tree->nslots = 20;
alpar@1:          else
alpar@1:          {  tree->nslots = nslots + nslots;
alpar@1:             xassert(tree->nslots > nslots);
alpar@1:          }
alpar@1:          tree->slot = xcalloc(1+tree->nslots, sizeof(IOSLOT));
alpar@1:          if (save != NULL)
alpar@1:          {  memcpy(&tree->slot[1], &save[1], nslots * sizeof(IOSLOT));
alpar@1:             xfree(save);
alpar@1:          }
alpar@1:          /* push more free slots into the stack */
alpar@1:          for (p = tree->nslots; p > nslots; p--)
alpar@1:          {  tree->slot[p].node = NULL;
alpar@1:             tree->slot[p].next = tree->avail;
alpar@1:             tree->avail = p;
alpar@1:          }
alpar@1:       }
alpar@1:       /* pull a free slot from the stack */
alpar@1:       p = tree->avail;
alpar@1:       tree->avail = tree->slot[p].next;
alpar@1:       xassert(tree->slot[p].node == NULL);
alpar@1:       tree->slot[p].next = 0;
alpar@1:       return p;
alpar@1: }
alpar@1: 
alpar@1: static IOSNPD *new_node(glp_tree *tree, IOSNPD *parent)
alpar@1: {     IOSNPD *node;
alpar@1:       int p;
alpar@1:       /* pull a free slot for the new node */
alpar@1:       p = get_slot(tree);
alpar@1:       /* create descriptor of the new subproblem */
alpar@1:       node = dmp_get_atom(tree->pool, sizeof(IOSNPD));
alpar@1:       tree->slot[p].node = node;
alpar@1:       node->p = p;
alpar@1:       node->up = parent;
alpar@1:       node->level = (parent == NULL ? 0 : parent->level + 1);
alpar@1:       node->count = 0;
alpar@1:       node->b_ptr = NULL;
alpar@1:       node->s_ptr = NULL;
alpar@1:       node->r_ptr = NULL;
alpar@1:       node->solved = 0;
alpar@1: #if 0
alpar@1:       node->own_nn = node->own_nc = 0;
alpar@1:       node->e_ptr = NULL;
alpar@1: #endif
alpar@1: #if 1 /* 04/X-2008 */
alpar@1:       node->lp_obj = (parent == NULL ? (tree->mip->dir == GLP_MIN ?
alpar@1:          -DBL_MAX : +DBL_MAX) : parent->lp_obj);
alpar@1: #endif
alpar@1:       node->bound = (parent == NULL ? (tree->mip->dir == GLP_MIN ?
alpar@1:          -DBL_MAX : +DBL_MAX) : parent->bound);
alpar@1:       node->br_var = 0;
alpar@1:       node->br_val = 0.0;
alpar@1:       node->ii_cnt = 0;
alpar@1:       node->ii_sum = 0.0;
alpar@1: #if 1 /* 30/XI-2009 */
alpar@1:       node->changed = 0;
alpar@1: #endif
alpar@1:       if (tree->parm->cb_size == 0)
alpar@1:          node->data = NULL;
alpar@1:       else
alpar@1:       {  node->data = dmp_get_atom(tree->pool, tree->parm->cb_size);
alpar@1:          memset(node->data, 0, tree->parm->cb_size);
alpar@1:       }
alpar@1:       node->temp = NULL;
alpar@1:       node->prev = tree->tail;
alpar@1:       node->next = NULL;
alpar@1:       /* add the new subproblem to the end of the active list */
alpar@1:       if (tree->head == NULL)
alpar@1:          tree->head = node;
alpar@1:       else
alpar@1:          tree->tail->next = node;
alpar@1:       tree->tail = node;
alpar@1:       tree->a_cnt++;
alpar@1:       tree->n_cnt++;
alpar@1:       tree->t_cnt++;
alpar@1:       /* increase the number of child subproblems */
alpar@1:       if (parent == NULL)
alpar@1:          xassert(p == 1);
alpar@1:       else
alpar@1:          parent->count++;
alpar@1:       return node;
alpar@1: }
alpar@1: 
alpar@1: void ios_clone_node(glp_tree *tree, int p, int nnn, int ref[])
alpar@1: {     IOSNPD *node;
alpar@1:       int k;
alpar@1:       /* obtain pointer to the subproblem to be cloned */
alpar@1:       xassert(1 <= p && p <= tree->nslots);
alpar@1:       node = tree->slot[p].node;
alpar@1:       xassert(node != NULL);
alpar@1:       /* the specified subproblem must be active */
alpar@1:       xassert(node->count == 0);
alpar@1:       /* and must be in the frozen state */
alpar@1:       xassert(tree->curr != node);
alpar@1:       /* remove the specified subproblem from the active list, because
alpar@1:          it becomes inactive */
alpar@1:       if (node->prev == NULL)
alpar@1:          tree->head = node->next;
alpar@1:       else
alpar@1:          node->prev->next = node->next;
alpar@1:       if (node->next == NULL)
alpar@1:          tree->tail = node->prev;
alpar@1:       else
alpar@1:          node->next->prev = node->prev;
alpar@1:       node->prev = node->next = NULL;
alpar@1:       tree->a_cnt--;
alpar@1:       /* create clone subproblems */
alpar@1:       xassert(nnn > 0);
alpar@1:       for (k = 1; k <= nnn; k++)
alpar@1:          ref[k] = new_node(tree, node)->p;
alpar@1:       return;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  ios_delete_node - delete specified subproblem
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "glpios.h"
alpar@1: *  void ios_delete_node(glp_tree *tree, int p);
alpar@1: *
alpar@1: *  DESCRIPTION
alpar@1: *
alpar@1: *  The routine ios_delete_node deletes the specified subproblem, whose
alpar@1: *  reference number is p. The subproblem must be active and must be in
alpar@1: *  the frozen state (i.e. it must not be the current subproblem).
alpar@1: *
alpar@1: *  Note that deletion is performed recursively, i.e. if a subproblem to
alpar@1: *  be deleted is the only child of its parent, the parent subproblem is
alpar@1: *  also deleted, etc. */
alpar@1: 
alpar@1: void ios_delete_node(glp_tree *tree, int p)
alpar@1: {     IOSNPD *node, *temp;
alpar@1:       /* obtain pointer to the subproblem to be deleted */
alpar@1:       xassert(1 <= p && p <= tree->nslots);
alpar@1:       node = tree->slot[p].node;
alpar@1:       xassert(node != NULL);
alpar@1:       /* the specified subproblem must be active */
alpar@1:       xassert(node->count == 0);
alpar@1:       /* and must be in the frozen state */
alpar@1:       xassert(tree->curr != node);
alpar@1:       /* remove the specified subproblem from the active list, because
alpar@1:          it is gone from the tree */
alpar@1:       if (node->prev == NULL)
alpar@1:          tree->head = node->next;
alpar@1:       else
alpar@1:          node->prev->next = node->next;
alpar@1:       if (node->next == NULL)
alpar@1:          tree->tail = node->prev;
alpar@1:       else
alpar@1:          node->next->prev = node->prev;
alpar@1:       node->prev = node->next = NULL;
alpar@1:       tree->a_cnt--;
alpar@1: loop: /* recursive deletion starts here */
alpar@1:       /* delete the bound change list */
alpar@1:       {  IOSBND *b;
alpar@1:          while (node->b_ptr != NULL)
alpar@1:          {  b = node->b_ptr;
alpar@1:             node->b_ptr = b->next;
alpar@1:             dmp_free_atom(tree->pool, b, sizeof(IOSBND));
alpar@1:          }
alpar@1:       }
alpar@1:       /* delete the status change list */
alpar@1:       {  IOSTAT *s;
alpar@1:          while (node->s_ptr != NULL)
alpar@1:          {  s = node->s_ptr;
alpar@1:             node->s_ptr = s->next;
alpar@1:             dmp_free_atom(tree->pool, s, sizeof(IOSTAT));
alpar@1:          }
alpar@1:       }
alpar@1:       /* delete the row addition list */
alpar@1:       while (node->r_ptr != NULL)
alpar@1:       {  IOSROW *r;
alpar@1:          r = node->r_ptr;
alpar@1:          if (r->name != NULL)
alpar@1:             dmp_free_atom(tree->pool, r->name, strlen(r->name)+1);
alpar@1:          while (r->ptr != NULL)
alpar@1:          {  IOSAIJ *a;
alpar@1:             a = r->ptr;
alpar@1:             r->ptr = a->next;
alpar@1:             dmp_free_atom(tree->pool, a, sizeof(IOSAIJ));
alpar@1:          }
alpar@1:          node->r_ptr = r->next;
alpar@1:          dmp_free_atom(tree->pool, r, sizeof(IOSROW));
alpar@1:       }
alpar@1: #if 0
alpar@1:       /* delete the edge addition list */
alpar@1:       /* delete the clique addition list */
alpar@1:       /* (not implemented yet) */
alpar@1:       xassert(node->own_nn == 0);
alpar@1:       xassert(node->own_nc == 0);
alpar@1:       xassert(node->e_ptr == NULL);
alpar@1: #endif
alpar@1:       /* free application-specific data */
alpar@1:       if (tree->parm->cb_size == 0)
alpar@1:          xassert(node->data == NULL);
alpar@1:       else
alpar@1:          dmp_free_atom(tree->pool, node->data, tree->parm->cb_size);
alpar@1:       /* free the corresponding node slot */
alpar@1:       p = node->p;
alpar@1:       xassert(tree->slot[p].node == node);
alpar@1:       tree->slot[p].node = NULL;
alpar@1:       tree->slot[p].next = tree->avail;
alpar@1:       tree->avail = p;
alpar@1:       /* save pointer to the parent subproblem */
alpar@1:       temp = node->up;
alpar@1:       /* delete the subproblem descriptor */
alpar@1:       dmp_free_atom(tree->pool, node, sizeof(IOSNPD));
alpar@1:       tree->n_cnt--;
alpar@1:       /* take pointer to the parent subproblem */
alpar@1:       node = temp;
alpar@1:       if (node != NULL)
alpar@1:       {  /* the parent subproblem exists; decrease the number of its
alpar@1:             child subproblems */
alpar@1:          xassert(node->count > 0);
alpar@1:          node->count--;
alpar@1:          /* if now the parent subproblem has no childs, it also must be
alpar@1:             deleted */
alpar@1:          if (node->count == 0) goto loop;
alpar@1:       }
alpar@1:       return;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  ios_delete_tree - delete branch-and-bound tree
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "glpios.h"
alpar@1: *  void ios_delete_tree(glp_tree *tree);
alpar@1: *
alpar@1: *  DESCRIPTION
alpar@1: *
alpar@1: *  The routine ios_delete_tree deletes the branch-and-bound tree, which
alpar@1: *  the parameter tree points to, and frees all the memory allocated to
alpar@1: *  this program object.
alpar@1: *
alpar@1: *  On exit components of the problem object are restored to correspond
alpar@1: *  to the original MIP passed to the routine ios_create_tree. */
alpar@1: 
alpar@1: void ios_delete_tree(glp_tree *tree)
alpar@1: {     glp_prob *mip = tree->mip;
alpar@1:       int i, j;
alpar@1:       int m = mip->m;
alpar@1:       int n = mip->n;
alpar@1:       xassert(mip->tree == tree);
alpar@1:       /* remove all additional rows */
alpar@1:       if (m != tree->orig_m)
alpar@1:       {  int nrs, *num;
alpar@1:          nrs = m - tree->orig_m;
alpar@1:          xassert(nrs > 0);
alpar@1:          num = xcalloc(1+nrs, sizeof(int));
alpar@1:          for (i = 1; i <= nrs; i++) num[i] = tree->orig_m + i;
alpar@1:          glp_del_rows(mip, nrs, num);
alpar@1:          xfree(num);
alpar@1:       }
alpar@1:       m = tree->orig_m;
alpar@1:       /* restore original attributes of rows and columns */
alpar@1:       xassert(m == tree->orig_m);
alpar@1:       xassert(n == tree->n);
alpar@1:       for (i = 1; i <= m; i++)
alpar@1:       {  glp_set_row_bnds(mip, i, tree->orig_type[i],
alpar@1:             tree->orig_lb[i], tree->orig_ub[i]);
alpar@1:          glp_set_row_stat(mip, i, tree->orig_stat[i]);
alpar@1:          mip->row[i]->prim = tree->orig_prim[i];
alpar@1:          mip->row[i]->dual = tree->orig_dual[i];
alpar@1:       }
alpar@1:       for (j = 1; j <= n; j++)
alpar@1:       {  glp_set_col_bnds(mip, j, tree->orig_type[m+j],
alpar@1:             tree->orig_lb[m+j], tree->orig_ub[m+j]);
alpar@1:          glp_set_col_stat(mip, j, tree->orig_stat[m+j]);
alpar@1:          mip->col[j]->prim = tree->orig_prim[m+j];
alpar@1:          mip->col[j]->dual = tree->orig_dual[m+j];
alpar@1:       }
alpar@1:       mip->pbs_stat = mip->dbs_stat = GLP_FEAS;
alpar@1:       mip->obj_val = tree->orig_obj;
alpar@1:       /* delete the branch-and-bound tree */
alpar@1:       xassert(tree->local != NULL);
alpar@1:       ios_delete_pool(tree, tree->local);
alpar@1:       dmp_delete_pool(tree->pool);
alpar@1:       xfree(tree->orig_type);
alpar@1:       xfree(tree->orig_lb);
alpar@1:       xfree(tree->orig_ub);
alpar@1:       xfree(tree->orig_stat);
alpar@1:       xfree(tree->orig_prim);
alpar@1:       xfree(tree->orig_dual);
alpar@1:       xfree(tree->slot);
alpar@1:       if (tree->root_type != NULL) xfree(tree->root_type);
alpar@1:       if (tree->root_lb != NULL) xfree(tree->root_lb);
alpar@1:       if (tree->root_ub != NULL) xfree(tree->root_ub);
alpar@1:       if (tree->root_stat != NULL) xfree(tree->root_stat);
alpar@1:       xfree(tree->non_int);
alpar@1: #if 0
alpar@1:       xfree(tree->n_ref);
alpar@1:       xfree(tree->c_ref);
alpar@1:       xfree(tree->j_ref);
alpar@1: #endif
alpar@1:       if (tree->pcost != NULL) ios_pcost_free(tree);
alpar@1:       xfree(tree->iwrk);
alpar@1:       xfree(tree->dwrk);
alpar@1: #if 0
alpar@1:       scg_delete_graph(tree->g);
alpar@1: #endif
alpar@1:       if (tree->pred_type != NULL) xfree(tree->pred_type);
alpar@1:       if (tree->pred_lb != NULL) xfree(tree->pred_lb);
alpar@1:       if (tree->pred_ub != NULL) xfree(tree->pred_ub);
alpar@1:       if (tree->pred_stat != NULL) xfree(tree->pred_stat);
alpar@1: #if 0
alpar@1:       xassert(tree->cut_gen == NULL);
alpar@1: #endif
alpar@1:       xassert(tree->mir_gen == NULL);
alpar@1:       xassert(tree->clq_gen == NULL);
alpar@1:       xfree(tree);
alpar@1:       mip->tree = NULL;
alpar@1:       return;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  ios_eval_degrad - estimate obj. degrad. for down- and up-branches
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "glpios.h"
alpar@1: *  void ios_eval_degrad(glp_tree *tree, int j, double *dn, double *up);
alpar@1: *
alpar@1: *  DESCRIPTION
alpar@1: *
alpar@1: *  Given optimal basis to LP relaxation of the current subproblem the
alpar@1: *  routine ios_eval_degrad performs the dual ratio test to compute the
alpar@1: *  objective values in the adjacent basis for down- and up-branches,
alpar@1: *  which are stored in locations *dn and *up, assuming that x[j] is a
alpar@1: *  variable chosen to branch upon. */
alpar@1: 
alpar@1: void ios_eval_degrad(glp_tree *tree, int j, double *dn, double *up)
alpar@1: {     glp_prob *mip = tree->mip;
alpar@1:       int m = mip->m, n = mip->n;
alpar@1:       int len, kase, k, t, stat;
alpar@1:       double alfa, beta, gamma, delta, dz;
alpar@1:       int *ind = tree->iwrk;
alpar@1:       double *val = tree->dwrk;
alpar@1:       /* current basis must be optimal */
alpar@1:       xassert(glp_get_status(mip) == GLP_OPT);
alpar@1:       /* basis factorization must exist */
alpar@1:       xassert(glp_bf_exists(mip));
alpar@1:       /* obtain (fractional) value of x[j] in optimal basic solution
alpar@1:          to LP relaxation of the current subproblem */
alpar@1:       xassert(1 <= j && j <= n);
alpar@1:       beta = mip->col[j]->prim;
alpar@1:       /* since the value of x[j] is fractional, it is basic; compute
alpar@1:          corresponding row of the simplex table */
alpar@1:       len = lpx_eval_tab_row(mip, m+j, ind, val);
alpar@1:       /* kase < 0 means down-branch; kase > 0 means up-branch */
alpar@1:       for (kase = -1; kase <= +1; kase += 2)
alpar@1:       {  /* for down-branch we introduce new upper bound floor(beta)
alpar@1:             for x[j]; similarly, for up-branch we introduce new lower
alpar@1:             bound ceil(beta) for x[j]; in the current basis this new
alpar@1:             upper/lower bound is violated, so in the adjacent basis
alpar@1:             x[j] will leave the basis and go to its new upper/lower
alpar@1:             bound; we need to know which non-basic variable x[k] should
alpar@1:             enter the basis to keep dual feasibility */
alpar@1: #if 0 /* 23/XI-2009 */
alpar@1:          k = lpx_dual_ratio_test(mip, len, ind, val, kase, 1e-7);
alpar@1: #else
alpar@1:          k = lpx_dual_ratio_test(mip, len, ind, val, kase, 1e-9);
alpar@1: #endif
alpar@1:          /* if no variable has been chosen, current basis being primal
alpar@1:             infeasible due to the new upper/lower bound of x[j] is dual
alpar@1:             unbounded, therefore, LP relaxation to corresponding branch
alpar@1:             has no primal feasible solution */
alpar@1:          if (k == 0)
alpar@1:          {  if (mip->dir == GLP_MIN)
alpar@1:             {  if (kase < 0)
alpar@1:                   *dn = +DBL_MAX;
alpar@1:                else
alpar@1:                   *up = +DBL_MAX;
alpar@1:             }
alpar@1:             else if (mip->dir == GLP_MAX)
alpar@1:             {  if (kase < 0)
alpar@1:                   *dn = -DBL_MAX;
alpar@1:                else
alpar@1:                   *up = -DBL_MAX;
alpar@1:             }
alpar@1:             else
alpar@1:                xassert(mip != mip);
alpar@1:             continue;
alpar@1:          }
alpar@1:          xassert(1 <= k && k <= m+n);
alpar@1:          /* row of the simplex table corresponding to specified basic
alpar@1:             variable x[j] is the following:
alpar@1:                x[j] = ... + alfa * x[k] + ... ;
alpar@1:             we need to know influence coefficient, alfa, at non-basic
alpar@1:             variable x[k] chosen with the dual ratio test */
alpar@1:          for (t = 1; t <= len; t++)
alpar@1:             if (ind[t] == k) break;
alpar@1:          xassert(1 <= t && t <= len);
alpar@1:          alfa = val[t];
alpar@1:          /* determine status and reduced cost of variable x[k] */
alpar@1:          if (k <= m)
alpar@1:          {  stat = mip->row[k]->stat;
alpar@1:             gamma = mip->row[k]->dual;
alpar@1:          }
alpar@1:          else
alpar@1:          {  stat = mip->col[k-m]->stat;
alpar@1:             gamma = mip->col[k-m]->dual;
alpar@1:          }
alpar@1:          /* x[k] cannot be basic or fixed non-basic */
alpar@1:          xassert(stat == GLP_NL || stat == GLP_NU || stat == GLP_NF);
alpar@1:          /* if the current basis is dual degenerative, some reduced
alpar@1:             costs, which are close to zero, may have wrong sign due to
alpar@1:             round-off errors, so correct the sign of gamma */
alpar@1:          if (mip->dir == GLP_MIN)
alpar@1:          {  if (stat == GLP_NL && gamma < 0.0 ||
alpar@1:                 stat == GLP_NU && gamma > 0.0 ||
alpar@1:                 stat == GLP_NF) gamma = 0.0;
alpar@1:          }
alpar@1:          else if (mip->dir == GLP_MAX)
alpar@1:          {  if (stat == GLP_NL && gamma > 0.0 ||
alpar@1:                 stat == GLP_NU && gamma < 0.0 ||
alpar@1:                 stat == GLP_NF) gamma = 0.0;
alpar@1:          }
alpar@1:          else
alpar@1:             xassert(mip != mip);
alpar@1:          /* determine the change of x[j] in the adjacent basis:
alpar@1:             delta x[j] = new x[j] - old x[j] */
alpar@1:          delta = (kase < 0 ? floor(beta) : ceil(beta)) - beta;
alpar@1:          /* compute the change of x[k] in the adjacent basis:
alpar@1:             delta x[k] = new x[k] - old x[k] = delta x[j] / alfa */
alpar@1:          delta /= alfa;
alpar@1:          /* compute the change of the objective in the adjacent basis:
alpar@1:             delta z = new z - old z = gamma * delta x[k] */
alpar@1:          dz = gamma * delta;
alpar@1:          if (mip->dir == GLP_MIN)
alpar@1:             xassert(dz >= 0.0);
alpar@1:          else if (mip->dir == GLP_MAX)
alpar@1:             xassert(dz <= 0.0);
alpar@1:          else
alpar@1:             xassert(mip != mip);
alpar@1:          /* compute the new objective value in the adjacent basis:
alpar@1:             new z = old z + delta z */
alpar@1:          if (kase < 0)
alpar@1:             *dn = mip->obj_val + dz;
alpar@1:          else
alpar@1:             *up = mip->obj_val + dz;
alpar@1:       }
alpar@1:       /*xprintf("obj = %g; dn = %g; up = %g\n",
alpar@1:          mip->obj_val, *dn, *up);*/
alpar@1:       return;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  ios_round_bound - improve local bound by rounding
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "glpios.h"
alpar@1: *  double ios_round_bound(glp_tree *tree, double bound);
alpar@1: *
alpar@1: *  RETURNS
alpar@1: *
alpar@1: *  For the given local bound for any integer feasible solution to the
alpar@1: *  current subproblem the routine ios_round_bound returns an improved
alpar@1: *  local bound for the same integer feasible solution.
alpar@1: *
alpar@1: *  BACKGROUND
alpar@1: *
alpar@1: *  Let the current subproblem has the following objective function:
alpar@1: *
alpar@1: *     z =   sum  c[j] * x[j] + s >= b,                               (1)
alpar@1: *         j in J
alpar@1: *
alpar@1: *  where J = {j: c[j] is non-zero and integer, x[j] is integer}, s is
alpar@1: *  the sum of terms corresponding to fixed variables, b is an initial
alpar@1: *  local bound (minimization).
alpar@1: *
alpar@1: *  From (1) it follows that:
alpar@1: *
alpar@1: *     d *  sum  (c[j] / d) * x[j] + s >= b,                          (2)
alpar@1: *        j in J
alpar@1: *
alpar@1: *  or, equivalently,
alpar@1: *
alpar@1: *     sum  (c[j] / d) * x[j] >= (b - s) / d = h,                     (3)
alpar@1: *   j in J
alpar@1: *
alpar@1: *  where d = gcd(c[j]). Since the left-hand side of (3) is integer,
alpar@1: *  h = (b - s) / d can be rounded up to the nearest integer:
alpar@1: *
alpar@1: *     h' = ceil(h) = (b' - s) / d,                                   (4)
alpar@1: *
alpar@1: *  that gives an rounded, improved local bound:
alpar@1: *
alpar@1: *     b' = d * h' + s.                                               (5)
alpar@1: *
alpar@1: *  In case of maximization '>=' in (1) should be replaced by '<=' that
alpar@1: *  leads to the following formula:
alpar@1: *
alpar@1: *     h' = floor(h) = (b' - s) / d,                                  (6)
alpar@1: *
alpar@1: *  which should used in the same way as (4).
alpar@1: *
alpar@1: *  NOTE: If b is a valid local bound for a child of the current
alpar@1: *        subproblem, b' is also valid for that child subproblem. */
alpar@1: 
alpar@1: double ios_round_bound(glp_tree *tree, double bound)
alpar@1: {     glp_prob *mip = tree->mip;
alpar@1:       int n = mip->n;
alpar@1:       int d, j, nn, *c = tree->iwrk;
alpar@1:       double s, h;
alpar@1:       /* determine c[j] and compute s */
alpar@1:       nn = 0, s = mip->c0, d = 0;
alpar@1:       for (j = 1; j <= n; j++)
alpar@1:       {  GLPCOL *col = mip->col[j];
alpar@1:          if (col->coef == 0.0) continue;
alpar@1:          if (col->type == GLP_FX)
alpar@1:          {  /* fixed variable */
alpar@1:             s += col->coef * col->prim;
alpar@1:          }
alpar@1:          else
alpar@1:          {  /* non-fixed variable */
alpar@1:             if (col->kind != GLP_IV) goto skip;
alpar@1:             if (col->coef != floor(col->coef)) goto skip;
alpar@1:             if (fabs(col->coef) <= (double)INT_MAX)
alpar@1:                c[++nn] = (int)fabs(col->coef);
alpar@1:             else
alpar@1:                d = 1;
alpar@1:          }
alpar@1:       }
alpar@1:       /* compute d = gcd(c[1],...c[nn]) */
alpar@1:       if (d == 0)
alpar@1:       {  if (nn == 0) goto skip;
alpar@1:          d = gcdn(nn, c);
alpar@1:       }
alpar@1:       xassert(d > 0);
alpar@1:       /* compute new local bound */
alpar@1:       if (mip->dir == GLP_MIN)
alpar@1:       {  if (bound != +DBL_MAX)
alpar@1:          {  h = (bound - s) / (double)d;
alpar@1:             if (h >= floor(h) + 0.001)
alpar@1:             {  /* round up */
alpar@1:                h = ceil(h);
alpar@1:                /*xprintf("d = %d; old = %g; ", d, bound);*/
alpar@1:                bound = (double)d * h + s;
alpar@1:                /*xprintf("new = %g\n", bound);*/
alpar@1:             }
alpar@1:          }
alpar@1:       }
alpar@1:       else if (mip->dir == GLP_MAX)
alpar@1:       {  if (bound != -DBL_MAX)
alpar@1:          {  h = (bound - s) / (double)d;
alpar@1:             if (h <= ceil(h) - 0.001)
alpar@1:             {  /* round down */
alpar@1:                h = floor(h);
alpar@1:                bound = (double)d * h + s;
alpar@1:             }
alpar@1:          }
alpar@1:       }
alpar@1:       else
alpar@1:          xassert(mip != mip);
alpar@1: skip: return bound;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  ios_is_hopeful - check if subproblem is hopeful
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "glpios.h"
alpar@1: *  int ios_is_hopeful(glp_tree *tree, double bound);
alpar@1: *
alpar@1: *  DESCRIPTION
alpar@1: *
alpar@1: *  Given the local bound of a subproblem the routine ios_is_hopeful
alpar@1: *  checks if the subproblem can have an integer optimal solution which
alpar@1: *  is better than the best one currently known.
alpar@1: *
alpar@1: *  RETURNS
alpar@1: *
alpar@1: *  If the subproblem can have a better integer optimal solution, the
alpar@1: *  routine returns non-zero; otherwise, if the corresponding branch can
alpar@1: *  be pruned, the routine returns zero. */
alpar@1: 
alpar@1: int ios_is_hopeful(glp_tree *tree, double bound)
alpar@1: {     glp_prob *mip = tree->mip;
alpar@1:       int ret = 1;
alpar@1:       double eps;
alpar@1:       if (mip->mip_stat == GLP_FEAS)
alpar@1:       {  eps = tree->parm->tol_obj * (1.0 + fabs(mip->mip_obj));
alpar@1:          switch (mip->dir)
alpar@1:          {  case GLP_MIN:
alpar@1:                if (bound >= mip->mip_obj - eps) ret = 0;
alpar@1:                break;
alpar@1:             case GLP_MAX:
alpar@1:                if (bound <= mip->mip_obj + eps) ret = 0;
alpar@1:                break;
alpar@1:             default:
alpar@1:                xassert(mip != mip);
alpar@1:          }
alpar@1:       }
alpar@1:       else
alpar@1:       {  switch (mip->dir)
alpar@1:          {  case GLP_MIN:
alpar@1:                if (bound == +DBL_MAX) ret = 0;
alpar@1:                break;
alpar@1:             case GLP_MAX:
alpar@1:                if (bound == -DBL_MAX) ret = 0;
alpar@1:                break;
alpar@1:             default:
alpar@1:                xassert(mip != mip);
alpar@1:          }
alpar@1:       }
alpar@1:       return ret;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  ios_best_node - find active node with best local bound
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "glpios.h"
alpar@1: *  int ios_best_node(glp_tree *tree);
alpar@1: *
alpar@1: *  DESCRIPTION
alpar@1: *
alpar@1: *  The routine ios_best_node finds an active node whose local bound is
alpar@1: *  best among other active nodes.
alpar@1: *
alpar@1: *  It is understood that the integer optimal solution of the original
alpar@1: *  mip problem cannot be better than the best bound, so the best bound
alpar@1: *  is an lower (minimization) or upper (maximization) global bound for
alpar@1: *  the original problem.
alpar@1: *
alpar@1: *  RETURNS
alpar@1: *
alpar@1: *  The routine ios_best_node returns the subproblem reference number
alpar@1: *  for the best node. However, if the tree is empty, it returns zero. */
alpar@1: 
alpar@1: int ios_best_node(glp_tree *tree)
alpar@1: {     IOSNPD *node, *best = NULL;
alpar@1:       switch (tree->mip->dir)
alpar@1:       {  case GLP_MIN:
alpar@1:             /* minimization */
alpar@1:             for (node = tree->head; node != NULL; node = node->next)
alpar@1:                if (best == NULL || best->bound > node->bound)
alpar@1:                   best = node;
alpar@1:             break;
alpar@1:          case GLP_MAX:
alpar@1:             /* maximization */
alpar@1:             for (node = tree->head; node != NULL; node = node->next)
alpar@1:                if (best == NULL || best->bound < node->bound)
alpar@1:                   best = node;
alpar@1:             break;
alpar@1:          default:
alpar@1:             xassert(tree != tree);
alpar@1:       }
alpar@1:       return best == NULL ? 0 : best->p;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  ios_relative_gap - compute relative mip gap
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "glpios.h"
alpar@1: *  double ios_relative_gap(glp_tree *tree);
alpar@1: *
alpar@1: *  DESCRIPTION
alpar@1: *
alpar@1: *  The routine ios_relative_gap computes the relative mip gap using the
alpar@1: *  formula:
alpar@1: *
alpar@1: *     gap = |best_mip - best_bnd| / (|best_mip| + DBL_EPSILON),
alpar@1: *
alpar@1: *  where best_mip is the best integer feasible solution found so far,
alpar@1: *  best_bnd is the best (global) bound. If no integer feasible solution
alpar@1: *  has been found yet, rel_gap is set to DBL_MAX.
alpar@1: *
alpar@1: *  RETURNS
alpar@1: *
alpar@1: *  The routine ios_relative_gap returns the relative mip gap. */
alpar@1: 
alpar@1: double ios_relative_gap(glp_tree *tree)
alpar@1: {     glp_prob *mip = tree->mip;
alpar@1:       int p;
alpar@1:       double best_mip, best_bnd, gap;
alpar@1:       if (mip->mip_stat == GLP_FEAS)
alpar@1:       {  best_mip = mip->mip_obj;
alpar@1:          p = ios_best_node(tree);
alpar@1:          if (p == 0)
alpar@1:          {  /* the tree is empty */
alpar@1:             gap = 0.0;
alpar@1:          }
alpar@1:          else
alpar@1:          {  best_bnd = tree->slot[p].node->bound;
alpar@1:             gap = fabs(best_mip - best_bnd) / (fabs(best_mip) +
alpar@1:                DBL_EPSILON);
alpar@1:          }
alpar@1:       }
alpar@1:       else
alpar@1:       {  /* no integer feasible solution has been found yet */
alpar@1:          gap = DBL_MAX;
alpar@1:       }
alpar@1:       return gap;
alpar@1: }
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  ios_solve_node - solve LP relaxation of current subproblem
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "glpios.h"
alpar@1: *  int ios_solve_node(glp_tree *tree);
alpar@1: *
alpar@1: *  DESCRIPTION
alpar@1: *
alpar@1: *  The routine ios_solve_node re-optimizes LP relaxation of the current
alpar@1: *  subproblem using the dual simplex method.
alpar@1: *
alpar@1: *  RETURNS
alpar@1: *
alpar@1: *  The routine returns the code which is reported by glp_simplex. */
alpar@1: 
alpar@1: int ios_solve_node(glp_tree *tree)
alpar@1: {     glp_prob *mip = tree->mip;
alpar@1:       glp_smcp parm;
alpar@1:       int ret;
alpar@1:       /* the current subproblem must exist */
alpar@1:       xassert(tree->curr != NULL);
alpar@1:       /* set some control parameters */
alpar@1:       glp_init_smcp(&parm);
alpar@1:       switch (tree->parm->msg_lev)
alpar@1:       {  case GLP_MSG_OFF:
alpar@1:             parm.msg_lev = GLP_MSG_OFF; break;
alpar@1:          case GLP_MSG_ERR:
alpar@1:             parm.msg_lev = GLP_MSG_ERR; break;
alpar@1:          case GLP_MSG_ON:
alpar@1:          case GLP_MSG_ALL:
alpar@1:             parm.msg_lev = GLP_MSG_ON; break;
alpar@1:          case GLP_MSG_DBG:
alpar@1:             parm.msg_lev = GLP_MSG_ALL; break;
alpar@1:          default:
alpar@1:             xassert(tree != tree);
alpar@1:       }
alpar@1:       parm.meth = GLP_DUALP;
alpar@1:       if (tree->parm->msg_lev < GLP_MSG_DBG)
alpar@1:          parm.out_dly = tree->parm->out_dly;
alpar@1:       else
alpar@1:          parm.out_dly = 0;
alpar@1:       /* if the incumbent objective value is already known, use it to
alpar@1:          prematurely terminate the dual simplex search */
alpar@1:       if (mip->mip_stat == GLP_FEAS)
alpar@1:       {  switch (tree->mip->dir)
alpar@1:          {  case GLP_MIN:
alpar@1:                parm.obj_ul = mip->mip_obj;
alpar@1:                break;
alpar@1:             case GLP_MAX:
alpar@1:                parm.obj_ll = mip->mip_obj;
alpar@1:                break;
alpar@1:             default:
alpar@1:                xassert(mip != mip);
alpar@1:          }
alpar@1:       }
alpar@1:       /* try to solve/re-optimize the LP relaxation */
alpar@1:       ret = glp_simplex(mip, &parm);
alpar@1:       tree->curr->solved++;
alpar@1: #if 0
alpar@1:       xprintf("ret = %d; status = %d; pbs = %d; dbs = %d; some = %d\n",
alpar@1:          ret, glp_get_status(mip), mip->pbs_stat, mip->dbs_stat,
alpar@1:          mip->some);
alpar@1:       lpx_print_sol(mip, "sol");
alpar@1: #endif
alpar@1:       return ret;
alpar@1: }
alpar@1: 
alpar@1: /**********************************************************************/
alpar@1: 
alpar@1: IOSPOOL *ios_create_pool(glp_tree *tree)
alpar@1: {     /* create cut pool */
alpar@1:       IOSPOOL *pool;
alpar@1: #if 0
alpar@1:       pool = dmp_get_atom(tree->pool, sizeof(IOSPOOL));
alpar@1: #else
alpar@1:       xassert(tree == tree);
alpar@1:       pool = xmalloc(sizeof(IOSPOOL));
alpar@1: #endif
alpar@1:       pool->size = 0;
alpar@1:       pool->head = pool->tail = NULL;
alpar@1:       pool->ord = 0, pool->curr = NULL;
alpar@1:       return pool;
alpar@1: }
alpar@1: 
alpar@1: int ios_add_row(glp_tree *tree, IOSPOOL *pool,
alpar@1:       const char *name, int klass, int flags, int len, const int ind[],
alpar@1:       const double val[], int type, double rhs)
alpar@1: {     /* add row (constraint) to the cut pool */
alpar@1:       IOSCUT *cut;
alpar@1:       IOSAIJ *aij;
alpar@1:       int k;
alpar@1:       xassert(pool != NULL);
alpar@1:       cut = dmp_get_atom(tree->pool, sizeof(IOSCUT));
alpar@1:       if (name == NULL || name[0] == '\0')
alpar@1:          cut->name = NULL;
alpar@1:       else
alpar@1:       {  for (k = 0; name[k] != '\0'; k++)
alpar@1:          {  if (k == 256)
alpar@1:                xerror("glp_ios_add_row: cut name too long\n");
alpar@1:             if (iscntrl((unsigned char)name[k]))
alpar@1:                xerror("glp_ios_add_row: cut name contains invalid chara"
alpar@1:                   "cter(s)\n");
alpar@1:          }
alpar@1:          cut->name = dmp_get_atom(tree->pool, strlen(name)+1);
alpar@1:          strcpy(cut->name, name);
alpar@1:       }
alpar@1:       if (!(0 <= klass && klass <= 255))
alpar@1:          xerror("glp_ios_add_row: klass = %d; invalid cut class\n",
alpar@1:             klass);
alpar@1:       cut->klass = (unsigned char)klass;
alpar@1:       if (flags != 0)
alpar@1:          xerror("glp_ios_add_row: flags = %d; invalid cut flags\n",
alpar@1:             flags);
alpar@1:       cut->ptr = NULL;
alpar@1:       if (!(0 <= len && len <= tree->n))
alpar@1:          xerror("glp_ios_add_row: len = %d; invalid cut length\n",
alpar@1:             len);
alpar@1:       for (k = 1; k <= len; k++)
alpar@1:       {  aij = dmp_get_atom(tree->pool, sizeof(IOSAIJ));
alpar@1:          if (!(1 <= ind[k] && ind[k] <= tree->n))
alpar@1:             xerror("glp_ios_add_row: ind[%d] = %d; column index out of "
alpar@1:                "range\n", k, ind[k]);
alpar@1:          aij->j = ind[k];
alpar@1:          aij->val = val[k];
alpar@1:          aij->next = cut->ptr;
alpar@1:          cut->ptr = aij;
alpar@1:       }
alpar@1:       if (!(type == GLP_LO || type == GLP_UP || type == GLP_FX))
alpar@1:          xerror("glp_ios_add_row: type = %d; invalid cut type\n",
alpar@1:             type);
alpar@1:       cut->type = (unsigned char)type;
alpar@1:       cut->rhs = rhs;
alpar@1:       cut->prev = pool->tail;
alpar@1:       cut->next = NULL;
alpar@1:       if (cut->prev == NULL)
alpar@1:          pool->head = cut;
alpar@1:       else
alpar@1:          cut->prev->next = cut;
alpar@1:       pool->tail = cut;
alpar@1:       pool->size++;
alpar@1:       return pool->size;
alpar@1: }
alpar@1: 
alpar@1: IOSCUT *ios_find_row(IOSPOOL *pool, int i)
alpar@1: {     /* find row (constraint) in the cut pool */
alpar@1:       /* (smart linear search) */
alpar@1:       xassert(pool != NULL);
alpar@1:       xassert(1 <= i && i <= pool->size);
alpar@1:       if (pool->ord == 0)
alpar@1:       {  xassert(pool->curr == NULL);
alpar@1:          pool->ord = 1;
alpar@1:          pool->curr = pool->head;
alpar@1:       }
alpar@1:       xassert(pool->curr != NULL);
alpar@1:       if (i < pool->ord)
alpar@1:       {  if (i < pool->ord - i)
alpar@1:          {  pool->ord = 1;
alpar@1:             pool->curr = pool->head;
alpar@1:             while (pool->ord != i)
alpar@1:             {  pool->ord++;
alpar@1:                xassert(pool->curr != NULL);
alpar@1:                pool->curr = pool->curr->next;
alpar@1:             }
alpar@1:          }
alpar@1:          else
alpar@1:          {  while (pool->ord != i)
alpar@1:             {  pool->ord--;
alpar@1:                xassert(pool->curr != NULL);
alpar@1:                pool->curr = pool->curr->prev;
alpar@1:             }
alpar@1:          }
alpar@1:       }
alpar@1:       else if (i > pool->ord)
alpar@1:       {  if (i - pool->ord < pool->size - i)
alpar@1:          {  while (pool->ord != i)
alpar@1:             {  pool->ord++;
alpar@1:                xassert(pool->curr != NULL);
alpar@1:                pool->curr = pool->curr->next;
alpar@1:             }
alpar@1:          }
alpar@1:          else
alpar@1:          {  pool->ord = pool->size;
alpar@1:             pool->curr = pool->tail;
alpar@1:             while (pool->ord != i)
alpar@1:             {  pool->ord--;
alpar@1:                xassert(pool->curr != NULL);
alpar@1:                pool->curr = pool->curr->prev;
alpar@1:             }
alpar@1:          }
alpar@1:       }
alpar@1:       xassert(pool->ord == i);
alpar@1:       xassert(pool->curr != NULL);
alpar@1:       return pool->curr;
alpar@1: }
alpar@1: 
alpar@1: void ios_del_row(glp_tree *tree, IOSPOOL *pool, int i)
alpar@1: {     /* remove row (constraint) from the cut pool */
alpar@1:       IOSCUT *cut;
alpar@1:       IOSAIJ *aij;
alpar@1:       xassert(pool != NULL);
alpar@1:       if (!(1 <= i && i <= pool->size))
alpar@1:          xerror("glp_ios_del_row: i = %d; cut number out of range\n",
alpar@1:             i);
alpar@1:       cut = ios_find_row(pool, i);
alpar@1:       xassert(pool->curr == cut);
alpar@1:       if (cut->next != NULL)
alpar@1:          pool->curr = cut->next;
alpar@1:       else if (cut->prev != NULL)
alpar@1:          pool->ord--, pool->curr = cut->prev;
alpar@1:       else
alpar@1:          pool->ord = 0, pool->curr = NULL;
alpar@1:       if (cut->name != NULL)
alpar@1:          dmp_free_atom(tree->pool, cut->name, strlen(cut->name)+1);
alpar@1:       if (cut->prev == NULL)
alpar@1:       {  xassert(pool->head == cut);
alpar@1:          pool->head = cut->next;
alpar@1:       }
alpar@1:       else
alpar@1:       {  xassert(cut->prev->next == cut);
alpar@1:          cut->prev->next = cut->next;
alpar@1:       }
alpar@1:       if (cut->next == NULL)
alpar@1:       {  xassert(pool->tail == cut);
alpar@1:          pool->tail = cut->prev;
alpar@1:       }
alpar@1:       else
alpar@1:       {  xassert(cut->next->prev == cut);
alpar@1:          cut->next->prev = cut->prev;
alpar@1:       }
alpar@1:       while (cut->ptr != NULL)
alpar@1:       {  aij = cut->ptr;
alpar@1:          cut->ptr = aij->next;
alpar@1:          dmp_free_atom(tree->pool, aij, sizeof(IOSAIJ));
alpar@1:       }
alpar@1:       dmp_free_atom(tree->pool, cut, sizeof(IOSCUT));
alpar@1:       pool->size--;
alpar@1:       return;
alpar@1: }
alpar@1: 
alpar@1: void ios_clear_pool(glp_tree *tree, IOSPOOL *pool)
alpar@1: {     /* remove all rows (constraints) from the cut pool */
alpar@1:       xassert(pool != NULL);
alpar@1:       while (pool->head != NULL)
alpar@1:       {  IOSCUT *cut = pool->head;
alpar@1:          pool->head = cut->next;
alpar@1:          if (cut->name != NULL)
alpar@1:             dmp_free_atom(tree->pool, cut->name, strlen(cut->name)+1);
alpar@1:          while (cut->ptr != NULL)
alpar@1:          {  IOSAIJ *aij = cut->ptr;
alpar@1:             cut->ptr = aij->next;
alpar@1:             dmp_free_atom(tree->pool, aij, sizeof(IOSAIJ));
alpar@1:          }
alpar@1:          dmp_free_atom(tree->pool, cut, sizeof(IOSCUT));
alpar@1:       }
alpar@1:       pool->size = 0;
alpar@1:       pool->head = pool->tail = NULL;
alpar@1:       pool->ord = 0, pool->curr = NULL;
alpar@1:       return;
alpar@1: }
alpar@1: 
alpar@1: void ios_delete_pool(glp_tree *tree, IOSPOOL *pool)
alpar@1: {     /* delete cut pool */
alpar@1:       xassert(pool != NULL);
alpar@1:       ios_clear_pool(tree, pool);
alpar@1:       xfree(pool);
alpar@1:       return;
alpar@1: }
alpar@1: 
alpar@1: /**********************************************************************/
alpar@1: 
alpar@1: #if 0
alpar@1: static int refer_to_node(glp_tree *tree, int j)
alpar@1: {     /* determine node number corresponding to binary variable x[j] or
alpar@1:          its complement */
alpar@1:       glp_prob *mip = tree->mip;
alpar@1:       int n = mip->n;
alpar@1:       int *ref;
alpar@1:       if (j > 0)
alpar@1:          ref = tree->n_ref;
alpar@1:       else
alpar@1:          ref = tree->c_ref, j = - j;
alpar@1:       xassert(1 <= j && j <= n);
alpar@1:       if (ref[j] == 0)
alpar@1:       {  /* new node is needed */
alpar@1:          SCG *g = tree->g;
alpar@1:          int n_max = g->n_max;
alpar@1:          ref[j] = scg_add_nodes(g, 1);
alpar@1:          if (g->n_max > n_max)
alpar@1:          {  int *save = tree->j_ref;
alpar@1:             tree->j_ref = xcalloc(1+g->n_max, sizeof(int));
alpar@1:             memcpy(&tree->j_ref[1], &save[1], g->n * sizeof(int));
alpar@1:             xfree(save);
alpar@1:          }
alpar@1:          xassert(ref[j] == g->n);
alpar@1:          tree->j_ref[ref[j]] = j;
alpar@1:          xassert(tree->curr != NULL);
alpar@1:          if (tree->curr->level > 0) tree->curr->own_nn++;
alpar@1:       }
alpar@1:       return ref[j];
alpar@1: }
alpar@1: #endif
alpar@1: 
alpar@1: #if 0
alpar@1: void ios_add_edge(glp_tree *tree, int j1, int j2)
alpar@1: {     /* add new edge to the conflict graph */
alpar@1:       glp_prob *mip = tree->mip;
alpar@1:       int n = mip->n;
alpar@1:       SCGRIB *e;
alpar@1:       int first, i1, i2;
alpar@1:       xassert(-n <= j1 && j1 <= +n && j1 != 0);
alpar@1:       xassert(-n <= j2 && j2 <= +n && j2 != 0);
alpar@1:       xassert(j1 != j2);
alpar@1:       /* determine number of the first node, which was added for the
alpar@1:          current subproblem */
alpar@1:       xassert(tree->curr != NULL);
alpar@1:       first = tree->g->n - tree->curr->own_nn + 1;
alpar@1:       /* determine node numbers for both endpoints */
alpar@1:       i1 = refer_to_node(tree, j1);
alpar@1:       i2 = refer_to_node(tree, j2);
alpar@1:       /* add edge (i1,i2) to the conflict graph */
alpar@1:       e = scg_add_edge(tree->g, i1, i2);
alpar@1:       /* if the current subproblem is not the root and both endpoints
alpar@1:          were created on some previous levels, save the edge */
alpar@1:       if (tree->curr->level > 0 && i1 < first && i2 < first)
alpar@1:       {  IOSRIB *rib;
alpar@1:          rib = dmp_get_atom(tree->pool, sizeof(IOSRIB));
alpar@1:          rib->j1 = j1;
alpar@1:          rib->j2 = j2;
alpar@1:          rib->e = e;
alpar@1:          rib->next = tree->curr->e_ptr;
alpar@1:          tree->curr->e_ptr = rib;
alpar@1:       }
alpar@1:       return;
alpar@1: }
alpar@1: #endif
alpar@1: 
alpar@1: /* eof */