Mathematica 教學：Branch-and-Bound method for Integer Programming

I write this program to draw the tree plot to demonstrate the Branch-and-Bound method for Integer Programming.

myIPTreePlot[lpprob_List,level_]:=Block[{initans,vars,BaB,myans},
initans=LinearProgramming@@lpprob;
vars=ToExpression["x"<>ToString[#]&/@Range[Length@lpprob[[1]]]];

BaB[{prob_,ans_}]:=Block[{bb,left,right,bbprob,mypath},
bb=Table[fun[var],{var,ans[[1,-1]]},{fun,{Floor,Ceiling}}];
left[n_]:={prob[[1]],Insert[prob[[2]],
-IdentityMatrix[Length@ans[[1,-1]]][[n]],-1],
Insert[prob[[3]],-bb[[n,1]],-1]};
right[n_]:={prob[[1]],Insert[prob[[2]],
IdentityMatrix[Length@ans[[1,-1]]][[n]],-1],
Insert[prob[[3]],bb[[n,2]],-1]};

mypath=
Quiet@Flatten[Map[{#,{Insert[ans[[1]],LinearProgramming@@#,-1],
Insert[ans[[2]],
Flatten[{#[[2,-1]],#[[3,-1]]}],-1]}}&,
Table[{left[n],right[n]},{n,Length@bb}],{2}],1];
mypath=If[FreeQ[#[[2,1,1;;-2]],#[[2,1,-1]]],#,{prob,ans}]&/@mypath;
mypath=If[Head[#[[2,1,-1]]]===LinearProgramming,{prob,ans},#]&/@mypath];

myans=Select[Flatten[NestList[Flatten[Map[BaB,#],1]&,
{{lpprob,{{initans},{Table[0,{1+Length@lpprob[[1]]}]}}}},
level],1][[All,2,2]],Length[#]>=2&];

TreePlot[Gather[Flatten[#[[1;;-2]]->#&/@myans,1]][[All,1]],
VertexLabeling->True,DirectedEdges->True,
VertexRenderingFunction->({Yellow,Black,
Text[Framed[If[#2[[-1,1;;-2]]===Table[0,{Length@lpprob[[1]]}],
Grid[{{initans},{lpprob[[1]].initans}},Frame->All,
Spacings->{1,1}],
Grid[{{Reduce[Thread[#2[[All,1;;2]].vars>=#2[[All,-1]]]]},
{LinearProgramming@@{lpprob[[1]],
Join[lpprob[[2]],#2[[All,1;;-2]]],
Join[lpprob[[3]],#2[[All,-1]]]}}},Frame->All,
Spacings->{2,2}]],Background->RGBColor[1,1,0.8],
FrameStyle->RGBColor[0.94,0.85,0.36]],#1]}&),
ImageSize->600]
]


myIPTreePlot[-{{3,4},{{2,1},{2,3}},{6,9}},5]

myIPTreePlot[{{-5,-8},{{-1,-1},{-5,-9}},{-6,-45}},5]

Tags: Mathematica 教學, Mathematica 教學 畫圖, Mathematica 教學 程式

• 編輯文章
• 此文章網址
• 轉寄此文章
• 目前有0 意見