1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/glpios12.c Mon Dec 06 13:09:21 2010 +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 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 */