如何消除线性规划结果偏差？宿舍耦合学生分配问题咨询

问题描述 #

开发学生宿舍分配程序时，将学生按宿舍偏好建模为指派问题输入LP求解器。加入“室友偏好”（学生耦合为占用2个床位的条目）后，求解器最优解总是将耦合学生分配至所有人最不喜欢的宿舍，有失公平。伪代码模型如下：

N is number of students 
M is number of dorms
a[i] is 1 if entry i is not coupled, 2 if entry i is coupled (meaning 2 students are staying together)
c[i][j] indicates student i's ranking of dorm j, 0 is least favorite and M - 1 is most favorite
x[i][j] is a boolean: true if the students gets into dorm j, false if not

Objective: Maximize Sum of c[i][j] * x[i][j] for i: 0 to N - 1 and for j: 0: to M - 1

Constraints: 
- Each student can only be allocated to one dorm: x[i][0] + x[i][1] + ... + x[i][M - 1] = 1
- Each dorm can hold students only to its capacity: a[0] * x[0][j] + a[1] * x[1][j] + ... + a[N-1] * x[N - 1][j] = capacity of dorm j

先后使用glpk.js、neos-server.org的SCIP、HIGHS等求解器，结果一致，随机化输入顺序也无改善，询问是否可通过求解器设置减少对耦合学生的分配歧视。

解决方案 #

问题核心并非求解器设置，而是模型设计的偏向性——当前目标仅最大化总偏好值，求解器会优先将高偏好宿舍的床位分配给单个学生（占用1个床位，能让更多高偏好值被计入总和），把占用2个床位的耦合学生“挤”进低偏好宿舍。以下是具体改进方向：

1. 给耦合学生的偏好加权 #

耦合是学生的明确需求，需在目标函数中赋予更高权重，让求解器优先考虑他们的偏好：

• 若a[i]==2，将目标函数中对应项c[i][j] * x[i][j]乘以系数（如1.5~2），比如调整为1.5 * c[i][j] * x[i][j]。这样耦合学生的偏好贡献被放大，求解器不会轻易将他们分配至最差宿舍。

2. 修正容量约束的逻辑 #

原约束使用=强制宿舍住满，这会导致剩余床位的宿舍（通常是低偏好宿舍）必须塞进耦合学生。将约束改为小于等于：

sum(a[i] * x[i][j] for all i) <= capacity[j]

允许宿舍有空床位，避免强制塞人到低偏好宿舍。

3. 添加公平性约束 #

可直接限制耦合学生分配至最差宿舍的数量，比如禁止耦合学生进入最不受欢迎的宿舍：

sum(x[i][j_worst] for i where a[i]==2) = 0

或设置上限（如最多1组耦合学生进入最差宿舍），从约束层面保障公平。

4. 求解器辅助调整（次要手段） #

如果坚持使用原模型，可尝试：

• 设置变量分支优先级：在求解器中给耦合学生对应的x[i][j]变量设置更高分支优先级，让求解器优先尝试给他们分配偏好更高的宿舍（不同求解器设置方式不同，比如SCIP可通过变量属性配置）；
• 枚举次优解：让求解器输出多个接近最优的可行解，从中挑选更公平的分配方案（GLPK、SCIP均支持多解枚举功能）。

内容的提问来源于stack exchange，提问作者Tin Nguyen