用电晕限制优化活动座位分配

Question

问题：给定一组注册组，每个注册组的人数不同(1-7)，以及一组座位组（不可变，至少相距2m)，座位数不同于1-4个，我想找到人组对座位组的最佳分配：

• 人组可以分为几个座位组（但最好不是）
• 不同的人组不能共享座位组
• （可选）分配应使“浪费”的座位数最小化，即使空座位组中的座位数最大化
• （理想情况下，它应该在Google Apps脚本中运行，因此内存和计算复杂性应该尽可能小）

第一次尝试：我对决策问题感兴趣（可行吗？）以及优化问题（参见可选优化函数）。我把它模拟成一个SAT问题，但这没有找到最优解。

null

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

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

虽然这将空座位的数量减至最低，但并没有将使用的桌子数量减至最低，也没有将接纳的团体数量减至最大。如果你想这样做，你可以扩展目标函数，为每一个被拒绝的群体增加一个惩罚。

ILPs是NP难的，所以如果没有正确的求解器，它可能不可能运行谷歌应用程序。我对那件事没有经验，所以恐怕我帮不了你。但是有一些方法可以减少你的搜索空间。