source: glpk-cmake/src/glpios12.c

/* glpios12.c (node selection heuristics) */

/***********************************************************************
*  This code is part of GLPK (GNU Linear Programming Kit).
*
*  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
*  2009, 2010 Andrew Makhorin, Department for Applied Informatics,
*  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
*  E-mail: <mao@gnu.org>.
*
*  GLPK is free software: you can redistribute it and/or modify it
*  under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  GLPK is distributed in the hope that it will be useful, but WITHOUT
*  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
*  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
*  License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
***********************************************************************/

#include "glpios.h"

/***********************************************************************
*  NAME
*
*  ios_choose_node - select subproblem to continue the search
*
*  SYNOPSIS
*
*  #include "glpios.h"
*  int ios_choose_node(glp_tree *T);
*
*  DESCRIPTION
*
*  The routine ios_choose_node selects a subproblem from the active
*  list to continue the search. The choice depends on the backtracking
*  technique option.
*
*  RETURNS
*
*  The routine ios_choose_node return the reference number of the
*  subproblem selected. */

static int most_feas(glp_tree *T);
static int best_proj(glp_tree *T);
static int best_node(glp_tree *T);

int ios_choose_node(glp_tree *T)
{     int p;
      if (T->parm->bt_tech == GLP_BT_DFS)
      {  /* depth first search */
         xassert(T->tail != NULL);
         p = T->tail->p;
      }
      else if (T->parm->bt_tech == GLP_BT_BFS)
      {  /* breadth first search */
         xassert(T->head != NULL);
         p = T->head->p;
      }
      else if (T->parm->bt_tech == GLP_BT_BLB)
      {  /* select node with best local bound */
         p = best_node(T);
      }
      else if (T->parm->bt_tech == GLP_BT_BPH)
      {  if (T->mip->mip_stat == GLP_UNDEF)
         {  /* "most integer feasible" subproblem */
            p = most_feas(T);
         }
         else
         {  /* best projection heuristic */
            p = best_proj(T);
         }
      }
      else
         xassert(T != T);
      return p;
}

static int most_feas(glp_tree *T)
{     /* select subproblem whose parent has minimal sum of integer
         infeasibilities */
      IOSNPD *node;
      int p;
      double best;
      p = 0, best = DBL_MAX;
      for (node = T->head; node != NULL; node = node->next)
      {  xassert(node->up != NULL);
         if (best > node->up->ii_sum)
            p = node->p, best = node->up->ii_sum;
      }
      return p;
}

static int best_proj(glp_tree *T)
{     /* select subproblem using the best projection heuristic */
      IOSNPD *root, *node;
      int p;
      double best, deg, obj;
      /* the global bound must exist */
      xassert(T->mip->mip_stat == GLP_FEAS);
      /* obtain pointer to the root node, which must exist */
      root = T->slot[1].node;
      xassert(root != NULL);
      /* deg estimates degradation of the objective function per unit
         of the sum of integer infeasibilities */
      xassert(root->ii_sum > 0.0);
      deg = (T->mip->mip_obj - root->bound) / root->ii_sum;
      /* nothing has been selected so far */
      p = 0, best = DBL_MAX;
      /* walk through the list of active subproblems */
      for (node = T->head; node != NULL; node = node->next)
      {  xassert(node->up != NULL);
         /* obj estimates optimal objective value if the sum of integer
            infeasibilities were zero */
         obj = node->up->bound + deg * node->up->ii_sum;
         if (T->mip->dir == GLP_MAX) obj = - obj;
         /* select the subproblem which has the best estimated optimal
            objective value */
         if (best > obj) p = node->p, best = obj;
      }
      return p;
}

static int best_node(glp_tree *T)
{     /* select subproblem with best local bound */
      IOSNPD *node, *best = NULL;
      double bound, eps;
      switch (T->mip->dir)
      {  case GLP_MIN:
            bound = +DBL_MAX;
            for (node = T->head; node != NULL; node = node->next)
               if (bound > node->bound) bound = node->bound;
            xassert(bound != +DBL_MAX);
            eps = 0.001 * (1.0 + fabs(bound));
            for (node = T->head; node != NULL; node = node->next)
            {  if (node->bound <= bound + eps)
               {  xassert(node->up != NULL);
                  if (best == NULL ||
#if 1
                  best->up->ii_sum > node->up->ii_sum) best = node;
#else
                  best->lp_obj > node->lp_obj) best = node;
#endif
               }
            }
            break;
         case GLP_MAX:
            bound = -DBL_MAX;
            for (node = T->head; node != NULL; node = node->next)
               if (bound < node->bound) bound = node->bound;
            xassert(bound != -DBL_MAX);
            eps = 0.001 * (1.0 + fabs(bound));
            for (node = T->head; node != NULL; node = node->next)
            {  if (node->bound >= bound - eps)
               {  xassert(node->up != NULL);
                  if (best == NULL ||
#if 1
                  best->up->ii_sum > node->up->ii_sum) best = node;
#else
                  best->lp_obj < node->lp_obj) best = node;
#endif
               }
            }
            break;
         default:
            xassert(T != T);
      }
      xassert(best != NULL);
      return best->p;
}

/* eof */