function [x,optv] = bnb(f,A,b,Aeq,Beq,LB,UB,X0,OPTIONS,ind,optv) % this function solves the following linear programming by branch and bound method % % min f' * x % subject to A*x <= b % Aeq*x == Beq % LB <= x <= UB % x(ind) are integers % CHEN Xiongda if nargin<11, optv = + Inf; if nargin<10, ind = 1:length(f); if nargin<9, OPTIONS = optimset; if nargin<8, X0 = zeros(size(f)); if nargin<7, UB = + Inf * ones(size(X0)); if nargin<6, LB = - Inf * ones(size(X0)); end; end; end; end; end; end; [x,fval,exitflag] = linprog(f,A,b,Aeq,Beq,LB,UB,X0,OPTIONS); if exitflag<=0, % this program is infeasible or the algorithm failed, or reached the maximum % number of iterations without converging. return; elseif fval>=optv, % this program has an objective value no less than the solved ones. return; end if all(abs(round(x(ind))-x(ind))<=1e-8), optv = fval; % obtain an integer solution return; else z = find( abs(round(x(ind))-x(ind))>1e-8 ); z = ind(z(1)); UB1 = UB; UB1(z) = floor(x(z)); LB1 = LB; LB1(z) = ceil(x(z)); if UB1(z)>=LB(z), [x1,optv1] = bnb(f,A,b,Aeq,Beq,LB,UB1,x,OPTIONS,ind,optv); if optv1