如何在Matlab中将分支定界算法从递归转换为迭代方式

我明白把分支定界从递归改成迭代确实容易卡壳，尤其是要把递归里隐式的调用栈逻辑手动模拟出来。结合你给出的递归代码片段，我给你捋清楚迭代版的核心思路和具体实现步骤，帮你搞定这个转换：

递归的本质是系统帮你维护了一个调用栈，每次递归调用都会把当前节点的参数压栈，返回时再弹栈继续处理。迭代版的关键就是自己用数据结构（比如数组或栈对象）来存每个待处理节点的所有参数，手动复刻这个压栈、弹栈的过程。

每个节点需要保存的参数就是你递归函数里的输入：f, A, b, Aeq, beq, lb, ub, M, e，还有当前的bound（用来剪枝的最优解下界）。

• 初始化栈结构：把根节点（也就是最开始调用递归时的初始参数）打包成一个结构体或元组，压入栈中。
• 循环处理栈中节点：只要栈不为空，就重复以下步骤：
  1. 求解松弛LP问题：和递归逻辑一致，调用linprog求解当前节点的线性规划松弛问题，得到x0, val0, status0。
  2. 剪枝判断：如果status0 <= 0（松弛问题无解）或者val0 > 当前bound（这个节点的下界已经比已知最优解大，没必要继续分支），直接跳过该节点，进入下一次循环。
  3. 检查整数解：找出不满足整数约束的变量（abs(x0(M)-round(x0(M)))>e），如果没有这样的变量：
     • 说明找到一个可行整数解，要是val0比当前最优值小，就更新bound、最优解xx和val。
     • 处理完直接进入下一次循环，无需分支。
  4. 生成分支节点：选择一个分支变量（比如第一个不满足整数约束的变量），生成两个子节点：
     • 左分支：给变量加<= floor(br_value)的约束，对应你代码里的A1和b1，把新的参数打包成节点压入栈。
     • 右分支：给变量加>= ceil(br_value)的约束，对应A2和b2，同样打包压栈。
  5. 注意栈的顺序：如果想保持和递归一样的深度优先搜索顺序，要注意压栈顺序——比如先压右分支，再压左分支，因为栈是后进先出，这样弹出时会先处理左分支。

这里给你写一个简化的Matlab迭代版代码，和你提供的递归逻辑对齐：

function [xx,val,status,bb]=bnb_iterative(f,A,b,Aeq,beq,lb,ub,M,e,initial_bound)
    % 初始化栈，每个元素是包含所有参数的结构体
    stack = struct();
    % 根节点参数
    stack(1).f = f;
    stack(1).A = A;
    stack(1).b = b;
    stack(1).Aeq = Aeq;
    stack(1).beq = beq;
    stack(1).lb = lb;
    stack(1).ub = ub;
    stack(1).bound = initial_bound;
    stack(1).M = M;
    stack(1).e = e;
    
    % 初始化最优解相关变量
    xx = [];
    val = initial_bound;
    status = 0;
    bb = initial_bound;
    options = optimoptions('linprog','Display','off'); % 关闭输出，可选
    
    while ~isempty(stack)
        % 弹出栈顶节点（后进先出）
        current_node = stack(end);
        stack(end) = [];
        
        % 求解当前节点的松弛LP
        [x0,val0,status0]=linprog(current_node.f,current_node.A,current_node.b,...
            current_node.Aeq,current_node.beq,current_node.lb,current_node.ub,[],options);
        
        % 剪枝：无解或下界超过当前最优，直接跳过
        if status0 <= 0 || val0 > current_node.bound
            continue;
        end
        
        % 检查是否满足整数约束
        ind = find(abs(x0(current_node.M)-round(x0(current_node.M)))>current_node.e);
        if isempty(ind)
            % 更新最优解
            if val0 < val
                xx = x0;
                val = val0;
                bb = val0;
                status = 1; % 标记找到可行解
            end
            continue;
        end
        
        % 选择第一个不满足整数约束的变量作为分支变量
        br_var = current_node.M(ind(1));
        br_value = x0(br_var);
        
        % 生成左分支：x <= floor(br_value)
        A1 = [current_node.A; zeros(1, length(f))];
        A1(end, br_var) = 1;
        b1 = [current_node.b; floor(br_value)];
        left_node = struct();
        left_node.f = current_node.f;
        left_node.A = A1;
        left_node.b = b1;
        left_node.Aeq = current_node.Aeq;
        left_node.beq = current_node.beq;
        left_node.lb = current_node.lb;
        left_node.ub = current_node.ub;
        left_node.bound = bb; % 用当前最优bound剪枝
        left_node.M = current_node.M;
        left_node.e = current_node.e;
        stack = [stack, left_node];
        
        % 生成右分支：x >= ceil(br_value)（等价于 -x <= -ceil(br_value)）
        A2 = [current_node.A; zeros(1, length(f))];
        A2(end, br_var) = -1;
        b2 = [current_node.b; -ceil(br_value)];
        right_node = struct();
        right_node.f = current_node.f;
        right_node.A = A2;
        right_node.b = b2;
        right_node.Aeq = current_node.Aeq;
        right_node.beq = current_node.beq;
        right_node.lb = current_node.lb;
        right_node.ub = current_node.ub;
        right_node.bound = bb;
        right_node.M = current_node.M;
        right_node.e = current_node.e;
        stack = [stack, right_node];
    end
end

• 参数完整性：每个栈节点必须包含所有需要的参数，避免遗漏导致逻辑错误，比如M（整数约束变量集合）、e（整数判断阈值）这些容易忘的参数。
• bound实时更新：每次找到更优的整数解后，要把新的bound同步到后续压栈的节点，这样能最大化剪枝效率，减少不必要的计算。
• 栈的效率：Matlab用数组模拟栈时，末尾弹栈是O(1)操作，但压栈是O(n)，如果问题规模大，可以考虑预分配栈空间，或者用专门的栈数据结构优化。
• 分支变量选择：示例里用的是第一个不满足整数约束的变量，你也可以改成更高效的策略（比如选择分数部分最大的变量），进一步优化分支效率。

内容的提问来源于stack exchange，提问作者bnbfreak