glpios01.c

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

               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 = 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 = 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 = 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 = 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->own_nn = node->own_nc = 0;
      node->e_ptr = NULL;
#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 (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 1
      /* 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);