如何使用求解器对软件使用组合统计数据解聚合还原用户明细

求解器方案可行性 #

使用求解器解决该反向解聚合问题是完全可行的，你之前遇到的非线性问题是约束设置思路有误导致的，不需要引入非线性逻辑，可直接转换为整数线性规划问题求解。

你可以按如下思路调整约束设置：

• 定义二进制变量x[u][s]，取值为1代表用户u使用软件s，取值为0代表不使用
• 对上三角矩阵中每一组软件对(s_i, s_j)，对每个用户u新增二进制辅助变量y[u][s_i][s_j]，并添加3条线性约束：
  • y[u][s_i][s_j] ≤ x[u][s_i]
  • y[u][s_i][s_j] ≤ x[u][s_j]
  • y[u][s_i][s_j] ≥ x[u][s_i] + x[u][s_j] - 1
    上述约束可以保证y[u][s_i][s_j]只有在x[u][s_i]和x[u][s_j]同时为1时取值为1，其余场景均为0，完全等价于你之前要实现的乘积逻辑
• 最后添加聚合约束：对每组软件对(s_i, s_j)，所有用户的y[u][s_i][s_j]之和等于上三角矩阵中对应位置的数值，再补充总用户数为5的边界约束即可

GLPK适配性说明 #

GLPK完全可以实现该需求，不需要更换其他求解器。调整约束为上述线性形式后，就属于GLPK支持的整数线性规划求解范围，按GLPK的语法规则定义变量和约束即可求出满足要求的用户使用明细矩阵。

如果后续需要处理更大规模的问题想优化求解速度，也可以根据使用场景选择Gurobi、Cplex等商业求解器，或者SCIP等开源求解器，但针对你当前5用户5软件的小规模问题，GLPK的性能完全足够。

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