fd.m

整数规划的分枝定界法在MATLAB中的实现

function [x,val] = FD(n,f,a,b,aeq,beq,lb,ub)
%整数规划分支定界算法matlab通用源程序
%各参数的意义同matlab优化工具箱的线性规划函数linprog
%调用前，输入参数要化成matlab的标准形式

x=zeros(n,1); %制造一个n维的零向量
x1=zeros(n,1);
m1=2;
m2=1;
[x1,val1]=linprog(f,a,b,aeq,beq,lb,ub); % 经过线性规划得到初始点（可能不是整数）

if (x1==0)  % 如果x1为0
   x=x1;
   val=val1;
elseif (round(x1)==x1) % 如果得到了整数解则算法停止
   x=x1;
   val=val1;
else                   % 否则，下述为分枝定界的过程
   e1={0,a,b,aeq,beq,lb,ub,x1,val1}; % 将上述量存放成细胞型数据
   e(1,1)={e1};       % e表示细胞的集合，对应分支树      
   zl=0;              % 最优值的边界
   zu=-val1;
  while (zu~=zl)
     for c=1:1:m2    
       if (m1~=2)      %一个细胞分支无解，则它的左右子节点也无解，
         if (cell2mat(e{m1-1,c}(1))==1)
            e1={1,[],[],[],[],[],[],[],0};
            e(m1,c*2-1)={e1};
            e(m1,c*2)={e1};
            continue;
         end;
       end;
       x1=cell2mat(e{m1-1,c}(8));   %一个节点分支的初始化  
       x2=zeros(n,1);
       s=0;
       s1=1;
       s2=1;
       lb1=cell2mat(e{m1-1,c}(6));
       ub1=cell2mat(e{m1-1,c}(7));
       lb2=cell2mat(e{m1-1,c}(6));
       ub2=cell2mat(e{m1-1,c}(7));

       for d=1:1:n              %分支
         if (abs((round(x1(d))-x1(d)))>0.0001)&(s==0)           %该节点的最优解非整数且未分支(s=0)
           s=1;
           lb1(d)=fix(x1(d))+1;      %左右分支后定新界lb1、ub2，如果满足约束条件，s1、s2置0，表示有解
             if (a*lb1<=b)
               s1=0;
             end;
             ub2(d)=fix(x1(d));
             if (a*lb2<=b)
               s2=0;
             end;
         end;
       end;

       e1={s1,a,b,aeq,beq,lb1,ub1,[],0};       %将分支的结果存放入细胞内，整数解和最优值未知
       e2={s2,a,b,aeq,beq,lb2,ub2,[],0};
       e(m1,c*2-1)={e1};
       e(m1,c*2)={e2};
     end;

     m1=m1+1;             %细胞集合的行、列数更新，m2=2^(m1-2)
     m2=m2*2;
     
     for c=1:1:m2
        if (cell2mat(e{m1-1,c}(1))==0)  %新的边界下求解，结果存放入细胞内
           [x1,val1]=linprog(f,cell2mat(e{m1-1,c}( 2)),cell2mat(e{m1-1,c}(3)),cell2mat(e{m1-1,c}(4)),cell2mat(e{m1-1,c}(5)),cell2mat(e{m1-1,c}(6)),cell2mat(e{m1-1,c}(7)));
           e1={cell2mat(e{m1-1,c}(1)),cell2mat(e{m1-1,c}(2)),cell2mat(e{m1-1,c}(3)),cell2mat(e{m1-1,c}(4)),cell2mat(e{m1-1,c}(5)),cell2mat(e{m1-1,c}(6)),cell2mat(e{m1-1,c}(7)),x1,val1};
           e(m1-1,c)={e1};
        end;
        z=val1;        %如果最优值超过下界，所得解不可用
        if ((-z)<(-zl))
           e1={1,[],[],[],[],[],[],[],0};
           e(m1-1,c)={e1};
        elseif (abs(round(x1)-x1)<=0.0001)   %如果所得解接近整数，将最优值的下界更新
           zl=z;  
        end;
    end;
    
    for c=1:1:m2
       if (cell2mat(e{m1-1,c}(1))==0)    %最优值的上界更新
          zu=cell2mat(e{m1-1,c}(9));
       end;
    end;
    
    for c=1:1:m2
       if (-cell2mat(e{m1-1,c}(9))>(-zu))
         zu=cell2mat(e{m1-1,c}(9));
       end;
    end;
  end;    %while循环结束，最优值的上下界相等

  for c=1:1:m2
     if (cell2mat(e{m1-1,c}(1))==0)&(cell2mat(e{m1-1,c}(9))==zu)   %整数解
        x=cell2mat(e{m1-1,c}(8));
     end;
  end;
  
val=zu;                         %最优值

end;