Opened 8 years ago
Closed 7 years ago
#20 closed defect (duplicate)
wrong dual bound reported when running with nonzero gap tolerance
Reported by: | stefan | Owned by: | somebody |
---|---|---|---|
Priority: | major | Milestone: | |
Component: | component1 | Version: | |
Keywords: | Cc: |
Description
Hi,
when I run Couenne/stable/0.4 with bonmin.allowable_fraction_gap 0.2, it reports the best found solutions objective value as best bound (bb.bestBound()), i.e., having closed the gap, if stopped due to the gap limit:
Coin0506I Presolve 105 (-1) rows, 60 (-21) columns and 295 (-31) elements Clp0006I 0 Obj 42 Primal inf 69.55171 (10) Clp0006I 51 Obj 45.02 Clp0000I Optimal - objective value 45.02 Clp0032I Optimal objective 45.02 - 51 iterations time 0.002, Presolve 0.00 Clp0000I Optimal - objective value 45.02 Clp0000I Optimal - objective value 45.02 Cbc0013I At root node, 0 cuts changed objective from 45.02 to 45.02 in 1 passes Cbc0014I Cut generator 0 (Couenne convexifier cuts) - 0 row cuts average 0.0 elements, 1 column cuts (1 active) Cbc0010I After 0 nodes, 0 on tree, 1e+50 best solution, best possible 45.02 (0.05 seconds) Cbc0004I Integer solution of 53.1 found after 907 iterations and 86 nodes (0.51 seconds) Cbc0011I Exiting as integer gap of 8.06 less than 0 or 20% Cbc0001I Search completed - best objective 53.1, took 920 iterations and 87 nodes (0.57 seconds) Cbc0035I Maximum depth 42, 0 variables fixed on reduced cost Couenne convexifier cuts was tried 157 times and created 2166 cuts of which 219 were active after adding rounds of cuts Couenne finished. Found feasible solution. Best solution: 5.310000e+01 (87 nodes, 0.674 seconds) Best possible: 5.310000e+01
If I run with zero gap tolerance and interrupt with Ctrl+C, a correct dual bound is reported:
Coin0506I Presolve 105 (-1) rows, 60 (-21) columns and 295 (-31) elements Clp0006I 0 Obj 42 Primal inf 69.55171 (10) Clp0006I 51 Obj 45.02 Clp0000I Optimal - objective value 45.02 Clp0032I Optimal objective 45.02 - 51 iterations time 0.002, Presolve 0.00 Clp0000I Optimal - objective value 45.02 Clp0000I Optimal - objective value 45.02 Cbc0013I At root node, 0 cuts changed objective from 45.02 to 45.02 in 1 passes Cbc0014I Cut generator 0 (Couenne convexifier cuts) - 0 row cuts average 0.0 elements, 1 column cuts (1 active) Cbc0010I After 0 nodes, 0 on tree, 1e+50 best solution, best possible 45.02 (0.05 seconds) Cbc0004I Integer solution of 53.1 found after 907 iterations and 86 nodes (0.50 seconds) Cbc0010I After 100 nodes, 43 on tree, 53.1 best solution, best possible 45.046667 (0.75 seconds) Cbc0010I After 200 nodes, 88 on tree, 53.1 best solution, best possible 45.06 (1.11 seconds) Cbc0010I After 300 nodes, 134 on tree, 53.1 best solution, best possible 45.06 (1.49 seconds) ^CCbc0003I Exiting on maximum nodes Cbc0005I Partial search - best objective 53.1 (best possible 45.06), took 4042 iterations and 323 nodes (1.55 seconds) Cbc0035I Maximum depth 42, 26 variables fixed on reduced cost Couenne convexifier cuts was tried 608 times and created 8466 cuts of which 1067 were active after adding rounds of cuts Node or iteration limit exceeded or user interrupt, we will report iteration limit in listing file. Couenne finished. Found feasible solution. Best solution: 5.310000e+01 (323 nodes, 1.714 seconds) Best possible: 4.506000e+01
Change History (3)
comment:1 Changed 8 years ago by pbelotti
comment:2 Changed 8 years ago by stefan
Yes, let's say I use Couenne as a library.
The problem is not the upper bound, but the lower bound. I used bb.bestBound() where bb is the Bonmin::Bab class that, but I see that you use bb.model().getBestPossibleObjValue().
This seems to make a difference due to some bug either in Bonmin, in Cbc, or both, but not in Couenne :-).
I submitted a new bug report for Bonmin and will use a workaround with bb.model().getBestPossibleObjValue() in the meanwhile.
Stefan
comment:3 Changed 7 years ago by pbelotti
- Resolution set to duplicate
- Status changed from new to closed
Seems fixed with a change in Bonmin.
Given that this is not the normal output by Couenne, I assume you are not using the standalone version. Recently, a few changes have been introduced in the way feasible solutions are saved. Check Couenne/src/main/BonCouenne.cpp at line 347, where lower and upper bound are retrieved from a separate data structure.
I tried the standalone Couenne version with the same option (with and without the prefix "bonmin.") and obtained different lower and upper bounds when the allowed gap is nonzero.