拉格朗日松弛算法-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),dual,1.尋找到下界 2.得到一個(gè)初始的解,illustration for dual problems,原問(wèn)題：尋找使得目標(biāo)值最小的x,對(duì)偶問(wèn)題：尋找使得目標(biāo)函數(shù)最大的,Steps of SG,Step1:選一個(gè)初始拉格朗日乘子如 0,t=1; Step2：對(duì)于 從中任選一個(gè)次梯度 ；若 0則達(dá)到了最優(yōu)解而停止計(jì)算；否則， t=t+1,重復(fù)STEP2；,Illustration of SG,upper1,上升很慢,Gama,Lemma1：when Lemma2： and for all k, then Halve the dual gap,Illustration for gama,upper,lower,description,Basic parallel machine scheduling,job4,job3,job2,job1,M2,M1,Pro_time, weight, duedate, start_time,目 標(biāo) 2.能力約束 3.自身約束,Formulation,problem formulation,Steps of LG method,step1 .relaxation of the hard constrain step2 .solve the L-G dual problem using S-G method step3. get feasible solution using heuristic alg0rithm,Why using LG method,Good primal sequence Good bound.,First step relaxation,Dual problem,Max min problem (LSS),Dual problem,decomposition,給定 將上述問(wèn)題分解成N個(gè)子問(wèn)題,Solve dual problem,給定一個(gè),將 帶回原問(wèn)題 得到關(guān)于 的函數(shù) 用次梯度法 得到一個(gè) 新的,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,List 按照（LG start） K=1,i=1,Mk=0?,no,有任務(wù)在k完成嗎,yes,Mk+;(k+1 N),yes,Set K= k+1,Reform the list,i+;調(diào)度下一個(gè)job,i=job_num?,re- fresh start,Refresh start,no,end,yes,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 paithe 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),Pai stands for the cost of resource at time k,Illustration for pai,不同時(shí)刻的pai在整個(gè)迭代過(guò)程中的趨向,K在,Illustration for pai,1.2.3.4.5分別代表不同的迭代時(shí)間,經(jīng)過(guò)迭代pai46最終的值,Illustration for pai,Pai !=0,Pai !=0; How can the solution of a completely different problem gives you a good primal solution?,原問(wèn)題一定跟對(duì)偶問(wèn)題很