glpapi12.c

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

/* glpapi12.c (branch-and-bound interface routines) */

/***********************************************************************
*  This code is part of GLPK (GNU Linear Programming Kit).
*
*  Copyright (C) 2000,01,02,03,04,05,06,07,08,2009 Andrew Makhorin,
*  Department for Applied Informatics, Moscow Aviation Institute,
*  Moscow, Russia. All rights reserved. E-mail: <[e-mail]>.
*
*  GLPK is free software: you can redistribute it and/or modify it
*  under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  GLPK is distributed in the hope that it will be useful, but WITHOUT
*  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
*  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
*  License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
***********************************************************************/

#include "glpios.h"

/***********************************************************************
*  NAME
*
*  glp_ios_reason - determine reason for calling the callback routine
*
*  SYNOPSIS
*
*  glp_ios_reason(glp_tree *tree);
*
*  RETURNS
*
*  The routine glp_ios_reason returns a code, which indicates why the
*  user-defined callback routine is being called. */

int glp_ios_reason(glp_tree *tree)
{     return
         tree->reason;
}

/***********************************************************************
*  NAME
*
*  glp_ios_get_prob - access the problem object
*
*  SYNOPSIS
*
*  glp_prob *glp_ios_get_prob(glp_tree *tree);
*
*  DESCRIPTION
*
*  The routine glp_ios_get_prob can be called from the user-defined
*  callback routine to access the problem object, which is used by the
*  MIP solver. It is the original problem object passed to the routine
*  glp_intopt if the MIP presolver is not used; otherwise it is an
*  internal problem object built by the presolver. If the current
*  subproblem exists, LP segment of the problem object corresponds to
*  its LP relaxation.
*
*  RETURNS
*
*  The routine glp_ios_get_prob returns a pointer to the problem object
*  used by the MIP solver. */

glp_prob *glp_ios_get_prob(glp_tree *tree)
{     return
         tree->mip;
}

/***********************************************************************
*  NAME
*
*  glp_ios_tree_size - determine size of the branch-and-bound tree
*
*  SYNOPSIS
*
*  void glp_ios_tree_size(glp_tree *tree, int *a_cnt, int *n_cnt,
*     int *t_cnt);
*
*  DESCRIPTION
*
*  The routine glp_ios_tree_size stores the following three counts which
*  characterize the current size of the branch-and-bound tree:
*
*  a_cnt is the current number of active nodes, i.e. the current size of
*        the active list;
*
*  n_cnt is the current number of all (active and inactive) nodes;
*
*  t_cnt is the total number of nodes including those which have been
*        already removed from the tree. This count is increased whenever
*        a new node appears in the tree and never decreased.
*
*  If some of the parameters a_cnt, n_cnt, t_cnt is a null pointer, the
*  corresponding count is not stored. */

void glp_ios_tree_size(glp_tree *tree, int *a_cnt, int *n_cnt,
      int *t_cnt)
{     if (a_cnt != NULL) *a_cnt = tree->a_cnt;
      if (n_cnt != NULL) *n_cnt = tree->n_cnt;
      if (t_cnt != NULL) *t_cnt = tree->t_cnt;
      return;
}

/***********************************************************************
*  NAME
*
*  glp_ios_curr_node - determine current active subproblem
*
*  SYNOPSIS
*
*  int glp_ios_curr_node(glp_tree *tree);
*
*  RETURNS
*
*  The routine glp_ios_curr_node returns the reference number of the
*  current active subproblem. However, if the current subproblem does
*  not exist, the routine returns zero. */

int glp_ios_curr_node(glp_tree *tree)
{     IOSNPD *node;
      /* obtain pointer to the current subproblem */
      node = tree->curr;
      /* return its reference number */
      return node == NULL ? 0 : node->p;
}

/***********************************************************************
*  NAME
*
*  glp_ios_next_node - determine next active subproblem
*
*  SYNOPSIS
*
*  int glp_ios_next_node(glp_tree *tree, int p);
*
*  RETURNS
*
*  If the parameter p is zero, the routine glp_ios_next_node returns
*  the reference number of the first active subproblem. However, if the
*  tree is empty, zero is returned.
*
*  If the parameter p is not zero, it must specify the reference number
*  of some active subproblem, in which case the routine returns the
*  reference number of the next active subproblem. However, if there is
*  no next active subproblem in the list, zero is returned.
*
*  All subproblems in the active list are ordered chronologically, i.e.
*  subproblem A precedes subproblem B if A was created before B. */

int glp_ios_next_node(glp_tree *tree, int p)
{     IOSNPD *node;
      if (p == 0)
      {  /* obtain pointer to the first active subproblem */
         node = tree->head;
      }
      else
      {  /* obtain pointer to the specified subproblem */
         if (!(1 <= p && p <= tree->nslots))
err:        xerror("glp_ios_next_node: p = %d; invalid subproblem refer"
               "ence number\n", p);
         node = tree->slot[p].node;
         if (node == NULL) goto err;
         /* the specified subproblem must be active */
         if (node->count != 0)
            xerror("glp_ios_next_node: p = %d; subproblem not in the ac"
               "tive list\n", p);
         /* obtain pointer to the next active subproblem */
         node = node->next;
      }
      /* return the reference number */
      return node == NULL ? 0 : node->p;
}

