<div dir="ltr"><div><div>Hi Ted<br><br></div>I sent it to your email.<br><br></div>regards<br>Shahin<br></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Mar 8, 2014 at 6:00 PM, <span dir="ltr"><<a href="mailto:dip-request@list.coin-or.org" target="_blank">dip-request@list.coin-or.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Send Dip mailing list submissions to<br>
<a href="mailto:dip@list.coin-or.org">dip@list.coin-or.org</a><br>
<br>
To subscribe or unsubscribe via the World Wide Web, visit<br>
<a href="http://list.coin-or.org/mailman/listinfo/dip" target="_blank">http://list.coin-or.org/mailman/listinfo/dip</a><br>
or, via email, send a message with subject or body 'help' to<br>
<a href="mailto:dip-request@list.coin-or.org">dip-request@list.coin-or.org</a><br>
<br>
You can reach the person managing the list at<br>
<a href="mailto:dip-owner@list.coin-or.org">dip-owner@list.coin-or.org</a><br>
<br>
When replying, please edit your Subject line so it is more specific<br>
than "Re: Contents of Dip digest..."<br>
<br>
<br>
Today's Topics:<br>
<br>
1. Re: issues with DualStabAlpha (Ted Ralphs)<br>
<br>
<br>
----------------------------------------------------------------------<br>
<br>
Message: 1<br>
Date: Fri, 7 Mar 2014 17:27:48 -0600<br>
From: Ted Ralphs <<a href="mailto:ted@lehigh.edu">ted@lehigh.edu</a>><br>
To: Shahin Gelareh <<a href="mailto:shahin.gelareh@gmail.com">shahin.gelareh@gmail.com</a>><br>
Cc: dip <<a href="mailto:dip@list.coin-or.org">dip@list.coin-or.org</a>><br>
Subject: Re: [Dip] issues with DualStabAlpha<br>
Message-ID:<br>
<CA+GYycuH0Js8vPq=pT=<a href="mailto:JPTxWOG9WTr8iNmOZRA_gsysETP8EUA@mail.gmail.com">JPTxWOG9WTr8iNmOZRA_gsysETP8EUA@mail.gmail.com</a>><br>
Content-Type: text/plain; charset="iso-8859-1"<br>
<br>
HI Shahin,<br>
<br>
Thanks for this report. Dual stabilization is not well tested, but it's<br>
something I have wanted to take a look at. Can you share the instance with<br>
which you generated these results?<br>
<br>
Cheers,<br>
<br>
Ted<br>
<br>
<br>
On Fri, Mar 7, 2014 at 6:27 AM, Shahin Gelareh <<a href="mailto:shahin.gelareh@gmail.com">shahin.gelareh@gmail.com</a>>wrote:<br>
<br>
> Dear all<br>
><br>
> I have a MIP decomposed into a RMP and three pricing problems.<br>
> The RMP is feasible because I added a feasible solution in the relevant<br>
> function.<br>
><br>
> The optimal solution is 149 and the feasible solution I added is 213.<br>
> The decomposition suffers from the degeneracy and the fact that dual duals<br>
> are not promising after some time.<br>
><br>
> I have set DualStab = 1 and played with DualStabAlpha. Strange results<br>
> have been observed. In brief with low DualStabAlpha I get optimal solution<br>
> but with higher values the solution is wrong.<br>
><br>
> I appreciate any comment.<br>
> Shahin<br>
><br>
> For DualStabAlpha = 0.3 I have optimality.<br>
><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 *BestLB= 149.00000 BestUB= 149.00000* Nodes= 58 SetupCPU=<br>
> 0.78 SolveCPU= 257.59 TotalCPU= 258.36 SetupReal= 0.77 SetupReal= 257.59<br>
> TotalReal= 1<br>
> .55<br>
> ERROR. BestKnownUB= 1e+020 but DECOMP claims GlobalUB= 149<br>
> Press any key to continue . . .<br>
><br>
><br>
> For DualStabAlpha = 0.9 I face with a premature convergence to a<br>
> non-optimal solution<br>
><br>
> Processing Node 2 algo= PRICE_AND_CUT phase= PHASE_PRICE1 c= 0 p=<br>
> 3 LB= -0.768 UB= 0.720 nodeLB= -0.768 gLB= -2.563 gUB=<br>
> 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=<br>
> 4 LB= -0.694 UB= 0.720 nodeLB= -0.694 gLB= -2.563 gUB=<br>
> 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=<br>
> 5 LB= -0.548 UB= 0.693 nodeLB= -0.548 gLB= -2.563 gUB=<br>
> 231.00<br>
> lpGap= 2.265 ipGap= 422.755 time= 7.10<br>
> D-ALGO : 7.11 [CPU: 7.107 ] --- processNode() -----------> funcT<br>
> = 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 *BestLB= 231.00000 BestUB= 231.00000* Nodes= 3 SetupCPU=<br>
> 0.90 SolveCPU= 6.27 TotalCPU= 7.17 SetupReal= 0.90 SetupReal= 6.27<br>
> TotalReal= 1.79<br>
> ERROR. BestKnownUB= 1e+020 but DECOMP claims GlobalUB= 231<br>
> Press any key to continue . . .<br>
><br>
><br>
> with DualStabAlpha = 0.7 we get a lower bound which is higher than the<br>
> optimal I know (I terminated the iterations manually).<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=<br>
> 6 LB= -1.184 UB= 0.200 nodeLB= -1.118 gLB= 150.780 gUB=<br>
> 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=<br>
> 7 LB= -0.723 UB= 0.200 nodeLB= -0.723 gLB= 150.780 gUB=<br>
> 159.000<br>
> lpGap= 1.277 ipGap= 221.003 time= 332.51<br>
> D-ALGO : 333 [CPU: 332.5 ] --- processNode() -----------> funcT<br>
> = 0.455<br>
> D-ALGO : 333 [CPU: 333 ] <--- processNode() -----------<br>
> Process Node 242 (algo = PRICE_AND_CUT, phaseLast = PHASE_PRICE1) gLB =<br>
> 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=<br>
> 1 LB= -0.800 UB= 0.800 nodeLB= -0.800 gLB= 150.780 gUB=<br>
> 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=<br>
> 2 LB= -0.693 UB= 0.800 nodeLB= -0.693 gLB= 150.780 gUB=<br>
> 159.000<br>
> lpGap= 2.154 ipGap= 230.327 time= 332.65<br>
> ^CPress any key to continue . . .<br>
><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>
><br>
<br>
<br>
<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>
-------------- next part --------------<br>
An HTML attachment was scrubbed...<br>
URL: <<a href="http://list.coin-or.org/pipermail/dip/attachments/20140307/41d6ef37/attachment-0001.html" target="_blank">http://list.coin-or.org/pipermail/dip/attachments/20140307/41d6ef37/attachment-0001.html</a>><br>
<br>
------------------------------<br>
<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>
<br>
End of Dip Digest, Vol 30, Issue 2<br>
**********************************<br>
</blockquote></div><br></div>