使用约束编程求解稳定婚姻问题：BoundedLinearExpression不可迭代错误

你的核心问题是：OR-Tools的CP-SAT求解器中，OnlyEnforceIf和AddImplication方法要求传入布尔变量，但直接使用<比较得到的是BoundedLinearExpression类型，无法直接作为参数。我们需要先将这些排名比较的条件转换为布尔变量，再建立正确的蕴含约束。

关键解决方案步骤 #

1. 为每个排名比较创建布尔变量
   对于每个涉及决策变量的不等式（比如mensRanking[m][w] < mans_rank_of_wife），我们需要创建一个布尔变量来表示该条件是否成立，然后添加约束将布尔变量与不等式绑定，确保两者等价。

2. 用AddImplication实现蕴含逻辑
   稳定婚姻的核心约束是蕴含关系：

   • 如果男性m更喜欢女性w而非自己的妻子 → 女性w必须更喜欢自己的丈夫而非m
   • 如果女性w更喜欢男性m而非自己的丈夫 → 男性m必须更喜欢自己的妻子而非w
     我们可以通过AddImplication(bool_a, bool_b)来实现bool_a → bool_b的逻辑。

3. 修复SolutionPrinter的定义
   你代码中的SolutionPrinter(x)存在未定义变量的问题，需要实现一个能打印匹配结果的解处理器。

完整修正代码 #

import random
from ortools.sat.python import cp_model

class SolutionPrinter(cp_model.CpSolverSolutionCallback):
    def __init__(self, men, women, wives, husbands, mensRanking, womensRanking):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self._men = men
        self._women = women
        self._wives = wives
        self._husbands = husbands
        self._mensRanking = mensRanking
        self._womensRanking = womensRanking
        self._solution_count = 0

    def OnSolutionCallback(self):
        self._solution_count += 1
        print(f"\nSolution {self._solution_count}:")
        for man in self._men:
            wife = self.Value(self._wives[man])
            print(f"Man {man} is married to Woman {wife}")
        print("---")

    def SolutionCount(self):
        return self._solution_count

def main():
    n = 4
    men = range(n)
    women = range(n)
    
    # 随机生成排名（数字越小优先级越高）
    mensRanking = [random.sample(range(n), n) for _ in men]
    womensRanking = [random.sample(range(n), n) for _ in women]

    model = cp_model.CpModel()
    
    # 决策变量：wives[man] = man的妻子；husbands[woman] = woman的丈夫
    husbands = [model.NewIntVar(0, n-1, f'woman_{i}_husband') for i in women]
    wives = [model.NewIntVar(0, n-1, f'man_{i}_wife') for i in men]

    # 双向映射约束：妻子的丈夫是自己，丈夫的妻子是自己
    for man in men:
        model.AddElement(wives[man], husbands, man)
    for woman in women:
        model.AddElement(husbands[woman], wives, woman)

    # 遍历所有男女组合，添加稳定约束
    for m in men:
        for w in women:
            # 获取m对自己妻子的排名
            mans_rank_of_wife = model.NewIntVar(0, n-1, f'm_{m}_rank_wife')
            model.AddElement(wives[m], mensRanking[m], mans_rank_of_wife)
            
            # 获取w对自己丈夫的排名
            womans_rank_of_husband = model.NewIntVar(0, n-1, f'w_{w}_rank_husband')
            model.AddElement(husbands[w], womensRanking[w], womans_rank_of_husband)

            # 1. 布尔变量：m更喜欢w而非自己的妻子
            m_prefers_w_over_wife = model.NewBoolVar(f'm_{m}_prefers_w_{w}')
            # 绑定布尔变量与不等式：当变量为真时，不等式成立；反之则不成立
            model.Add(mensRanking[m][w] < mans_rank_of_wife).OnlyEnforceIf(m_prefers_w_over_wife)
            model.Add(mensRanking[m][w] >= mans_rank_of_wife).OnlyEnforceIf(m_prefers_w_over_wife.Not())

            # 布尔变量：w更喜欢自己的丈夫而非m
            w_prefers_husband_over_m = model.NewBoolVar(f'w_{w}_prefers_husband_over_m_{m}')
            model.Add(womans_rank_of_husband < womensRanking[w][m]).OnlyEnforceIf(w_prefers_husband_over_m)
            model.Add(womans_rank_of_husband >= womensRanking[w][m]).OnlyEnforceIf(w_prefers_husband_over_m.Not())

            # 添加蕴含约束：如果m更喜欢w，那么w必须更喜欢自己的丈夫
            model.AddImplication(m_prefers_w_over_wife, w_prefers_husband_over_m)

            # 2. 反向约束：w更喜欢m而非自己的丈夫 → m更喜欢自己的妻子而非w
            w_prefers_m_over_husband = model.NewBoolVar(f'w_{w}_prefers_m_{m}')
            model.Add(womensRanking[w][m] < womans_rank_of_husband).OnlyEnforceIf(w_prefers_m_over_husband)
            model.Add(womensRanking[w][m] >= womans_rank_of_husband).OnlyEnforceIf(w_prefers_m_over_husband.Not())

            m_prefers_wife_over_w = model.NewBoolVar(f'm_{m}_prefers_wife_over_w_{w}')
            model.Add(mans_rank_of_wife < mensRanking[m][w]).OnlyEnforceIf(m_prefers_wife_over_w)
            model.Add(mans_rank_of_wife >= mensRanking[m][w]).OnlyEnforceIf(m_prefers_wife_over_w.Not())

            model.AddImplication(w_prefers_m_over_husband, m_prefers_wife_over_w)

    # 求解并打印所有解
    solver = cp_model.CpSolver()
    solution_printer = SolutionPrinter(men, women, wives, husbands, mensRanking, womensRanking)
    status = solver.SearchForAllSolutions(model, solution_printer)
    
    print(f"\nSolver Status: {solver.StatusName(status)}")
    print(f"Total solutions found: {solution_printer.SolutionCount()}")
    print(solver.ResponseStats())

if __name__ == "__main__":
    main()

代码解释 #

• 布尔变量绑定：通过OnlyEnforceIf的正反两个约束，确保布尔变量完全等价于对应的排名不等式。例如m_prefers_w_over_wife为True当且仅当mensRanking[m][w] < mans_rank_of_wife。
• 蕴含约束：AddImplication(a, b)确保当a为True时，b必须为True，完美实现了稳定婚姻的核心逻辑。
• SolutionPrinter：自定义的解处理器，能够打印每一组稳定匹配结果，方便验证。

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