使用 Corona 限制优化活动座位分配

Question

问题： 给定一组组注册，每个组注册人数不同（1-7），和一组座位组（不变，相距至少 2m），从 1-4 个座位不等，我想找到人群到座位组的最佳分配：

人们可以分成几个座位组（尽管最好不要）
座位组不能由不同的人群共享
（可选）分配应尽量减少 'wasted' 个座位的数量，即最大化空座位组中的座位数量
（理想情况下，它应该在 Google Apps 脚本中运行，因此内存和计算复杂度应尽可能小）

第一次尝试： 我对决策问题（是否可行？）以及优化问题（参见可选优化函数）感兴趣。我已将其建模为 SAT 问题，但这并没有找到最佳解决方案。

出于这个原因，我尝试将其建模为优化问题。我正在考虑多背包的（远程）变体，但我还不能命名它：

项目：座位组（尺寸 -> 重量）
背包：人群（尺寸 -> 容器尺寸）
限制条件：商品组合重量 >= 容器尺寸
优化：最小化项目数量

如你所见，与标准问题相比，约束和优化是相反的。所以我的问题是：我是在正确的轨道上还是你会换一种方式？如果正确，这个优化问题有名字吗？

Answer 1

您可以将其视为整数线性规划问题，定义如下：

let P = the set of people groups, people group i consists of p_i people;
let T = the set of tables, table j has t_j places;
let x_ij be 1 if people from people group i are placed at table j, 0 otherwise
let M be a large penalty factor for empty seats
let N be a large penalty factor for splitting groups

     // # of free spaces = # unavailable - # occupied
     // every time a group uses more than one table,
     // a penalty of N * (#tables - 1) is incurred
min  M * [SUM_j(SUM_i[x_ij] * t_j) - SUM_i(p_i)] + N * SUM_i[(SUM_j(x_ij) - 1)]

     // at most one group per table
s.t. SUM_i(x_ij) <= 1 for all j

     // every group has enough seats
     SUM_j(x_ij * t_j) = p_i for all i

     0 <= x_ij <= 1

虽然这最大限度地减少了空座位的数量，但并没有最大限度地减少使用的桌子数量或最大限度地增加接纳的团体数量。如果您想这样做，您可以通过为每个被拒之门外的小组添加惩罚来扩展 objective 功能。

ILP 是 NP-hard，因此如果没有合适的求解器，可能无法使用 Google 应用程序实现此运行。我没有这方面的经验，所以我恐怕帮不了你。但是有一些方法可以减少搜索 space.

一个人会通过一个叫做 column generation 的东西。在这里，问题分为两部分。复杂的主问题是您的主要研究问题，但它不是整个解决方案 space，而是试图从不同的候选分配（或列）中找到最优解。

目标是定义一个子问题，推荐这些新的潜在解决方案，然后将这些解决方案合并到主问题中。一个好的子问题的力量在于它应该可以简化为一个更简单的模型，例如 Knapsack 或 Dijkstra。

使用 Corona 限制优化活动座位分配

Optimize event seat assignments with Corona restrictions

algorithm

optimization

knapsack-problem

linear-programming

sat