lemon-project-template-glpk
view 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 source
1 /* glpios12.c (node selection heuristics) */
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 ***********************************************************************/
25 #include "glpios.h"
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. */
48 static int most_feas(glp_tree *T);
49 static int best_proj(glp_tree *T);
50 static int best_node(glp_tree *T);
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 }
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 }
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 }
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 }
176 /* eof */