Unit test fails with some compile options (bad CglFlowCover cut) - found after looking at Cbc entry in Wikipedia!!!!!!!!!!!!

[jjhforrest]

I will discuss my reference to Wikipedia in another issue - but for now ..

I was trying many different compile options for Cbc and for one of them a standard unit test failed with a bad result for miplib/mod011.
I tracked it down to a bad cut generated by CglFlowCover. I am not an expert in flow cover cuts, but when lifting a cut the code looks at the variable upper bounds of continuous variables. So if z is a variable upper bound on continuous variable x then the coefficient for x in the cut may be replaced by some multiple of z. If another continuous variable y also has z as its variable upper bound then there is some extra computation. It is this that causes a bad cut to be generated.

This duplication rarely happens. It would be easy to skip generating the cut - but can some expert in the flow cover cut code look at CglFlowCover and see if there might be an error.

I was using master. For a very bold person I attach the file used to build Cbc. With my normal options the error does not occur.

convanilla.txt

[jjhforrest]

I can see the bug. When a coefficient in cut is lifted then a coefficient is added but also the rhs is changed.

  xCoef[i] = -movement;
  cutRHS -= movement;

If there is a duplicate vub then the coefficients are added in cut. BUT the rhs has been modified twice. If the solution value of vub variable is 0.0 this is obviously incorrect as the rhs is totally wrong.

The fix is
++ b/src/CglFlowCover/CglFlowCover.cpp
@@ -1167,6 +1167,8 @@ CglFlowCover::generateOneFlowCut( const OsiSolverInterface & si,
lastInd=cutInd[i];
} else {
lastCoef += cutCoef[i];

•   // but take off rhs part which has now been added twice
  

•   cutRHS -= cutCoef[i];
   }
  

  That fixes problem but can someone check it.

Also some of the coding seems slow - speeding it up would also allow a slightly more elegant fix

[jhmgoossens]

Interesting reading! Any idea why this only seems to occur with special compile options? Different preprocessing etc.?

While you’re at it, could you add a unit test to the flow cover test file that now passes with your fix, but consistently fails an assert with the original code?
Maybe such a detailed unit test is not that simple.

[jjhforrest]

Still not sure my possible fix is correct - but you should be able to reproduce. I saved model just before problems - saved as onopt_83.mps

If I run
cbc onopt_83.mps -preprocess off -flowcover root -heuristic off -solve

the code gets wrong answer.

my build parameters were simple - condebug.txt and you get correct solution with -flowcover off

condebug.txt

onopt_83.mps.txt