总结：我们如何找到最优（？）解法

这是一篇关于我们如何找到该挑战已知最佳解法的（简短？）描述。由于这个挑战与最初的挑战非常相似，我们实际上会同时描述两者。

我们的基本解决方法与最初的圣诞老人挑战非常相似，也是许多团队采用的方法。我们将目标函数线性化，并使用 Gurobi 求解生成的 MIP（混合整数规划）模型（实际上，Gurobi 那些不可思议的圣诞精灵在挑战开始前刚刚发布了最新版本，这绝非巧合……；)）。为了完整性，我们展示完整的模型。

首先，将每个家庭分配到每一天是非常直观的。对于每个家庭 \(f \in F\) 和每一天 \(d \in D\)，我们引入一个二元变量：

表示家庭 \(f\) 分配给日期 \(d\)。每个家庭必须被分配一次且仅一次：

匹配目标仅取决于每个家庭被分配到的日期：

其中 \(c_{f,d}\)，\(f \in F\)，\(d \in D\)，表示家庭 \(f \in F\) 分配给日期 \(d \in D\) 的分配成本。

然后我们需要计算每天分配的人数。设 \(p_f\)，\(f \in F\) 表示家庭 \(f \in F\) 的人数，那么（整数）变量：

表示分配给日期 \(d \in D\) 的人数。正确的数量通过以下约束确定：

这是简单的部分。现在我们需要对非线性惩罚进行建模。基本的观察是，惩罚目标的每一项仅取决于两个值：\(i=1, \ldots, 5\) 时的 \(N_d\) 和 \(N_{d+i}\)（最初的圣诞老人挑战只有 \(i=1\) 的项），并且每个 \(N_d\) 只能取值 \(V := \{125, \ldots, 300\}\)。正如许多人已经意识到的，这可以按如下方式线性化：

首先，我们引入二元变量 \(n_{d,v}\)，\(d \in D\)，\(v \in V\)，当且仅当 \(n_d = v\) 时（即恰好有 \(v\) 个人被分配到日期 \(d\)），\(n_{d,v} = 1\)。因为 \(n_d\) 恰好有一个值，我们添加约束：

\(n_{d,v}\) 和 \(n_d\) 变量通过以下方式连接：

如前所述，惩罚目标的每一项仅取决于两个变量 \(n_d\) 和 \(n_{d+i}\) 的值，或者等价地取决于 \(n_{d,v}\) 和 \(n_{d+i,v'}\)。设 \(c_{m,m',i}\) 为当 \(n_d = m\) 和 \(n_{d+i} = m'\) 时某个惩罚项的值（对于某个 \(d \in D\)）。那么惩罚目标是：

（在最初的问题中，只有 i=1 的项出现）。当然，这还不是一个线性目标（因为 \(n_{d,m} \cdot n_{d+i,m'}\)）。标准方法是引入一个新的二元变量来表示每个乘积：

这仍然是一个非线性约束，但因为 \(n_{d,\cdot}\) 和 \(