function [optSolution,optValue,exists]=BranchBound(c,A,b)
% 分支定界法
% 整数规划问题标准型
% min c'*x
% s.t.
% A*x<=b

upper = inf;
lower = -inf;
branchStack_A(1) = {A};
branchStack_B(1) = {b};
numOfVariable = length(c);

while ~isempty(branchStack_A)
    len = length(branchStack_A);
    A = branchStack_A{len};
    b = branchStack_B{len};
    branchStack_A(len) = [];
    branchStack_B(len) = [];
    
%     A
%     b
    [x,opt,exist] = linprog(c,A,b);
    if 1 == exist && (opt - upper) <= 1e-7
        for iVar = [1:numOfVariable + 1]
            if iVar <= numOfVariable
                if abs(x(iVar) - round(x(iVar))) > 1e-7
                    %进行分枝操作，就将子问题入栈
                    temp_A = zeros(1,numOfVariable);
                    
                    temp_A(iVar) = -1;
                    branchStack_A(len) = {[A;temp_A]};
                    branchStack_B(len) = {[b;-(floor(x(iVar) + 1))]};
                    
                    temp_A(iVar) = 1;
                    branchStack_A(len + 1) = {[A;temp_A]};
                    branchStack_B(len + 1) = {[b;floor(x(iVar))]};
                    break;
                end
            else
                %是个整数解.更新upper
                if abs(upper - opt) < 1e-7
                    optSolution(:,end + 1) = x;
                else
                    optSolution = x;
                    upper = opt;
                    optValue = opt;
                end
            end
        end %for
    end %if
end%while
   
sizeOfSolution = size(optSolution);
if sizeOfSolution(2) == 0
    exists = 0;
else
    exists = 1;
end
end