glpios03.c

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

         /* some local bound for the current subproblem might be set
            before, so we should only improve it */
         bound = ios_round_bound(tree, bound);
         if (mip->dir == GLP_MIN)
         {  if (tree->curr->bound < bound)
               tree->curr->bound = bound;
         }
         else if (mip->dir == GLP_MAX)
         {  if (tree->curr->bound > bound)
               tree->curr->bound = bound;
         }
         else
            xassert(mip != mip);
         if (tree->parm->msg_lev >= GLP_MSG_DBG)
            xprintf("Local bound is %.9e\n", bound);
      }
#endif
      /* if the local bound indicates that integer optimal solution of
         the current subproblem cannot be better than the global bound,
         prune the branch */
      if (!is_branch_hopeful(tree, p))
      {  if (tree->parm->msg_lev >= GLP_MSG_DBG)
            xprintf("Current branch is hopeless and can be pruned\n");
         goto fath;
      }
      /* call the user-defined callback routine to generate additional
         rows ("lazy" constraints) */
      if (tree->parm->cb_func != NULL)
      {  /*int old_m = mip->m;*/
         xassert(tree->reason == 0);
         tree->reason = GLP_IROWGEN;
         tree->parm->cb_func(tree, tree->parm->cb_info);
         tree->reason = 0;
         if (tree->terminate)
         {  ret = GLP_ESTOP;
            goto done;
         }
#if 0
         if (mip->m != old_m)
         {  int nrs = mip->m - old_m;
            xassert(nrs > 0);
            if (tree->parm->msg_lev >= GLP_MSG_DBG)
            {  if (nrs == 1)
                  xprintf("One row has been generated\n");
               else
                  xprintf("%d rows have been generated\n", nrs);
            }
            goto more;
         }
#else
         if (tree->reopt)
         {  tree->reopt = 0;
            goto more;
         }
#endif
      }
      /* check if the basic solution is integer feasible */
      check_integrality(tree);
      /* if the basic solution satisfies to all integrality conditions,
         it is a new, better integer feasible solution */
      if (tree->curr->ii_cnt == 0)
      {  if (tree->parm->msg_lev >= GLP_MSG_DBG)
            xprintf("New integer feasible solution found\n");
         record_solution(tree);
         if (tree->parm->msg_lev >= GLP_MSG_ON)
            show_progress(tree, 1);
         write_sol(tree);
#if 0
         display_cut_info(tree);
#else
         xassert(display_cut_info == display_cut_info);
#endif
         /* call the user-defined callback routine to make it happy */
         if (tree->parm->cb_func != NULL)
         {  xassert(tree->reason == 0);
            tree->reason = GLP_IBINGO;
            tree->parm->cb_func(tree, tree->parm->cb_info);
            tree->reason = 0;
            if (tree->terminate)
            {  ret = GLP_ESTOP;
               goto done;
            }
         }
         /* the current subproblem is fathomed; prune its branch */
         goto fath;
      }
      /* basic solution of LP relaxation of the current subproblem is
         integer infeasible */
      /* try to fix some non-basic structural variables of integer kind
         on their current bounds using reduced costs */
      if (mip->mip_stat == GLP_FEAS)
         fix_by_red_cost(tree);
#if 0
//      if (tree->just_selected && tree->solved == 1)
      if (tree->curr->level % 10 == 0 && tree->solved == 1)
      {  double *x = xcalloc(1+tree->mip->n, sizeof(double));
         if (fpump(tree->mip, x) == 0)
            glp_ios_heur_sol(tree, x);
         xfree(x);
      }
