[Scip] count feasible solutions - bug?

[Timo Berthold]

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
>