glpapi12.c

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

         ios_best_node(tree);
}

/***********************************************************************
*  NAME
*
*  glp_ios_mip_gap - compute relative MIP gap
*
*  SYNOPSIS
*
*  double glp_ios_mip_gap(glp_tree *tree);
*
*  DESCRIPTION
*
*  The routine glp_ios_mip_gap computes the relative MIP gap with the
*  following formula:
*
*     gap = |best_mip - best_bnd| / (|best_mip| + DBL_EPSILON),
*
*  where best_mip is the best integer feasible solution found so far,
*  best_bnd is the best (global) bound. If no integer feasible solution
*  has been found yet, gap is set to DBL_MAX.
*
*  RETURNS
*
*  The routine glp_ios_mip_gap returns the relative MIP gap. */

double glp_ios_mip_gap(glp_tree *tree)
{     return
         ios_relative_gap(tree);
}

/***********************************************************************
*  NAME
*
*  glp_ios_node_data - access subproblem application-specific data
*
*  SYNOPSIS
*
*  void *glp_ios_node_data(glp_tree *tree, int p);
*
*  DESCRIPTION
*
*  The routine glp_ios_node_data allows the application accessing a
*  memory block allocated for the subproblem (which may be active or
*  inactive), whose reference number is p.
*
*  The size of the block is defined by the control parameter cb_size
*  passed to the routine glp_intopt. The block is initialized by binary
*  zeros on creating corresponding subproblem, and its contents is kept
*  until the subproblem will be removed from the tree.
*
*  The application may use these memory blocks to store specific data
*  for each subproblem.
*
*  RETURNS
*
*  The routine glp_ios_node_data returns a pointer to the memory block
*  for the specified subproblem. Note that if cb_size = 0, the routine
*  returns a null pointer. */

void *glp_ios_node_data(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 pointer to the application-specific data */
      return node->data;
}

/***********************************************************************
*  NAME
*
*  glp_ios_row_attr - retrieve additional row attributes
*
*  SYNOPSIS
*
*  void glp_ios_row_attr(glp_tree *tree, int i, glp_attr *attr);
*
*  DESCRIPTION
*
*  The routine glp_ios_row_attr retrieves additional attributes of row
*  i and stores them in the structure glp_attr. */

void glp_ios_row_attr(glp_tree *tree, int i, glp_attr *attr)
{     GLPROW *row;
      if (!(1 <= i && i <= tree->mip->m))
         xerror("glp_ios_row_attr: i = %d; row number out of range\n",
            i);
      row = tree->mip->row[i];
      attr->level = row->level;
      attr->origin = row->origin;
      attr->klass = row->klass;
      return;
}

/**********************************************************************/

int glp_ios_pool_size(glp_tree *tree)
{     /* determine current size of the cut pool */
      if (tree->reason != GLP_ICUTGEN)
         xerror("glp_ios_pool_size: operation not allowed\n");
      xassert(tree->local != NULL);
      return tree->local->size;
}

/**********************************************************************/

int glp_ios_add_row(glp_tree *tree,
      const char *name, int klass, int flags, int len, const int ind[],
      const double val[], int type, double rhs)
{     /* add row (constraint) to the cut pool */
      int num;
      if (tree->reason != GLP_ICUTGEN)
         xerror("glp_ios_add_row: operation not allowed\n");
      xassert(tree->local != NULL);
      num = ios_add_row(tree, tree->local, name, klass, flags, len,
         ind, val, type, rhs);
      return num;
}

/**********************************************************************/

void glp_ios_del_row(glp_tree *tree, int i)
{     /* remove row (constraint) from the cut pool */
      if (tree->reason != GLP_ICUTGEN)
         xerror("glp_ios_del_row: operation not allowed\n");
      ios_del_row(tree, tree->local, i);
      return;
}

/**********************************************************************/

void glp_ios_clear_pool(glp_tree *tree)
{     /* remove all rows (constraints) from the cut pool */
      if (tree->reason != GLP_ICUTGEN)
         xerror("glp_ios_clear_pool: operation not allowed\n");
      ios_clear_pool(tree, tree->local);
      return;
}

/***********************************************************************
*  NAME
*
*  glp_ios_can_branch - check if can branch upon specified variable
*
*  SYNOPSIS
*
*  int glp_ios_can_branch(glp_tree *tree, int j);
*
*  RETURNS
*
*  If j-th variable (column) can be used to branch upon, the routine
*  glp_ios_can_branch returns non-zero, otherwise zero. */

int glp_ios_can_branch(glp_tree *tree, int j)
{     if (!(1 <= j && j <= tree->mip->n))
         xerror("glp_ios_can_branch: j = %d; column number out of range"
            "\n", j);
      return tree->non_int[j];
}

/***********************************************************************
*  NAME
*
*  glp_ios_branch_upon - choose variable to branch upon
*
*  SYNOPSIS
*
*  void glp_ios_branch_upon(glp_tree *tree, int j, int sel);
*
*  DESCRIPTION
*
*  The routine glp_ios_branch_upon can be called from the user-defined
*  callback routine in response to the reason GLP_IBRANCH to choose a
*  branching variable, whose ordinal number is j. Should note that only
*  variables, for which the routine glp_ios_can_branch returns non-zero,
*  can be used to branch upon.
*
*  The parameter sel is a flag that indicates which branch (subproblem)
*  should be selected next to continue the search:
*
*  GLP_DN_BRNCH - select down-branch;
*  GLP_UP_BRNCH - select up-branch;
*  GLP_NO_BRNCH - use general selection technique. */

