[Scip] count feasible solutions - bug?

[Timo Berthold]

> 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
>