[Coin-symphony] non-terminating problems

[Ted Ralphs]

Yes, with integer programs, one must be very careful with tolerances.
Occasionally, the LP solver will return solutions that are not within
tolerances because of unscaled infeasibilities. A recent change to the
code caused this situation not to be handled correctly. Release 5.1.7
should fix this problem. Can you give it a try?

Cheers,

Ted

Michael Hennebry wrote:
> 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.
> 


-- 
Dr. Ted Ralphs
Associate Professor
Industrial and Systems Engineering
Lehigh University
(610)758-4784
tkralphs at lehigh.edu
www.lehigh.edu/~tkr2