[Dip] issues with DualStabAlpha
Shahin Gelareh
shahin.gelareh at gmail.com
Fri Mar 7 07:27:19 EST 2014
Dear all
I have a MIP decomposed into a RMP and three pricing problems.
The RMP is feasible because I added a feasible solution in the relevant
function.
The optimal solution is 149 and the feasible solution I added is 213.
The decomposition suffers from the degeneracy and the fact that dual duals
are not promising after some time.
I have set DualStab = 1 and played with DualStabAlpha. Strange results have
been observed. In brief with low DualStabAlpha I get optimal solution but
with higher values the solution is wrong.
I appreciate any comment.
Shahin
For DualStabAlpha = 0.3 I have optimality.
Alps0208I Search completed.
Alps0261I Best solution found had quality 149 and was found at depth 30
Alps0265I Number of nodes fully processed: 58
Alps0266I Number of nodes partially processed: 3
Alps0267I Number of nodes branched: 30
Alps0268I Number of nodes pruned before processing: 0
Alps0270I Number of nodes left: 0
Alps0272I Tree depth: 8
Alps0274I Search CPU time: 257.53 seconds
Alps0278I Search wall-clock time: 257.53 seconds
================ DECOMP Statistics [BEGIN]: ===============
Total Decomp = 256.57 100.00 61 16.95
Total Solve Relax = 253.52 98.81 7461 0.48
Total Solve Relax App = 0.01 0.00 7461 0.00
Total Solution Update = 17.72 6.91 2780 0.07
Total Generate Cuts = 0.15 0.06 6 0.03
Total Generate Vars = 204.81 79.83 2485 0.47
Total Compress Cols = 0.56 0.22 391 0.01
================ DECOMP Statistics [END ]: ===============
x(0)(1)(2)(1) 1.00
x(0)(2)(1)(2) 1.00
x(0)(4)(0)(4) 1.00
x(1)(3)(2)(4) 1.00
x(2)(6)(1)(8) 1.00
x(3)(5)(2)(9) 1.00
x(4)(8)(0)(12) 1.00
x(5)(7)(2)(16) 1.00
x(6)(0)(1)(14) 1.00
x(7)(0)(2)(23) 1.00
x(8)(0)(0)(20) 1.00
Status= 0 *BestLB= 149.00000 BestUB= 149.00000* Nodes= 58 SetupCPU=
0.78 SolveCPU= 257.59 TotalCPU= 258.36 SetupReal= 0.77 SetupReal= 257.59
TotalReal= 1
.55
ERROR. BestKnownUB= 1e+020 but DECOMP claims GlobalUB= 149
Press any key to continue . . .
For DualStabAlpha = 0.9 I face with a premature convergence to a
non-optimal solution
Processing Node 2 algo= PRICE_AND_CUT phase= PHASE_PRICE1 c= 0 p= 3
LB= -0.768 UB= 0.720 nodeLB= -0.768 gLB= -2.563 gUB=
231.00
lpGap= 1.938 ipGap= 301.777 time= 6.86
Processing Node 2 algo= PRICE_AND_CUT phase= PHASE_PRICE1 c= 0 p= 4
LB= -0.694 UB= 0.720 nodeLB= -0.694 gLB= -2.563 gUB=
231.00
lpGap= 2.038 ipGap= 333.932 time= 6.98
Processing Node 2 algo= PRICE_AND_CUT phase= PHASE_PRICE1 c= 0 p= 5
LB= -0.548 UB= 0.693 nodeLB= -0.548 gLB= -2.563 gUB=
231.00
lpGap= 2.265 ipGap= 422.755 time= 7.10
D-ALGO : 7.11 [CPU: 7.107 ] --- processNode() -----------> funcT =
0.678
Alps0208I Search completed.
Alps0261I Best solution found had quality 231 and was found at depth 0
Alps0264I Number of nodes processed: 3
Alps0267I Number of nodes branched: 1
Alps0268I Number of nodes pruned before processing: 0
Alps0270I Number of nodes left: 0
Alps0272I Tree depth: 1
Alps0274I Search CPU time: 6.21 seconds
Alps0278I Search wall-clock time: 6.21 seconds
================ DECOMP Statistics [BEGIN]: ===============
Total Decomp = 6.14 100.00 3 3.57
Total Solve Relax = 8.46 137.76 144 0.54
Total Solve Relax App = 0.00 0.00 144 0.00
Total Solution Update = 0.22 3.65 46 0.01
Total Generate Cuts = 0.00 0.00 0 0.00
Total Generate Vars = 5.26 85.66 46 0.15
Total Compress Cols = 0.00 0.00 0 0.00
================ DECOMP Statistics [END ]: ===============
x(0)(6)(1)(6) 1.00
x(0)(7)(2)(7) 1.00
x(0)(8)(0)(8) 1.00
x(1)(0)(2)(29) 1.00
x(2)(0)(1)(18) 1.00
x(3)(1)(2)(28) 1.00
x(4)(0)(0)(24) 1.00
x(5)(3)(2)(23) 1.00
x(6)(2)(1)(16) 1.00
x(7)(5)(2)(16) 1.00
x(8)(4)(0)(20) 1.00
Status= 0 *BestLB= 231.00000 BestUB= 231.00000* Nodes= 3 SetupCPU=
0.90 SolveCPU= 6.27 TotalCPU= 7.17 SetupReal= 0.90 SetupReal= 6.27
TotalReal= 1.79
ERROR. BestKnownUB= 1e+020 but DECOMP claims GlobalUB= 231
Press any key to continue . . .
with DualStabAlpha = 0.7 we get a lower bound which is higher than the
optimal I know (I terminated the iterations manually).
lpGap= 1.179 ipGap= 143.197 time= 332.39
Processing Node 241 algo= PRICE_AND_CUT phase= PHASE_PRICE1 c= 0 p= 6
LB= -1.184 UB= 0.200 nodeLB= -1.118 gLB= 150.780 gUB=
159.000
lpGap= 1.179 ipGap= 143.197 time= 332.45
Processing Node 241 algo= PRICE_AND_CUT phase= PHASE_PRICE1 c= 0 p= 7
LB= -0.723 UB= 0.200 nodeLB= -0.723 gLB= 150.780 gUB=
159.000
lpGap= 1.277 ipGap= 221.003 time= 332.51
D-ALGO : 333 [CPU: 332.5 ] --- processNode() -----------> funcT =
0.455
D-ALGO : 333 [CPU: 333 ] <--- processNode() -----------
Process Node 242 (algo = PRICE_AND_CUT, phaseLast = PHASE_PRICE1) gLB =
150.78 gUB = 159 gap = 0.05452 time = 332.526
phase = PHASE_PRICE1
Processing Node 242 algo= PRICE_AND_CUT phase= PHASE_PRICE1 c= 0 p= 1
LB= -0.800 UB= 0.800 nodeLB= -0.800 gLB= 150.780 gUB=
159.000
lpGap= 2.000 ipGap= 199.750 time= 332.59
Processing Node 242 algo= PRICE_AND_CUT phase= PHASE_PRICE1 c= 0 p= 2
LB= -0.693 UB= 0.800 nodeLB= -0.693 gLB= 150.780 gUB=
159.000
lpGap= 2.154 ipGap= 230.327 time= 332.65
^CPress any key to continue . . .
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/dip/attachments/20140307/c387b44c/attachment.html>
More information about the Dip
mailing list