[Scip] Is possible that SCIP returns an infeasible solution as the best one

[Gerald Gamrath]

Hi Rostislav,

the solution returned by SCIPgetBestSol() should always be feasible (as 
long as there is a solution returned, i.e., SCIP found solutions (which 
is true in your case)).

So in your case, there seems to be some bug which allows SCIP to find 
the last solution, which is infeasible. It might, e.g., be an issue in 
the heuristic or a presolving step. Perhaps there is also a numerical 
problem, if you have large numbers in your model or your solution.

Is the run performed with plain SCIP or do you have some extra plugins 
included? Can you send us the instance, so that we can check what happens?

Best,
Gerald


Am 18.05.2013 13:10, schrieb Rostislav Stanek:
> Dear SCIP community,
> I have one question: Is it possible that SCIP returns an infeasible
> solution as the best one. I use the function SCIPgetBestSol(SCIP *scip)
> to obtain the optimal solution. But this solution is not always
> feasible. In the doxygen documentation stays: “gets best feasible primal
> solution found [...], or NULL if no solution has been found or the
> candidate store is empty;”.
>
> Listing:
> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols
> |rows |cuts |confs|strbr| dualbound | primalbound | gap
> 3.2s| 1 | 0 | 867 | - | 41M| 0 | 10 |9203 | 193 |9203 | 162 | 0 | 30 |
> 10 | 2.613000e+04 | 2.735200e+04 | 4.68%
> 3.2s| 1 | 0 | 867 | - | 41M| 0 | 10 |9203 | 193 |9203 | 162 | 0 | 30 |
> 10 | 2.613000e+04 | 2.735200e+04 | 4.68%
> 3.3s| 1 | 0 | 874 | - | 41M| 0 | 20 |9203 | 193 |9203 | 166 | 4 | 30 |
> 10 | 2.613000e+04 | 2.735200e+04 | 4.68%
> 3.3s| 1 | 0 | 874 | - | 41M| 0 | 20 |9203 | 193 |9203 | 166 | 4 | 30 |
> 10 | 2.613000e+04 | 2.735200e+04 | 4.68%
> 3.3s| 1 | 2 | 874 | - | 41M| 0 | 20 |9203 | 193 |9203 | 166 | 4 | 30 |
> 27 | 2.613000e+04 | 2.735200e+04 | 4.68%
> f 4.1s| 49 | 49 | 1415 | 11.0 | 42M| 27 | - |9203 | 193 |9203 | 164 | 4
> | 30 | 409 | 2.613000e+04 | 2.620000e+04 | 0.27%
> * 4.7s| 95 | 91 | 1744 | 9.2 | 43M| 37 | - |9203 | 178 |9203 | 165 | 5 |
> 30 | 688 | 2.613000e+04 | 2.614400e+04 | 0.05%
> 4.8s| 100 | 94 | 1764 | 8.9 | 43M| 41 | - |9203 | 178 |9203 | 165 | 5 |
> 30 | 726 | 2.613000e+04 | 2.614400e+04 | 0.05%
> * 5.2s| 124 | 104 | 2030 | 9.3 | 43M| 58 | - |9203 | 178 |9203 | 165 | 5
> | 30 |1003 | 2.613000e+04 | 2.614100e+04 | 0.04%
> * 5.3s| 126 | 104 | 2036 | 9.2 | 44M| 59 | - |9203 | 178 |9203 | 165 | 5
> | 30 |1015 | 2.613000e+04 | 2.613600e+04 | 0.02%
> s 5.3s| 131 | 0 | 2095 | 9.3 | 43M| 60 | - |9203 | 178 |9203 | 165 | 5 |
> 30 |1022 | 2.613000e+04 | 2.612500e+04 | 0.02%
>
> SCIP Status : problem is solved [optimal solution found]
> Solving Time (sec) : 5.32
> Solving Nodes : 131 (total of 132 nodes in 2 runs)
> Primal Bound : +2.61250000000000e+04 (7 solutions)
> Dual Bound : +2.61250000000000e+04
> Gap : 0.00 %
>
> [...]
>
> violation: left hand side is violated by 5
>
> The primal bound gets smaller than the dual bound in the last step. And
> I am sure that a feasible solution exists. Do I understand something wrong?
> Thank you very much for response.
> Yours faithfully
> Rostislav Stanek
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip