lemon-project-template-glpk
diff deps/glpk/src/glpios12.c @ 9:33de93886c88
Import GLPK 4.47
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 20:59:10 +0100 |
parents | |
children |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/deps/glpk/src/glpios12.c Sun Nov 06 20:59:10 2011 +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, 2011 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 */