如何赢得圣诞老人工作室之旅
首先，我要感谢 @inversion 准备了这场精彩的比赛。真的非常有趣。
其次，抱歉过了这么久我才写下这篇帖子。
第三，是的，你们大多数人说得对。我也使用了混合整数规划。
现在让我们开始吧！
我寻找最优解的路径始于认识到“非线性”的目标函数可以通过枚举某一天和次日可能访问的所有人数组合来进行线性化。
之后，我简短地查看了数据，并认为不会有太多的家庭被分配到非首选的日子。尽管如此，我不想完全排除这种可能性。这引导我得出了以下结论：
混合整数线性规划松弛
x_{f,d^f_p}是一个二进制变量，当且仅当家庭f被分配到其偏好p（对于p=1,...,10）时，该变量为1；x_{f,d^f_{11}}为1当且仅当家庭未被分配到其任何一个首选日期，其中d^f_{11}被设定为“第101天”。y_{d,i,j}是一个二进制变量，当且仅当第d天有i人且第d+1天有j人被分配时，该变量为1。注意，为了表述方便，我们也引入了变量y_{100,i,j}（对于i≠j）。在此设定下，我们可以将每个变量y_{100,i,j}固定为0（对于i≠j）。显然，我在实现中没有添加这些变量。z_d是代表第d天分配了多少人的“连续”变量。- 项
(1)是我们想要最小化的目标函数，其中pc(p)代表偏好成本，ac(i,j)代表会计成本。 - 方程
(2)确保每个家庭要么被分配到其首选日期之一，要么被分配到“第101天”（代表该家庭未被分配到其偏好之一）。 - 方程
(3)确保第d天被分配了当天的访问人数以及次日的访问人数。 - 方程
(4)在某种意义上是“流量守恒”，确保连续几天的人数相吻合。 - 方程
(5)将连续日期变量与日期数量变量耦合起来。 - 不等式
(6)确保分配到某天的人数至少等于那些偏好该天并被分配到该天的人数，其中n_f是家庭f的成员数量。 - 方程
(7)确保分配到所有天数的人数总和等于家庭成员总数。
请注意，通常情况下，此 MIP 的解不一定是圣诞老人问题的可行解。此外，我认为如果数据不好，使此 MIP 的解变得可行可能与从头解决圣诞老人问题一样具有挑战性。
尽管如此，数据看起来并没有那么糟糕，事实证明我从未需要“修复”一个解。
大约两个小时后，Gurobi 找到了一个高质量的解，我自然立即将其提交到了排行榜。由于我实现中的一个错误，这导致了一个得分 >34145044298 的解，这是整个比赛期间排行榜上显示的最差分数。
修复错误后，我得到了一个值 ≤74589 的解。三个小时后，Gurobi 产生了一个值 ≤70913 的解，该解在 24 小时内没有进一步改善。
尽管如此，我没有使用这些解，因为我同时在进行变量数量的缩减工作。