l01p_ie.m

清华大学运筹学课件

% the programm is with the integer 0-1 programming use inenumber method

function [x,f]=L01p_ie(c,A,b,N)

% the function is use the inenumber function
% 0-1 linear programming problem
% min f=c'*x,s.t.A*x<=b,x=0 or 1
% N is the number of equational constraints in the front of the constraints
% x is the optimal solution and the f is the optimal value

if nargin<4
   N=0;
end

c=c(:);
b=b(:);
A=[-A(1:N,:);A];
b=[-b(1:N);b];


[m,n]=size(A);
x=[];
f=abs(c')*ones(n,1);
A=[c';A];
b=[f;b];

i=1;
while i<=2^n
      B=transdetobi(i-1,n)';
      j=1;
      t1=A(j,:)*B-b(j);
      
      while (t1<=0&j<m+1)
            j=j+1;
            t1=A(j,:)*B-b(j);
            if t1>0
            j=1;
            end
      end

      if j==m+1
         x=B;
         f=c'*B;
         b(1)=min([b(1),f]);
      end
  i=i+1;
end