1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/glpapi13.c Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,702 @@
1.4 +/* glpapi13.c (branch-and-bound interface routines) */
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 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 +* glp_ios_reason - determine reason for calling the callback routine
1.34 +*
1.35 +* SYNOPSIS
1.36 +*
1.37 +* glp_ios_reason(glp_tree *tree);
1.38 +*
1.39 +* RETURNS
1.40 +*
1.41 +* The routine glp_ios_reason returns a code, which indicates why the
1.42 +* user-defined callback routine is being called. */
1.43 +
1.44 +int glp_ios_reason(glp_tree *tree)
1.45 +{ return
1.46 + tree->reason;
1.47 +}
1.48 +
1.49 +/***********************************************************************
1.50 +* NAME
1.51 +*
1.52 +* glp_ios_get_prob - access the problem object
1.53 +*
1.54 +* SYNOPSIS
1.55 +*
1.56 +* glp_prob *glp_ios_get_prob(glp_tree *tree);
1.57 +*
1.58 +* DESCRIPTION
1.59 +*
1.60 +* The routine glp_ios_get_prob can be called from the user-defined
1.61 +* callback routine to access the problem object, which is used by the
1.62 +* MIP solver. It is the original problem object passed to the routine
1.63 +* glp_intopt if the MIP presolver is not used; otherwise it is an
1.64 +* internal problem object built by the presolver. If the current
1.65 +* subproblem exists, LP segment of the problem object corresponds to
1.66 +* its LP relaxation.
1.67 +*
1.68 +* RETURNS
1.69 +*
1.70 +* The routine glp_ios_get_prob returns a pointer to the problem object
1.71 +* used by the MIP solver. */
1.72 +
1.73 +glp_prob *glp_ios_get_prob(glp_tree *tree)
1.74 +{ return
1.75 + tree->mip;
1.76 +}
1.77 +
1.78 +/***********************************************************************
1.79 +* NAME
1.80 +*
1.81 +* glp_ios_tree_size - determine size of the branch-and-bound tree
1.82 +*
1.83 +* SYNOPSIS
1.84 +*
1.85 +* void glp_ios_tree_size(glp_tree *tree, int *a_cnt, int *n_cnt,
1.86 +* int *t_cnt);
1.87 +*
1.88 +* DESCRIPTION
1.89 +*
1.90 +* The routine glp_ios_tree_size stores the following three counts which
1.91 +* characterize the current size of the branch-and-bound tree:
1.92 +*
1.93 +* a_cnt is the current number of active nodes, i.e. the current size of
1.94 +* the active list;
1.95 +*
1.96 +* n_cnt is the current number of all (active and inactive) nodes;
1.97 +*
1.98 +* t_cnt is the total number of nodes including those which have been
1.99 +* already removed from the tree. This count is increased whenever
1.100 +* a new node appears in the tree and never decreased.
1.101 +*
1.102 +* If some of the parameters a_cnt, n_cnt, t_cnt is a null pointer, the
1.103 +* corresponding count is not stored. */
1.104 +
1.105 +void glp_ios_tree_size(glp_tree *tree, int *a_cnt, int *n_cnt,
1.106 + int *t_cnt)
1.107 +{ if (a_cnt != NULL) *a_cnt = tree->a_cnt;
1.108 + if (n_cnt != NULL) *n_cnt = tree->n_cnt;
1.109 + if (t_cnt != NULL) *t_cnt = tree->t_cnt;
1.110 + return;
1.111 +}
1.112 +
1.113 +/***********************************************************************
1.114 +* NAME
1.115 +*
1.116 +* glp_ios_curr_node - determine current active subproblem
1.117 +*
1.118 +* SYNOPSIS
1.119 +*
1.120 +* int glp_ios_curr_node(glp_tree *tree);
1.121 +*
1.122 +* RETURNS
1.123 +*
1.124 +* The routine glp_ios_curr_node returns the reference number of the
1.125 +* current active subproblem. However, if the current subproblem does
1.126 +* not exist, the routine returns zero. */
1.127 +
1.128 +int glp_ios_curr_node(glp_tree *tree)
1.129 +{ IOSNPD *node;
1.130 + /* obtain pointer to the current subproblem */
1.131 + node = tree->curr;
1.132 + /* return its reference number */
1.133 + return node == NULL ? 0 : node->p;
1.134 +}
1.135 +
1.136 +/***********************************************************************
1.137 +* NAME
1.138 +*
1.139 +* glp_ios_next_node - determine next active subproblem
1.140 +*
1.141 +* SYNOPSIS
1.142 +*
1.143 +* int glp_ios_next_node(glp_tree *tree, int p);
1.144 +*
1.145 +* RETURNS
1.146 +*
1.147 +* If the parameter p is zero, the routine glp_ios_next_node returns
1.148 +* the reference number of the first active subproblem. However, if the
1.149 +* tree is empty, zero is returned.
1.150 +*
1.151 +* If the parameter p is not zero, it must specify the reference number
1.152 +* of some active subproblem, in which case the routine returns the
1.153 +* reference number of the next active subproblem. However, if there is
1.154 +* no next active subproblem in the list, zero is returned.
1.155 +*
1.156 +* All subproblems in the active list are ordered chronologically, i.e.
1.157 +* subproblem A precedes subproblem B if A was created before B. */
1.158 +
1.159 +int glp_ios_next_node(glp_tree *tree, int p)
1.160 +{ IOSNPD *node;
1.161 + if (p == 0)
1.162 + { /* obtain pointer to the first active subproblem */
1.163 + node = tree->head;
1.164 + }
1.165 + else
1.166 + { /* obtain pointer to the specified subproblem */
1.167 + if (!(1 <= p && p <= tree->nslots))
1.168 +err: xerror("glp_ios_next_node: p = %d; invalid subproblem refer"
1.169 + "ence number\n", p);
1.170 + node = tree->slot[p].node;
1.171 + if (node == NULL) goto err;
1.172 + /* the specified subproblem must be active */
1.173 + if (node->count != 0)
1.174 + xerror("glp_ios_next_node: p = %d; subproblem not in the ac"
1.175 + "tive list\n", p);
1.176 + /* obtain pointer to the next active subproblem */
1.177 + node = node->next;
1.178 + }
1.179 + /* return the reference number */
1.180 + return node == NULL ? 0 : node->p;
1.181 +}
1.182 +
1.183 +/***********************************************************************
1.184 +* NAME
1.185 +*
1.186 +* glp_ios_prev_node - determine previous active subproblem
1.187 +*
1.188 +* SYNOPSIS
1.189 +*
1.190 +* int glp_ios_prev_node(glp_tree *tree, int p);
1.191 +*
1.192 +* RETURNS
1.193 +*
1.194 +* If the parameter p is zero, the routine glp_ios_prev_node returns
1.195 +* the reference number of the last active subproblem. However, if the
1.196 +* tree is empty, zero is returned.
1.197 +*
1.198 +* If the parameter p is not zero, it must specify the reference number
1.199 +* of some active subproblem, in which case the routine returns the
1.200 +* reference number of the previous active subproblem. However, if there
1.201 +* is no previous active subproblem in the list, zero is returned.
1.202 +*
1.203 +* All subproblems in the active list are ordered chronologically, i.e.
1.204 +* subproblem A precedes subproblem B if A was created before B. */
1.205 +
1.206 +int glp_ios_prev_node(glp_tree *tree, int p)
1.207 +{ IOSNPD *node;
1.208 + if (p == 0)
1.209 + { /* obtain pointer to the last active subproblem */
1.210 + node = tree->tail;
1.211 + }
1.212 + else
1.213 + { /* obtain pointer to the specified subproblem */
1.214 + if (!(1 <= p && p <= tree->nslots))
1.215 +err: xerror("glp_ios_prev_node: p = %d; invalid subproblem refer"
1.216 + "ence number\n", p);
1.217 + node = tree->slot[p].node;
1.218 + if (node == NULL) goto err;
1.219 + /* the specified subproblem must be active */
1.220 + if (node->count != 0)
1.221 + xerror("glp_ios_prev_node: p = %d; subproblem not in the ac"
1.222 + "tive list\n", p);
1.223 + /* obtain pointer to the previous active subproblem */
1.224 + node = node->prev;
1.225 + }
1.226 + /* return the reference number */
1.227 + return node == NULL ? 0 : node->p;
1.228 +}
1.229 +
1.230 +/***********************************************************************
1.231 +* NAME
1.232 +*
1.233 +* glp_ios_up_node - determine parent subproblem
1.234 +*
1.235 +* SYNOPSIS
1.236 +*
1.237 +* int glp_ios_up_node(glp_tree *tree, int p);
1.238 +*
1.239 +* RETURNS
1.240 +*
1.241 +* The parameter p must specify the reference number of some (active or
1.242 +* inactive) subproblem, in which case the routine iet_get_up_node
1.243 +* returns the reference number of its parent subproblem. However, if
1.244 +* the specified subproblem is the root of the tree and, therefore, has
1.245 +* no parent, the routine returns zero. */
1.246 +
1.247 +int glp_ios_up_node(glp_tree *tree, int p)
1.248 +{ IOSNPD *node;
1.249 + /* obtain pointer to the specified subproblem */
1.250 + if (!(1 <= p && p <= tree->nslots))
1.251 +err: xerror("glp_ios_up_node: p = %d; invalid subproblem reference "
1.252 + "number\n", p);
1.253 + node = tree->slot[p].node;
1.254 + if (node == NULL) goto err;
1.255 + /* obtain pointer to the parent subproblem */
1.256 + node = node->up;
1.257 + /* return the reference number */
1.258 + return node == NULL ? 0 : node->p;
1.259 +}
1.260 +
1.261 +/***********************************************************************
1.262 +* NAME
1.263 +*
1.264 +* glp_ios_node_level - determine subproblem level
1.265 +*
1.266 +* SYNOPSIS
1.267 +*
1.268 +* int glp_ios_node_level(glp_tree *tree, int p);
1.269 +*
1.270 +* RETURNS
1.271 +*
1.272 +* The routine glp_ios_node_level returns the level of the subproblem,
1.273 +* whose reference number is p, in the branch-and-bound tree. (The root
1.274 +* subproblem has level 0, and the level of any other subproblem is the
1.275 +* level of its parent plus one.) */
1.276 +
1.277 +int glp_ios_node_level(glp_tree *tree, int p)
1.278 +{ IOSNPD *node;
1.279 + /* obtain pointer to the specified subproblem */
1.280 + if (!(1 <= p && p <= tree->nslots))
1.281 +err: xerror("glp_ios_node_level: p = %d; invalid subproblem referen"
1.282 + "ce number\n", p);
1.283 + node = tree->slot[p].node;
1.284 + if (node == NULL) goto err;
1.285 + /* return the node level */
1.286 + return node->level;
1.287 +}
1.288 +
1.289 +/***********************************************************************
1.290 +* NAME
1.291 +*
1.292 +* glp_ios_node_bound - determine subproblem local bound
1.293 +*
1.294 +* SYNOPSIS
1.295 +*
1.296 +* double glp_ios_node_bound(glp_tree *tree, int p);
1.297 +*
1.298 +* RETURNS
1.299 +*
1.300 +* The routine glp_ios_node_bound returns the local bound for (active or
1.301 +* inactive) subproblem, whose reference number is p.
1.302 +*
1.303 +* COMMENTS
1.304 +*
1.305 +* The local bound for subproblem p is an lower (minimization) or upper
1.306 +* (maximization) bound for integer optimal solution to this subproblem
1.307 +* (not to the original problem). This bound is local in the sense that
1.308 +* only subproblems in the subtree rooted at node p cannot have better
1.309 +* integer feasible solutions.
1.310 +*
1.311 +* On creating a subproblem (due to the branching step) its local bound
1.312 +* is inherited from its parent and then may get only stronger (never
1.313 +* weaker). For the root subproblem its local bound is initially set to
1.314 +* -DBL_MAX (minimization) or +DBL_MAX (maximization) and then improved
1.315 +* as the root LP relaxation has been solved.
1.316 +*
1.317 +* Note that the local bound is not necessarily the optimal objective
1.318 +* value to corresponding LP relaxation; it may be stronger. */
1.319 +
1.320 +double glp_ios_node_bound(glp_tree *tree, int p)
1.321 +{ IOSNPD *node;
1.322 + /* obtain pointer to the specified subproblem */
1.323 + if (!(1 <= p && p <= tree->nslots))
1.324 +err: xerror("glp_ios_node_bound: p = %d; invalid subproblem referen"
1.325 + "ce number\n", p);
1.326 + node = tree->slot[p].node;
1.327 + if (node == NULL) goto err;
1.328 + /* return the node local bound */
1.329 + return node->bound;
1.330 +}
1.331 +
1.332 +/***********************************************************************
1.333 +* NAME
1.334 +*
1.335 +* glp_ios_best_node - find active subproblem with best local bound
1.336 +*
1.337 +* SYNOPSIS
1.338 +*
1.339 +* int glp_ios_best_node(glp_tree *tree);
1.340 +*
1.341 +* RETURNS
1.342 +*
1.343 +* The routine glp_ios_best_node returns the reference number of the
1.344 +* active subproblem, whose local bound is best (i.e. smallest in case
1.345 +* of minimization or largest in case of maximization). However, if the
1.346 +* tree is empty, the routine returns zero.
1.347 +*
1.348 +* COMMENTS
1.349 +*
1.350 +* The best local bound is an lower (minimization) or upper
1.351 +* (maximization) bound for integer optimal solution to the original
1.352 +* MIP problem. */
1.353 +
1.354 +int glp_ios_best_node(glp_tree *tree)
1.355 +{ return
1.356 + ios_best_node(tree);
1.357 +}
1.358 +
1.359 +/***********************************************************************
1.360 +* NAME
1.361 +*
1.362 +* glp_ios_mip_gap - compute relative MIP gap
1.363 +*
1.364 +* SYNOPSIS
1.365 +*
1.366 +* double glp_ios_mip_gap(glp_tree *tree);
1.367 +*
1.368 +* DESCRIPTION
1.369 +*
1.370 +* The routine glp_ios_mip_gap computes the relative MIP gap with the
1.371 +* following formula:
1.372 +*
1.373 +* gap = |best_mip - best_bnd| / (|best_mip| + DBL_EPSILON),
1.374 +*
1.375 +* where best_mip is the best integer feasible solution found so far,
1.376 +* best_bnd is the best (global) bound. If no integer feasible solution
1.377 +* has been found yet, gap is set to DBL_MAX.
1.378 +*
1.379 +* RETURNS
1.380 +*
1.381 +* The routine glp_ios_mip_gap returns the relative MIP gap. */
1.382 +
1.383 +double glp_ios_mip_gap(glp_tree *tree)
1.384 +{ return
1.385 + ios_relative_gap(tree);
1.386 +}
1.387 +
1.388 +/***********************************************************************
1.389 +* NAME
1.390 +*
1.391 +* glp_ios_node_data - access subproblem application-specific data
1.392 +*
1.393 +* SYNOPSIS
1.394 +*
1.395 +* void *glp_ios_node_data(glp_tree *tree, int p);
1.396 +*
1.397 +* DESCRIPTION
1.398 +*
1.399 +* The routine glp_ios_node_data allows the application accessing a
1.400 +* memory block allocated for the subproblem (which may be active or
1.401 +* inactive), whose reference number is p.
1.402 +*
1.403 +* The size of the block is defined by the control parameter cb_size
1.404 +* passed to the routine glp_intopt. The block is initialized by binary
1.405 +* zeros on creating corresponding subproblem, and its contents is kept
1.406 +* until the subproblem will be removed from the tree.
1.407 +*
1.408 +* The application may use these memory blocks to store specific data
1.409 +* for each subproblem.
1.410 +*
1.411 +* RETURNS
1.412 +*
1.413 +* The routine glp_ios_node_data returns a pointer to the memory block
1.414 +* for the specified subproblem. Note that if cb_size = 0, the routine
1.415 +* returns a null pointer. */
1.416 +
1.417 +void *glp_ios_node_data(glp_tree *tree, int p)
1.418 +{ IOSNPD *node;
1.419 + /* obtain pointer to the specified subproblem */
1.420 + if (!(1 <= p && p <= tree->nslots))
1.421 +err: xerror("glp_ios_node_level: p = %d; invalid subproblem referen"
1.422 + "ce number\n", p);
1.423 + node = tree->slot[p].node;
1.424 + if (node == NULL) goto err;
1.425 + /* return pointer to the application-specific data */
1.426 + return node->data;
1.427 +}
1.428 +
1.429 +/***********************************************************************
1.430 +* NAME
1.431 +*
1.432 +* glp_ios_row_attr - retrieve additional row attributes
1.433 +*
1.434 +* SYNOPSIS
1.435 +*
1.436 +* void glp_ios_row_attr(glp_tree *tree, int i, glp_attr *attr);
1.437 +*
1.438 +* DESCRIPTION
1.439 +*
1.440 +* The routine glp_ios_row_attr retrieves additional attributes of row
1.441 +* i and stores them in the structure glp_attr. */
1.442 +
1.443 +void glp_ios_row_attr(glp_tree *tree, int i, glp_attr *attr)
1.444 +{ GLPROW *row;
1.445 + if (!(1 <= i && i <= tree->mip->m))
1.446 + xerror("glp_ios_row_attr: i = %d; row number out of range\n",
1.447 + i);
1.448 + row = tree->mip->row[i];
1.449 + attr->level = row->level;
1.450 + attr->origin = row->origin;
1.451 + attr->klass = row->klass;
1.452 + return;
1.453 +}
1.454 +
1.455 +/**********************************************************************/
1.456 +
1.457 +int glp_ios_pool_size(glp_tree *tree)
1.458 +{ /* determine current size of the cut pool */
1.459 + if (tree->reason != GLP_ICUTGEN)
1.460 + xerror("glp_ios_pool_size: operation not allowed\n");
1.461 + xassert(tree->local != NULL);
1.462 + return tree->local->size;
1.463 +}
1.464 +
1.465 +/**********************************************************************/
1.466 +
1.467 +int glp_ios_add_row(glp_tree *tree,
1.468 + const char *name, int klass, int flags, int len, const int ind[],
1.469 + const double val[], int type, double rhs)
1.470 +{ /* add row (constraint) to the cut pool */
1.471 + int num;
1.472 + if (tree->reason != GLP_ICUTGEN)
1.473 + xerror("glp_ios_add_row: operation not allowed\n");
1.474 + xassert(tree->local != NULL);
1.475 + num = ios_add_row(tree, tree->local, name, klass, flags, len,
1.476 + ind, val, type, rhs);
1.477 + return num;
1.478 +}
1.479 +
1.480 +/**********************************************************************/
1.481 +
1.482 +void glp_ios_del_row(glp_tree *tree, int i)
1.483 +{ /* remove row (constraint) from the cut pool */
1.484 + if (tree->reason != GLP_ICUTGEN)
1.485 + xerror("glp_ios_del_row: operation not allowed\n");
1.486 + ios_del_row(tree, tree->local, i);
1.487 + return;
1.488 +}
1.489 +
1.490 +/**********************************************************************/
1.491 +
1.492 +void glp_ios_clear_pool(glp_tree *tree)
1.493 +{ /* remove all rows (constraints) from the cut pool */
1.494 + if (tree->reason != GLP_ICUTGEN)
1.495 + xerror("glp_ios_clear_pool: operation not allowed\n");
1.496 + ios_clear_pool(tree, tree->local);
1.497 + return;
1.498 +}
1.499 +
1.500 +/***********************************************************************
1.501 +* NAME
1.502 +*
1.503 +* glp_ios_can_branch - check if can branch upon specified variable
1.504 +*
1.505 +* SYNOPSIS
1.506 +*
1.507 +* int glp_ios_can_branch(glp_tree *tree, int j);
1.508 +*
1.509 +* RETURNS
1.510 +*
1.511 +* If j-th variable (column) can be used to branch upon, the routine
1.512 +* glp_ios_can_branch returns non-zero, otherwise zero. */
1.513 +
1.514 +int glp_ios_can_branch(glp_tree *tree, int j)
1.515 +{ if (!(1 <= j && j <= tree->mip->n))
1.516 + xerror("glp_ios_can_branch: j = %d; column number out of range"
1.517 + "\n", j);
1.518 + return tree->non_int[j];
1.519 +}
1.520 +
1.521 +/***********************************************************************
1.522 +* NAME
1.523 +*
1.524 +* glp_ios_branch_upon - choose variable to branch upon
1.525 +*
1.526 +* SYNOPSIS
1.527 +*
1.528 +* void glp_ios_branch_upon(glp_tree *tree, int j, int sel);
1.529 +*
1.530 +* DESCRIPTION
1.531 +*
1.532 +* The routine glp_ios_branch_upon can be called from the user-defined
1.533 +* callback routine in response to the reason GLP_IBRANCH to choose a
1.534 +* branching variable, whose ordinal number is j. Should note that only
1.535 +* variables, for which the routine glp_ios_can_branch returns non-zero,
1.536 +* can be used to branch upon.
1.537 +*
1.538 +* The parameter sel is a flag that indicates which branch (subproblem)
1.539 +* should be selected next to continue the search:
1.540 +*
1.541 +* GLP_DN_BRNCH - select down-branch;
1.542 +* GLP_UP_BRNCH - select up-branch;
1.543 +* GLP_NO_BRNCH - use general selection technique. */
1.544 +
1.545 +void glp_ios_branch_upon(glp_tree *tree, int j, int sel)
1.546 +{ if (!(1 <= j && j <= tree->mip->n))
1.547 + xerror("glp_ios_branch_upon: j = %d; column number out of rang"
1.548 + "e\n", j);
1.549 + if (!(sel == GLP_DN_BRNCH || sel == GLP_UP_BRNCH ||
1.550 + sel == GLP_NO_BRNCH))
1.551 + xerror("glp_ios_branch_upon: sel = %d: invalid branch selectio"
1.552 + "n flag\n", sel);
1.553 + if (!(tree->non_int[j]))
1.554 + xerror("glp_ios_branch_upon: j = %d; variable cannot be used t"
1.555 + "o branch upon\n", j);
1.556 + if (tree->br_var != 0)
1.557 + xerror("glp_ios_branch_upon: branching variable already chosen"
1.558 + "\n");
1.559 + tree->br_var = j;
1.560 + tree->br_sel = sel;
1.561 + return;
1.562 +}
1.563 +
1.564 +/***********************************************************************
1.565 +* NAME
1.566 +*
1.567 +* glp_ios_select_node - select subproblem to continue the search
1.568 +*
1.569 +* SYNOPSIS
1.570 +*
1.571 +* void glp_ios_select_node(glp_tree *tree, int p);
1.572 +*
1.573 +* DESCRIPTION
1.574 +*
1.575 +* The routine glp_ios_select_node can be called from the user-defined
1.576 +* callback routine in response to the reason GLP_ISELECT to select an
1.577 +* active subproblem, whose reference number is p. The search will be
1.578 +* continued from the subproblem selected. */
1.579 +
1.580 +void glp_ios_select_node(glp_tree *tree, int p)
1.581 +{ IOSNPD *node;
1.582 + /* obtain pointer to the specified subproblem */
1.583 + if (!(1 <= p && p <= tree->nslots))
1.584 +err: xerror("glp_ios_select_node: p = %d; invalid subproblem refere"
1.585 + "nce number\n", p);
1.586 + node = tree->slot[p].node;
1.587 + if (node == NULL) goto err;
1.588 + /* the specified subproblem must be active */
1.589 + if (node->count != 0)
1.590 + xerror("glp_ios_select_node: p = %d; subproblem not in the act"
1.591 + "ive list\n", p);
1.592 + /* no subproblem must be selected yet */
1.593 + if (tree->next_p != 0)
1.594 + xerror("glp_ios_select_node: subproblem already selected\n");
1.595 + /* select the specified subproblem to continue the search */
1.596 + tree->next_p = p;
1.597 + return;
1.598 +}
1.599 +
1.600 +/***********************************************************************
1.601 +* NAME
1.602 +*
1.603 +* glp_ios_heur_sol - provide solution found by heuristic
1.604 +*
1.605 +* SYNOPSIS
1.606 +*
1.607 +* int glp_ios_heur_sol(glp_tree *tree, const double x[]);
1.608 +*
1.609 +* DESCRIPTION
1.610 +*
1.611 +* The routine glp_ios_heur_sol can be called from the user-defined
1.612 +* callback routine in response to the reason GLP_IHEUR to provide an
1.613 +* integer feasible solution found by a primal heuristic.
1.614 +*
1.615 +* Primal values of *all* variables (columns) found by the heuristic
1.616 +* should be placed in locations x[1], ..., x[n], where n is the number
1.617 +* of columns in the original problem object. Note that the routine
1.618 +* glp_ios_heur_sol *does not* check primal feasibility of the solution
1.619 +* provided.
1.620 +*
1.621 +* Using the solution passed in the array x the routine computes value
1.622 +* of the objective function. If the objective value is better than the
1.623 +* best known integer feasible solution, the routine computes values of
1.624 +* auxiliary variables (rows) and stores all solution components in the
1.625 +* problem object.
1.626 +*
1.627 +* RETURNS
1.628 +*
1.629 +* If the provided solution is accepted, the routine glp_ios_heur_sol
1.630 +* returns zero. Otherwise, if the provided solution is rejected, the
1.631 +* routine returns non-zero. */
1.632 +
1.633 +int glp_ios_heur_sol(glp_tree *tree, const double x[])
1.634 +{ glp_prob *mip = tree->mip;
1.635 + int m = tree->orig_m;
1.636 + int n = tree->n;
1.637 + int i, j;
1.638 + double obj;
1.639 + xassert(mip->m >= m);
1.640 + xassert(mip->n == n);
1.641 + /* check values of integer variables and compute value of the
1.642 + objective function */
1.643 + obj = mip->c0;
1.644 + for (j = 1; j <= n; j++)
1.645 + { GLPCOL *col = mip->col[j];
1.646 + if (col->kind == GLP_IV)
1.647 + { /* provided value must be integral */
1.648 + if (x[j] != floor(x[j])) return 1;
1.649 + }
1.650 + obj += col->coef * x[j];
1.651 + }
1.652 + /* check if the provided solution is better than the best known
1.653 + integer feasible solution */
1.654 + if (mip->mip_stat == GLP_FEAS)
1.655 + { switch (mip->dir)
1.656 + { case GLP_MIN:
1.657 + if (obj >= tree->mip->mip_obj) return 1;
1.658 + break;
1.659 + case GLP_MAX:
1.660 + if (obj <= tree->mip->mip_obj) return 1;
1.661 + break;
1.662 + default:
1.663 + xassert(mip != mip);
1.664 + }
1.665 + }
1.666 + /* it is better; store it in the problem object */
1.667 + if (tree->parm->msg_lev >= GLP_MSG_ON)
1.668 + xprintf("Solution found by heuristic: %.12g\n", obj);
1.669 + mip->mip_stat = GLP_FEAS;
1.670 + mip->mip_obj = obj;
1.671 + for (j = 1; j <= n; j++)
1.672 + mip->col[j]->mipx = x[j];
1.673 + for (i = 1; i <= m; i++)
1.674 + { GLPROW *row = mip->row[i];
1.675 + GLPAIJ *aij;
1.676 + row->mipx = 0.0;
1.677 + for (aij = row->ptr; aij != NULL; aij = aij->r_next)
1.678 + row->mipx += aij->val * aij->col->mipx;
1.679 + }
1.680 + return 0;
1.681 +}
1.682 +
1.683 +/***********************************************************************
1.684 +* NAME
1.685 +*
1.686 +* glp_ios_terminate - terminate the solution process.
1.687 +*
1.688 +* SYNOPSIS
1.689 +*
1.690 +* void glp_ios_terminate(glp_tree *tree);
1.691 +*
1.692 +* DESCRIPTION
1.693 +*
1.694 +* The routine glp_ios_terminate sets a flag indicating that the MIP
1.695 +* solver should prematurely terminate the search. */
1.696 +
1.697 +void glp_ios_terminate(glp_tree *tree)
1.698 +{ if (tree->parm->msg_lev >= GLP_MSG_DBG)
1.699 + xprintf("The search is prematurely terminated due to applicati"
1.700 + "on request\n");
1.701 + tree->stop = 1;
1.702 + return;
1.703 +}
1.704 +
1.705 +/* eof */