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