/* 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 */