[Scip] integer variables get assigned non-integer values
Timo Berthold
berthold at zib.de
Wed Dec 4 10:03:49 CET 2013
Hi SCIP list,
I just realized that I send my reply only to Zhanibek directly, not to the
mailing list. Whoever is interested, find it below.
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.
Cheers
Timo
---------------------------- Original Message ----------------------------
Subject: Re: [Scip] integer variables get assigned non-integer values
From: "Timo Berthold" <berthold at zib.de>
Date: Wed, December 4, 2013 8:16 am
To: itomatik at gmail.com
--------------------------------------------------------------------------
Hi Zhanibek,
That's expected behavior.
SCIP (and all other major MIP solvers) use numerical tolerances at many
places, including the checks for integrality of a variable, for the
feasibility of a constraint and for the primal-dual gap being zero.
These tolerances are typically somewhere between e-06 and e-09.
It may therefore happen that integrality, feasibility or optimality are
violated by some epsilon. For the vast majority of applications that's not
a problem and one can do what you suggest: Just ignore these violations
and round variables etc. It may however happen, that the rounded solution
then in turn violates some constraint (by epsilon or even by more). If you
want to doublecheck, what you can do is the following (I am giving a
description for using SCIP from the interactive shell):
Adjust the solution as you suggested, store it in a *.sol file, read in
your problem again, read in the solution, and see whether SCIP accepts it
or whether it complains that some constraint is violated.
Cheers
Timo
> Dear Zhanibev,
>
> 1. I try to answer both of your questions at once:
>
> The definition of an integer in SCIP is:
>
> x is integer <=> x \in [ [x] - eps, [x] +eps ].
> The standard numeric epsilon is eps=10^-6 which gives you
> reasonable integral values on most instances.
>
> If I'm not mistaken, SCIP already solved your integer problem
> within an eps of 10^-12.
>
> Just for the sake of completeness: you can change the floating
> epsilon from inside the SCIP interactive shell:
> set numerics epsilon 0.1
>
> 2. Decreasing number of LP iterations
>
> I guess you are the very first to complain about a decrasing number
> of LP iterations during the solve ;)
> The first reason is that at the first node (the root node), SCIP
> solves a lot more LPs than at consecutive
> nodes during the cut-separation loop. The second reason is that
> during branch-and-bound,
> not every node-LP needs to solved from scratch (i.e., by feeding
> the node LP into the LP solver as a new
> problem).
> Basically, the LP relaxation at a node usually differs from its
> parent node's LP relaxation by a single
> bound change, namely that of the variable branched on. The LP basis
> information stays dually
> feasible and is quickly reoptimized (made primal feasible) by a
> small number of dual simplex interations.
> This is called warm starting and should be almost always be faster
> (in terms of the LP iteration count)
> than resolving the LP from scratch.
> SCIP solves the branch-and-bound tree by selecting nodes in a
> depth-first-search like fashion (to some extent)
> to take advantage of fast warm starting.
>
> Regards
> Gregor
>
> Am 04.12.2013 06:55, schrieb Zhanibek Datbayev:
>> Hey guys,
>>
>> I'm trying to tackle a MIP problem using SCIP. All of my variables are
>> either integer or binary, but sometimes SCIP produces non-integer
>> values. For example below all of the values are integers except of one
>> which gets 3491.99999999999.
>>
>> Is that expected behavior? Should I not worry about this kind of
>> values and just convert them to integers (adding 0.1 before doing that)?
>>
>> Thanks in advance!
>>
>> -Zhanibek
>>
>>
>> x#2#1 4215 (obj:0)
>> x#2#5 56830 (obj:0)
>> x#2#7 2688 (obj:0)
>> x#2#8 2048 (obj:0)
>> x#2#11 20315 (obj:0)
>> x#3#10 82685 (obj:0)
>> x#3#20 3492 (obj:0)
>> x#4#1 4215
>> (obj:0.227623824612884)
>> x#4#8 2048
>> (obj:0.315622376912749)
>> x#4#10 82685
>> (obj:0.57256205816212)
>> x#4#12 31615
>> (obj:0.297351147308957)
>> x#4#17 5120
>> (obj:0.183683178270458)
>> x#4#20 3492
>> (obj:0.0293412067324434)
>> x#5#5 56830
>> (obj:0.355742408976591)
>> x#5#7 2688
>> (obj:0.0281349154730122)
>> x#5#11 20315
>> (obj:0.275787370980847)
>> x#5#13 5540
>> (obj:0.0513514245076417)
>> x#5#14 20735
>> (obj:0.300966021551557)
>> x#5#15 20735
>> (obj:0.176821089959373)
>> x#5#18 2432
>> (obj:3.17376668601277e-07)
>> x#6#8 2048
>> (obj:0.000522082564132327)
>> x#6#12 31615
>> (obj:0.00409922840858967)
>> x#6#14 20735
>> (obj:0.00136236177674599)
>> x#6#18 2432
>> (obj:-0.117098565680789)
>> x#7#5 56830
>> (obj:0.00617355213116657)
>> x#8#1 4215
>> (obj:0.000811301308183401)
>> x#8#7 2688
>> (obj:0.16746227096924)
>> x#8#10 82685
>> (obj:-0.00863945585761269)
>> x#8#11 20315
>> (obj:0.0277269751371639)
>> x#8#13 5540
>> (obj:0.198066307858387)
>> x#8#15 20735
>> (obj:0.0286204044109112)
>> x#8#17 5120
>> (obj:0.0021240047761656)
>> x#8#20 3492
>> (obj:0.0878842690501064)
>> x#9#10 82685
>> (obj:0.13516549310118)
>> x#9#14 20735
>> (obj:0.103485318216289)
>> x#10#7 2688
>> (obj:0.221488641675372)
>> x#10#15 20735
>> (obj:0.0966569518978526)
>> x#10#18 2432
>> (obj:0.00821715230798994)
>> x#11#1 4215
>> (obj:0.0309833140905398)
>> x#11#10 82685
>> (obj:0.193435054244922)
>> x#11#20 3491.99999999999
>> (obj:0.272961110760302)
>> x#12#5 56830
>> (obj:0.170908606920874)
>> x#12#8 2048
>> (obj:0.0436318450636487)
>> x#12#12 31615
>> (obj:0.114663635932676)
>> x#13#11 20315
>> (obj:0.113443166741343)
>> x#13#13 5540
>> (obj:0.238776163163475)
>> x#14#1 4215
>> (obj:0.021654717840975)
>> x#14#7 2688
>> (obj:0.0162037953878893)
>> x#14#12 31615
>> (obj:0.0780633298974657)
>> x#14#13 5540
>> (obj:0.0190470353724125)
>> x#14#17 5120
>> (obj:0.0211936119326756)
>> x#14#18 2432
>> (obj:0.00580446075062875)
>> x#15#8 2048
>> (obj:0.0295371902538209)
>> x#15#11 20315
>> (obj:0.0853453710938286)
>> x#15#20 3492
>> (obj:0.0192241961849487)
>> x#16#5 56830
>> (obj:1.08525723231457)
>> x#16#17 5120
>> (obj:0.252856127702844)
>> x#17#14 20735
>> (obj:1.07428897058425)
>> x#18#15 20735
>> (obj:0.624205140104469)
>> x#1#12 31615
>> (obj:0.294458508903076)
>> x#1#13 5540
>> (obj:0.0143650582634939)
>> x#1#14 20735
>> (obj:0.0609253833279164)
>> x#1#15 20735
>> (obj:0.223615760650029)
>> x#1#17 5120
>> (obj:0.0466027306419037)
>> x#1#18 2432
>> (obj:0.0053056051642484)
>>
>>
>>
>> _______________________________________________
>> 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
>
More information about the Scip
mailing list