[Coin-symphony] non-terminating problems

[Mark Williams]

Yes, thanks, it does fix the problem.

Im still seeing some non-terminating cases, but they appear to be a different issue - Im still investigating.

Thanks,

Mark Williams


On 12/21/2007 10:55 AM, Ted Ralphs wrote:
> 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.
>>
> 
>