Python 实现整数线性规划：分枝定界法（Branch and Bound）

分枝定界法是一种求解整数线性规划问题的常用方法。该方法的基本思想是将整数线性规划问题不断分解成子问题，然后对每个子问题进行求解，直到得到最优解。

Python 实现整数线性规划的分枝定界法，可以基于 Python 的优化库 `PuLP`。以下是一个简单的示例代码：

from pulp import *

# 定义整数线性规划问题
prob = LpProblem("Integer Linear Programming", LpMinimize)

# 添加变量
x1 = LpVariable("x1", lowBound=0, cat='Integer')
x2 = LpVariable("x2", lowBound=0, cat='Integer')

# 添加目标函数
prob += 3*x1 + 4*x2

# 添加约束条件
prob += 2*x1 + x2 >= 3
prob += x1 + 2*x2 >= 3

# 求解
prob.solve()

# 输出结果
print("Status:", LpStatus[prob.status])
print("Minimum value:", value(prob.objective))
print("Optimal solution:")
for v in prob.variables():
    print(v.name, "=", v.varValue)

以上代码是一个简单的整数线性规划问题的求解示例，其中定义了两个变量 `x1` 和 `x2`，并添加了目标函数和两个约束条件。通过 `prob.solve()` 方法进行求解，并输出最优解及对应的变量取值。

分枝定界法的实现，可以通过递归地将当前问题分解成两个子问题，并对子问题进行求解，直到得到最优解。在每次分解时，需要对当前解的上下界进行计算，并通过 `prob +=` 方法添加上下界约束条件。具体实现可以参考以下示例代码：

from pulp import *

# 定义整数线性规划问题
prob = LpProblem("Integer Linear Programming", LpMinimize)

# 添加变量
x1 = LpVariable("x1", lowBound=0, cat='Integer')
x2 = LpVariable("x2", lowBound=0, cat='Integer')

# 添加目标函数
prob += 3*x1 + 4*x2

# 添加初始约束条件
prob += 2*x1 + x2 >= 3
prob += x1 + 2*x2 >= 3

def solve_branch_and_bound(prob):
    # 求解当前问题
    prob.solve()
    
    # 获取当前解的上下界
    upper_bound = value(prob.objective)
    lower_bound = upper_bound
    
    # 分解问题并求解
    for v in prob.variables():
        # 向上取整
        upper_value = int(v.varValue) + 1
        # 向下取整
        lower_value = int(v.varValue)
        
        # 分解为两个子问题
        prob1 = LpProblem("Integer Linear Programming", LpMinimize)
        prob2 = LpProblem("Integer Linear Programming", LpMinimize)

        # 添加变量
        x1 = LpVariable("x1", lowBound=0, cat='Integer')
        x2 = LpVariable("x2", lowBound=0, cat='Integer')

        # 添加目标函数
        prob1 += 3*x1 + 4*x2
        prob2 += 3*x1 + 4*x2

        # 添加约束条件
        for c in prob.constraints:
            prob1 += c
            prob2 += c

        # 添加上下界约束条件
        if v.name == 'x1':
            prob1 += x1 >= upper_value
            prob2 += x1 <= lower_value
        elif v.name == 'x2':
            prob1 += x2 >= upper_value
            prob2 += x2 <= lower_value

        # 求解子问题
        prob1.solve()
        prob2.solve()

        # 计算上下界
        if value(prob1.objective) < value(prob2.objective):
            upper_bound = min(upper_bound, value(prob1.objective))
        else:
            upper_bound = min(upper_bound, value(prob2.objective))

        lower_bound = max(lower_bound, value(prob1.objective), value(prob2.objective))

    # 判断是否达到最优解
    if upper_bound == lower_bound:
        return upper_bound

    # 分解子问题并求解
    for v in prob.variables():
        # 向上取整
        upper_value = int(v.varValue) + 1
        # 向下取整
        lower_value = int(v.varValue)

        # 分解为两个子问题
        prob1 = LpProblem("Integer Linear Programming", LpMinimize)
        prob2 = LpProblem("Integer Linear Programming", LpMinimize)

        # 添加变量
        x1 = LpVariable("x1", lowBound=0, cat='Integer')
        x2 = LpVariable("x2", lowBound=0, cat='Integer')

        # 添加目标函数
        prob1 += 3*x1 + 4*x2
        prob2 += 3*x1 + 4*x2

        # 添加约束条件
        for c in prob.constraints:
            prob1 += c
            prob2 += c

        # 添加上下界约束条件
        if v.name == 'x1':
            prob1 += x1 >= upper_value
            prob2 += x1 <= lower_value
        elif v.name == 'x2':
            prob1 += x2 >= upper_value
            prob2 += x2 <= lower_value

        # 判断是否需要继续分解
        if min(value(prob1.objective), value(prob2.objective)) > upper_bound:
            continue

        # 递归求解子问题
        if value(prob1.objective) <= value(prob2.objective):
            upper_bound = min(upper_bound, solve_branch_and_bound(prob1))
        else:
            upper_bound = min(upper_bound, solve_branch_and_bound(prob2))

    return upper_bound

# 求解
optimal_value = solve_branch_and_bound(prob)

# 输出结果
print("Minimum value:", optimal_value)
print("Optimal solution:")
for v in prob.variables():
    print(v.name, "=", v.varValue)

以上代码实现了整数线性规划的分枝定界法，其中 `solve_branch_and_bound` 方法用于递归地分解问题并求解。在每次分解时，都会计算当前解的上下界，并根据上下界约束条件进行分解。通过递归求解子问题，最终得到最优解。