/ Published in: MatLab
Expand |
Embed | Plain Text
Copy this code and paste it in your HTML
--- solve_problems.m function report = solve_problems() % data_files={'Alberta';'Galvao100';'Galvao100';'Galvao150';'Galvao150';'Galvao150'}; % p=[10 10 15 5 15 20]; % data_files={'TestData'}; % p=[2]; data_files={'Alberta'}; p=[10]; dist=distances([data_file '_distances.txt']); end --- distances.m function distances=distances(data_file) from=distance_data(row,1); to=distance_data(row,2); distance=distance_data(row,3); distances(to,from)=distance; distances(from,to)=distance; end --- solve_p_median.m function [bestLB,iterations,debug]=solve_p_median(dist,demand,p) bestLB=0; bestUB=inf; currentLB=0; currentUB=inf; iterations(1,:)=[0 currentLB bestLB currentUB bestUB]; pi=2; i=1; piUpdateTime=1; improvementOccurred=0; debug=[0 0 2 zeros(1,p) u']; % parameters stored for debugging (iteration, step_size, pi, open facilities, u) for s=1:n_s cost=dist(:,s).*demand; newCost=cost-u; end facilities=order(1:p); % open p facilities where z is smallest if(currentLB>bestLB) bestLB=currentLB; end currentUB=findUB(facilities,dist,demand); if(currentUB<bestUB) bestUB=currentUB; end if(normOfRelaxedCsts == 0) % hit the lower bound break end step=pi*(bestUB-currentLB)/normOfRelaxedCsts; % s^t = {\pi (UB* - z_{LR}(u^t)) \over \sum_c (1-\sum_s x_{sc})^2} if(~improvementsOccur(iterations,piUpdateTime)) piUpdateTime=i; end end % result = iterationNo > 15000 | (bestUB == bestLB); function result=improvementsOccur(iterations,piUpdateTime) n=30; timeSinceLastPiUpdate=currentTime-piUpdateTime; if(currentTime <= n | timeSinceLastPiUpdate <= n) result = 1; else lastImpForLB=whenDidLastImprovementOccur(iterations(end-n:end,3)); lastImpForUB=whenDidLastImprovementOccur(iterations(end-n:end,5)); if(lastImpForLB <= n | lastImpForUB <= n) result = 1; else result = 0; end end function lastImp=whenDidLastImprovementOccur(iterations) lastValue=iterations(end); function currentUB=findUB(facilities,dist,demand) feasibleAssignments=assignCustomers(facilities,dist); function customerAssignments=assignCustomers(facilities,dist) distOpenFacilities=dist(facilities,:); for c=1:n_c customerAssignments(facilities(order(c)),c)=1; end