1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/src/glpios12.c	Sun Nov 06 20:59:10 2011 +0100
     1.3 @@ -0,0 +1,176 @@
     1.4 +/* glpios12.c (node selection heuristics) */
     1.5 +
     1.6 +/***********************************************************************
     1.7 +*  This code is part of GLPK (GNU Linear Programming Kit).
     1.8 +*
     1.9 +*  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
    1.10 +*  2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
    1.11 +*  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
    1.12 +*  E-mail: <mao@gnu.org>.
    1.13 +*
    1.14 +*  GLPK is free software: you can redistribute it and/or modify it
    1.15 +*  under the terms of the GNU General Public License as published by
    1.16 +*  the Free Software Foundation, either version 3 of the License, or
    1.17 +*  (at your option) any later version.
    1.18 +*
    1.19 +*  GLPK is distributed in the hope that it will be useful, but WITHOUT
    1.20 +*  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    1.21 +*  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
    1.22 +*  License for more details.
    1.23 +*
    1.24 +*  You should have received a copy of the GNU General Public License
    1.25 +*  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
    1.26 +***********************************************************************/
    1.27 +
    1.28 +#include "glpios.h"
    1.29 +
    1.30 +/***********************************************************************
    1.31 +*  NAME
    1.32 +*
    1.33 +*  ios_choose_node - select subproblem to continue the search
    1.34 +*
    1.35 +*  SYNOPSIS
    1.36 +*
    1.37 +*  #include "glpios.h"
    1.38 +*  int ios_choose_node(glp_tree *T);
    1.39 +*
    1.40 +*  DESCRIPTION
    1.41 +*
    1.42 +*  The routine ios_choose_node selects a subproblem from the active
    1.43 +*  list to continue the search. The choice depends on the backtracking
    1.44 +*  technique option.
    1.45 +*
    1.46 +*  RETURNS
    1.47 +*
    1.48 +*  The routine ios_choose_node return the reference number of the
    1.49 +*  subproblem selected. */
    1.50 +
    1.51 +static int most_feas(glp_tree *T);
    1.52 +static int best_proj(glp_tree *T);
    1.53 +static int best_node(glp_tree *T);
    1.54 +
    1.55 +int ios_choose_node(glp_tree *T)
    1.56 +{     int p;
    1.57 +      if (T->parm->bt_tech == GLP_BT_DFS)
    1.58 +      {  /* depth first search */
    1.59 +         xassert(T->tail != NULL);
    1.60 +         p = T->tail->p;
    1.61 +      }
    1.62 +      else if (T->parm->bt_tech == GLP_BT_BFS)
    1.63 +      {  /* breadth first search */
    1.64 +         xassert(T->head != NULL);
    1.65 +         p = T->head->p;
    1.66 +      }
    1.67 +      else if (T->parm->bt_tech == GLP_BT_BLB)
    1.68 +      {  /* select node with best local bound */
    1.69 +         p = best_node(T);
    1.70 +      }
    1.71 +      else if (T->parm->bt_tech == GLP_BT_BPH)
    1.72 +      {  if (T->mip->mip_stat == GLP_UNDEF)
    1.73 +         {  /* "most integer feasible" subproblem */
    1.74 +            p = most_feas(T);
    1.75 +         }
    1.76 +         else
    1.77 +         {  /* best projection heuristic */
    1.78 +            p = best_proj(T);
    1.79 +         }
    1.80 +      }
    1.81 +      else
    1.82 +         xassert(T != T);
    1.83 +      return p;
    1.84 +}
    1.85 +
    1.86 +static int most_feas(glp_tree *T)
    1.87 +{     /* select subproblem whose parent has minimal sum of integer
    1.88 +         infeasibilities */
    1.89 +      IOSNPD *node;
    1.90 +      int p;
    1.91 +      double best;
    1.92 +      p = 0, best = DBL_MAX;
    1.93 +      for (node = T->head; node != NULL; node = node->next)
    1.94 +      {  xassert(node->up != NULL);
    1.95 +         if (best > node->up->ii_sum)
    1.96 +            p = node->p, best = node->up->ii_sum;
    1.97 +      }
    1.98 +      return p;
    1.99 +}
   1.100 +
   1.101 +static int best_proj(glp_tree *T)
   1.102 +{     /* select subproblem using the best projection heuristic */
   1.103 +      IOSNPD *root, *node;
   1.104 +      int p;
   1.105 +      double best, deg, obj;
   1.106 +      /* the global bound must exist */
   1.107 +      xassert(T->mip->mip_stat == GLP_FEAS);
   1.108 +      /* obtain pointer to the root node, which must exist */
   1.109 +      root = T->slot[1].node;
   1.110 +      xassert(root != NULL);
   1.111 +      /* deg estimates degradation of the objective function per unit
   1.112 +         of the sum of integer infeasibilities */
   1.113 +      xassert(root->ii_sum > 0.0);
   1.114 +      deg = (T->mip->mip_obj - root->bound) / root->ii_sum;
   1.115 +      /* nothing has been selected so far */
   1.116 +      p = 0, best = DBL_MAX;
   1.117 +      /* walk through the list of active subproblems */
   1.118 +      for (node = T->head; node != NULL; node = node->next)
   1.119 +      {  xassert(node->up != NULL);
   1.120 +         /* obj estimates optimal objective value if the sum of integer
   1.121 +            infeasibilities were zero */
   1.122 +         obj = node->up->bound + deg * node->up->ii_sum;
   1.123 +         if (T->mip->dir == GLP_MAX) obj = - obj;
   1.124 +         /* select the subproblem which has the best estimated optimal
   1.125 +            objective value */
   1.126 +         if (best > obj) p = node->p, best = obj;
   1.127 +      }
   1.128 +      return p;
   1.129 +}
   1.130 +
   1.131 +static int best_node(glp_tree *T)
   1.132 +{     /* select subproblem with best local bound */
   1.133 +      IOSNPD *node, *best = NULL;
   1.134 +      double bound, eps;
   1.135 +      switch (T->mip->dir)
   1.136 +      {  case GLP_MIN:
   1.137 +            bound = +DBL_MAX;
   1.138 +            for (node = T->head; node != NULL; node = node->next)
   1.139 +               if (bound > node->bound) bound = node->bound;
   1.140 +            xassert(bound != +DBL_MAX);
   1.141 +            eps = 0.001 * (1.0 + fabs(bound));
   1.142 +            for (node = T->head; node != NULL; node = node->next)
   1.143 +            {  if (node->bound <= bound + eps)
   1.144 +               {  xassert(node->up != NULL);
   1.145 +                  if (best == NULL ||
   1.146 +#if 1
   1.147 +                  best->up->ii_sum > node->up->ii_sum) best = node;
   1.148 +#else
   1.149 +                  best->lp_obj > node->lp_obj) best = node;
   1.150 +#endif
   1.151 +               }
   1.152 +            }
   1.153 +            break;
   1.154 +         case GLP_MAX:
   1.155 +            bound = -DBL_MAX;
   1.156 +            for (node = T->head; node != NULL; node = node->next)
   1.157 +               if (bound < node->bound) bound = node->bound;
   1.158 +            xassert(bound != -DBL_MAX);
   1.159 +            eps = 0.001 * (1.0 + fabs(bound));
   1.160 +            for (node = T->head; node != NULL; node = node->next)
   1.161 +            {  if (node->bound >= bound - eps)
   1.162 +               {  xassert(node->up != NULL);
   1.163 +                  if (best == NULL ||
   1.164 +#if 1
   1.165 +                  best->up->ii_sum > node->up->ii_sum) best = node;
   1.166 +#else
   1.167 +                  best->lp_obj < node->lp_obj) best = node;
   1.168 +#endif
   1.169 +               }
   1.170 +            }
   1.171 +            break;
   1.172 +         default:
   1.173 +            xassert(T != T);
   1.174 +      }
   1.175 +      xassert(best != NULL);
   1.176 +      return best->p;
   1.177 +}
   1.178 +
   1.179 +/* eof */