如何用Google OR-Tools在Python中获取二元LP问题的多个最优解

针对你遇到的问题，核心原因是没有在找到解后添加排除已找到解的约束，且未明确限制求解器仅在最优解空间内搜索。以下是两种可行的解决方法：

方法一：CP-SAT求解器（推荐） #

CP-SAT默认的搜索策略可能重复返回同一个解，需要自定义解收集器，每次找到解后添加约束排除该解，同时固定目标值等于最优值V，确保只搜索最优解。

代码实现 #

from ortools.sat.python import cp_model

class SolutionPrinterWithExclusion(cp_model.CpSolverSolutionCallback):
    def __init__(self, variables, limit, model):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.variables = variables
        self.limit = limit
        self.model = model
        self.solution_count = 0
        self.solutions = []

    def on_solution_callback(self):
        self.solution_count += 1
        # 保存当前解
        current_sol = [self.Value(v) for v in self.variables]
        self.solutions.append(current_sol)
        print(f"Solution {self.solution_count}: {current_sol[:10]}...")  # 截断输出避免过长
        
        # 添加约束排除当前解：x与current_sol至少有一位不同
        diff_expr = []
        for i in range(len(self.variables)):
            if current_sol[i] == 1:
                diff_expr.append(self.variables[i].Not())  # x[i]不能为1
            else:
                diff_expr.append(self.variables[i])  # x[i]不能为0
        self.model.Add(cp_model.Or(diff_expr))
        
        if self.solution_count >= self.limit:
            self.StopSearch()

# 构建模型
model = cp_model.CpModel()
n = 150
x = [model.NewIntVar(0, 1, f'x_{i}') for i in range(n)]

# 添加原始约束A*x <= b
for j in range(n):
    constraint_expr = [int(A[j][l]) * x[l] for l in range(n)]
    model.Add(sum(constraint_expr) <= int(b[j][0]))

# 固定目标值等于最优值V
V = 112
model.Add(sum(x) == V)  # 用==替代>=，明确限制仅搜索最优解

# 求解
solver = cp_model.CpSolver()
solution_printer = SolutionPrinterWithExclusion(x, 100, model)
solver.parameters.enumerate_all_solutions = True
status = solver.Solve(model, solution_printer)

# 输出结果
print(f"求解状态: {solver.StatusName(status)}")
print(f"共找到{solution_printer.solution_count}个最优解")

关键说明 #

• 自定义SolutionPrinterWithExclusion类，在每次找到解后添加排除约束，确保求解器下次搜索不同的解。
• 使用sum(x) == V替代原有的sum(constraint_obj_val) <= -V，更直观且能减少无效搜索。

方法二：SCIP求解器 #

SCIP的NextSolution()默认返回任意可行解，需先固定目标值为V，再循环求解并添加排除约束。

代码实现 #

from ortools.linear_solver import pywraplp

# 初始化SCIP求解器
solver = pywraplp.Solver.CreateSolver('SCIP')
if not solver:
    exit()

n = 150
x = [solver.IntVar(0, 1, f'x_{i}') for i in range(n)]

# 添加原始约束A*x <= b
for j in range(n):
    constraint_expr = sum(int(A[j][l]) * x[l] for l in range(n))
    solver.Add(constraint_expr <= int(b[j][0]))

# 先求解得到最优目标值V
objective = solver.Sum(x)
solver.Maximize(objective)
status = solver.Solve()
V = int(solver.Objective().Value())
print(f"最优目标值V: {V}")

# 重置目标，添加约束sum(x) == V，转为寻找可行解
solver.ClearObjective()
solver.Add(solver.Sum(x) == V)
solver.Minimize(0)  # 设置无关目标，仅找可行解

solutions = []
max_solutions = 100

while len(solutions) < max_solutions:
    status = solver.Solve()
    if status not in [solver.OPTIMAL, solver.FEASIBLE]:
        break  # 无更多解
    
    # 保存当前解
    current_sol = [int(x[i].SolutionValue()) for i in range(n)]
    solutions.append(current_sol)
    print(f"Solution {len(solutions)}: {current_sol[:10]}...")
    
    # 添加约束排除当前解
    diff_sum = 0
    for i in range(n):
        sol_i = current_sol[i]
        if sol_i == 1:
            diff_sum += (1 - x[i])
        else:
            diff_sum += x[i]
    solver.Add(diff_sum >= 1)

print(f"共找到{len(solutions)}个最优解")

关键说明 #

• 先求解得到最优值V，再添加sum(x) == V约束，强制求解器仅在最优解空间内搜索。
• 每次找到解后添加排除约束，避免SCIP返回重复解或次优解。

通用注意事项 #

1. 必须排除已找到的解：这是获取不同最优解的核心，否则求解器会优先返回熟悉的解路径。
2. 固定目标值：用sum(x) == V替代sum(x) >= V，因为V是最大值，两者等价，但==能减少求解器的搜索范围。
3. CP-SAT参数调整：若仍出现重复解，可调整搜索策略：

   solver.parameters.search_branching = cp_model.PORTFOLIO_SEARCH
   

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