/***********************************************************************
*  NAME
*
*  glp_ios_prev_node - determine previous active subproblem
*
*  SYNOPSIS
*
*  int glp_ios_prev_node(glp_tree *tree, int p);
*
*  RETURNS
*
*  If the parameter p is zero, the routine glp_ios_prev_node returns
*  the reference number of the last active subproblem. However, if the
*  tree is empty, zero is returned.
*
*  If the parameter p is not zero, it must specify the reference number
*  of some active subproblem, in which case the routine returns the
*  reference number of the previous active subproblem. However, if there
*  is no previous active subproblem in the list, zero is returned.
*
*  All subproblems in the active list are ordered chronologically, i.e.
*  subproblem A precedes subproblem B if A was created before B. */

int glp_ios_prev_node(glp_tree *tree, int p)
{     IOSNPD *node;
      if (p == 0)
      {  /* obtain pointer to the last active subproblem */
         node = tree->tail;
      }
      else
      {  /* obtain pointer to the specified subproblem */
         if (!(1 <= p && p <= tree->nslots))
err:        xerror("glp_ios_prev_node: p = %d; invalid subproblem refer"
               "ence number\n", p);
         node = tree->slot[p].node;
         if (node == NULL) goto err;
         /* the specified subproblem must be active */
         if (node->count != 0)
            xerror("glp_ios_prev_node: p = %d; subproblem not in the ac"
               "tive list\n", p);
         /* obtain pointer to the previous active subproblem */
         node = node->prev;
      }
      /* return the reference number */
      return node == NULL ? 0 : node->p;
}

/***********************************************************************
*  NAME
*
*  glp_ios_up_node - determine parent subproblem
*
*  SYNOPSIS
*
*  int glp_ios_up_node(glp_tree *tree, int p);
*
*  RETURNS
*
*  The parameter p must specify the reference number of some (active or
*  inactive) subproblem, in which case the routine iet_get_up_node
*  returns the reference number of its parent subproblem. However, if
*  the specified subproblem is the root of the tree and, therefore, has
*  no parent, the routine returns zero. */

int glp_ios_up_node(glp_tree *tree, int p)
{     IOSNPD *node;
      /* obtain pointer to the specified subproblem */
      if (!(1 <= p && p <= tree->nslots))
err:     xerror("glp_ios_up_node: p = %d; invalid subproblem reference "
            "number\n", p);
      node = tree->slot[p].node;
      if (node == NULL) goto err;
      /* obtain pointer to the parent subproblem */
      node = node->up;
      /* return the reference number */
      return node == NULL ? 0 : node->p;
}

/***********************************************************************
*  NAME
*
*  glp_ios_node_level - determine subproblem level
*
*  SYNOPSIS
*
*  int glp_ios_node_level(glp_tree *tree, int p);
*
*  RETURNS
*
*  The routine glp_ios_node_level returns the level of the subproblem,
*  whose reference number is p, in the branch-and-bound tree. (The root
*  subproblem has level 0, and the level of any other subproblem is the
*  level of its parent plus one.) */

int glp_ios_node_level(glp_tree *tree, int p)
{     IOSNPD *node;
      /* obtain pointer to the specified subproblem */
      if (!(1 <= p && p <= tree->nslots))
err:     xerror("glp_ios_node_level: p = %d; invalid subproblem referen"
            "ce number\n", p);
      node = tree->slot[p].node;
      if (node == NULL) goto err;
      /* return the node level */
      return node->level;
}

/***********************************************************************
*  NAME
*
*  glp_ios_node_bound - determine subproblem local bound
*
*  SYNOPSIS
*
*  double glp_ios_node_bound(glp_tree *tree, int p);
*
*  RETURNS
*
*  The routine glp_ios_node_bound returns the local bound for (active or
*  inactive) subproblem, whose reference number is p.
*
*  COMMENTS
*
*  The local bound for subproblem p is an lower (minimization) or upper
*  (maximization) bound for integer optimal solution to this subproblem
*  (not to the original problem). This bound is local in the sense that
*  only subproblems in the subtree rooted at node p cannot have better
*  integer feasible solutions.
*
*  On creating a subproblem (due to the branching step) its local bound
*  is inherited from its parent and then may get only stronger (never
*  weaker). For the root subproblem its local bound is initially set to
*  -DBL_MAX (minimization) or +DBL_MAX (maximization) and then improved
*  as the root LP relaxation has been solved.
*
*  Note that the local bound is not necessarily the optimal objective
*  value to corresponding LP relaxation; it may be stronger. */

double glp_ios_node_bound(glp_tree *tree, int p)
{     IOSNPD *node;
      /* obtain pointer to the specified subproblem */
      if (!(1 <= p && p <= tree->nslots))
err:     xerror("glp_ios_node_bound: p = %d; invalid subproblem referen"
            "ce number\n", p);
      node = tree->slot[p].node;
      if (node == NULL) goto err;
      /* return the node local bound */
      return node->bound;
}

/***********************************************************************
*  NAME
*
*  glp_ios_best_node - find active subproblem with best local bound
*
*  SYNOPSIS
*
*  int glp_ios_best_node(glp_tree *tree);
*
*  RETURNS
*
*  The routine glp_ios_best_node returns the reference number of the
*  active subproblem, whose local bound is best (i.e. smallest in case
*  of minimization or largest in case of maximization). However, if the
*  tree is empty, the routine returns zero.
*
*  COMMENTS
*
*  The best local bound is an lower (minimization) or upper
*  (maximization) bound for integer optimal solution to the original
*  MIP problem. */

int glp_ios_best_node(glp_tree *tree)
{     return