function?[newxnewfvalstatusnewbound]?=?branchbound（fABIxfvalboundAeqBeqlbube）

%?分支定界法求解整數規劃
%?fABAeqBeqlbub與線性規劃相同
%?I為整數限制變量的向量
%?x為初始解，fval為初始值

options?=?optimset（‘display‘‘off‘）;
[x0fval0status0]=linprog（fABAeqBeqlbub[]options）;

%遞歸中的最終退出條件
%無解或者解比現有上界大則返回原解
if?status0?<=?0?||?fval0?>=?bound
????newx?=?x;
????newfval?=?fval;
????newbound?=?bound;
????status?=?status0;
????return;
end

%是否為整數解如果是整數解則返回
intindex?=?find（abs（x0（I）?-?round（x0（I）））?>?e）;
if?isempty（intindex）
????newx（I）?=?round（x0（I））;
????newfval?=?fval0;
????newbound?=?fval0;
????status?=?1;
????return;
end

%當有非整可行解時，則進行分支求解
%此時必定會有整數解或空解
%找到第一個不滿足整數要求的變量
n?=?I（intindex（1））;
addA?=?zeros（1length（f））;
addA（n）?=?1;
%構造第一個分支?x<=floor（x（n））
A?=?[A;addA];
B?=?[Bfloor（x（n））];
[x1fval1status1bound1]?=?branchbound（fABIx0fval0boundAeqBeqlbube）;
A（end:）?=?[];
B（:end）?=?[];
%解得第一個分支，若為更優解則替換，若不是則保持原狀

status?=?status1;
if?status1?>?0?&&?bound1?????newx?=?x1;
????newfval?=?fval1;
????bound?=?fval1;
????newbound?=?bound1;
else
????newx?=?x0;
????newfval?=?fval0;
????newbound?=?bound;
end

%構造第二分支
A?=?[A;-addA];
B?=?[B-ceil（x（n））];
[x2fval2status2bound2]?=?branchbound（fABIx0fval0boundAeqBeqlbube）;????
A（end:）?=?[];
B（:end）?=?[];

%解得第二分支，并與第一分支做比較，如果更優則替換
if?status2?>?0?&&?bound2?????status?=?status2;
????newx?=?x2;
????newfval?=?fval2;
????newbound?=?bound2;
end

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2010-05-25?23:52??運籌學整數規劃分支定界法MATLAB實現（中文注釋）\
?????文件????????1679??2010-05-25?23:34??運籌學整數規劃分支定界法MATLAB實現（中文注釋）\branchbound.m
?????文件????????1294??2010-05-25?23:33??運籌學整數規劃分支定界法MATLAB實現（中文注釋）\intprog.m
?????文件?????????208??2010-05-25?23:51??運籌學整數規劃分支定界法MATLAB實現（中文注釋）\test.m