Lin Liu
As you can see ,yalmip works extremely slow for my model. Yalmiptime is greater than solvertime. If I try bigger instance,it may take hours for yalmip to transfer my model. I know my model is big:about 100000 constraints or more.I am not sure if this phenomenon is common.
I upload my model, please say something about it.
thank you!
function [result] = EFIPPILP( CG,Z,cost,demand,d,pCycle,STLG,DTLG)
%EFIPPILP ILP方法实现路径保护
spanSet=cell([],1);%将所有的图上边放在Span_set中
[left,right]=find(Z);
for j=1:length(left)
spanSet(j)={[left(j),right(j)]};
cost(j)=1;
end
alpha=100000;
beta=0.0001;
%确定x的值，表示业务r是否能被P圈p保护
for r=1:length(demand)
for p=1:length(pCycle)
x(r,p)=pathprotectbycyclewithlimit(demand{r},pCycle{p});
end
end
%确定qi的值，表示P-cycle p是否使用了图上边 spanSet j
for j=1:length(spanSet)
for p=1:length(pCycle)
qi(j,p)=pathoncycle(spanSet{j},pCycle{p});
end
end
%确定Delta的值，表示业务m和n是否相交，1表示相交
for m=1:length(demand)
for n=1:length(demand)
delta(m,n)=pathcrosseachother(demand{m},demand{n});
end
end
%---------------------------------------------------------------------%
%计算FIPP的ILP模型
%第一步，决策变量定义
s=intvar(1,length(spanSet));
nump=intvar(1,length(pCycle));
numrp=intvar(length(demand),length(pCycle),'full');
gama=binvar(length(demand),length(pCycle),'full');
%第二步，约束条件定义
cons=[];
%约束条件2，保证所有的业务（d(r)）都需要被保护
for r=1:length(demand)
cons=[cons,sum(x(r,:).*(numrp(r,:)))>=d(r)];
end
%约束条件3，第r个业务用于保护第p个p圈的次数要少于第p个p圈使用的总次数
for r=1:length(demand)
for p=1:length(pCycle)
cons=[cons,nump(p)>=numrp(r,p)];
end
end
%约束条件4，4-1,边j被所有p圈使用的次数决定了该边应配置的保护容量
%4-2,链路j的保护容量s(j)与工作容量(TLG)之和不能超过链路总容量CG
for j=1:length(spanSet)
cons=[cons,s(j)>=sum(nump.*qi(j,:),2)];
s(j)+STLG(spanSet{j}(1),spanSet{j}(2))<=CG(spanSet{j}(1),spanSet{j}(2));
end
%约束条件5，如果numrp(r,p)>0,则Gama(r,p)=1,如果numrp=0,则Gama(r,p)=0;
for r=1:length(demand)
for p=1:length(pCycle)
cons=[cons,gama(r,p)>=beta*numrp(r,p)];
end
end
%约束条件6
for r=1:length(demand)
for p=1:length(pCycle)
cons=[cons,gama(r,p)<=alpha*numrp(r,p)];
end
end
% % %约束条件7,保证不相交的两个业务才能被同一个P圈保护
for p=1:length(pCycle)
for m=1:length(demand)
for n=m+1:length(demand)
cons=[cons,delta(m,n)+gama(m,p)+gama(n,p)<=2];
end
end
end
%设置目标函数
obj=sum(s);
options=sdpsettings('solver','gurobi','cachesolvers',1);
options.gurobi.MIPGap=0.05; %gap值限制
output=optimize(cons,obj,options) %求解MILP，并输出相关参数
DR=(sum(sum(DTLG))-sum(sum(STLG)))/sum(sum(STLG));
FIPP=value(obj)/sum(sum(STLG));
end
Johan Löfberg
Lin Liu
Johan Löfberg
for r=1:length(demand)
for p=1:length(pCycle)
cons=[cons,nump(p)>=numrp(r,p)];
end
end
n = 100;
delta = sdpvar(n,n);
gama = sdpvar(n,n);
cons = [];
tic
for p=1:n
for m=1:n
for n=m+1:n
cons=[cons,delta(m,n)+gama(m,p)+gama(n,p)<=2];
end
end
end
toc
tic
cons = [];
for p=1:10
for m=1:10
s = gama(m,p);
cons=[cons,delta(m,m+1:10)+s+gama(m+1:10,p)'<=2];
end
end
toc
Of course, dimension in various directions makes a difference. Removing the outer-most loop is more efficient since the inner most doesn't always have maximal dimension, so twice as fast
ticcons = []; for m=1:n for n=m+1:n cons=[cons,delta(m,n)+gama(m,:)+gama(n,:)<=2]; end endtocEliminating more loops by clever repmating etc will drop this to close to 0.