lecture-column-generation

《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.MyXbxs,bb2B,s2Slsxs,bLb2BsX2Sxs,bdss2Sb2Byb2{0,1}b2Bxs,

8、b2Ns2S,b2B8Thursday,13June13AFirstMIPModelXminybminimizethenumberofboardsb2Bs.t.MyXbxs,bb2B,s2Slsxs,bLb2BsX2Sxs,bdss2Sb2Byb2{0,1}b2Bxs,b2Ns2S,b2B8Thursday,13June13