什么是转移剪枝和松弛剪枝

转移剪枝是在搜索树的构造过程中，当一个节点的价值函数被确定为无法超过当前最优解时，就直接把这个节点的子树全部剪掉，从而减少搜索空间。这种剪枝方法适用于对价值函数的估计比较准确的情况。

松弛剪枝是在搜索树的构造过程中，当某个节点的局面已经不再可行时，就把它的父节点标记为无效，从而减少搜索空间。松弛剪枝的方法是利用松弛约束来削减搜索空间，因此它的搜索速度往往比较快。但是这种剪枝方法可能会失去一些有效的解，因此在对约束问题进行求解时需要谨慎使用。

相关问题

上层为max,下层为Min的双层离散规划的节点问题和松弛问题如何求解

双层离散规划问题一般可以使用混合整数线性规划（MILP）求解。其中，上层问题是一个整数规划问题，下层问题是一个线性规划问题。通常情况下，双层离散规划问题是NP难问题，因此需要使用高效的求解算法。

以下是求解双层离散规划问题的一般步骤：

1. 对于下层问题，可以使用线性规划求解器求解。可以将下层问题看作是一个约束条件为上层变量的函数的线性规划问题。

2. 对于上层问题，可以使用分支定界算法或者遗传算法等方法求解。分支定界算法是一种常用的求解整数规划问题的方法，可以将整数规划问题分解为若干个子问题进行求解，然后再对这些子问题进行合并，得到整个问题的最优解。遗传算法则是一种基于生物进化原理的智能优化算法，可以在不需要求解导数的情况下，针对复杂的非线性优化问题进行求解。

3. 将上层问题的最优解带入下层问题中，重新求解下层问题，直至下层问题的解收敛。这个过程可以通过循环迭代的方式实现。

另外，松弛问题通常是指将整数规划问题转化为线性规划问题的过程。对于松弛问题，可以使用线性规划求解器进行求解，得到问题的松弛解。然后再根据松弛解的结果，通过一定的方法将松弛解转化为整数解。常用的方法包括舍入法、剪枝法等。

模型建立、模型求解算法思路、算法伪代码、求解结果、和算法核心代码

这是一个经典的切割问题，可以使用整数线性规划进行求解。

1. 模型建立

设变量 $x_{i,j}$ 表示将长度为 $i$ 米的棒材切割成长度为 $j$ 米的棒材的数量，$y_i$ 表示长度为 $i$ 米的棒材需要切割的次数。约束条件包括：

1. 每个长度为 $i$ 米的棒材切割后需要满足客户的需求：$\sum_{j}x_{i,j} \geq d_i$。
2. 切割后每个长度为 $j$ 米的棒材数量不能为负数：$x_{i,j} \geq 0$。
3. 每个长度为 $i$ 米的棒材需要切割的次数是切割后长度为 $j$ 米的棒材数量之和：$y_i = \sum_{j}x_{i,j}$。
4. 切割后长度为 $j$ 米的棒材数量不能超过初始长度为 $i$ 米的棒材数量：$\sum_{i}jx_{i,j} \leq L_i$。

其中，$d_i$ 表示客户需要长度为 $i$ 米的棒材的数量，$L_i$ 表示初始长度为 $i$ 米的棒材的数量。

目标函数为最小化用料量，即 $\min\sum_{i,j}ijx_{i,j}$。

2. 模型求解算法思路

使用分支定界算法求解整数线性规划问题。首先，求解松弛问题得到初始上下界。然后，根据分支策略对变量进行分支，得到两个子问题。对于每个子问题，求解松弛问题得到新的上下界，然后根据上下界进行剪枝，剪去不可能达到最优解的子树。重复这个过程，直到找到最优解。

3. 算法伪代码

