John does California Odyssey (with code)

我很幸运能与 Alain 和 Stéphane 组队。如果没有他们，我不会参加这次比赛，因为我已经参加了另一场比赛。而且如果没有他们，我不可能那么快找到最优解，也就肯定拿不到金牌。团队成员的贡献都非常显著。我们通过不同的观点切入问题，这非常富有成效。

我们从这个 notebook 开始：https://www.kaggle.com/vipito/santa-ip/

它包含几个有趣的组件：

• 一个用于家庭分配到日期的 LP（线性规划）模型。
• 连续几天占用率差异的最大约束。
• 一种用于改进解的局部搜索。

然后我们探索了许多变体和改进。当我们中的一个人找到解时，会分享给其他人，以便他们在下一次运行中可以以此为基础开始。我们迭代了许多模型和运行。通常我们不会让程序运行超过一天。事实上，起始点越好，终点也越好！而且，在使用 MIP（混合整数规划）模型时，起始点越好，模型就越小，因为许多变量可以预先设置为 0。

我们尝试的方法包括：数据/解分析、局部搜索、LNS（大邻域搜索）、线性化、近似、简化和对称性破坏。让我们来看看其中的每一个，顺序不分先后。

局部搜索

我们从公共 kernel 的随机搜索开始，但后来转向了一种类似于最大流算法中使用的搜索：寻找一系列保持占用率基本不变且能降低成本的家庭重新分配链。例如，比较我们在探索早期发现的两个解，我们发现它们仅在少数地方存在差异：

Family: 261 83 - 67
Family: 779 67 - 7
Family: 798 35 - 45
Family: 2926 1 - 35
Family: 3215 25 - 83
Family: 4716 45 - 1
Same: 4994

如果我们仔细观察，会发现移动是可以链接起来的：

35-45-1-35
25-83-67-7

我们有一个 3-循环和一个 3-路径，它们捕获了所有的变化。

我们编写了一个系统性的搜索代码，用于查找给定长度内的链。这比在可能的家庭交换上进行暴力搜索要有效得多。

数据/解分析

在我们最初的几个解之后，我们发现选择排名的分布高度倾斜。大多数家庭得到了他们前 4 个选择中的一个。第一个后果是通过仅考虑最多 4 或 6 个选择来限制模型复杂性，具体取决于运行情况。如果没弄错的话，所有家庭在我们的最优解中都得到了他们前 6 个选择之一。我们在最后证明最优性时放宽了这个限制。

数据分析的另一个例子是查看 gap(d)，即某天 d 占用率的绝对差异。这是成本为 69158.xxx 的解中 gap(d) 随该天占用率变化的函数图。

我们看到有一个单纯形凸包，这可以建议添加额外的条件约束。例如：

if (number(d) >= 126), then (number(d)-number(d-1)) <= a-b*number(d)

其中 number(d) 是第 d 天的占用率，a 和 b 是我们为每次运行设置的两个参数。

成本近似

会计成本函数是非凸的，这使得优化变得棘手。这是一个被高值（我记得是 100,000）封顶后的对数图。

即使是非凸的，它也有一些明显的属性。它随 gap 的增加而增加，且增长速度超过线性。这引出了最小