Replies: 1 comment 2 replies
-
Hi @ed-lam , Yes, that's a very good point. In general, the question is which node selection rule is best for improving the dual bound ? If the time required to process each node (that is, solving its LP relaxation, mostly) is constant, then worst-dual bound first is the optimal choice. The global dual bound is indeed equal to the worst (local) dual bound of each leaf node in the tree, so processing nodes whose (local) dual bound does not match the global dual bound will never have any immediate effect in terms of global bound improvement. So why not using worst-db first node selection for the competition ? We've discussed that while setting up the challenge, and there is a practical reason that makes a node selection strategy with a diving behavior appealing as well. Immediately solving the LP of a child node is very cheap. Since branching only introduces a new constraint with respect to the parent node (usually a simple variable bound tightening), the LP data structure and solution of the parent node can be reused very efficiently for immediately solving a child node. When SCIP does not dive but instead jumps around the B&B tree, then this nice property is not exploited and it has to basically rebuild and solve every LP from scratch, hence overall it will process much less nodes over time. Another reason for sticking with the current node selection rule is that it is the default rule employed by SCIP for solving real problems in practice, hence it makes sense to not deviate too much from this setting to remain in a somewhat realistic scenario. Those two reasons made us keep SCIP's default node selection rule for evaluation in the dual task. But the question is not entirely settled, so if we realize that the current node selection rule does not allow to distinguish clearly between participants then we might reconsider. Hope that helped clarify things ! Please feel free to share your thoughts and comments, as we gladly appreciate any feedback :) We know the actual setting is not perfect, but that's the best we came up with. Best, |
Beta Was this translation helpful? Give feedback.
-
I'm just looking at the node selection rule in the dual task. It appears to be some kind of depth-first search. In this case, no matter how good your branching rule is, the global dual bound cannot improve if the nodes near the root are still open (in the search frontier). I think using best-first or even breadth-first would be better because the dual task is measuring the improvement in the dual bound.
Beta Was this translation helpful? Give feedback.
All reactions