资源描述:
《lecture-column-generation》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、DiscreteOptimizationColumnGenerationThursday,13June13GoalsoftheLecture‣Columngeneration–introduction–cuttingstock2Thursday,13June13Motivation‣BranchandCut–solvingaMIPwithexponentiallymanyconstraints•subtourconstraints–generatetheconstraintsondemand‣Columngenerat
2、ion–solvingaLPwithexponentiallymanyvariables–variablesrepresentcomplexobjects‣BranchandPrice–solvingaMIPwithexponentiallymanyvariables–branchingovercolumngeneration3Thursday,13June13CuttingStock(GilmoreandGomory)‣Given–anumberoflargewoodboardsofalengthL–anumbero
3、fshelvesofvarioussizesthatneedtobecutfromtheboards–thedemandforeachshelfsize•howmanytocut.‣Find–thesmallestnumberofboardstocutinordertomeetthedemandforshelves4Thursday,13June13CuttingStock(GilmoreandGomory)L=11020455055755Thursday,13June13CuttingStock(Gilmoreand
4、Gomory)L=11020d1=4845d2=3550d3=2455d4=1075d5=85Thursday,13June13CuttingStock(GilmoreandGomory)L=1106Thursday,13June13CuttingStock(GilmoreandGomory)L=11020756Thursday,13June13CuttingStock(GilmoreandGomory)L=110207550556Thursday,13June13CuttingStock(GilmoreandGomo
5、ry)L=1102075505520202020206Thursday,13June13AFirstMIPModel‣Decisionvariables–yb=1ifboardbisusedinthesolution–xsbisthenumberofshelvesoftypescutfromboardb7Thursday,13June13AFirstMIPModel‣Decisionvariables–yb=1ifboardbisusedinthesolution–xsbisthenumberofshelvesofty
6、pescutfromboardb‣Constraints–aboardisusedifsomeshelfiscutfromit–theshelvescutfromaboardcannotexceedthecapacityoftheboard–thedemandismet7Thursday,13June13AFirstMIPModel‣Decisionvariables–yb=1ifboardbisusedinthesolution–xsbisthenumberofshelvesoftypescutfromboardb‣
7、Constraints–aboardisusedifsomeshelfiscutfromit–theshelvescutfromaboardcannotexceedthecapacityoftheboard–thedemandismet‣Objectives–minimizethenumberofboardsused7Thursday,13June13AFirstMIPModelXminybb2Bs.t.MyXb xs,bb2B,s2Slsxs,bLb2BsX2Sxs,b dss2Sb2Byb2{0,1}b2Bxs,
8、b2Ns2S,b2B8Thursday,13June13AFirstMIPModelXminybminimizethenumberofboardsb2Bs.t.MyXb xs,bb2B,s2Slsxs,bLb2BsX2Sxs,b dss2Sb2Byb2{0,1}b2Bxs,b2Ns2S,b2B8Thursday,13June13