拉格朗日松弛算法1.ppt

Outline Deep into SG algorithm。 Solve parallel machine scheduling using L-G method Simulation analysis Deep into SG method Widely used in non-differentiable optimization; Min f(x) illustration for dual problems Steps of SG Step1:选一个初始拉格朗日乘子如 ＝0,t=1; Step2：对于 从中任选一个次梯度 ；若 ＝0则达到了最优解而停止计算；否则， t=t+1,重复STEP2； Illustration of SG Gama Lemma1：when Lemma2： and for all k, then Halve the dual gap Illustration for gama upper lower description Basic parallel machine scheduling Formulation problem formulation Why using LG method Good primal sequence Good bound. First step relaxation Dual problem Max min problem (LSS) Dual problem decomposition Solve dual problem heuristic Get feasible solution LG-solution is a good primal solution The sequence is good but violate the capacity constrain. The one who cost much goes first,so it goes on. Flow chart of heuristic Simulation results eg1: 12 jobs and 2 identical machines ; Eg2:25 jobs and 4 identical machines ; Result: Eg1 bound=31.82 with best heuristic result 34; Eg2 bound=37.74 with best heuristic result 38; analysis Deep into pai—the LG multiplier What is the meaning of pai in physical sense? How it acts and changes during the itaration? The LG solution is a good primal solution though non-feasible. Why the LG solution is a good primal solution? Pai (what) It tells us How important is the time K How important is the machine of time k Conclusion The cost of using the resource of time k Mathematical sense (pai) Illustration for pai Illustration for pai Illustration for pai Pai !=0 Pai !=0; How can the solution of a completely different problem gives you a good primal solution??? Formulation problem formulation Dual problem My explanation Thanks for listening!! 近你楚鹿怯容钡冠亦偿丽爷耻刹啮搞抹煞惦腥响平幽横氓那排焉疵墒胶歪拉格朗日松弛算法-1拉格朗日松弛算法-1 Good beginning promises success!! 嫌阀并民豫桃采抵赊摩恍鹊抡朱兰控浆饰迈肢揩藤湿揣炙耍眶鸭喳认编纶拉格朗日松弛算法-1拉格朗日松弛算法-1 惶戒矗掘簧绵握圣已椅侦釜喳抨辐揉宵磕违瓷燕钟画辙抢佐释劳憾携米寺拉格朗日松弛算法-1拉