[Scip] count feasible solutions - slowdown?

Tue Oct 30 21:21:35 MET 2012

One other small thing ... I notice that scip 2.1.1 takes 52 seconds on
my rather slow computer to complete "count" on this toy problem
whereas scip 3.0.0 takes 107 seconds.

One can also see from the output of 2.1.1 that it seems it has had to
do less work. Scip 2.1.1 gives

SCIP Status        : problem is solved [infeasible]
Solving Time (sec) : 51.99
Solving Nodes      : 61279
Primal Bound       : +1.00000000000000e+20 (0 solutions)
Dual Bound         : +1.00000000000000e+20
Gap                : 0.00 %
Feasible Solutions : 13120 (0 non-trivial feasible subtrees)

Compare 61279 to 78487, although the numbers don't immediately seem to
explain the whole difference.

Raphael

On 30 October 2012 18:21, Timo Berthold <berthold at zib.de> wrote:
>> This means that your IP has 78487
>> different solutions - including suboptimal ones!
>
> My bad! Of course the IP has 13120 feasible solutions and SCIP needed
> 78487 nodes to figure that out. Copy-and-paste can be tricky...
>
> Thanks to Inken for pointing that out.
>
> Cheers
> Timo
>
>> tl;dr: Not a bug, SCIP output is just confusing here, maybe changed in
>> next release
>>
>> Hi Raphael,
>>
>> The SCIP status is infeasible just because of an implementation trick that
>> is done inside SCIP to count solutions. Roughly speaking: Feasible
>> solution get cut off (and counted at that time), which is why all feasible
>> solutions have been provably counted as soon as the remaining, "uncounted"
>> part is detected to be infeasible. This means that your IP has 78487
>> different solutions - including suboptimal ones!
>>
>> If you want to only count optimal solutions, you should add a constraint
>> that the objective function equals 9.32346000000000e+05, which is the
>> optimal solution as you wrote.
>>
>> On the side note:
>> Non-trivial feasible subtrees are a structure that is exploited when
>> during the branch-and-bound SCIP detects that all possible assigments of
>> the remaining unfixed variables will yield feasibility. Then the whole
>> subtree is counted at once: Meaning 2^NrUnfixedVars (in acse of binary
>> vars) is added and the whole subtree is cut off, instead of checking each
>> single solution.
>>
>> Best regards
>> Timo
>>
>>> I have a toy IP included below.  I would like to count the number of
>>> feasible solutions (I am using
>>> http://scip.zib.de/download.php?fname=scip-3.0.0.linux.x86.gnu.opt.spx.zip).
>>>
>>> If I read it in and then run
>>>
>>> count
>>>
>>> It whirs away for a couple of minutes and then gives
>>>
>>> SCIP Status        : problem is solved [infeasible]
>>> Solving Time (sec) : 109.47
>>> Solving Nodes      : 78487
>>> Primal Bound       : +1.00000000000000e+20 (0 solutions)
>>> Dual Bound         : +1.00000000000000e+20
>>> Gap                : 0.00 %
>>> Feasible Solutions : 13120 (0 non-trivial feasible subtrees)
>>>
>>>
>>> I don't understand this as if I now do
>>>
>>> free
>>> read "almgren.3.lp"
>>> optimize
>>>
>>> I get
>>>
>>> SCIP Status        : problem is solved [optimal solution found]
>>> Solving Time (sec) : 0.01
>>> Solving Nodes      : 1
>>> Primal Bound       : +9.32346000000000e+05 (1 solutions)
>>> Dual Bound         : +9.32346000000000e+05
>>> Gap                : 0.00 %
>>>
>>> Why does the count method say it is infeasible and give those
>>> primal/dual bounds?  Also, as an aside, what does 0 non-trivial
>>> feasible subtrees mean?
>>>
>>> Raphael
>>>
>>> \ SCIP STATISTICS
>>> \   Problem name     : Almgren3
>>> \   Variables        : 16 (0 binary, 16 integer, 0 implicit integer, 0
>>> continuous)
>>> \   Constraints      : 5
>>> \   Obj. scale       : 1
>>> \   Obj. offset      : 0
>>> Minimize
>>>  Obj: +9534.5 C__1 +9523 C__2 +9517 C__3 +9514 C__4 -9534 C__5 -9522
>>> C__6 -9516 C__7 -9513 C__8 +12.5 C__9
>>>       +18 C__10 +9.5 C__11 -12 C__12 -17.5 C__13 -9 C__14 +2.5 C__15 -2
>>> C__16
>>> Subject to
>>>  R__1: +1 C__1 -1 C__5 +1 C__9 +1 C__10 -1 C__12 -1 C__13 = +0
>>>  R__2: +1 C__2 -1 C__6 -1 C__9 +1 C__11 +1 C__12 -1 C__14 +1 C__15 -1
>>> C__16 = +0
>>>  R__3: +1 C__3 -1 C__7 -1 C__10 +1 C__13 -2 C__15 +2 C__16 = +0
>>>  R__4: +1 C__4 -1 C__8 -1 C__11 +1 C__14 +1 C__15 -1 C__16 = +98
>>>  atmost: +9534.5 C__1 +9523 C__2 +9517 C__3 +9514 C__4 -9534 C__5
>>> -9522 C__6 -9516 C__7 -9513 C__8 +12.5 C__9
>>>   +18 C__10 +9.5 C__11 -12 C__12 -17.5 C__13 -9 C__14 +2.5 C__15 -2
>>> C__16 <= +932347.5
>>> Bounds
>>>  0 <= C__1 <= 290
>>>  0 <= C__2 <= 466
>>>  0 <= C__3 <= 40
>>>  0 <= C__4 <= 397
>>>  0 <= C__5 <= 2417
>>>  0 <= C__6 <= 28
>>>  0 <= C__7 <= 380
>>>  0 <= C__8 <= 21
>>>  0 <= C__9 <= 1510
>>>  0 <= C__10 <= 449
>>>  0 <= C__11 <= 200
>>>  0 <= C__12 <= 6
>>>  0 <= C__13 <= 100
>>>  0 <= C__14 <= 932
>>>  0 <= C__15 <= 49
>>>  0 <= C__16 <= 841
>>> Generals
>>>  C__1 C__2 C__3 C__4 C__5 C__6 C__7 C__8 C__9 C__10 C__11 C__12 C__13
>>> C__14 C__15 C__16
>>> End
>>> _______________________________________________
>>> 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
>>
>