[Scip] optimal value with no primal solution
Miles Lubin
miles.lubin at gmail.com
Sat Jul 7 17:37:12 MEST 2012
Hi Stefan,
It seems like a tricky numerical issue. I build the instance using the
API, and when I dump it to an .lp file and try to solve it, the issue
no longer occurs. If you say that the primal solution is still there
after the solve, I can work around this by not checking
SCIPisPrimalboundSol().
Thanks,
Miles
On Sat, Jul 7, 2012 at 3:04 AM, Stefan Heinz <heinz at zib.de> wrote:
> Hi Miles,
>
> that is most likely a numeric issue. I remember that we fixed something in
> our developer version. With the next release (in August) that should work.
>
> Why does that happen? The user has the possibility to pass on objective
> limit to the solver. That is possible via the interactive shell:
>
> SCIP> set limit objective 5000
>
> or via the callable library
>
> http://scip.zib.de/doc/html/scip_8h.html#a3fd90b931b38d2d8f344114babc2a67e
>
> The solver uses that for propagation for example. To point out to the user
> that the current primal bound is just a user objective limit and is not
> covered by a "real" primal solution we print that "*" next to primal value
> in the output. In the moment a better primal is found the new primal bound
> is covered by primal solution and the "*" goes away.
>
> In your case several restarts arise during that solutions a copy back to the
> original problem space. Later during the comparison if the current primal
> bound is covered by a primal solution numerically issues arise which means
> that the solver believes that primal is not covered.
>
> In any case you should get access to the optimal solution.
>
> Could you please send me that instance such that I can check if this issue
> is fixed in the next release?
>
> Best Stefan
>
>
>
> On 07/06/2012 08:56 PM, Miles Lubin wrote:
>>
>> I'm experiencing a strange behavior where SCIPgetStatus() returns
>> SCIP_STATUS_OPTIMAL and SCIPisPrimalboundSol() returns false. It's
>> hard to see how this makes any sense. Below is the output produced
>> while solving the problem. Note in the last round there is an asterisk
>> next to the primalbound. Can anyone explain?
>>
>> Thanks,
>> Miles
>>
>>
>> presolving:
>> (round 1) 290 del vars, 30 del conss, 0 add conss, 290 chg bounds, 0
>> chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 21 clqs
>> (round 2) 290 del vars, 30 del conss, 0 add conss, 300 chg bounds, 0
>> chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 21 clqs
>> (round 3) 290 del vars, 30 del conss, 0 add conss, 300 chg bounds, 0
>> chg sides, 0 chg coeffs, 21 upgd conss, 0 impls, 21 clqs
>> (0.0s) probing: 51/220 (23.2%) - 0 fixings, 0 aggregations, 0
>> implications, 0 bound changes
>> (0.0s) probing aborted: 50/50 successive totally useless probings
>> presolving (4 rounds):
>> 290 deleted vars, 30 deleted constraints, 0 added constraints, 300
>> tightened bounds, 0 added holes, 0 changed sides, 0 changed
>> coefficients
>> 0 implications, 21 cliques
>> presolved problem has 230 variables (220 bin, 0 int, 10 impl, 0 cont)
>> and 31 constraints
>> 21 constraints of type <setppc>
>> 10 constraints of type <linear>
>> Presolving Time: 0.00
>>
>> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons
>> |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
>> T 0.0s| 1 | 0 | 0 | - |1253k| 0 | - | 230 | 31 |
>> 230 | 31 | 0 | 0 | 0 | -- | 2.130311e-01 | Inf
>> 0.0s| 1 | 0 | 147 | - |1223k| 0 | 9 | 230 | 31 |
>> 230 | 31 | 0 | 0 | 0 |-1.842823e-01 | 2.130311e-01 | Inf
>> b 0.0s| 1 | 0 | 156 | - |1243k| 0 | - | 230 | 31 |
>> 230 | 31 | 0 | 0 | 0 |-1.842823e-01 | 1.985037e-01 | Inf
>> r 0.0s| 1 | 0 | 156 | - |1243k| 0 | 9 | 230 | 31 |
>> 230 | 31 | 0 | 0 | 0 |-1.842823e-01 |-2.592320e-02 | 610.88%
>> 0.0s| 1 | 0 | 156 | - |1243k| 0 | 9 | 230 | 31 |
>> 230 | 31 | 0 | 0 | 0 |-1.842823e-01 |-2.592320e-02 | 610.88%
>> 0.0s| 1 | 0 | 166 | - |1266k| 0 | 20 | 230 | 31 |
>> 230 | 40 | 9 | 0 | 0 |-1.745582e-01 |-2.592320e-02 | 573.37%
>> R 0.0s| 1 | 0 | 166 | - |1279k| 0 | 20 | 230 | 31 |
>> 230 | 40 | 9 | 0 | 0 |-1.745582e-01 |-3.768126e-02 | 363.25%
>> 0.0s| 1 | 0 | 195 | - |1308k| 0 | 32 | 230 | 31 |
>> 230 | 48 | 17 | 0 | 0 |-1.665577e-01 |-3.768126e-02 | 342.02%
>> 0.0s| 1 | 0 | 217 | - |1343k| 0 | 23 | 230 | 31 |
>> 230 | 60 | 29 | 0 | 0 |-1.642489e-01 |-3.768126e-02 | 335.89%
>> R 0.0s| 1 | 0 | 217 | - |1350k| 0 | 23 | 230 | 31 |
>> 230 | 60 | 29 | 0 | 0 |-1.642489e-01 |-6.997148e-02 | 134.74%
>> s 0.0s| 1 | 0 | 217 | - |1357k| 0 | 23 | 230 | 31 |
>> 230 | 60 | 29 | 0 | 0 |-1.642489e-01 |-9.942573e-02 | 65.20%
>> 0.0s| 1 | 0 | 248 | - |1372k| 0 | 50 | 230 | 31 |
>> 230 | 65 | 34 | 0 | 0 |-1.615500e-01 |-9.942573e-02 | 62.48%
>> 0.0s| 1 | 0 | 269 | - |1391k| 0 | 63 | 230 | 31 |
>> 230 | 75 | 44 | 0 | 0 |-1.599932e-01 |-9.942573e-02 | 60.92%
>> 0.0s| 1 | 0 | 299 | - |1414k| 0 | 59 | 230 | 31 |
>> 230 | 83 | 52 | 0 | 0 |-1.577820e-01 |-9.942573e-02 | 58.69%
>> R 0.0s| 1 | 0 | 299 | - |1421k| 0 | 59 | 230 | 31 |
>> 230 | 83 | 52 | 0 | 0 |-1.577820e-01 |-1.048695e-01 | 50.46%
>> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons
>> |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
>> s 0.0s| 1 | 0 | 299 | - |1428k| 0 | 59 | 230 | 31 |
>> 230 | 83 | 52 | 0 | 0 |-1.577820e-01 |-1.093695e-01 | 44.27%
>> 0.0s| 1 | 0 | 317 | - |1445k| 0 | 71 | 230 | 31 |
>> 230 | 91 | 60 | 0 | 0 |-1.570913e-01 |-1.093695e-01 | 43.63%
>> 0.1s| 1 | 0 | 331 | - |1463k| 0 | 73 | 230 | 31 |
>> 230 | 100 | 69 | 0 | 0 |-1.566600e-01 |-1.093695e-01 | 43.24%
>> 0.1s| 1 | 0 | 342 | - |1470k| 0 | 81 | 230 | 31 |
>> 230 | 106 | 75 | 0 | 0 |-1.564992e-01 |-1.093695e-01 | 43.09%
>> 0.1s| 1 | 0 | 347 | - |1474k| 0 | 69 | 230 | 31 |
>> 230 | 109 | 78 | 0 | 0 |-1.562761e-01 |-1.093695e-01 | 42.89%
>> 0.1s| 1 | 0 | 348 | - |1482k| 0 | 69 | 230 | 31 |
>> 230 | 110 | 79 | 0 | 0 |-1.562709e-01 |-1.093695e-01 | 42.88%
>> 0.1s| 1 | 0 | 349 | - |1489k| 0 | 70 | 230 | 31 |
>> 230 | 111 | 80 | 0 | 0 |-1.562665e-01 |-1.093695e-01 | 42.88%
>> E 0.1s| 1 | 0 | 349 | - |1496k| 0 | 70 | 230 | 31 |
>> 230 | 111 | 80 | 0 | 0 |-1.562665e-01 |-1.526621e-01 | 2.36%
>> 0.1s| 1 | 0 | 349 | - |1496k| 0 | 70 | 230 | 31 |
>> 230 | 111 | 80 | 0 | 0 |-1.562665e-01 |-1.526621e-01 | 2.36%
>> 0.1s| 1 | 0 | 349 | - |1496k| 0 | 70 | 230 | 31 |
>> 230 | 111 | 80 | 0 | 0 |-1.562665e-01 |-1.526621e-01 | 2.36%
>> 0.1s| 1 | 0 | 349 | - |1496k| 0 | - | 230 | 31 |
>> 230 | 111 | 80 | 0 | 31 |-1.562665e-01 |-1.526621e-01 | 2.36%
>> (run 1, node 1) restarting after 80 global fixings of integer variables
>>
>> (restart) converted 34 cuts from the global cut pool into linear
>> constraints
>> presolving:
>> (round 1) 80 del vars, 0 del conss, 0 add conss, 0 chg bounds, 0 chg
>> sides, 1 chg coeffs, 0 upgd conss, 26 impls, 21 clqs
>> (round 2) 80 del vars, 0 del conss, 0 add conss, 0 chg bounds, 0 chg
>> sides, 1 chg coeffs, 10 upgd conss, 26 impls, 21 clqs
>> (round 3) 80 del vars, 1 del conss, 9 add conss, 0 chg bounds, 12 chg
>> sides, 25 chg coeffs, 44 upgd conss, 280 impls, 21 clqs
>> (round 4) 80 del vars, 64 del conss, 70 add conss, 0 chg bounds, 73
>> chg sides, 147 chg coeffs, 44 upgd conss, 280 impls, 21 clqs
>> presolving (5 rounds):
>> 80 deleted vars, 64 deleted constraints, 70 added constraints, 0
>> tightened bounds, 0 added holes, 73 changed sides, 147 changed
>> coefficients
>> 280 implications, 21 cliques
>> presolved problem has 150 variables (150 bin, 0 int, 0 impl, 0 cont)
>> and 71 constraints
>> 9 constraints of type <knapsack>
>> 62 constraints of type <setppc>
>> Presolving Time: 0.00
>>
>> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons
>> |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
>> 0.1s| 1 | 0 | 480 | - |1451k| 0 | 4 | 150 | 71 |
>> 150 | 71 | 0 | 0 | 31 |-1.719788e-01 |-1.526621e-01 | 12.65%
>> 0.1s| 1 | 0 | 502 | - |1471k| 0 | 60 | 150 | 71 |
>> 150 | 75 | 4 | 0 | 31 |-1.627608e-01 |-1.526621e-01 | 6.62%
>> 0.1s| 1 | 0 | 502 | - |1469k| 0 | 60 | 150 | 71 |
>> 150 | 75 | 4 | 0 | 31 |-1.627608e-01 |-1.526621e-01 | 6.62%
>> 0.1s| 1 | 0 | 509 | - |1463k| 0 | 58 | 150 | 61 |
>> 150 | 75 | 4 | 0 | 59 |-1.611716e-01 |-1.526621e-01 | 5.57%
>> 0.2s| 1 | 0 | 513 | - |1459k| 0 | 54 | 150 | 58 |
>> 150 | 75 | 4 | 0 | 78 |-1.605924e-01 |-1.526621e-01 | 5.19%
>> 0.2s| 1 | 0 | 513 | - |1456k| 0 | - | 150 | 58 |
>> 150 | 75 | 4 | 0 | 92 |-1.605924e-01 |-1.526621e-01 | 5.19%
>> (run 2, node 1) restarting after 39 global fixings of integer variables
>>
>> (restart) converted 4 cuts from the global cut pool into linear
>> constraints
>>
>> presolving:
>> (round 1) 53 del vars, 6 del conss, 0 add conss, 0 chg bounds, 0 chg
>> sides, 0 chg coeffs, 0 upgd conss, 288 impls, 19 clqs
>> (round 2) 53 del vars, 6 del conss, 0 add conss, 0 chg bounds, 0 chg
>> sides, 0 chg coeffs, 1 upgd conss, 288 impls, 19 clqs
>> presolving (3 rounds):
>> 53 deleted vars, 6 deleted constraints, 0 added constraints, 0
>> tightened bounds, 0 added holes, 0 changed sides, 0 changed
>> coefficients
>> 288 implications, 19 cliques
>> presolved problem has 97 variables (97 bin, 0 int, 0 impl, 0 cont) and
>> 56 constraints
>> 6 constraints of type <knapsack>
>> 50 constraints of type <setppc>
>> Presolving Time: 0.00
>>
>> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons
>> |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
>> 0.2s| 1 | 0 | 603 | - |1418k| 0 | 49 | 97 | 56 |
>> 97 | 56 | 0 | 0 | 92 |-1.600634e-01 |-1.526621e-01 | 4.85%
>> 0.2s| 1 | 0 | 620 | - |1427k| 0 | 57 | 97 | 56 |
>> 97 | 62 | 6 | 0 | 92 |-1.563144e-01 |-1.526621e-01 | 2.39%
>> 0.2s| 1 | 0 | 620 | - |1426k| 0 | 57 | 97 | 56 |
>> 97 | 62 | 6 | 0 | 92 |-1.563144e-01 |-1.526621e-01 | 2.39%
>> 0.2s| 1 | 0 | 636 | - |1418k| 0 | 35 | 97 | 49 |
>> 97 | 62 | 6 | 0 | 113 |-1.548002e-01 |-1.526621e-01 | 1.40%
>> 0.2s| 1 | 0 | 636 | - |1415k| 0 | 35 | 97 | 49 |
>> 97 | 60 | 6 | 0 | 113 |-1.548002e-01 |-1.526621e-01 | 1.40%
>> 0.2s| 1 | 0 | 636 | - |1415k| 0 | - | 97 | 49 |
>> 97 | 60 | 6 | 0 | 129 |-1.548002e-01 |-1.526621e-01 | 1.40%
>> (run 3, node 1) restarting after 39 global fixings of integer variables
>>
>> (restart) converted 6 cuts from the global cut pool into linear
>> constraints
>>
>> presolving:
>> (round 1) 46 del vars, 14 del conss, 20 add conss, 0 chg bounds, 22
>> chg sides, 42 chg coeffs, 0 upgd conss, 306 impls, 12 clqs
>> (round 2) 46 del vars, 24 del conss, 20 add conss, 0 chg bounds, 22
>> chg sides, 42 chg coeffs, 2 upgd conss, 306 impls, 12 clqs
>> (round 3) 46 del vars, 25 del conss, 20 add conss, 0 chg bounds, 22
>> chg sides, 42 chg coeffs, 2 upgd conss, 306 impls, 12 clqs
>> presolving (4 rounds):
>> 46 deleted vars, 25 deleted constraints, 20 added constraints, 0
>> tightened bounds, 0 added holes, 22 changed sides, 42 changed
>> coefficients
>> 306 implications, 12 cliques
>> presolved problem has 51 variables (51 bin, 0 int, 0 impl, 0 cont) and
>> 50 constraints
>> 2 constraints of type <knapsack>
>> 48 constraints of type <setppc>
>> Presolving Time: 0.01
>>
>> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons
>> |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
>> 0.2s| 1 | 0 | 683 | - |1381k| 0 | 1 | 51 | 50 |
>> 51 | 50 | 0 | 0 | 129 |-1.543720e-01 |-1.526621e-01 | 1.12%
>> 0.2s| 1 | 0 | 683 | - |1385k| 0 | 1 | 51 | 50 |
>> 51 | 48 | 0 | 0 | 129 |-1.543720e-01 |-1.526621e-01 | 1.12%
>> 0.2s| 1 | 0 | 686 | - |1391k| 0 | 2 | 51 | 48 |
>> 51 | 50 | 2 | 0 | 129 |-1.541920e-01 |-1.526621e-01 | 1.00%
>> 0.2s| 1 | 2 | 686 | - |1398k| 0 | 2 | 51 | 48 |
>> 51 | 50 | 2 | 0 | 131 |-1.541920e-01 |-1.526621e-01 | 1.00%
>> (run 4, node 1) restarting after 5 global fixings of integer variables
>>
>> (restart) converted 1 cuts from the global cut pool into linear
>> constraints
>>
>> presolving:
>> (round 1) 18 del vars, 21 del conss, 0 add conss, 0 chg bounds, 0 chg
>> sides, 0 chg coeffs, 1 upgd conss, 316 impls, 5 clqs
>> (round 2) 22 del vars, 31 del conss, 0 add conss, 0 chg bounds, 0 chg
>> sides, 0 chg coeffs, 1 upgd conss, 318 impls, 5 clqs
>> presolving (3 rounds):
>> 22 deleted vars, 31 deleted constraints, 0 added constraints, 0
>> tightened bounds, 0 added holes, 0 changed sides, 0 changed
>> coefficients
>> 318 implications, 5 cliques
>> presolved problem has 29 variables (29 bin, 0 int, 0 impl, 0 cont) and
>> 18 constraints
>> 2 constraints of type <knapsack>
>> 15 constraints of type <setppc>
>> 1 constraints of type <logicor>
>> Presolving Time: 0.01
>>
>> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons
>> |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
>> 0.2s| 1 | 0 | 700 | - |1355k| 0 | 2 | 29 | 18 |
>> 29 | 18 | 0 | 0 | 131 |-1.541920e-01 |-1.526621e-01 | 1.00%
>> 0.2s| 1 | 0 | 700 | - |1361k| 0 | 2 | 29 | 18 |
>> 29 | 18 | 0 | 0 | 131 |-1.541920e-01 |-1.526621e-01 | 1.00%
>> 0.2s| 1 | 0 | 702 | - |1369k| 0 | 13 | 29 | 18 |
>> 29 | 20 | 2 | 0 | 131 |-1.540008e-01 |-1.526621e-01 | 0.88%
>> 0.2s| 1 | 0 | 702 | - |1366k| 0 | - | 29 | 18 |
>> 29 | 20 | 2 | 0 | 136 |-1.540008e-01 |-1.526621e-01 | 0.88%
>> (run 5, node 1) restarting after 11 global fixings of integer variables
>>
>> (restart) converted 2 cuts from the global cut pool into linear
>> constraints
>> presolving:
>> (round 1) 20 del vars, 13 del conss, 0 add conss, 0 chg bounds, 0 chg
>> sides, 0 chg coeffs, 2 upgd conss, 322 impls, 0 clqs
>> (round 2) 22 del vars, 15 del conss, 0 add conss, 0 chg bounds, 0 chg
>> sides, 0 chg coeffs, 2 upgd conss, 322 impls, 0 clqs
>> (round 3) 22 del vars, 15 del conss, 0 add conss, 1 chg bounds, 0 chg
>> sides, 0 chg coeffs, 2 upgd conss, 322 impls, 0 clqs
>> (round 4) 23 del vars, 15 del conss, 0 add conss, 1 chg bounds, 0 chg
>> sides, 1 chg coeffs, 2 upgd conss, 332 impls, 0 clqs
>> presolving (5 rounds):
>> 23 deleted vars, 15 deleted constraints, 0 added constraints, 1
>> tightened bounds, 0 added holes, 0 changed sides, 1 changed
>> coefficients
>> 332 implications, 0 cliques
>> presolved problem has 6 variables (6 bin, 0 int, 0 impl, 0 cont) and 5
>> constraints
>> 2 constraints of type <knapsack>
>> 3 constraints of type <logicor>
>> Presolving Time: 0.01
>>
>> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons
>> |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
>> 0.2s| 1 | 0 | 707 | - |1341k| 0 | 4 | 6 | 5 |
>> 6 | 5 | 0 | 0 | 136 |-1.538920e-01 |-1.526621e-01 | 0.81%
>> s 0.2s| 1 | 0 | 707 | - |1348k| 0 | 4 | 6 | 5 |
>> 6 | 5 | 0 | 0 | 136 |-1.538920e-01 |-1.531920e-01 | 0.46%
>> 0.2s| 1 | 0 | 711 | - |1354k| 0 | 1 | 6 | 5 |
>> 6 | 7 | 2 | 0 | 136 |-1.532753e-01 |-1.531920e-01 | 0.05%
>> 0.2s| 1 | 0 | 711 | - |1354k| 0 | 1 | 6 | 5 |
>> 6 | 6 | 2 | 0 | 136 |-1.532753e-01 |-1.531920e-01 | 0.05%
>> 0.2s| 1 | 2 | 711 | - |1355k| 0 | 1 | 6 | 5 |
>> 6 | 6 | 2 | 0 | 136 |-1.532753e-01 |-1.531920e-01 | 0.05%
>> (run 6, node 1) restarting after 1 global fixings of integer variables
>>
>> (restart) converted 2 cuts from the global cut pool into linear
>> constraints
>>
>> presolving:
>> (round 1) 1 del vars, 1 del conss, 0 add conss, 0 chg bounds, 0 chg
>> sides, 0 chg coeffs, 2 upgd conss, 332 impls, 0 clqs
>> (round 2) 1 del vars, 2 del conss, 0 add conss, 0 chg bounds, 1 chg
>> sides, 2 chg coeffs, 2 upgd conss, 332 impls, 0 clqs
>> presolving (3 rounds):
>> 1 deleted vars, 2 deleted constraints, 0 added constraints, 0
>> tightened bounds, 0 added holes, 1 changed sides, 2 changed
>> coefficients
>> 332 implications, 0 cliques
>> presolved problem has 5 variables (5 bin, 0 int, 0 impl, 0 cont) and 5
>> constraints
>> 3 constraints of type <knapsack>
>> 2 constraints of type <logicor>
>> Presolving Time: 0.01
>>
>> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons
>> |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
>> 0.2s| 1 | 0 | 715 | - |1347k| 0 | 2 | 5 | 5 |
>> 5 | 5 | 0 | 0 | 136 |-1.532753e-01 |-1.531920e-01*| 0.05%
>> 0.2s| 1 | 0 | 717 | - |1354k| 0 | 5 | 5 | 5 |
>> 5 | 7 | 2 | 0 | 136 |-1.532223e-01 |-1.531920e-01*| 0.02%
>> 0.2s| 1 | 0 | 717 | - |1354k| 0 | 5 | 5 | 5 |
>> 5 | 7 | 2 | 0 | 137 |-1.531920e-01 |-1.531920e-01*| 0.00%
>>
>> SCIP Status : problem is solved [optimal solution found]
>> Solving Time (sec) : 0.20
>> Solving Nodes : 1 (total of 7 nodes in 7 runs)
>> Primal Bound : -1.53191992881652e-01 (18 solutions)
>> Dual Bound : -1.53191992881652e-01
>> Gap : 0.00 %
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>
>
>
More information about the Scip
mailing list