[Scip] optimal value with no primal solution
Stefan Heinz
heinz at zib.de
Sat Jul 7 10:04:25 MEST 2012
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