[Scip] Simple but wired problem with SCIP

[Gerald Gamrath]

tl;dr: I second Michaels analysis: big-M's are too big, in particular 
with presolving disabled

Hi Mahdi,

when solving your LP file using SCIP wth default settings, I get the 
correct result. However, when I disable presolving, I also get the wrong 
solution which sets all y variables to 0. As Micha pointed out, by 
defining the constraints to be modifiable, you disable presolving, so 
you also get the wrong result.

The reason for this are the huge big-M coefficients of your y-variables 
in the open_facility constraints. As Micha already said, this can cause 
numerical troubles, as is the case here. When computing with floating 
point arithmetics, you usually use an epsilon for comparing values. In 
SCIP, every value in (-1e-09,1e-09) is regarded to be zero. On the other 
hand, the LP solver will set the y-variable so that they are just 
sufficient to fulfill the open_facility constraints, in particular, it 
can set one x-variable to 1 in each of the constraints and set the y 
variable to 1/2147483647, which is smaller than 1e-09 and is later 
interpreted as zero. This is the reason why big-M formulations are 
numerically tricky and you have to be very careful about the selection 
of the big-M.

During presolving, SCIP disaggregates the big-M constraint, enforcing 
that y has be set to 1 if any of the x variables is set to 1 (which 
leads to a tighter relaxation even compared to using a big-M of 
num_cust). That is why the problem does not occur with presolving 
elabled. But also without that presolving step, the problem is solved 
correctly as long as your big-M's have a reasonable size.

Best,
Gerald

Am 21.05.2013 15:26, schrieb michael.winkler at zib.de:
> Hi Mahdi,
>
> I did not and cannot compile your file.
>
> But I looked at your code and as you said, you want to B&B or B&C methods.
> Then it might be useful and necessary to set your constraints to be not
> modifiable, because you do not change your constraints during solving.
> Also your BigM should be chosen more carefully, because such big
> differences in coefficients may lead to numerical problems. (Probably BigM
> = num_cust should be enough in your case.)
> Another thing, before calling SCIPfree() you should release all variables
> and constraints by calling SCIPreleaseVar() or SCIPreleaseCons()
> respectively.
>
> Useful doxygen documentation:
>
> http://scip.zib.de/doc/html/cons__linear_8h.shtml#aa7aed137a4130b35b168812414413481
> http://scip.zib.de/doc/html/scip_8h.shtml#a738c6f77f0dcbe17cf8faa97c7573585
> http://scip.zib.de/doc/html/scip_8h.shtml#ae7055a40bc1c895c4acb118bcb8de4de
>
> Best, Michael
>
>> Hi
>>
>> I have a very strange problem and most probably very naive of me as well!
>> I have a very simple pure binary model which I run in simple SCIP (no use
>> of branch and price algorithm, only simple B&B algorithm).
>> When SCIP solves it, it gives a wrong solution! as if there is no variable
>> y and all x are one. but when I solve the generated LP file via CPLEX or
>> SCIP bins they solve the problem correctly.
>> I have attached the model and its LP file here.
>> What can be wrong?
>> Note that I want to solve the problem via B&B or B&C methods.
>>
>> Thanks,
>> Mahdi
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip