3.3 C++伪代码
// C++实现分支定界算法的伪代码 // 函数功能：我们要求一个最小化问题的最优解 //输入参数：problem 组合优化问题 // objective_function 目标函数值 // lower_bound_function 问题的下界 CombinatorialSolution branch_and_bound_solve( CombinatorialProblem problem, ObjectiveFunction objective_function /*f*/, BoundingFunction lower_bound_function /*g*/) { // Step 1 above double problem_upper_bound = std::numeric_limits<double>::infinity; // = B，设置正无穷无穷对问题的上界进行初始化 CombinatorialSolution heuristic_solution = heuristic_solve(problem); // x_h，启发式算法得到初始解 problem_upper_bound = objective_function(heuristic_solution); // B = f(x_h),将启发式算法得到的解作为问题的上界 CombinatorialSolution current_optimum = heuristic_solution;//设置启发算法的解为当前最优解 // Step 2 above queue<CandidateSolutionTree> candidate_queue; // problem-specific queue initialization candidate_queue = populate_candidates(problem); while (!candidate_queue.empty()) { // Step 3 above // Step 3.1 CandidateSolutionTree node = candidate_queue.pop(); // "node" represents N above if (node.represents_single_candidate()) { // Step 3.2 如果node是一个候选解，判断其是否小于当前上界，若是则更新上界；否则他就不是最优解，就要停止分支 if (objective_function(node.candidate()) < problem_upper_bound) { current_optimum = node.candidate(); problem_upper_bound = objective_function(current_optimum); } // else, node is a single candidate which is not optimum } else { // Step 3.3: node represents a branch of candidate solutions // "child_branch" represents N_i above for (auto&& child_branch : node.candidate_nodes) { if (lower_bound_function(child_branch) <= problem_upper_bound) { candidate_queue.enqueue(child_branch); // Step 3.3.2 } // otherwise, g(N_i) > B so we prune the branch; step 3.3.1 //如果得到一个更差的解，我们就放弃该分支 } } } return current_optimum; }
4 一个Matlab的实现示例
4.1 linprog函数使用详解
这里调用了Matlab的linprog函数，完整的函数说明文档可在Matlab中输入如下指令：
doc linprog
得到如下界面：
可知，该函数可以求解线性规划问题，设计到的参数说明：
其中的options参数：
exitflag参数：
4.2 一个Matlab求解的代码示例解析
分支定界函数
function [x,val]=kfz(n,f,a,b,aeq,beq,lb,ub) %获取变量个数的向量 x=zeros(n,1); % x1=zeros(n,1); m1=2; m2=1; %嗲用lingprog得到线性规划问题的最优解 [x1,val1]=linprog(f,a,b,aeq,beq,lb,ub) if (x1==0) x=x1; val=val1 elseif (round(x1)==x1)%线性问题的最优解都是整数，则它也是原问题的最优解 x=x1; val=val1 else e1={0,a,b,aeq,beq,lb,ub,x1,val1}; e(1,1)={e1}; zl=0; zu=-val1 while (zu~=zl) for c=1:1:m2 if (m1~=2) if (cell2mat(e{m1-1,c}(1))==1) e1={1,[],[],[],[],[],[],[],0}; e(m1,c*2-1)={e1}; e(m1,c*2)={e1}; continue; end; end; x1=cell2mat(e{m1-1,c}(8)); x2=zeros(n,1); s=0; s1=1; s2=1; lb1=cell2mat(e{m1-1,c}(6)); ub1=cell2mat(e{m1-1,c}(7)); lb2=cell2mat(e{m1-1,c}(6)); ub2=cell2mat(e{m1-1,c}(7)); for d=1:1:n if (abs((round(x1(d))-x1(d)))>0.0001)&(s==0) s=1; lb1(d)=fix(x1(d))+1 if (a*lb1<=b) s1=0; end; ub2(d)=fix(x1(d)) if (a*lb2<=b) s2=0; end; end; end; e1={s1,a,b,aeq,beq,lb1,ub1,[],0}; e2={s2,a,b,aeq,beq,lb2,ub2,[],0}; e(m1,c*2-1)={e1}; e(m1,c*2)={e2}; end; m1=m1+1; m2=m2*2; for c=1:1:m2 if (cell2mat(e{m1-1,c}(1))==0) [x1,val1]=linprog(f,cell2mat(e{m1-1,c}( 2)),cell2mat(e{m1-1,c}(3)),cell2mat(e{m1-1,c}(4)),cell2mat(e{m1-1,c}(5)),cell2mat(e{m1-1,c}(6)),cell2mat(e{m1-1,c}(7))); e1={cell2mat(e{m1-1,c}(1)),cell2mat(e{m1-1,c}(2)),cell2mat(e{m1-1,c}(3)),cell2mat(e{m1-1,c}(4)),cell2mat(e{m1-1,c}(5)),cell2mat(e{m1-1,c}(6)),cell2mat(e{m1-1,c}(7)),x1,val1}; e(m1-1,c)={e1}; end; z=val1; if ((-z)<(-zl)) e1={1,[],[],[],[],[],[],[],0}; e(m1-1,c)={e1}; elseif (abs(round(x1)-x1)<=0.0001) zl=z end; end; for c=1:1:m2 if (cell2mat(e{m1-1,c}(1))==0) zu=cell2mat(e{m1-1,c}(9)) end; end; for c=1:1:m2 if (-cell2mat(e{m1-1,c}(9))>(-zu)) zu=cell2mat(e{m1-1,c}(9)) end; end; end; for c=1:1:m2 if (cell2mat(e{m1-1,c}(1))==0)&(cell2mat(e{m1-1,c}(9))==zu) x=cell2mat(e{m1-1,c}(8)) end; end; val=-zu; end;
调用
f = [-1, -5]; A = [-1, 1; 5, 6;]; b = [2; 30]; Aeq = []; beq = []; lb = [0; 0]; ub = [4; inf]; [x,val]=kfz(2,f,A,b,Aeq,beq,lb,ub)
结果：
>> Untitled2 Optimization terminated. x1 = 1.6364 3.6364 val1 = -19.8182 zu = 19.8182 lb1 = 2 0 ub2 = 1 Inf Optimization terminated. Optimization terminated. zl = -16.0000 zu = -18.6667 zu = -16.0000 zu = -18.6667 lb1 = 2 4 ub2 = 4 3 zl = -16.0000 Optimization terminated. zu = -17.4000 lb1 = 3 0 ub2 = 2 3 Optimization terminated. Optimization terminated. zl = -17.0000 zl = -17.0000 zl = -17.0000 zl = -17.0000 zl = -17.0000 zu = -17.0000 x = 2.0000 3.0000 x = 2.0000 3.0000 val = 17.0000 >>
