lemon-project-template-glpk

annotate deps/glpk/src/glpios12.c @ 9:33de93886c88

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