1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/src/glpapi13.c	Sun Nov 06 20:59:10 2011 +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, 2011 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 */