列生成算法程序

1、主程序:clear;time=cputime;fab=matrix_gen(K,T,n,M,LT,Sij,wi);m=length(f);e=-ones(1,n+K*T);e(1:n)=zeros(1,n);e=sparse(e);u=ones(1,m);extx=sparse(zeros(m,T);blpx=sparse(zeros(m,10000);var2_br=-ones(1,n);rmpobj,x=rmp_solve(n,K,T.extx,f,a,b,e,var2_br);s=1;if(round(x)=x) optx=x; optobj=rmpobj; returnelse upb

2、=rmpobj; lowb=greedy(f,a,b,m,n,K,T); indbou=find(min(abs(x(end-n+1:end)-0.5)=abs(x(end-n+1:end)-0.5),1,first); var_br=sparse(zeros(1,n); var_br(1,indbou)=1; var2_br=sparse(-ones(2,n); var2_br(1,indbou)=1 var2=find(var2_br(s,:)=1); blpf=f; blpa=a; blpa(indbou,m-n+indbou)=0; blpe=e; blpu=u; extx=spars

3、e(zeros(m,2*T); extx(:,1:T)=iexl(n,K,T,m,M,a,var2); if extx(:,1:T)=-ones(m,T) blpobj(s)=-1; blpx(:,s)=zeros(m,1); pool(s)=0; else pool(s)=s; end s=s+1; var2_br(2,indbou)=0; pool(s)=s; s=s+1; while(nnz(pool)0) bpool=max(pool); spool=bpool-1; for i=spool:bpool if i=spool j=1; else j=2; end blpobj(i),b

4、lpx(:,i)=rmp_solve(n,K,T,extx(:,(j-1)*T+1:j*T),blpf,blpa,blpb(j:),blpe,var2_br(i,:); if blpx(:,i)=zeros(m,1) blpx(m-n+indbou,i)=1; end pool(i)=0; end if round(blpx(end-n+1:end,spool)=blpx(:,spool) if blpobj(spool)lowb lowb=blpobj(spool); end end if max(blpobj)lowb branch=find(max(blpobj)=blpobj,1,fi

5、rst); upb=blpobj(branch); blpobj(branch)=-blpobj(branch); indbou=find(min(abs(blpx(end-n+1;branch)-0.5)=abs(blpx(end-n+1:end,branch)-0.5),1,first); var_br(s+1)/2,:)=var_br(ceil(branch/2),:); var_br(s+1)/2,indbou)=1; var=find(var_br(s+1)/2)=1); blpa=a; blpa(var,m-n+var)=0; blpa=sparse(blpa); var2_br(

6、s,:)=var2_br(branch,:); var2_br(s,indbou)=1; var2=find(var2_br(s,:)=1); blpb(1,:)=b; blpb(1,var2)=nonzeross(-a(var2,m-n+var2); extx(:,1:T)=iexl(n,K,T,m,M,a,var2); if extx(:,1:T)=-ones(m,T) blpobj(s)=-1; blpx(:,s)=zeros(m,1); pool(s)=0; else pool(s)=s; end s=s+1; var2_br(s,:)=var2_br(branch,:); var2_

7、br(s,indbou)=0; var2=find(varx_br(s,:)=1); blpb(2,:)=b; blpb(2,var2)=nonzeros(-a(var2,m-n+var2); extx(:,T+1:2*T)=iexl(n,K,T,m,M,a,var2); pool(s)=s; s=s+1; end endendr=cputime-timematrix_gen子程序：function f,a,b=matrix_gen(K,T,n,M,LT,Sij,wi)m=sum(LT(:,2)-LT(:,1)+2*n;f=sparse(zeros(1,m);a=sparse(zeros(n+

8、K*T,m);b=sparse(zeros(1,n+K*T);for i=1:T b(1,n+(i-1)*K:n+i*K)=M;endwj=Sij*wj;vf=0;for i=1:n v_n(i)=LT(i,2)-LT(i,1)+1; f(vf+1:vf+v_n(i)=wj(i); vf=vf+v_n(i);enda1=a(1:n,:);a2=a(n+1:n_K*T,:);vf=0;for i=1:n a1(i,vf+1:vf+v_n(i)=1; a1(i,m-n+i)=-v_n(i); vf=vf+v_n(i);endfor i=1:T for j=1:n if LT(j,1)=i & i0

9、 v_1=columnl(find(rowl=i); v_1=v_1; for j=1:length(v_1) v_1(1,j)=find(nz_col=v_1(1,j); end splow(v_1)=1; end if nnz(i=row0)0 v_0=column0(find(row0=i); v_0=v_0; for j=1:length(v_0) v_0(1,j)=find(nz_col=v_0(1,j); end spu(v_0)=0; end lp(i)=lp_maker(spf,spa,spb,spe,splow,1); mxlpsolve(solve,sp(i); spobj

10、(i)=mxlpsolve(get_objective,lp(i)-rmpdual(n+i);endincre=1;while max(spobj)le-1 ind=find(max(spobj)=spobj),1,first); inx=mxlpsolve(get_variables,lp(ind); for i=1:T mxlpsolve(delete_lp,lp(i); end l=sparse(zeros(m,T+incre); l(:,1:end-1)=extx; extx=1; extx(find(A(ind,:)=inx; nrmpf=zeros(1,T+incre+n); nr

11、mpf(1,1:T+incre)=f*extx; nrmpa1=a(1:n,:)*extx,a(1:n,m-n+1:m); nrmpa2=rmpa2(:,1:end-n),zeros(T,1),rmpa2(:,end-n+1:end); rmpa2(ind,end-n)=1; nrmpa=nrmpa1;nrmpa2; rmpu=ones(1,T+n+incre); rmpobj,rmpx,rmpdual=lp_solve(nrmpf,nrmpa,rmpb,rmpe,rmpu,1); if isempty(rmpobj)=1 x=zeros(m,1); return; end lp=zeros(

12、1,T); spobj=zeros(1,T); for i=1:T A(i,:)=sum(a(n+(i-1)*K+1:n+i*K,:); nz_col=find(A(i,:); row,column=find(a(1:n,nz_col); spf=f(nz_col)-rmpdual(row); spa=a(n+(i-1)*K+1:n+i*K),nz_col); spb=b(n+(i-1)*K+1:n+i*K); spe=e(n+(i-1)*K+1:n+i*K); splow=zeros(1,length(spf); spu=ones(1,length(spf); if nnz(i=rowl)0

13、 v_1=columnl(find(rowl=i); v_1=v_1; for j=1:length(v_1) v_1(1,j)=find(nz_col=v_1(1,j); end splow(v_1)=1; end if nnz(i=row0)0 v_0=column0(find(row0=i); v_0=v_0; for j=1:length(v_0) v_0(1,j)=find(nz_col=v_0(1,j); end spu(v_0)=0; end lp(i)=lp_maker(spf,spa,spb,spe,splow,1); mxlpsolve(solve,sp(i); spobj

14、(i)=mxlpsolve(get_objective,lp(i)-rmpdual(n+i); end incre=incre+1;endx1=extx*rmpx(1:end-n);if isempty(v1)=1 x=x1(1:m-n);rmpx(end-n+1:end);else job=rmpx(end-n+1:end)=1; x=x1(1:m-n);job;endx=sparse(x); greedy子程序：functionlowb,lowbx=greedy(f,a,b,m,n,K,T)v=zeros(1,n);lowbx=zeros(1,m);for i=1:n v(i)=sum(f

15、.*a(i,:);endR,I=sort(v,descend);lowb=0;for i=1:n nz_col=find(a(I(i),:); lowbx(1,nz_col)=1; if nnz(a*lowbx=b)n+K*T lowbx(1,nz_col)=0; else lowb=lowb+R(i); endend iexl子程序：function extx=iexl(n,K,T,m,M,a,var2)extx1=zeros(T,m);A=zeros(T,m);for i=1:T A(i,:)=sum(a(n+(i-1)*K+1:n+i*K,:);endfor j=1:length(var

16、2) indbou=var2(j); col=find(a(indbou,1:m-n); B=A(:,col); B(find(B)=1; extx1=(:,col)=B;endfor i=1:T nz_col=find(A(i,:); y1_col=nz_col(find(extx1(i,nz_col)=1); if isempty(nz_col(find(extx1(i,nz_col)=1,1,first)=1; if min(M-sum(a(n+(i-1)*K+1:n+i*K,y1_col),2)0 extx=-ones(m,T); return end else if isempty(nz_col(find(extx1(i,n