alpar@1: /* glpios12.c (node selection heuristics) */
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  This code is part of GLPK (GNU Linear Programming Kit).
alpar@1: *
alpar@1: *  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@1: *  2009, 2010 Andrew Makhorin, Department for Applied Informatics,
alpar@1: *  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@1: *  E-mail: <mao@gnu.org>.
alpar@1: *
alpar@1: *  GLPK is free software: you can redistribute it and/or modify it
alpar@1: *  under the terms of the GNU General Public License as published by
alpar@1: *  the Free Software Foundation, either version 3 of the License, or
alpar@1: *  (at your option) any later version.
alpar@1: *
alpar@1: *  GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@1: *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@1: *  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@1: *  License for more details.
alpar@1: *
alpar@1: *  You should have received a copy of the GNU General Public License
alpar@1: *  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@1: ***********************************************************************/
alpar@1: 
alpar@1: #include "glpios.h"
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  NAME
alpar@1: *
alpar@1: *  ios_choose_node - select subproblem to continue the search
alpar@1: *
alpar@1: *  SYNOPSIS
alpar@1: *
alpar@1: *  #include "glpios.h"
alpar@1: *  int ios_choose_node(glp_tree *T);
alpar@1: *
alpar@1: *  DESCRIPTION
alpar@1: *
alpar@1: *  The routine ios_choose_node selects a subproblem from the active
alpar@1: *  list to continue the search. The choice depends on the backtracking
alpar@1: *  technique option.
alpar@1: *
alpar@1: *  RETURNS
alpar@1: *
alpar@1: *  The routine ios_choose_node return the reference number of the
alpar@1: *  subproblem selected. */
alpar@1: 
alpar@1: static int most_feas(glp_tree *T);
alpar@1: static int best_proj(glp_tree *T);
alpar@1: static int best_node(glp_tree *T);
alpar@1: 
alpar@1: int ios_choose_node(glp_tree *T)
alpar@1: {     int p;
alpar@1:       if (T->parm->bt_tech == GLP_BT_DFS)
alpar@1:       {  /* depth first search */
alpar@1:          xassert(T->tail != NULL);
alpar@1:          p = T->tail->p;
alpar@1:       }
alpar@1:       else if (T->parm->bt_tech == GLP_BT_BFS)
alpar@1:       {  /* breadth first search */
alpar@1:          xassert(T->head != NULL);
alpar@1:          p = T->head->p;
alpar@1:       }
alpar@1:       else if (T->parm->bt_tech == GLP_BT_BLB)
alpar@1:       {  /* select node with best local bound */
alpar@1:          p = best_node(T);
alpar@1:       }
alpar@1:       else if (T->parm->bt_tech == GLP_BT_BPH)
alpar@1:       {  if (T->mip->mip_stat == GLP_UNDEF)
alpar@1:          {  /* "most integer feasible" subproblem */
alpar@1:             p = most_feas(T);
alpar@1:          }
alpar@1:          else
alpar@1:          {  /* best projection heuristic */
alpar@1:             p = best_proj(T);
alpar@1:          }
alpar@1:       }
alpar@1:       else
alpar@1:          xassert(T != T);
alpar@1:       return p;
alpar@1: }
alpar@1: 
alpar@1: static int most_feas(glp_tree *T)
alpar@1: {     /* select subproblem whose parent has minimal sum of integer
alpar@1:          infeasibilities */
alpar@1:       IOSNPD *node;
alpar@1:       int p;
alpar@1:       double best;
alpar@1:       p = 0, best = DBL_MAX;
alpar@1:       for (node = T->head; node != NULL; node = node->next)
alpar@1:       {  xassert(node->up != NULL);
alpar@1:          if (best > node->up->ii_sum)
alpar@1:             p = node->p, best = node->up->ii_sum;
alpar@1:       }
alpar@1:       return p;
alpar@1: }
alpar@1: 
alpar@1: static int best_proj(glp_tree *T)
alpar@1: {     /* select subproblem using the best projection heuristic */
alpar@1:       IOSNPD *root, *node;
alpar@1:       int p;
alpar@1:       double best, deg, obj;
alpar@1:       /* the global bound must exist */
alpar@1:       xassert(T->mip->mip_stat == GLP_FEAS);
alpar@1:       /* obtain pointer to the root node, which must exist */
alpar@1:       root = T->slot[1].node;
alpar@1:       xassert(root != NULL);
alpar@1:       /* deg estimates degradation of the objective function per unit
alpar@1:          of the sum of integer infeasibilities */
alpar@1:       xassert(root->ii_sum > 0.0);
alpar@1:       deg = (T->mip->mip_obj - root->bound) / root->ii_sum;
alpar@1:       /* nothing has been selected so far */
alpar@1:       p = 0, best = DBL_MAX;
alpar@1:       /* walk through the list of active subproblems */
alpar@1:       for (node = T->head; node != NULL; node = node->next)
alpar@1:       {  xassert(node->up != NULL);
alpar@1:          /* obj estimates optimal objective value if the sum of integer
alpar@1:             infeasibilities were zero */
alpar@1:          obj = node->up->bound + deg * node->up->ii_sum;
alpar@1:          if (T->mip->dir == GLP_MAX) obj = - obj;
alpar@1:          /* select the subproblem which has the best estimated optimal
alpar@1:             objective value */
alpar@1:          if (best > obj) p = node->p, best = obj;
alpar@1:       }
alpar@1:       return p;
alpar@1: }
alpar@1: 
alpar@1: static int best_node(glp_tree *T)
alpar@1: {     /* select subproblem with best local bound */
alpar@1:       IOSNPD *node, *best = NULL;
alpar@1:       double bound, eps;
alpar@1:       switch (T->mip->dir)
alpar@1:       {  case GLP_MIN:
alpar@1:             bound = +DBL_MAX;
alpar@1:             for (node = T->head; node != NULL; node = node->next)
alpar@1:                if (bound > node->bound) bound = node->bound;
alpar@1:             xassert(bound != +DBL_MAX);
alpar@1:             eps = 0.001 * (1.0 + fabs(bound));
alpar@1:             for (node = T->head; node != NULL; node = node->next)
alpar@1:             {  if (node->bound <= bound + eps)
alpar@1:                {  xassert(node->up != NULL);
alpar@1:                   if (best == NULL ||
alpar@1: #if 1
alpar@1:                   best->up->ii_sum > node->up->ii_sum) best = node;
alpar@1: #else
alpar@1:                   best->lp_obj > node->lp_obj) best = node;
alpar@1: #endif
alpar@1:                }
alpar@1:             }
alpar@1:             break;
alpar@1:          case GLP_MAX:
alpar@1:             bound = -DBL_MAX;
alpar@1:             for (node = T->head; node != NULL; node = node->next)
alpar@1:                if (bound < node->bound) bound = node->bound;
alpar@1:             xassert(bound != -DBL_MAX);
alpar@1:             eps = 0.001 * (1.0 + fabs(bound));
alpar@1:             for (node = T->head; node != NULL; node = node->next)
alpar@1:             {  if (node->bound >= bound - eps)
alpar@1:                {  xassert(node->up != NULL);
alpar@1:                   if (best == NULL ||
alpar@1: #if 1
alpar@1:                   best->up->ii_sum > node->up->ii_sum) best = node;
alpar@1: #else
alpar@1:                   best->lp_obj < node->lp_obj) best = node;
alpar@1: #endif
alpar@1:                }
alpar@1:             }
alpar@1:             break;
alpar@1:          default:
alpar@1:             xassert(T != T);
alpar@1:       }
alpar@1:       xassert(best != NULL);
alpar@1:       return best->p;
alpar@1: }
alpar@1: 
alpar@1: /* eof */