Branch and Price generates already active columns

[guilhemdupuis]

Hello to all,

With the generalized assignment problem demo provided on GitHub, some columns appears to be generated multiple times. I get the following warning for most of the new columns, except during the resolution of the first node:
┌ Warning: Column already exists as MC_4000663 and is already active.
└ @ Coluna.Algorithm ~/.julia/packages/Coluna/OqFqT/src/Algorithm/colgen.jl:193

I used the model provided with the demos on GitHub, on the instance gapC-5-100. Model and dataset can be found at
https://covid19.framadrop.org/r/6vFxjdD226#Hqayehtwz0hbT0vTiCDmkh9vyLyWC6f1ouBURYgRJBM=

Environment:
Julia => 1.3.1
"Coluna" => v"0.3.0"
"GLPK" => v"0.12.1"
"BlockDecomposition" => v"1.2.0"
"MathOptInterface" => v"0.9.13"
"JuMP" => v"0.21.2"
OS: MacOs

Best regards,

Guilhem

[guimarqu]

Hi Guilhem,

It's because how we check if a column has negative reduced cost.
The reduced cost must be less than -1e-8. It's too small and some columns may be generated several times because of floating point approximations.

We should let the user decide the threshold.

[RodolpheGriset]

Thanks for your quick answer Guillaume, That's what we thought but we've prefered to be sur

[guilhemdupuis]

Thanks for the explanation.