Cbc
Cbc copied to clipboard
coin-or
Branch-and-bound node incorrectly pruned by infeasibility
Dear all, I am having some difficulty debugging a somewhat hard-to-trace issue in a cut generation code that I am writing and testing with the Cbc master branch. I believe that I have an instance in which a node of the branch-and-bound tree is incorrectly declared infeasible by Clp called from within Cbc, but this only happens within my code, and not when I try to produce a minimal example.
I have documented the issue (along with a link to the instance and code for my attempt at a minimal example) on my repository: https://github.com/akazachk/vpc/issues/24, but I want to post here in case anyone can offer insights into what might be going wrong, or what I can do to fix it.
This is a somewhat critical bug for me, because I use a partial branch-and-bound tree as the source of a disjunction for cut generation, and if the disjunction is invalid (which would happen when a feasible subtree is incorrectly pruned), then my cuts may be invalid.
Perhaps it is important to say that I set up a custom event handler in my code, and I set some particular options that are intended to improve the partial tree with respect to the eventual cuts I obtain. These options are documented in the bb_example code linked in the issue on my repo, but generally include things like turning off presolve and cuts, as well as employing the CbcBranchDefaultDecision and CbcCompareObjective classes.
Thank you in advance for your help.
On a possibly related note, I am curious about what Cbc reports as the objective value at branch-and-bound nodes (in the status messages): I notice that it can be rather different from the objective value that Clp (or Gurobi) obtains for those same nodes when invoked outside of Cbc.
I assume that Cbc does something approximate like this intentionally to speed up computations, but I am wondering if it is related to the issue I am encountering.
I will send you some updated code for badly scaled problems that may go into master to see if that helps. The problem is obviously difficult - part of statistics for bc1_presolved are -
Elements has 218656 entries 252 between -10 and -1, 252 exactly at -1 28314 between -1 and -0.1 16191 between -0.1 and -0.01 11875 between -0.01 and -0.001 9534 between -0.001 and -0.0001 7613 between -0.0001 and -1e-05 21883 between -1e-05 and -1e-08 12032 between -1e-08 and -1e-11 61 between -1e-11 and -1e-15 9963 between 1e-11 and 1e-08 28001 between 1e-08 and 1e-05 10521 between 1e-05 and 0.0001 12900 between 0.0001 and 0.001 15250 between 0.001 and 0.01 16843 between 0.01 and 0.1 16291 between 0.1 and 1, 814 exactly at 1 65 between 1 and 10 1 between 10 and 100
John Forrest On 24/09/2020 04:33, akazachk wrote:
Dear all, I am having some difficulty debugging a somewhat hard-to-trace issue in a cut generation code that I am writing and testing with the Cbc master branch. I believe that I have an instance in which a node of the branch-and-bound tree is incorrectly declared infeasible by Clp called from within Cbc, but this only happens within my code, and not when I try to produce a minimal example.
I have documented the issue (along with a link to the instance and code for my attempt at a minimal example) on my repository: akazachk/vpc#24 https://github.com/akazachk/vpc/issues/24, but I want to post here in case anyone can offer insights into what might be going wrong, or what I can do to fix it.
This is a somewhat critical bug for me, because I use a partial branch-and-bound tree as the source of a disjunction for cut generation, and if the disjunction is invalid (which would happen when a feasible subtree is incorrectly pruned), then my cuts may be invalid.
Perhaps it is important to say that I set up a custom event handler in my code, and I set some particular options that are intended to improve the partial tree with respect to the eventual cuts I obtain. These options are documented in the bb_example code linked in the issue on my repo, but generally include things like turning off presolve and cuts, as well as employing the |CbcBranchDefaultDecision| and |CbcCompareObjective| classes.
Thank you in advance for your help.
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/coin-or/Cbc/issues/338, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJYHGO5232SQNORGQJTHDSHK4YPANCNFSM4RXY6ADA.
I agree, numerics are an issue here. This is a presolved-by-Gurobi version of bc1 from MIPLIB 2017, which is part of the "numerics" set. I will try the updated code you send.
I find it curious that I am unable to recreate the "infeasible node" with my small example having seemingly identical settings to the ones used in my cut generation code ("vpc" code). Up to node 31, the bb_example code seems to generate a partial tree that is identical to the one in the vpc code, but clearly this is not the case. I first notice a difference in iteration 460 when solving node 31, though maybe there are differences between the two solution processes even earlier than I am detecting them. I am not sure if I am missing a setting, or what else is happening.