-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.m
82 lines (78 loc) · 1.82 KB
/
main.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
clc
clear all
dbstop if error
Dataget()
load data
impactSol = initializePathsWithImpact();%生成初始解
routes=impactSol;
impactcosts=0;
for route=routes'
route=route{1};
impactcosts=impactcosts+computeRouteCost(route, d);
end
A=zeros(n,length(routes));%系数矩阵
C=zeros(1,length(routes));%价值系数
[A,c]=addRoutesToMaster(routes, A, C, d);%把问题添加到主问题里
%assign A and B
[A,B,lb]=aissignA_B(A,routes);
% A=-A;
% [ran,col]=size(A);
% B=-ones(ran,1);
% B=[B;length(routes)];%限定系数
% A=[A;ones(1,length(routes))];%技术系数
% lb=zeros(1,length(routes));
rc=zeros(n+2,n+2);%reduced costs
iter=1;
tic
while 1
disp(['第',num2str(iter),'此迭代'])
[x,fval,exitflag,output,lambda]=linprog(c,A,B,[],[],lb);%求解
pi_i=lambda.ineqlin;
pi_i(end)=[];
pi_i=[0;pi_i;0];%检验数
for i=1:n+2
for j=1:n+2
rc(i,j)=d(i,j)-pi_i(i);
end
end
if find(rc<=-M)
break
end
newRoutes = subProblem(n, q, d, a, b, rc, Q, M);
if isempty(newRoutes)
break
end
for route=newRoutes'
if ismembermatrix(route,routes)
break
end
end
%Add new routes to master problem
newMat = zeros(n,length(newRoutes));
newCosts = zeros(1,length(newRoutes));
[newMat,newCosts] = addRoutesToMaster(newRoutes,newMat,newCosts,d);
routes = [routes;newRoutes];
[A,B,lb,c]=aissignA_B(newMat,routes,newCosts,A,c);
iter=iter+1;
toc
end
%% solve IP
% NumberofVariable=length(c);
% ops=sdpsettings('solver','gurobi','savesolveroutput',1);
% % Set variable type back to binary
% y=binvar(1,NumberofVariable);
% CT1=[];
% for i=1:n
% CT1=[CT1,(-A(i,:)*y(:)>=1)];
% end
% CT2=[sum(y(:))<=Kdim,y>=0];
% obj=y*c';
% sol=optimize(CT1+CT2,obj,ops);
% y=double(y);
% pos=find(y==1);
% routes{pos}
% obj=double(obj)
pos=find(x==1);
routes{pos}
fval
toc