[Coin-symphony] non-terminating problems

[Mark Williams]

I've built the symphony (5.1.5) application out of the box.

I have a number of models that simply dont terminate. They dont even find a feasible solution.

After a while in the debugger, I think I know why.

Once it gets stuck, it says:

> Cuts in the local pool: 0
> 
> 
> In iteration 1107, before calling branch()
> ... no cuts were added.
> Now displaying final relaxed solution...
> 
> No branching candidates found using default rule...
> Continue with this node.

at each iteration. And it gets nowhere.

When it checks for feasibility, it uses the default TEST_INTEGRALITY setting. There are a number of nodes whose values are around -1e-6, so this fails.

When it goes into the cut generator, all of these variables have bounds of [0,1], so as far as CglProbing is concerned, none of these variables needs to be integerized (because it clamps each var to lb if its less than lb+epsilon, and to ub if its greater than ub-epsilon).

And indeed, if I take the solution and round all the variables to integers, it *is* feasible (and I would imagine optimal too).

So the problem appears to be that the rounding error in the lp solution is greater than the integer tolerance.

One workaround would be to supply my own user_is_feasible function, and check for this condition; but Im not sure I can get at the current bounds for each variable (I can access the bounds specified by the problem, but Im thinking that symphony may have tightened them - so eg the initial problem bounds may be [-1,2], the current bounds may be [0,1], and the variable's value may be -1e-6). Of course, I could just use a larger epstol when checking the bounds - but then I have the problem of determining the correct value.

The correct fix would seem to be to clamp all the solution values to their bounds whenever dual_simplex returns LP_OPTIMAL.

Any insights would be appreciated.

Thanks

Mark Williams