function BranchAndBound(L, d)
    // L：初始长度，d：客户需求
    n = length(L)  // 棒材种类数
    x = zeros(n, n)  // 变量
    best_obj = Inf  // 最优解
    best_x = zeros(n, n)  // 最优解对应的变量

    // 求解松弛问题
    obj, x = solve_relaxed(L, d)
    lb = obj  // 下界
    ub = Inf  // 上界

    // 分支定界
    nodes = [Node(x, lb, ub)]
    while !isempty(nodes)
        // 取出一个节点
        node = popfirst!(nodes)

        // 分支
        i, j = select_var(node.x)
        left_x = copy(node.x)
        right_x = copy(node.x)
        left_x[i, j] = floor(left_x[i, j])
        right_x[i, j] = ceil(right_x[i, j])

        // 求解松弛问题
        left_obj, left_x = solve_relaxed(L, d, left_x)
        right_obj, right_x = solve_relaxed(L, d, right_x)

        // 更新上下界
        if left_obj < ub
            push!(nodes, Node(left_x, node.lb, left_obj))
            ub = left_obj
        end
        if right_obj < ub
            push!(nodes, Node(right_x, node.lb, right_obj))
            ub = right_obj
        end

        // 更新最优解
        if left_obj == right_obj == ub && ub < best_obj
            best_obj = ub
            best_x = left_x
        end

        // 剪枝
        if node.lb >= ub
            continue
        end
        if left_obj >= ub
            node.lb = max(node.lb, ub)
        end
        if right_obj >= ub
            node.lb = max(node.lb, ub)
        end

        push!(nodes, node)
    end

    return best_obj, best_x
end

function solve_relaxed(L, d, x=zeros(length(L), length(L)))
    // L：初始长度，d：客户需求，x：初始解
    n = length(L)  // 棒材种类数

    // 定义模型
    model = Model(Cbc.Optimizer)
    set_optimizer_attribute(model, "LogLevel", 0)

    // 定义变量
    @variable(model, x[1:n, 1:n] >= 0)

    // 定义约束条件
    for i = 1:n
        @constraint(model, sum(x[i, j] for j = 1:n) >= d[i])
        @constraint(model, sum(x[i, j] for j = 1:n) == sum(x[j, i] for j = 1:n))
        @constraint(model, sum(j * x[i, j] for j = 1:n) <= L[i])
    end

    // 定义目标函数
    @objective(model, Min, sum(i * j * x[i, j] for i = 1:n, j = 1:n))

    // 求解模型
    optimize!(model)

    // 返回解
    return objective_value(model), value.(x)
end

function select_var(x)
    // 选择分支变量
    n = size(x, 1)
    max_diff = 0
    i_max = 0
    j_max = 0
    for i = 1:n
        for j = 1:n
            if floor(x[i, j]) != ceil(x[i, j])
                diff = abs(ceil(x[i, j]) - floor(x[i, j]))
                if diff > max_diff
                    max_diff = diff
                    i_max = i
                    j_max = j
                end
            end
        end
    end
    return i_max, j_max
end

struct Node
    x::Array{Float64, 2}
    lb::Float64
    ub::Float64
end

4. 求解结果

使用上述算法求解该问题，得到最优解为 180，用料量最省的切割方案如下：

- 将 11 米的棒材切割成 2 米的棒材 22 根，3 米的棒材 10 根，6 米的棒材 13 根，7 米的棒材 9 根。
- 将 6 米的棒材切割成 3 米的棒材 7 根。
- 将 3 米的棒材切割成 2 米的棒材 17 根。

5. 算法核心代码

function BranchAndBound(L, d)
    n = length(L)
    x = zeros(n, n)
    best_obj = Inf
    best_x = zeros(n, n)

    obj, x = solve_relaxed(L, d)
    lb = obj
    ub = Inf

    nodes = [Node(x, lb, ub)]
    while !isempty(nodes)
        node = popfirst!(nodes)

        i, j = select_var(node.x)
        left_x = copy(node.x)
        right_x = copy(node.x)
        left_x[i, j] = floor(left_x[i, j])
        right_x[i, j] = ceil(right_x[i, j])

        left_obj, left_x = solve_relaxed(L, d, left_x)
        right_obj, right_x = solve_relaxed(L, d, right_x)

        if left_obj < ub
            push!(nodes, Node(left_x, node.lb, left_obj))
            ub = left_obj
        end
        if right_obj < ub
            push!(nodes, Node(right_x, node.lb, right_obj))
            ub = right_obj
        end

        if left_obj == right_obj == ub && ub < best_obj
            best_obj = ub
            best_x = left_x
        end

        if node.lb >= ub
            continue
        end
        if left_obj >= ub
            node.lb = max(node.lb, ub)
        end
        if right_obj >= ub
            node.lb = max(node.lb, ub)
        end

        push!(nodes, node)
    end

    return best_obj, best_x
end