#endif
      /* call the user-defined callback routine to find solution with
         primal heuristic */
      if (tree->parm->cb_func != NULL)
      {  xassert(tree->reason == 0);
         tree->reason = GLP_IHEUR;
         tree->parm->cb_func(tree, tree->parm->cb_info);
         tree->reason = 0;
         if (tree->terminate)
         {  ret = GLP_ESTOP;
            goto done;
         }
         /* check if the current branch became hopeless */
         if (!is_branch_hopeful(tree, p))
         {  if (tree->parm->msg_lev >= GLP_MSG_DBG)
               xprintf("Current branch became hopeless and can be prune"
                  "d\n");
            goto fath;
         }
      }
      tree->round++;
      /*** cut generation ***/
      xassert(tree->local != NULL);
      xassert(tree->local->size == 0);
      /* try to generate generic cuts with built-in generators */
      xassert(tree->reason == 0);
      tree->reason = GLP_ICUTGEN;
      generate_cuts(tree);
      tree->reason = 0;
      /* call the user-defined callback routine to generate cuts;
         note that it can add cuts either to the local cut pool or
         directly to the current subproblem */
      if (tree->parm->cb_func != NULL)
      {  xassert(tree->reason == 0);
         tree->reason = GLP_ICUTGEN;
         tree->parm->cb_func(tree, tree->parm->cb_info);
         tree->reason = 0;
         if (tree->terminate)
         {  ret = GLP_ESTOP;
            goto done;
         }
      }
      /* if the local cut pool is not empty, select useful cuts and add
         them to the current subproblem */
      if (tree->local->size > 0)
      {  xassert(tree->reason == 0);
         tree->reason = GLP_ICUTGEN;
         separation(tree);
         tree->reason = 0;
      }
      /* clear the local cut pool */
      ios_clear_pool(tree, tree->local);
      /* perform reoptimization, if necessary */
      if (tree->reopt)
      {  tree->reopt = 0;
         goto more;
      }
      /*** end of cut generation ***/
#if 1
      tree->just_selected = 0;
#endif
      /* call the user-defined callback routine to choose branching
         variable */
      if (tree->parm->cb_func != NULL)
      {  xassert(tree->reason == 0);
         xassert(tree->br_var == 0);
         xassert(tree->br_sel == 0);
         tree->reason = GLP_IBRANCH;
         tree->parm->cb_func(tree, tree->parm->cb_info);
         tree->reason = 0;
         if (tree->terminate)
         {  ret = GLP_ESTOP;
            goto done;
         }
      }
      /* if no branching variable has been chosen, use the technique
         specified by corresponding control parameter */
      if (tree->br_var == 0)
      {  switch (tree->parm->br_tech)
         {  case GLP_BR_FFV:
               /* branch on first fractional variable */
               branch_first(tree);
               break;
            case GLP_BR_LFV:
               /* branch on last fractional variable */
               branch_last(tree);
               break;
            case GLP_BR_MFV:
               /* branch on most fractional variable */
               branch_mostf(tree);
               break;
            case GLP_BR_DTH:
               /* branch using the heuristic by Dreebeck and Tomlin */
               branch_drtom(tree);
               break;
            case GLP_BR_HPC:
               /* hybrid pseudocost branching */
               ios_pcost_branch(tree);
               break;
            default:
               xassert(tree != tree);
         }
      }
      /* perform actual branching */
      ret = branch_on(tree);
      tree->br_var = 0;
      tree->br_sel = 0;
      if (ret == 0)
      {  if (tree->curr == NULL)
         {  /* next subproblem is not specified; use a general
               selection technique */
            goto back;
         }
         else
         {  /* continue the search from the subproblem which begins
               down- or up-branch (it has been revived by the branching
               routine) */
            goto loop;
         }
      }
      else if (ret == 1)
         goto more;
      else if (ret == 2)
         goto fath;
      else
         xassert(ret != ret);
fath: /* the current subproblem has been fathomed */
      if (tree->parm->msg_lev >= GLP_MSG_DBG)
         xprintf("Node %d fathomed\n", p);
      /* freeze the current subproblem */
      ios_freeze_node(tree);
      /* and prune the corresponding branch of the tree */
      ios_delete_node(tree, p);
      /* if a new integer feasible solution has just been found, other
         branches may become hopeless and therefore should be pruned */
      if (mip->mip_stat == GLP_FEAS) cleanup_the_tree(tree);
