[9] | 1 | /* glpios12.c (node selection heuristics) */ |
---|
| 2 | |
---|
| 3 | /*********************************************************************** |
---|
| 4 | * This code is part of GLPK (GNU Linear Programming Kit). |
---|
| 5 | * |
---|
| 6 | * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, |
---|
| 7 | * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics, |
---|
| 8 | * Moscow Aviation Institute, Moscow, Russia. All rights reserved. |
---|
| 9 | * E-mail: <mao@gnu.org>. |
---|
| 10 | * |
---|
| 11 | * GLPK is free software: you can redistribute it and/or modify it |
---|
| 12 | * under the terms of the GNU General Public License as published by |
---|
| 13 | * the Free Software Foundation, either version 3 of the License, or |
---|
| 14 | * (at your option) any later version. |
---|
| 15 | * |
---|
| 16 | * GLPK is distributed in the hope that it will be useful, but WITHOUT |
---|
| 17 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
---|
| 18 | * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public |
---|
| 19 | * License for more details. |
---|
| 20 | * |
---|
| 21 | * You should have received a copy of the GNU General Public License |
---|
| 22 | * along with GLPK. If not, see <http://www.gnu.org/licenses/>. |
---|
| 23 | ***********************************************************************/ |
---|
| 24 | |
---|
| 25 | #include "glpios.h" |
---|
| 26 | |
---|
| 27 | /*********************************************************************** |
---|
| 28 | * NAME |
---|
| 29 | * |
---|
| 30 | * ios_choose_node - select subproblem to continue the search |
---|
| 31 | * |
---|
| 32 | * SYNOPSIS |
---|
| 33 | * |
---|
| 34 | * #include "glpios.h" |
---|
| 35 | * int ios_choose_node(glp_tree *T); |
---|
| 36 | * |
---|
| 37 | * DESCRIPTION |
---|
| 38 | * |
---|
| 39 | * The routine ios_choose_node selects a subproblem from the active |
---|
| 40 | * list to continue the search. The choice depends on the backtracking |
---|
| 41 | * technique option. |
---|
| 42 | * |
---|
| 43 | * RETURNS |
---|
| 44 | * |
---|
| 45 | * The routine ios_choose_node return the reference number of the |
---|
| 46 | * subproblem selected. */ |
---|
| 47 | |
---|
| 48 | static int most_feas(glp_tree *T); |
---|
| 49 | static int best_proj(glp_tree *T); |
---|
| 50 | static int best_node(glp_tree *T); |
---|
| 51 | |
---|
| 52 | int ios_choose_node(glp_tree *T) |
---|
| 53 | { int p; |
---|
| 54 | if (T->parm->bt_tech == GLP_BT_DFS) |
---|
| 55 | { /* depth first search */ |
---|
| 56 | xassert(T->tail != NULL); |
---|
| 57 | p = T->tail->p; |
---|
| 58 | } |
---|
| 59 | else if (T->parm->bt_tech == GLP_BT_BFS) |
---|
| 60 | { /* breadth first search */ |
---|
| 61 | xassert(T->head != NULL); |
---|
| 62 | p = T->head->p; |
---|
| 63 | } |
---|
| 64 | else if (T->parm->bt_tech == GLP_BT_BLB) |
---|
| 65 | { /* select node with best local bound */ |
---|
| 66 | p = best_node(T); |
---|
| 67 | } |
---|
| 68 | else if (T->parm->bt_tech == GLP_BT_BPH) |
---|
| 69 | { if (T->mip->mip_stat == GLP_UNDEF) |
---|
| 70 | { /* "most integer feasible" subproblem */ |
---|
| 71 | p = most_feas(T); |
---|
| 72 | } |
---|
| 73 | else |
---|
| 74 | { /* best projection heuristic */ |
---|
| 75 | p = best_proj(T); |
---|
| 76 | } |
---|
| 77 | } |
---|
| 78 | else |
---|
| 79 | xassert(T != T); |
---|
| 80 | return p; |
---|
| 81 | } |
---|
| 82 | |
---|
| 83 | static int most_feas(glp_tree *T) |
---|
| 84 | { /* select subproblem whose parent has minimal sum of integer |
---|
| 85 | infeasibilities */ |
---|
| 86 | IOSNPD *node; |
---|
| 87 | int p; |
---|
| 88 | double best; |
---|
| 89 | p = 0, best = DBL_MAX; |
---|
| 90 | for (node = T->head; node != NULL; node = node->next) |
---|
| 91 | { xassert(node->up != NULL); |
---|
| 92 | if (best > node->up->ii_sum) |
---|
| 93 | p = node->p, best = node->up->ii_sum; |
---|
| 94 | } |
---|
| 95 | return p; |
---|
| 96 | } |
---|
| 97 | |
---|
| 98 | static int best_proj(glp_tree *T) |
---|
| 99 | { /* select subproblem using the best projection heuristic */ |
---|
| 100 | IOSNPD *root, *node; |
---|
| 101 | int p; |
---|
| 102 | double best, deg, obj; |
---|
| 103 | /* the global bound must exist */ |
---|
| 104 | xassert(T->mip->mip_stat == GLP_FEAS); |
---|
| 105 | /* obtain pointer to the root node, which must exist */ |
---|
| 106 | root = T->slot[1].node; |
---|
| 107 | xassert(root != NULL); |
---|
| 108 | /* deg estimates degradation of the objective function per unit |
---|
| 109 | of the sum of integer infeasibilities */ |
---|
| 110 | xassert(root->ii_sum > 0.0); |
---|
| 111 | deg = (T->mip->mip_obj - root->bound) / root->ii_sum; |
---|
| 112 | /* nothing has been selected so far */ |
---|
| 113 | p = 0, best = DBL_MAX; |
---|
| 114 | /* walk through the list of active subproblems */ |
---|
| 115 | for (node = T->head; node != NULL; node = node->next) |
---|
| 116 | { xassert(node->up != NULL); |
---|
| 117 | /* obj estimates optimal objective value if the sum of integer |
---|
| 118 | infeasibilities were zero */ |
---|
| 119 | obj = node->up->bound + deg * node->up->ii_sum; |
---|
| 120 | if (T->mip->dir == GLP_MAX) obj = - obj; |
---|
| 121 | /* select the subproblem which has the best estimated optimal |
---|
| 122 | objective value */ |
---|
| 123 | if (best > obj) p = node->p, best = obj; |
---|
| 124 | } |
---|
| 125 | return p; |
---|
| 126 | } |
---|
| 127 | |
---|
| 128 | static int best_node(glp_tree *T) |
---|
| 129 | { /* select subproblem with best local bound */ |
---|
| 130 | IOSNPD *node, *best = NULL; |
---|
| 131 | double bound, eps; |
---|
| 132 | switch (T->mip->dir) |
---|
| 133 | { case GLP_MIN: |
---|
| 134 | bound = +DBL_MAX; |
---|
| 135 | for (node = T->head; node != NULL; node = node->next) |
---|
| 136 | if (bound > node->bound) bound = node->bound; |
---|
| 137 | xassert(bound != +DBL_MAX); |
---|
| 138 | eps = 0.001 * (1.0 + fabs(bound)); |
---|
| 139 | for (node = T->head; node != NULL; node = node->next) |
---|
| 140 | { if (node->bound <= bound + eps) |
---|
| 141 | { xassert(node->up != NULL); |
---|
| 142 | if (best == NULL || |
---|
| 143 | #if 1 |
---|
| 144 | best->up->ii_sum > node->up->ii_sum) best = node; |
---|
| 145 | #else |
---|
| 146 | best->lp_obj > node->lp_obj) best = node; |
---|
| 147 | #endif |
---|
| 148 | } |
---|
| 149 | } |
---|
| 150 | break; |
---|
| 151 | case GLP_MAX: |
---|
| 152 | bound = -DBL_MAX; |
---|
| 153 | for (node = T->head; node != NULL; node = node->next) |
---|
| 154 | if (bound < node->bound) bound = node->bound; |
---|
| 155 | xassert(bound != -DBL_MAX); |
---|
| 156 | eps = 0.001 * (1.0 + fabs(bound)); |
---|
| 157 | for (node = T->head; node != NULL; node = node->next) |
---|
| 158 | { if (node->bound >= bound - eps) |
---|
| 159 | { xassert(node->up != NULL); |
---|
| 160 | if (best == NULL || |
---|
| 161 | #if 1 |
---|
| 162 | best->up->ii_sum > node->up->ii_sum) best = node; |
---|
| 163 | #else |
---|
| 164 | best->lp_obj < node->lp_obj) best = node; |
---|
| 165 | #endif |
---|
| 166 | } |
---|
| 167 | } |
---|
| 168 | break; |
---|
| 169 | default: |
---|
| 170 | xassert(T != T); |
---|
| 171 | } |
---|
| 172 | xassert(best != NULL); |
---|
| 173 | return best->p; |
---|
| 174 | } |
---|
| 175 | |
---|
| 176 | /* eof */ |
---|