[Dip] issues with DualStabAlpha
Ted Ralphs
ted at lehigh.edu
Fri Mar 7 18:27:48 EST 2014
HI Shahin,
Thanks for this report. Dual stabilization is not well tested, but it's
something I have wanted to take a look at. Can you share the instance with
which you generated these results?
Cheers,
Ted
On Fri, Mar 7, 2014 at 6:27 AM, Shahin Gelareh <shahin.gelareh at gmail.com>wrote:
> 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 . . .
>
> _______________________________________________
> Dip mailing list
> Dip at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/dip
>
--
Dr. Ted Ralphs
Associate Professor, Lehigh University
(610) 628-1280
ted 'at' lehigh 'dot' edu
coral.ie.lehigh.edu/~ted
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/dip/attachments/20140307/41d6ef37/attachment.html>
More information about the Dip
mailing list