[Scip] integer variables get assigned non-integer values

[Timo Berthold]

Heyho,

So, SCIP and other solvers find optimal solutions that are feasible and
optimal w.r.t. to some tolerance.
This can be defined mathematically sound and this definition is followed
by the solvers (every behavior that deviates from this I would consider a
bug).

If a user requires truly binary values, there are other possibilities, to
list some examples:
a) If also the matrix and the right hand side are binary, one may use a
SAT solver;
b) SCIP is the only major MIP solver, of which there exists a turly exact
version: http://scip.zib.de/exactmip.shtml with limit capabilities, though
(e.g., no cuts);
c) enumerate ;-)

Numerics is not an easy topic and quickly goes into pathological
discussions. Robert and Gerald showed you, how easy it is to construct
counterexamples.
Well, if we agree on using floating point numbers, here is an easy one for
which no solver based on floating point numbers will find the exact
representation, since it is not expressible as a finite term in base 2:

x = 10y, x \in {0,1}, y \in R

the value for y will always contain an error (much smaller than the
mentioned epsilons of course). Also, either the constraint or the value of
y will have an error.

Speaking of R, the real numbers, at latest when you talk about MINLP and
constraints including transcendental functions, "numerical exactness" in a
theoretical sense is out of reach for a solver. Yes, I know about symbolic
computing.

Guaranteeing only epsilon-feasibility and -optimality, of course comes at
a price. One is that with this background, more than one answer can be
correct. Robert's example is perfect for this, since it has a provably
feasible solution (up to epsilon) and also infeasibility can be proven up
to epsilon-tolerance.

So, I agree that numerics can be annoying, and this is one of the things
which we have to deal with the most when fixing bugs.
But also they are unavoidable to a certain degree and it neither realistic
nor practical to dogmatically ask for a different behavior. That in you
particular example the issue might me resolved, might well be, I do not
know.

Have fun,
Timo

> 2013/12/4 Stefan Lörwald <stefan.loerwald at gmail.com>
>
>>
>> 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.
>>
>
> I believe this is not what we want. If the user requires binary variables,
> and (w.r.t. tolerances) there is no binary feasible solution, the answer
> to
> the computation will be "there is no feasible solution". From a practical
> perspective, this is not very satisfactory. And it may be a false answer.
> Maybe there IS a feasible solution, but we did not find it b/c of
> computations are subject to tolerance.
>
> The solution you get from a MIP solver may be in some rare cases
> completely
> irrelevant, wrong or otherwise flawed. Probably, this does not happen too
> often, but it may happen. Now, I rather see an "almost" feasible solution
> than "there is no answer". At least as a practitioner. But again, both
> answers, feasible or infeasible, may be wrong, so I prefer the report "I
> probably found an almost feasible solution" rather than "the correct
> answer
> may be 'infeasible'".
>
> Marco
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>