<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
Hi Stefan,<br>
<br>
short example:<br>
min -x + 1e+10 y<br>
s.t. x <= 1e+06 y<br>
x >= 0<br>
y \in {0,1}<br>
<br>
So we have a big-M constraint with a very high M (which often causes
numerical problems).<br>
<br>
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.<br>
<br>
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.<br>
<br>
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.<br>
<br>
Best,<br>
Gerald<br>
<br>
<br>
Am 04.12.2013 10:20, schrieb Stefan Lörwald:
<blockquote
cite="mid:CAObMDb0EKTARmfrHo8mqTk7YmG7LohzNvuzdktCJZ11aiZ4+tg@mail.gmail.com"
type="cite">
<div dir="ltr">Hi Timo,
<div><br>
</div>
<div>if the user requires binary variables any solution having
non-binary results are per definition infeasible.</div>
<div>Therefore SCIP shouldn't report 0.9999999 as a feasible
solution (even w.r.t. tolerances), if it isn't 0/1 feasible.</div>
<div>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.</div>
<div><br>
</div>
<div>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?<br>
<div class="gmail_extra"><br>
</div>
<div class="gmail_extra">Stefan</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt
0.8ex; border-left: 1px solid rgb(204, 204, 204);
padding-left: 1ex;">
One amendment to Stefan's reply:<br>
<div class="im">> There is a small thing SCIP could
do better actually: sometimes you'll get<br>
> 0.9999999 instead of 1 (which is representable as
double) for e.g. binary<br>
> variables. In theory such output could be
enforced to 0/1 or integral<br>
> value once the solving process is completed.<br>
<br>
</div>
This is not correct in general. As argued below, it
might be that the<br>
0.9999999 solution is feasible (w.r.t. tolerances),
whereas the 0/1<br>
solution is not.</blockquote>
</div>
</div>
</div>
</div>
<pre wrap="">
<fieldset class="mimeAttachmentHeader"></fieldset>
_______________________________________________
Scip mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Scip@zib.de">Scip@zib.de</a>
<a class="moz-txt-link-freetext" href="http://listserv.zib.de/mailman/listinfo/scip">http://listserv.zib.de/mailman/listinfo/scip</a>
</pre>
</blockquote>
<br>
</body>
</html>