如何用OR-Tools解决离散变量约束下的影院观影评分最大化问题？

问题本质 #

你的需求是离散选择+严格递减约束的最大化优化问题，GLOP作为线性规划求解器仅支持连续变量，没法限制“每天只能选指定几部电影”这类离散选项，因此完全不适用。

OR-Tools首选：CP-SAT求解器 #

OR-Tools里的CP-SAT（Constraint Programming SAT）是专门处理离散约束优化问题的工具，完美匹配你的场景：

• 用布尔变量就能轻松建模“某天选某部电影”：比如x[day][movie]是布尔变量，值为1代表当天选这部电影，值为0则不选。
• 约束添加简单直接：
  • 每天必选且仅选一部允许的电影：给每一天加约束，当天所有可选电影对应的布尔变量之和等于1。
  • 评分严格递减：直接给相邻两天设置约束——当天选中电影的评分必须大于下一天选中电影的评分。
• 目标设置清晰：把每天选中电影的评分加起来，设置为最大化目标即可。

快速建模逻辑 #

1. 定义布尔变量：x[d][m]，d对应周一到周五，m对应当天可放映的电影。
2. 添加约束：
   • 每日选片唯一性：对每个d，sum(x[d][m] for m in 当天可选电影) = 1
   • 评分递减规则：对相邻两天d和d+1，sum(x[d][m] * 电影m评分 for m) > sum(x[d+1][n] * 电影n评分 for n)（覆盖周一到周四的相邻组合）
3. 设置目标函数：最大化sum( sum(x[d][m] * 电影m评分 for m) for d in 五天 )

备选：SCIP混合整数规划求解器 #

如果你习惯整数规划（MIP）的建模方式，OR-Tools集成的SCIP求解器也能解决，但建模会相对繁琐：

• 需要用0-1变量关联“是否选择某部电影”，再把每天的评分变量绑定到可选电影的评分值上，最后添加递减约束。
• 相比CP-SAT，这种方式对离散选择场景的适配性没那么直观，但也能实现需求。

其他可选库（不限于OR-Tools） #

如果不局限于OR-Tools，Python中的PuLP、Pyomo这类库也支持混合整数规划，搭配CBC、Gurobi等求解器也能完成需求，但OR-Tools的CP-SAT在编码效率和求解速度上更贴合你的问题。

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