列生成算法程序.doc

主程序 :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;returnelseupb=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)=1var2=find(var2_br(s,:)=1);blpf=f;blpa=a;blpa(indbou,m-n+indbou)=0;blpe=e;blpu=u;extx=sparse(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;elsepool(s)=s;ends=s+1;var2_br(2,indbou)=0;pool(s)=s;s=s+1;while (nnz(pool)>0) bpool=max(pool); spool=bpool-1;fori=spool:bpool if i=spoolj=1;elsej=2;endblpobj(i),blpx(:,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;endif round(blpx(end-n+1:end,spool)=blpx(:,spool)if blpobj(spool)>lowblowb=blpobj(spool);endendif max(blpobj)>lowb branch=find(max(blpobj)=blpobj,1, 'first' ); 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(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;elsepool(s)=s;ends=s+1; var2_br(s,:)=var2_br(branch,:); var2_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;endendendr=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+K*T,m);b=sparse(zeros(1,n+K*T);for i=1:Tb(1,n+(i-1)*K:n+i*K)=M;endwj=Sij*wj;vf=0;for i=1:nv_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:na1(i,vf+1:vf+v_n(i)=1;a1(i,m-n+i)=-v_n(i);vf=vf+v_n(i);endfor i=1:Tfor j=1:nif LT(j,1)<=i & i<LT(j,2)col=find(a1(j,:);a2(i-1)*K+1:i*K,col(i-LT(j,1)+1)=Sij(j,:)'endendenda=a1;a2;rmp_solve 子程序 :function rmpobj,x=rmp_solve(n,K,T,extx,f,a,b,e,var2_br) m=length(f);A=zeros(T,m);v1=find(var2_br=1);v0=find(var2_br=0);for i=1:TA(i,:)=sum(a(n+(i-1)*K+1:n+i*K,:);endrowl=zeros(length(v1),T);columnl=rowl;for j=1:length(v1)col_1=find(a(v1(i),1:m-n); row_1,column_1=find(A(:,col_1); rowl(j,1:length(row_1)=row_1;columnl(j.1:lengrh(column)=col_1;endrow0=zeros(length(v0),T);colunm0=row0;for j=1:length(v0)col_0=find(a(v0(j),1:m-n);row_0,column_0=find(A(:,col_0) row0(j,1:length(row_0)=row_0; column0(j,1:length(column_0)=col_0;endif isempty(extx)=1rmpobj=-1;x=zeros(m,1);return ;endrmpf=f*extx;rmpf=rmpf,zeros(1,n);rmpa1=a(1:n,:)*extx;rmpa1=rmpal,a(1:n,m-n+1:m); rmpa2=eye(T,T),zeros(T,n); rmpa=rmpa1;rmpa2;rmpb=ones(1,T+n);rmpb(1:n)=b(1:n); rmpb=sparse(rmpb);rmpe=e(1:n+T); rmpu=ones(1:n+T); rmpobj,rmpx,rmpdual=lp_solve(rmpf,rmpa,rmpb,rmpe,rmpu,1);if isempty(rmpobj)=1rmpobj=-1;x=zeros(m,1);return ;endlp=zeros(1,T); spobj=zeros(1,T);for i=1;Tnz_col=find(A(i,:);row,column=fin(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 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; endlp(i)=lp_maker(spf,spa,spb,spe,splow,1);mxlpsolve( 'solve' ,sp(i);spobj(i)=mxlpsolve( 'get_objective' ,lp(i)-rmpdual(n+i);endincre=1;while max(spobj)>le-1ind=find(max(spobj)=spobj),1,'first'inx=mxlpsolve('get_variables',lp(ind);for i=1:Tmxlpsolve('delete_lp' ,lp(i);endl=sparse(zeros(m,T+incre);l(:,1:end-1)=extx;extx=1;extx(find(A(ind,:)=inx;nrmpf=zeros(1,T+incre+n);nrmpf(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)=1x=zeros(m,1);return ;endlp=zeros(1,T);spobj=zeros(1,T);for i=1:TA(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)>0v_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);endsplow(v_1)=1;endif nnz(i=row0)>0v_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);endspu(v_0)=0;,lp(i)-rmpdual(n+i);end lp(i)=lp_maker(spf,spa,spb,spe,splow,1); mxlpsolve( 'solve' ,sp(i); spobj(i)=mxlpsolve( 'get_objective' endincre=incre+1;endx1=extx*rmpx(1:end-n);if isempty(v1)=1x=x1(1:m-n);rmpx(end-n+1:end);elsejob=rmpx(end-n+1:end)=1;x=x1(1:m-n);job;endx=sparse(x);greedy 子程序：function lowb,lowbx=greedy(f,a,b,m,n,K,T) v=zeros(1,n);lowbx=zeros(1,m);for i=1:nv(i)=sum(f.*a(i,:);endR,I=sort(v, 'descend' ); lowb=0;for i=1:nnz_col=find(a(I(i),:);lowbx(1,nz_col)=1;if nnz(a*lowbx'<=b')<n+K*T lowbx(1,nz_col)=0;elselowb=lowb+R(i);end endiexl 子程序：function extx=iexl(n,K,T,m,M,a,var2) extx1=zeros(T,m);A=zeros(T,m); for i=1:TA(i,:)=sum(a(n+(i-1)*K+1:n+i*K,:); end for j=1:length(var2)indbou=var2(j); col=find(a(indbou,1:m-n); B=A(:,col);B(find(B)=1;extx1=(:,col)=B; end for i=1:Tnz_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,if min(M'-sum(a(n+(i-1)*K+1:n+i*K,y1_col),2)<0 extx=-ones(m,T);'first')returnendelse if isempty(nz_col(find(extx1(i,nz_col)=1,1,n1_col(i)=nz_col(find(extx1(i,nz_col)=1,1,'first''first')=0;);extv(i)=min(min(M'-sum(a(n+(i-1)*K+1:n+i*K,y1_col),2)./a(n+(i-1)*K +1):n+1*K,n1_col(i),0);if extv(i)<0 extx=-ones(m,T); return end extx1(i,:)=0; end end extx=extx1' extx=sparse(extx) ;