glpios01.c

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

/* glpios01.c */

/***********************************************************************
*  This code is part of GLPK (GNU Linear Programming Kit).
*
*  Copyright (C) 2000,01,02,03,04,05,06,07,08,2009 Andrew Makhorin,
*  Department for Applied Informatics, Moscow Aviation Institute,
*  Moscow, Russia. All rights reserved. E-mail: <[e-mail]>.
*
*  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(int));
      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(int));
      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] = row->type;
         tree->orig_lb[i] = row->lb;
         tree->orig_ub[i] = row->ub;
         tree->orig_stat[i] = 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] = col->type;
         tree->orig_lb[m+j] = col->lb;
         tree->orig_ub[m+j] = col->ub;
         tree->orig_stat[m+j] = 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(int));
      memset(&tree->non_int[1], 0, n * sizeof(int));
      /* 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;
      /* 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));
      /* 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->br_var = 0;
      tree->br_sel = 0;
      tree->btrack = NULL;
      tree->terminate = 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(int));
               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(int));
            }
            /* save row attributes */
            for (i = 1; i <= m; i++)
            {  GLPROW *row = mip->row[i];
               tree->pred_type[i] = row->type;
               tree->pred_lb[i] = row->lb;
               tree->pred_ub[i] = row->ub;
               tree->pred_stat[i] = row->stat;
            }
            /* save column attributes */
            for (j = 1; j <= n; j++)
            {  GLPCOL *col = mip->col[j];
               tree->pred_type[mip->m+j] = col->type;
               tree->pred_lb[mip->m+j] = col->lb;
               tree->pred_ub[mip->m+j] = col->ub;
               tree->pred_stat[mip->m+j] = 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 1
         /* 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
      /* delete its row addition list (additional rows may appear, for
         example, due to branching on GUB constraints */
      /* (not implemented yet) */
      xassert(node->r_ptr == NULL);
#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(int));
         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(int));
         for (k = 1; k <= m+n; k++)
         {  if (k <= m)
            {  GLPROW *row = mip->row[k];
               tree->root_type[k] = row->type;
               tree->root_lb[k] = row->lb;
               tree->root_ub[k] = row->ub;
               tree->root_stat[k] = row->stat;
            }
            else
            {  GLPCOL *col = mip->col[k-m];
               tree->root_type[k] = col->type;
               tree->root_lb[k] = col->lb;
               tree->root_ub[k] = col->ub;
               tree->root_stat[k] = 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;