Tracking nodes pruned by bound and by infeasibility

[akazachk]

Dear all,

I am working on a program to save / print the branch-and-bound tree generated by Cbc, and it would help me to have input about the best way to catch that a node is pruned and the reason for the pruning. More generally, I am trying to collect all the decisions made by Cbc: which node is being explored, which variable is being branched on, etc. My apologies that this post/issue is long, as I try to explain some relevant aspects of accessing Cbc information through CbcEventHandlers here, as I understand them, to be sure I am using everything correctly (if it is useful, I can create a document for reference). In case it is relevant, I do set a few parameters in CbcModel, listed at the bottom of this issue. I am using the Cbc of commit c4a885e.

I think the natural point to collect most of the necessary branching information is at the node CbcEvent, but it seems I am missing some information then.

The current node will not be pruned if the solver is feasible and no integer-feasible solution has been found. Importantly, by the time of the node event, I think it is not necessary (but is it possible?) to check pruning by infeasibility or by bound: if the node LP is infeasible, or if the objective value is below the cutoff, as far as I understand, then (in both cases) the node LP will be declared infeasible at the time it is being solved in CbcModel.cpp::resolve at CbcModel.cpp:14698.* I think this is an important point, and I very well could be misunderstanding, so please correct me if I am wrong.

Checking for node LP feasibility I think is easy:

  !model_->solver()->isProvenPrimalInfeasible()

To check that no integer-feasible solution is found, we have access to newNode (the current potential leaf node being processed in CbcModel.cpp) through model_->currentNode() within our CbcEventHandler. I think that, in addition to the node LP being feasible, one needs to verify that

  (model_->currentNode() != NULL) && (model_->currentNode()->numberUnsatisfied() != 0)

Assuming that is correct, then I know how to handle a node that is not pruned, and the difficulty lies with tracking the pruned ones, and in particular, that I cannot seem to distinguish the case that a node is pruned by bound or by infeasibility. In contrast, I believe I can successfully track a node that is pruned by integrality, but it is also a little tricky.

I would really appreciate any help, and thank you in advance.

-- *Called from the other CbcModel.cpp::resolve at CbcModel.cpp:10608, itself called from CbcModel.cpp::solveWithCuts at CbcModel.cpp:8105, called from CbcModel.cpp::doOneNode at line CbcModel.cpp:16852.

---

To keep consistency with my code, here are the options I set for a given pointer to a CbcModel object cbc_model, though I am not sure how much depends on these choices:

  // Turn off presolve and cuts
  cbc_model->setTypePresolve(0);
  cbc_model->setMaximumCutPassesAtRoot(0);
  cbc_model->setMaximumCutPasses(0);
  cbc_model->setWhenCuts(0);

  // Strong branching options
  const int num_strong = 5;
  const int num_before_trusted = std::numeric_limits<int>::max();
  // Number of hot start iterations (I do not remember what this affects, perhaps strong branching)
  cbc_model->solver()->setIntParam(OsiMaxNumIterationHotStart, 100);
  // Number of strong branching candidates (5 is the default)
  cbc_model->setNumberStrong(num_strong);
  // Continue with strong branching, rather than switching to pseudocosts
  cbc_model->setNumberBeforeTrust(num_before_trusted);

  // The following is *required* to reach treeStatus events correctly in Cbc-2.10+
  cbc_model->setSecsPrintFrequency(-1);

  // Given a branching variable, which direction to choose?
  CbcBranchDecision* branch = new CbcBranchDefaultDecision();
  // Given a tree, which node to pick next?
  CbcCompareBase* compare = new CbcCompareObjective();

  // Install a "chooseMethod" for selection of branching variables
  OsiChooseStrongCustom choose; // this is a custom class but it should work exactly as OsiChooseStrong
  if (num_strong >= 0) {
    choose.setNumberStrong(num_strong);
  }
  if (num_before_trusted > 0) {
    choose.setNumberBeforeTrusted(num_before_trusted);
  }
  branch->setChooseMethod(choose);
  
  // Pass branching options to cbc_model
  cbc_model->setBranchingMethod(*branch);
  cbc_model->setNodeComparison(compare);

  // Lastly, pass in an event handler, say it is a class "MyCbcEventHandler"
  MyCbcEventHandler* eventHandler = new MyCbcEventHandler;
  cbc_model->passInEventHandler(eventHandler);

Lastly, in my code, I add an exit condition based on a maximum allowable number of open leaf nodes in the tree, but I guess it is mostly equivalent to set a bound on explored nodes:

  cbc_model->setMaximumNodes( ... );

Both with that option and with a time limit, there is an extra complication of catching Cbc before it goes to the endSearch CbcEvent, since by that event, the user has no access to information about the tree, since tree_->endSearch() is called at CbcModel.cpp:5145 before the CbcEventHandler::endSearch call a few lines later.

[jjhforrest]

When a subproblem is solved, it may end up being solved by the dual algorithm or the primal algorithm. The dual algorithm returns infeasible immediately the bound is violated, so there is no sensible way to tell the difference.

I would suggest that the #ifdef SAVE_NODE_INFO be changed to #ifdef COIN_MORE_INFORMATION and add more event handlers if that is defined.

I am assuming you are using OsiClp so you could pass in a ClpEventHandler and add -

startOfResolve, endOfResolve at beginning and end of OsiClpSolverInterface::resolve (and similar for other solves).

Then you could set the dual bound to infinity at start. At end you could then test objective value to set infeasible.

As nodes can also be pruned by cut generators and strong branching you may need yet more events (and to test at end of search). Feel free to suggest more CbcEventHandler events to be activated on -DCOIN_MORE_INFORMATION.

John Forrest

[akazachk]

Thank you for clarifying, I had suspected that a ClpEventHandler would be a potential solution (I am indeed using OsiClp, I should have said that before), but I was hoping there was some hidden status I could query.

I would suggest that the #ifdef SAVE_NODE_INFO be changed to #ifdef COIN_MORE_INFORMATION and add more event handlers if that is defined.

I think perhaps longer term, what you suggest would be a good idea, but maybe in the short term, after Cbc finishes, I can set up the LP at each pruned node and manually check feasibility.

For that, I have to properly track all the bound changes to get to that node (including bounds modified during branching and during strong branching), which I think I have already implemented almost successfully. When the node is not pruned, I recover changed bounds within the node CbcEvent, by querying the current bounds in model_->solver() (with respect to the original LP bounds, that I have saved), which I think is the right approach. Maybe this works even when the node is pruned.

As nodes can also be pruned by cut generators and strong branching you may need yet more events (and to test at end of search).

For the cut generators, I turn them off for now, but I agree that eventually I would need to catch those cases.

For strong branching, I think I have the pruning by integrality case somewhat handled at the moment, through the beforeSolution2 CbcEvent when a new best solution is installed from within CbcNode.cpp::chooseOsiBranch at line CbcNode.cpp:6023. On the other hand, I probably do not correctly capture pruning by bound or infeasibility if strong branching changes bounds.

Finally, I try to be careful with getting all information before the end of search, because the tree is cleared before the CbcEventHandler::endSearch event, due to the tree_->endSearch() called at CbcModel.cpp:5145.