 用户名 Email 自动登录 找回密码 密码 立即注册
 搜索

分枝（支）定界法

691主题 2万积分   29495 发表于 2019-4-9 00:08:38 | 显示全部楼层 |阅读模式
 分枝（支）定界法：百度网盘 链接：https://pan.baidu.com/s/1gtX4sNDCzvTMYZnSIVHGWg 提取码：xq06 主程序如下： %   This program solves mixed integer problems with a branch and bound method clc,clear,close all warning off %Small test problem, optimal solution should be -21 c = -[8 11 6 4]; A = [5 7 4 3]; b = 14; Aeq = []; beq = []; lb = [0 0 0 0]'; ub = [1 1 1 1]'; yidx = true(4,1); [x_best,  f_best] = miprog(c,A,b,Aeq,beq,lb,ub,yidx); disp(['X for Objective function value: ',num2str(x_best')]); disp(['Objective function value: ',num2str(f_best)]);复制代码lp-relaxation problem程序如下： function [x,fval,flag] = lpr(c,A,b,Aeq,beq,e,s,d,yidx,sol,opts) %LPR % Function to solve the lp-relaxation problem. Used by branch and bound algorithm. %Calculate the extra constraints imposed by s %if s is all NaN then no new constraints sidx = ~isnan(s); ydiag = double(yidx); if any(sidx)     ydiag(yidx) = d;     l = length(yidx);       Y = spdiags(ydiag,0,l,l);     %Remove zero entries     Y = Y(any(Y,2),:); end %linprog if any(sidx)     A = [A; Y];     b = [b; s(sidx).*d(sidx)]; end [x,fval,flag] = linprog(c,A,b,Aeq,beq,[],[],[],opts);复制代码分支定界法程序如下：function [x_best,  f_best] = miprog(c,A,b,Aeq,beq,lb,ub,yidx,o) %MIPROG % Branch and bound algorithm for linear mixed integer programs % %   min c'*x s.t. A*x <= b Aeq*x == beq lb <= x <= ub x(yidx) in [0,1,2,...] % %   where yidx is a logical index vector such that %   x(yidx) are the integer variables o.display = 'off'; o.iterplot = false; o.solver = 'linprog'; %Branch and bound specific options o.Delta = 1e-8; %Stopping tolerance of the gap (f_integer-f_lp)/(f_integer+f_lp) o.maxNodes = 1e5; %Maximum number of nodes in the branch and bound tree to visit o.intTol = 1e-6; %Integer tolerance %% Init %add upper and lower bounds to A Ab = speye(length(yidx)); if ~isempty(lb)     A = [A; -Ab];     b = [b; -lb]; end if ~isempty(ub)     A = [A; Ab];     b = [b; ub]; end %delete all-zero rows b = b(any(A,2),:); A = A(any(A,2),:); %linprog e=[]; opts = optimset('Display','off'); sol=2; %Assume no initial best integer solution %Add your own heuristic here to find a good incumbent solution, store it in %f_best,y_best,x_best f_best = inf; y_best = []; x_best = []; %Variable for holding the objective function variables of the lp-relaxation %problems f = inf(o.maxNodes,1); f(1) = 0; fs = inf; numIntSol = double(~isempty(y_best)); %Set of problems S = nan(sum(yidx),1); D = zeros(sum(yidx),1); %The priority in which the problems shall be solved priority = ; %The indices of the problems that have been visited visited = nan(o.maxNodes,1); i=0; %% Branch and bound loop while i==0 || isinf(f_best) || (~isempty(priority) &&  ((f_best-min(fs(priority)))/abs(f_best+min(fs(priority))) > o.Delta) &&  i diff                 diff = abs(round(y)-y);                 if all(diff don't evaluate this node         priority(1) = [];     end end复制代码 求解结果如下： X for Objective function value: -8.1911e-11           1           1           1 Objective function value: -21复制代码

 本版积分规则 回帖并转播 回帖后跳转到最后一页

GMT+8, 2019-6-19 17:52 , Processed in 0.108992 second(s), 24 queries .