在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
function [optSolution,optValue,exists]=BranchBound(c,A,b) % 分支定界法 % 整数规划问题标准型 % min c'*x % s.t. % A*x<=b upper = inf; lower = -inf; branchStack_A(1) = {A}; branchStack_B(1) = {b}; numOfVariable = length(c); while ~isempty(branchStack_A) len = length(branchStack_A); A = branchStack_A{len}; b = branchStack_B{len}; branchStack_A(len) = []; branchStack_B(len) = []; % A % b [x,opt,exist] = linprog(c,A,b); if 1 == exist && (opt - upper) <= 1e-7 for iVar = [1:numOfVariable + 1] if iVar <= numOfVariable if abs(x(iVar) - round(x(iVar))) > 1e-7 %进行分枝操作,就将子问题入栈 temp_A = zeros(1,numOfVariable); temp_A(iVar) = -1; branchStack_A(len) = {[A;temp_A]}; branchStack_B(len) = {[b;-(floor(x(iVar) + 1))]}; temp_A(iVar) = 1; branchStack_A(len + 1) = {[A;temp_A]}; branchStack_B(len + 1) = {[b;floor(x(iVar))]}; break; end else %是个整数解.更新upper if abs(upper - opt) < 1e-7 optSolution(:,end + 1) = x; else optSolution = x; upper = opt; optValue = opt; end end end %for end %if end%while sizeOfSolution = size(optSolution); if sizeOfSolution(2) == 0 exists = 0; else exists = 1; end end
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论