[Coin-symphony] non-terminating problems

[Michael Hennebry]

On Wed, 19 Dec 2007, Mark Williams wrote:

> > 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.

What I have done, many releases ago, with all-integer constraints,
is to calculate instance-specific tolerances.
The tolerances were selected to ensure that if I had an approximate
all-integer solution, rounding would not destroy feasibility.
That was why I needed all-integer data.
I could round, check whether it should be the new incumbent, and cut it off.

-- 
Michael   hennebry at web.cs.ndsu.NoDak.edu
"I AM DEATH, NOT TAXES.  *I* TURN UP ONLY ONCE."  --  Death