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

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

我们的基本解法思路与原始圣诞老人挑战赛非常相似，也是许多团队采用的方法。我们将目标函数线性化，并使用 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'\) 时某一项惩罚的值。那么惩罚目标为：

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

这仍然是一个非线性约束，但由于 \(n_{d,\cdot}\) 和 \(n_{d+i,\cdot}\) 中恰好各有一个为 1，这些约束可以被替换为：

以及：