[Dip] Dip Digest, Vol 30, Issue 2
Shahin Gelareh
shahin.gelareh at gmail.com
Sat Mar 8 20:56:17 EST 2014
Hi Ted
I sent it to your email.
regards
Shahin
On Sat, Mar 8, 2014 at 6:00 PM, <dip-request at list.coin-or.org> wrote:
> Send Dip mailing list submissions to
> dip at list.coin-or.org
>
> To subscribe or unsubscribe via the World Wide Web, visit
> http://list.coin-or.org/mailman/listinfo/dip
> or, via email, send a message with subject or body 'help' to
> dip-request at list.coin-or.org
>
> You can reach the person managing the list at
> dip-owner at list.coin-or.org
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of Dip digest..."
>
>
> Today's Topics:
>
> 1. Re: issues with DualStabAlpha (Ted Ralphs)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Fri, 7 Mar 2014 17:27:48 -0600
> From: Ted Ralphs <ted at lehigh.edu>
> To: Shahin Gelareh <shahin.gelareh at gmail.com>
> Cc: dip <dip at list.coin-or.org>
> Subject: Re: [Dip] issues with DualStabAlpha
> Message-ID:
> <CA+GYycuH0Js8vPq=pT=
> JPTxWOG9WTr8iNmOZRA_gsysETP8EUA at mail.gmail.com>
> Content-Type: text/plain; charset="iso-8859-1"
>
> 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-0001.html
> >
>
> ------------------------------
>
> _______________________________________________
> Dip mailing list
> Dip at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/dip
>
> End of Dip Digest, Vol 30, Issue 2
> **********************************
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/dip/attachments/20140309/f50edabf/attachment.html>
More information about the Dip
mailing list