[Scip] integer variables get assigned non-integer values

[Gerald Gamrath]

Hi Stefan,

short example:
min -x + 1e+10 y
s.t.  x <= 1e+06 y
        x >= 0
        y \in {0,1}

So we have a big-M constraint with a very high M (which often causes 
numerical problems).

The optimum is x=0, y=0, but with a tolerance of 1e-06, also y=1e-06,x=1 
is feasible and has a better objective value. Rounding y to 0 destroys 
feasibility. If you replace y by (1-z), z=0.9999999,x=1 would be 
feasible only within tolerances.

There are a few cases where you really need to be sure that the solution 
is optimal and feasible without tolerances, that's why there is also an 
extension of SCIP to an exact solver by Kati Wolter and Dan Steffy which 
you can download on the SCIP web page. It is one of the first codes of 
that kind.

However, for most practical reasons, floating point arithmetics with 
tolerances suffice, in particular when taking into account that the 
exact solver often leads to a slowdown of a factor of 10 to 100 or more. 
Also commercial MIP solvers like CPLEX, Gurobi or XPRESS all use 
floating point arithmetics and thus might return solutions which are 
feasible only in tolerances.

Best,
Gerald


Am 04.12.2013 10:20, schrieb Stefan Lörwald:
> Hi Timo,
>
> if the user requires binary variables any solution having non-binary 
> results are per definition infeasible.
> Therefore SCIP shouldn't report 0.9999999 as a feasible solution (even 
> w.r.t. tolerances), if it isn't 0/1 feasible.
> Either it should report as infeasible because the best value 
> (0.999999) doesn't satisfy the 0/1 constraint, or it should report as 
> infeasible because rounding to 1 would be infeasible.
>
> However I'd very much like to actually see a case in which 0.9999999 
> is feasible, but 1 is not. Do you have an example at hand?
>
> Stefan
>
>     One amendment to Stefan's reply:
>     > There is a small thing SCIP could do better actually: sometimes
>     you'll get
>     > 0.9999999 instead of 1 (which is representable as double) for
>     e.g. binary
>     > variables. In theory such output could be enforced to 0/1 or
>     integral
>     > value once the solving process is completed.
>
>     This is not correct in general. As argued below, it might be that the
>     0.9999999 solution is feasible (w.r.t. tolerances), whereas the 0/1
>     solution is not.
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20131204/3b295e33/attachment.html>