<div dir="ltr"><div><div>HI Shahin,<br><br></div>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?<br>
<br></div>Cheers,<br><div><br>Ted<br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Mar 7, 2014 at 6:27 AM, Shahin Gelareh <span dir="ltr"><<a href="mailto:shahin.gelareh@gmail.com" target="_blank">shahin.gelareh@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Dear all<br><br>I have a MIP decomposed into a RMP and three pricing problems.<br></div><div>The RMP is feasible because I added a feasible solution in the relevant function.<br>
<br></div><div>The optimal solution is 149 and the feasible solution I added is 213.<br>
</div><div>The decomposition suffers from the degeneracy and the fact that dual duals are not promising after some time.<br><br></div><div>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.<br>
<br></div><div>I appreciate any comment.<br></div><div>Shahin<br></div><div><br></div><div><span style="background-color:rgb(255,0,0)">For DualStabAlpha = 0.3 I have optimality.</span><br></div><div><br>Alps0208I Search completed.<br>
Alps0261I Best solution found had quality 149 and was found at depth 30<br>Alps0265I Number of nodes fully processed: 58<br>Alps0266I Number of nodes partially processed: 3<br>Alps0267I Number of nodes branched: 30<br>
Alps0268I Number of nodes pruned before processing: 0<br>Alps0270I Number of nodes left: 0<br>Alps0272I Tree depth: 8<br>Alps0274I Search CPU time: 257.53 seconds<br>Alps0278I Search wall-clock time: 257.53 seconds<br>
<br>================ DECOMP Statistics [BEGIN]: ===============<br>Total Decomp = 256.57 100.00 61 16.95<br>Total Solve Relax = 253.52 98.81 7461 0.48<br>Total Solve Relax App = 0.01 0.00 7461 0.00<br>
Total Solution Update = 17.72 6.91 2780 0.07<br>Total Generate Cuts = 0.15 0.06 6 0.03<br>Total Generate Vars = 204.81 79.83 2485 0.47<br>Total Compress Cols = 0.56 0.22 391 0.01<br>
================ DECOMP Statistics [END ]: ===============<br>x(0)(1)(2)(1) 1.00<br>x(0)(2)(1)(2) 1.00<br>x(0)(4)(0)(4) 1.00<br>x(1)(3)(2)(4) 1.00<br>x(2)(6)(1)(8) 1.00<br>
x(3)(5)(2)(9) 1.00<br>x(4)(8)(0)(12) 1.00<br>x(5)(7)(2)(16) 1.00<br>x(6)(0)(1)(14) 1.00<br>x(7)(0)(2)(23) 1.00<br>x(8)(0)(0)(20) 1.00<br>Status= 0 <font size="4"><b>BestLB= 149.00000 BestUB= 149.00000</b></font> Nodes= 58 SetupCPU= 0.78 SolveCPU= 257.59 TotalCPU= 258.36 SetupReal= 0.77 SetupReal= 257.59 TotalReal= 1<br>
.55<br>ERROR. BestKnownUB= 1e+020 but DECOMP claims GlobalUB= 149<br>Press any key to continue . . .<br><br><br></div><span style="background-color:rgb(255,0,0)">For DualStabAlpha = 0.9 I face with a premature convergence to a non-optimal solution</span><br>
<br>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<br>lpGap= 1.938 ipGap= 301.777 time= 6.86<br>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<br>
lpGap= 2.038 ipGap= 333.932 time= 6.98<br>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<br>lpGap= 2.265 ipGap= 422.755 time= 7.10<br>
D-ALGO : 7.11 [CPU: 7.107 ] --- processNode() -----------> funcT = 0.678<br><br>Alps0208I Search completed.<br>Alps0261I Best solution found had quality 231 and was found at depth 0<br>Alps0264I Number of nodes processed: 3<br>
Alps0267I Number of nodes branched: 1<br>Alps0268I Number of nodes pruned before processing: 0<br>Alps0270I Number of nodes left: 0<br>Alps0272I Tree depth: 1<br>Alps0274I Search CPU time: 6.21 seconds<br>
Alps0278I Search wall-clock time: 6.21 seconds<br><br>================ DECOMP Statistics [BEGIN]: ===============<br>Total Decomp = 6.14 100.00 3 3.57<br>Total Solve Relax = 8.46 137.76 144 0.54<br>
Total Solve Relax App = 0.00 0.00 144 0.00<br>Total Solution Update = 0.22 3.65 46 0.01<br>Total Generate Cuts = 0.00 0.00 0 0.00<br>Total Generate Vars = 5.26 85.66 46 0.15<br>
Total Compress Cols = 0.00 0.00 0 0.00<br>================ DECOMP Statistics [END ]: ===============<br>x(0)(6)(1)(6) 1.00<br>x(0)(7)(2)(7) 1.00<br>x(0)(8)(0)(8) 1.00<br>
x(1)(0)(2)(29) 1.00<br>x(2)(0)(1)(18) 1.00<br>x(3)(1)(2)(28) 1.00<br>x(4)(0)(0)(24) 1.00<br>x(5)(3)(2)(23) 1.00<br>x(6)(2)(1)(16) 1.00<br>x(7)(5)(2)(16) 1.00<br>
x(8)(4)(0)(20) 1.00<br>Status= 0 <font size="4"><b>BestLB= 231.00000 BestUB= 231.00000</b></font> Nodes= 3 SetupCPU= 0.90 SolveCPU= 6.27 TotalCPU= 7.17 SetupReal= 0.90 SetupReal= 6.27 TotalReal= 1.79<br>
ERROR. BestKnownUB= 1e+020 but DECOMP claims GlobalUB= 231<br>Press any key to continue . . .<br><div><br><br></div><div><span style="background-color:rgb(255,0,0)">with DualStabAlpha = 0.7 we get a lower bound which is higher than the optimal I know (I terminated the iterations manually).</span><br>
<br>lpGap= 1.179 ipGap= 143.197 time= 332.39<br>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<br>
lpGap= 1.179 ipGap= 143.197 time= 332.45<br>
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<br>lpGap= 1.277 ipGap= 221.003 time= 332.51<br>D-ALGO : 333 [CPU: 332.5 ] --- processNode() -----------> funcT = 0.455<br>
D-ALGO : 333 [CPU: 333 ] <--- processNode() -----------<br>Process Node 242 (algo = PRICE_AND_CUT, phaseLast = PHASE_PRICE1) gLB = 150.78 gUB = 159 gap = 0.05452 time = 332.526<br>phase = PHASE_PRICE1<br>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<br>
lpGap= 2.000 ipGap= 199.750 time= 332.59<br>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<br>lpGap= 2.154 ipGap= 230.327 time= 332.65<br>
^CPress any key to continue . . .<br></div></div>
<br>_______________________________________________<br>
Dip mailing list<br>
<a href="mailto:Dip@list.coin-or.org">Dip@list.coin-or.org</a><br>
<a href="http://list.coin-or.org/mailman/listinfo/dip" target="_blank">http://list.coin-or.org/mailman/listinfo/dip</a><br></blockquote></div><br><br clear="all"><br>-- <br>Dr. Ted Ralphs<br>Associate Professor, Lehigh University<br>
(610) 628-1280<br>ted 'at' lehigh 'dot' edu<br><a href="http://coral.ie.lehigh.edu/~ted" target="_blank">coral.ie.lehigh.edu/~ted</a><br>
</div>