COIN-OR::LEMON - Graph Library

source: glpk-cmake/src/glpios12.c @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 5.7 KB
Line 
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 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
48static int most_feas(glp_tree *T);
49static int best_proj(glp_tree *T);
50static int best_node(glp_tree *T);
51
52int 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
83static 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
98static 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
128static 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 */
Note: See TracBrowser for help on using the repository browser.