[Scip] count feasible solutions - bug?

Tue Oct 30 20:21:18 MET 2012

Thanks very much.

It would be great, as you say, if the output could be made more
obvious to the uninitiated.  Even the primal/dual bounds lines seem to
confirm the misunderstanding.

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