#if 1
      goto back;
#else
      /* if the active list is empty, the search is finished */
      if (tree->head == NULL)
      {  if (tree->parm->msg_lev >= GLP_MSG_DBG)
            xprintf("Active list is empty!\n");
         xassert(dmp_in_use(tree->pool).lo == 0);
         ret = 0;
         goto done;
      }
      /* perform backtracking */
      switch (tree->bt_tech)
      {  case GLP_BT_DFS:
            /* depth first search */
            xassert(tree->tail != NULL);
            ios_revive_node(tree, tree->tail->p);
            break;
         case GLP_BT_BFS:
            /* breadth first search */
            xassert(tree->head != NULL);
            ios_revive_node(tree, tree->head->p);
            break;
         case GLP_BT_BLB:
            /* select node with best local bound */
            ios_revive_node(tree, ios_best_node(tree));
            break;
         case GLP_BT_BPH:
            if (mip->mip_stat == GLP_UNDEF)
            {  /* "most integer feasible" subproblem */
               btrack_most_feas(tree);
            }
            else
            {  /* best projection heuristic */
               btrack_best_proj(tree);
            }
            break;
         default:
            xassert(tree != tree);
      }
      /* continue the search from the subproblem selected */
      goto loop;
#endif
done: /* display status of the search on exit from the solver */
      if (tree->parm->msg_lev >= GLP_MSG_ON)
         show_progress(tree, 0);
#if 1
      if (tree->mir_gen != NULL)
         ios_mir_term(tree->mir_gen), tree->mir_gen = NULL;
      if (tree->clq_gen != NULL)
         ios_clq_term(tree->clq_gen), tree->clq_gen = NULL;
#endif
      /* return to the calling program */
      return ret;
}

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

#define cut_factor 0.30
#define max_pool 10
#define ub_min_eff 0.02
#define max_par 0.1

#define first_attempt (tree->first_attempt)
#define max_added_cuts (tree->max_added_cuts)
#define min_eff (tree->min_eff)
#define miss (tree->miss)
#define just_selected (tree->just_selected)

static void generate_cuts(glp_tree *tree)
{     /* generate generic cuts */
      if (first_attempt)
      {  first_attempt = 0;
         max_added_cuts = tree->mip->n;
#if 1
         if (max_added_cuts < 1000) max_added_cuts = 1000;
#endif
      }
      if (!(tree->parm->mir_cuts == GLP_ON ||
            tree->parm->gmi_cuts == GLP_ON ||
            tree->parm->cov_cuts == GLP_ON ||
            tree->parm->clq_cuts == GLP_ON)) goto done;
      if (tree->curr->level > 0 && !just_selected) goto done;
      /* if added_cuts >= max_added_cuts then return */
#if 1 /* 20/IX-2008 */
      {  int i, added_cuts = 0;
         for (i = tree->orig_m+1; i <= tree->mip->m; i++)
         {  if (tree->mip->row[i]->origin == GLP_RF_CUT)
               added_cuts++;
         }
         /* xprintf("added_cuts = %d\n", added_cuts); */
         if (added_cuts >= max_added_cuts) goto done;
      }
#endif
      /* add to POOL all cuts violated by x* */
      if (tree->parm->gmi_cuts == GLP_ON)
      {  if (tree->round <= 5)
            ios_gmi_gen(tree);
      }
      if (tree->parm->mir_cuts == GLP_ON)
      {  xassert(tree->mir_gen != NULL);
         ios_mir_gen(tree, tree->mir_gen);
      }
      if (tree->parm->cov_cuts == GLP_ON)
      {  /* cover cuts works well along with mir cuts */
         /*if (tree->round <= 5)*/
            ios_cov_gen(tree);
      }
      if (tree->parm->clq_cuts == GLP_ON)
      {  if (tree->clq_gen != NULL)
         {  if (tree->curr->level == 0 && tree->round <= 50 ||
                tree->curr->level >  0 && tree->round <= 5)