我的最优解

我使用了带有无限制评估许可证的 Gurobi 9.0。感谢 Gurobi 提供评估许可证。SCIP 在 ortools 中只能让我达到 68910.94 的成绩。

• 我将每天的入住率固定在以下数组中，并在每天数值的 +/-5 范围内运行 MIP（混合整数规划）模型。

  estimate_occupancies = np.array([300, 287, 300, 300, 286, 262, 250, 250, 271, 296, 300, 300, 279,
          264, 256, 273, 294, 282, 259, 228, 196, 164, 125, 300, 300, 295,
          278, 263, 257, 253, 279, 276, 252, 219, 188, 156, 125, 283, 271,
          248, 216, 184, 159, 125, 300, 282, 257, 226, 194, 161, 125, 286,
          264, 236, 201, 168, 137, 125, 266, 241, 207, 166, 125, 125, 125,
          253, 225, 190, 147, 125, 125, 125, 227, 207, 175, 129, 125, 125,
          125, 235, 220, 189, 147, 125, 125, 125, 256, 234, 202, 161, 125,
          125, 125, 234, 214, 181, 136, 125, 125, 125])

  在这个范围内，MIP 模型在我的 macbook 上运行不到 10 分钟。
• 我是从哪里得到这些预估入住率的呢？我在 5000x10 个偏好成本连续变量（取值范围 0 到 1）+ 100x176x176 个会计成本二进制变量上运行了 LP（线性规划）模型，就像 这个讨论帖 中的指南一样，并添加了这些二次约束，其中 zs 是我的 100x176x176 个会计成本变量：

  for i in range(0, N_DAYS, 2):   ## 每两天只需要一次
      for u in range(0, 176, 2):   # 每两个入住率
          for v in range(0, 176):   
              two_vars = zs[i][u, v] + zs[i][u+1, v]   
              m.addConstr(two_vars*two_vars==two_vars)

  这些二次约束仅 LP 模型需要，在 MIP 模型中我们不需要它。在 LP 模型中，它们强制松弛解为某一天使用两个相邻的入住率。这样，LP 模型在松弛解中就不会对会计成本过于乐观。你不需要将 LP 模型运行到底，只需在找到 67xxx 的解时停止即可，这在我的 macbook 上大约需要 25 分钟。

这个解决方案听起来简单且快速，但我花了几个月的时间才弄明白。祝贺并感谢大家，如果没有参考这场精彩比赛中的讨论，我无法获得这个分数。