Getting the reason why a node in SCIP was pruned

Question

I've implemented a Branch-and-Cut algorithm using SCIP in C++. My optimization problem has a minimization objective function and currently my code have a bug that I'm struggling to fix it. My problem has an optimal value of 100, but the program returns 101. Looking at the Branch-and-Bound tree (using the visualization tools), I see that SCIP is prunning a node with LP bound 100. Moreover, after some further investigations, I found that indeed, the optimal solution with value 100 should be feasible for this node. I also confirmed that this node is not being prunned by my custom constraint handler. Thus, in order to debug this, I was looking for a way to find out why SCIP prunned this specific node, is there a way of doing this?

I've already tried using the "debug solution" feature, but since I have custom branching rules, it is not working properly. Every time it branches, it reports that my input solution (the optimal one) violates one of the branching inequalities. Moreover, it is not reporting any information on why the problematic node was prunned. Also, when I create the constraint for branching, I set the check flag to FALSE.

Thank you very much for your time and I'd appreciate any comments on this subject.

edit: I'm also locking the variables in my custom constraint handler, so that SCIP will not fix some variables incorrectly.

Answer 1

Ah, I found your question on the mailing list. I looked into the code for checking debug solutions, and I think there is a bug in the way SCIP treats branching constraints wrt to the debug solution (probably because nobody used branching constraints with the debug solution feature). Only the bound changes are checked, not the branching constraints, to determine if the debug solution is relevant for that node. The isSolutionInNode method would need to be extended to also account for node->conssetchg. Unfortunately, that means you cannot use the debug solution feature to hunt down your bug.

Just to make sure, right now your branching inequalities say that the sum is either exactly 2 or at least 4, is this correct? (since you wrote at most 2) Why is this a valid disjunction for the problem you are solving?

If you are completely stuck at this point, but not comfortable enough within SCIP to extend the isSolutionNode yourself I can try to code a patch for you.