CP-SAT模型多次调用Minimize的工作机制与效果探究

核心问题 #

在CP-SAT模型中多次调用Minimize方法时，需明确以下三点：

• 多次Minimize的实际作用机制是什么？
• 多个目标之间是否存在优先级？
• 调用顺序是否会影响求解结果或过程？

现有资料情况 #

社区（如Stack Overflow、Kripke教程）建议通过迭代调用Minimize处理多目标优化，但OR-Tools官方文档及源码未明确说明多次调用Minimize的具体行为细节。

测试验证 #

通过自定义Python脚本测试多次Minimize的效果，同时用回调限制求解结果数量为10个，初步测试显示多次Minimize确实会影响求解结果，且多个目标可能处于相同优先级。

测试代码 #

from ortools.sat.python import cp_model


class CallbackStopper(cp_model.CpSolverSolutionCallback):

    def __init__(self):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.solutions = 0

    def on_solution_callback(self):
        self.solutions += 1
        if self.solutions == 10:
            self.StopSearch()


def solve_multiple_minimizes(minimizes = 0):
    model = cp_model.CpModel()
    solver = cp_model.CpSolver()

    data = [model.NewIntVar(0, 100, f'<num_{i}>') for i in range(20)]
    model.AddAllDifferent(data)

    if minimizes >= 1:
        every_second_one = [n for i, n in enumerate(data) if i % 2]
        for i in range(1, len(every_second_one)):
            model.Add(every_second_one[i-1] < every_second_one[i])
        model.Minimize(sum(every_second_one))

    if minimizes >= 2:
        quorter = data[len(data)//4:]
        model.Minimize(sum(quorter))

    if minimizes >= 3:
        half = data[len(data)//2:]
        model.Minimize(sum(half))

    status = solver.Solve(model, CallbackStopper())

    if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        print(f'{solver.ResponseProto()}')
        return '- error -'
    
    return [solver.Value(n) for n in data]

for i in range(4):
    print(f'{i = }: {solve_multiple_minimizes(i)}')

测试输出 #

i = 0: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
i = 1: [10, 0, 11, 1, 13, 2, 15, 3, 17, 4, 19, 5, 12, 6, 14, 7, 16, 8, 18, 9]
i = 2: [19, 3, 18, 4, 17, 5, 2, 6, 1, 7, 0, 8, 9, 10, 15, 12, 11, 13, 16, 14]
i = 3: [15, 4, 16, 5, 18, 6, 19, 7, 17, 9, 2, 10, 8, 11, 0, 12, 3, 13, 1, 14]

结论 #

1. 多次Minimize的工作机制：CP-SAT会将多次调用的Minimize目标合并为一个加权和目标（默认权重均为1），即求解所有目标表达式之和的最小值。
2. 目标优先级：从测试结果看，未体现明显优先级差异，多个目标处于同等地位，共同参与总和的最小化。
3. 调用顺序的影响：调用顺序不会改变目标的权重（均为1），但可能影响求解过程中的搜索启发式，进而导致不同的可行解输出（如测试中i=2和i=3的结果差异），不过最终的最优解（若存在）会是所有目标总和的最小值。

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