void glp_ios_branch_upon(glp_tree *tree, int j, int sel)
{     if (!(1 <= j && j <= tree->mip->n))
         xerror("glp_ios_branch_upon: j = %d; column number out of rang"
            "e\n", j);
      if (!(sel == GLP_DN_BRNCH || sel == GLP_UP_BRNCH ||
            sel == GLP_NO_BRNCH))
         xerror("glp_ios_branch_upon: sel = %d: branch selection flag i"
            "nvalid\n", sel);
      if (!(tree->non_int[j]))
         xerror("glp_ios_branch_upon: j = %d; variable cannot be used t"
            "o branch upon\n", j);
      if (tree->br_var != 0)
         xerror("glp_ios_branch_upon: branching variable already chosen"
            "\n");
      tree->br_var = j;
      tree->br_sel = sel;
      return;
}

/***********************************************************************
*  NAME
*
*  glp_ios_select_node - select subproblem to continue the search
*
*  SYNOPSIS
*
*  void glp_ios_select_node(glp_tree *tree, int p);
*
*  DESCRIPTION
*
*  The routine glp_ios_select_node can be called from the user-defined
*  callback routine in response to the reason GLP_ISELECT to select an
*  active subproblem, whose reference number is p. The search will be
*  continued from the subproblem selected. */

void glp_ios_select_node(glp_tree *tree, int p)
{     IOSNPD *node;
      /* obtain pointer to the specified subproblem */
      if (!(1 <= p && p <= tree->nslots))
err:     xerror("glp_ios_select_node: p = %d; invalid subproblem refere"
            "nce 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_select_node: p = %d; subproblem not in the act"
            "ive list\n", p);
      /* no subproblem must be selected yet */
      if (tree->btrack != NULL)
         xerror("glp_ios_select_node: subproblem already selected\n");
      /* select the specified subproblem to continue the search */
      tree->btrack = node;
      return;
}

/***********************************************************************
*  NAME
*
*  glp_ios_heur_sol - provide solution found by heuristic
*
*  SYNOPSIS
*
*  int glp_ios_heur_sol(glp_tree *tree, const double x[]);
*
*  DESCRIPTION
*
*  The routine glp_ios_heur_sol can be called from the user-defined
*  callback routine in response to the reason GLP_IHEUR to provide an
*  integer feasible solution found by a primal heuristic.
*
*  Primal values of *all* variables (columns) found by the heuristic
*  should be placed in locations x[1], ..., x[n], where n is the number
*  of columns in the original problem object. Note that the routine
*  glp_ios_heur_sol *does not* check primal feasibility of the solution
*  provided.
*
*  Using the solution passed in the array x the routine computes value
*  of the objective function. If the objective value is better than the
*  best known integer feasible solution, the routine computes values of
*  auxiliary variables (rows) and stores all solution components in the
*  problem object.
*
*  RETURNS
*
*  If the provided solution is accepted, the routine glp_ios_heur_sol
*  returns zero. Otherwise, if the provided solution is rejected, the
*  routine returns non-zero. */

int glp_ios_heur_sol(glp_tree *tree, const double x[])
{     glp_prob *mip = tree->mip;
      int m = tree->orig_m;
      int n = tree->n;
      int i, j;
      double obj;
      xassert(mip->m >= m);
      xassert(mip->n == n);
      /* check values of integer variables and compute value of the
         objective function */
      obj = mip->c0;
      for (j = 1; j <= n; j++)
      {  GLPCOL *col = mip->col[j];
         if (col->kind == GLP_IV)
         {  /* provided value must be integral */
            if (x[j] != floor(x[j])) return 1;
         }
         obj += col->coef * x[j];
      }
      /* check if the provided solution is better than the best known
         integer feasible solution */
      if (mip->mip_stat == GLP_FEAS)
      {  switch (mip->dir)
         {  case GLP_MIN:
               if (obj >= tree->mip->mip_obj) return 1;
               break;
            case GLP_MAX:
               if (obj <= tree->mip->mip_obj) return 1;
               break;
            default:
               xassert(mip != mip);
         }
      }
      /* it is better; store it in the problem object */
      if (tree->parm->msg_lev >= GLP_MSG_ON)
         xprintf("Solution found by heuristic: %.12g\n", obj);
      mip->mip_stat = GLP_FEAS;
      mip->mip_obj = obj;
      for (j = 1; j <= n; j++)
         mip->col[j]->mipx = x[j];
      for (i = 1; i <= m; i++)
      {  GLPROW *row = mip->row[i];
         GLPAIJ *aij;
         row->mipx = 0.0;
         for (aij = row->ptr; aij != NULL; aij = aij->r_next)
            row->mipx += aij->val * aij->col->mipx;
      }
      return 0;
}

/***********************************************************************
*  NAME
*
*  glp_ios_terminate - terminate the solution process.
*
*  SYNOPSIS
*
*  void glp_ios_terminate(glp_tree *tree);
*
*  DESCRIPTION
*
*  The routine glp_ios_terminate sets a flag indicating that the MIP
*  solver should prematurely terminate the search. */

void glp_ios_terminate(glp_tree *tree)
{     if (tree->parm->msg_lev >= GLP_MSG_DBG)
         xprintf("The search is prematurely terminated due to applicati"
            "on request\n");
      tree->terminate = 1;
      return;
}

/* eof */