intprogram.m

清华大学运筹学课件

% the programm is with the integer linear programming use branch and bound method!
% please input the parameters in the main function in the command winows

function [x,f]=ILp(c,A,b,vlb,vub,x0,neqcstr,pre)

% min f=c'*x,s.t. A*x<=b,vlb<=x<=vub
% the vectors of x is required as integers as whole
% x0 is the initialization,'[]' is also ok
% neqcstr is the number of equational constraints,when 0 can be delete
% pre is the concise rate
% x is the integer optimization and f is the optimal value


%%%%%%%%%%%%%%%%


if nargin<8,pre=0;      % nargin is the factually input variants number 
  if nargin<7,neqcstr=0;
    if nargin<6,x0=[];
      if nargin<5,vub=[];
        if nargin<4,vlb=[];
        end
      end
    end
  end
end

%%%%%%%%%%%%%%%%%%

% set to column vectors

x0=x0(:);
c=c(:);
b=b(:);
vlb=vlb(:);
vub=vub(:);
mm=1;
j=1;
nvars=length(c');   % number of variants

fvub=inf;     
xall=[];
fall=[];
x_f_b=[];
[xtemp,ztemp,how]=lp(c,A,b,vlb,vub,x0,neqcstr,-1);

ftemp=c'*xtemp;

%%%%%%%%%%%%%%%%%%%%%%%

if strcmp(how,'ok')      % compare between how and ok
   temp0=round(xtemp);
   temp1=floor(xtemp);
   temp2=find(abs(xtemp-temp0)>pre);
   mtemp=length(temp2);
   if ~isempty(temp2)
       x_f_b=[xtemp;ftemp;vlb;vub];
     while j<=mm
         i=1;
          while i<=mtemp
            
             %%%%%%%%%%%%%%%%%%%%%
             if x_f_b(nvars+1,j)<=fvub
              vlbl=x_f_b(nvars+2:2*nvars+1,j);
              vubl=x_f_b(2*nvars+2:3*nvars+1,j);
              vubl(temp2(i))=temp1(temp2(i));
              [xtemp,z,how]=lp(c,[A;c'],[b;fvub],vlbl,vubl,x0,neqcstr,-1);
              ftemp=c'*xtemp; 
               
                 if strcmp(how,'ok')
                    templ0=round(xtemp);
                    templ1=floor(xtemp);
                    templ2=find(abs(xtemp-templ0)>pre); 
                   if isempty(templ2)
                      xall=[xall,xtemp];
                      fall=[fall,ftemp];
                      fvub=min([fvub,fall]);
                   elseif ftemp<=fvub
                      x_f_b=[x_f_b,[xtemp;ftemp;vlbl;vubl]];
                   end
                 end
            end
           %%%%%%%%%%%%%%%%%%
            if x_f_b(nvars+1,j)<=fvub
               vlbr=x_f_b(nvars+2:2*nvars+1,j);
               vlbr(temp2(i))=temp1(temp2(i))+1;
               vubr=x_f_b(2*nvars+2:3*nvars+1,j);
            
               [xtemp,z,how]=lp(c,[A;c'],[b;fvub],vlbr,vubr,x0,neqcstr,-1);
               ftemp=c'*xtemp;
            
                 if strcmp(how,'ok')
                    tempr0=round(xtemp);
                    tempr1=floor(xtemp);
                    tempr2=find(abs(xtemp-tempr0)>pre);
                   if isempty(tempr2)
                      xall=[xall,xtemp];
                      fall=[fall,ftemp];
                      fvub=min([fvub,fall]);
                   elseif ftemp<=fvub
                      x_f_b=[x_f_b,[xtemp;ftemp;vlbr;vubr]];
                   end
                 end
            end
           %%%%%%%%%%%%%%%%%%%%%
           
          i=i+1;

        end  % the second while 

     xint=x_f_b(1:nvars,:);
     [m,mm]=size(xint);
     
     j=j+1; 
   


     if j>mm
          break
     end   % the end because the break 

     temp0=round(xint(:,j));
     temp1=floor(xint(:,j));
     temp2=find(abs(xint(:,j)-temp0)>pre);
     mtemp=length(temp2);
    end  % the end of while
    
   else  % correspond the second if
      x=xtemp;
      f=ftemp;
   end   % the end of second if

%%%%%%%%%%%%%%%%%%5
   if ~isempty(fall)
       fmin=min(fall);
       nmin=find(fall==fmin);
       x=xall(:,nmin);
       f=fmin;
   end

else  % correspond the first if
     x=nan*ones(1,nvars);
     
end