纸浆整数规划约束被忽略

Question

我正在尝试仅使用布尔变量解决 LpProblem，而 Pulp 似乎忽略了一些约束。提供有关该问题的一些背景信息：

我想为学校在尝试创建课堂小组时面临的问题找到最佳解决方案。在这种情况下，给学生一份论文，让他们最多写 5 名其他学生，学校保证他们将与至少其中一名学生在一起。要了解我如何将此问题建模为整数规划问题，请参阅 this question.

在那link你会看到我的变量被定义为x_ij = 1如果学生i和学生j在一起，否则x_i_j = 0。此外，在 link 中，我询问了我在使用 Pulp 时遇到的约束：如果 x_i_j = 1 且 x_j_k = 1，则通过传递属性，x_i_k = 1。也就是说，如果i同学和j同学在一起，j同学和k同学在一起，那么i同学自然会和k同学在一起。

我的objective是最大化输入矩阵和变量矩阵进行阿达玛乘积时得到的矩阵所有元素之和。换句话说，我想尽可能多地考虑学生的要求。

我现在将提供一些代码片段和屏幕截图，以帮助可视化问题：

输入（只是一个例子：真实矩阵是37x37）

输出

正如您在最后一张图片中看到的，x_27 = 1 和 x_37 = 1 但 x_23 = 0 没有意义。

下面是我定义变量的方式

def define_variables():
  variables = []
  for i in range(AMOUNT_OF_STUDENTS):
    row = []
    for j in range(AMOUNT_OF_STUDENTS):
      row.append(LpVariable(f"x_{i}_{j}", lowBound=0, upBound=1, cat='Integer'))
    variables.append(row)
  return variables

这是我定义传递约束的方式

    for i in range(len(variables)):
      for j in range(i, len(variables)):
        if i != j:
          problem += variables[i][j] == variables[j][i]   # Symmetry
        for k in range(j, len(variables)):
          if i < j < k < len(variables):
            problem += variables[i][j] + variables[j][k] - variables[i][k] <= 1 # Transitive
            problem += variables[i][j] + variables[i][k] - variables[j][k] <= 1
            problem += variables[j][k] + variables[i][k] - variables[i][j] <= 1

打印 LpProblem 时，我看到约束显然不起作用：

正如您在输出中看到的：x_2_7 = 1 和 x_3_7 = 1。因此，要满足此约束条件，x_2_3 也应为 1，但您可以也在输出中看到，它是 0.

对可能发生的事情有什么想法吗？我已经被困了好几天了，这个问题似乎建模得很好，当我只有 8 个学生（64 个变量）时它就起作用了。现在我有 37 个学生（1369 个变量），它似乎表现得很奇怪。求解器得出了一个解，但它似乎忽略了一些约束。

非常感谢任何帮助！提前谢谢你。

Answer 1

这称为集合划分问题，PuLP 在其文档中有一个示例 here。

本质上，不是将变量建模为学生 A 是否与学生 B 处于同一 class 的指标，而是定义一组学生与一组 class房间。然后，您可以将您的学生偏好应用为约束或最大化 objective.

的一部分

Answer 2

约束工作正常。找到下面的分析：（交叉发布自 github：https://github.com/coin-or/pulp/issues/377）

import pulp as pl
import pytups as pt

path = 'debugSolution.txt'

# import model
_vars, prob = pl.LpProblem.from_json(path)

# get all variables with non-zero value
vars_value = pt.SuperDict(_vars).vfilter(pl.value)

# export the lp
prob.writeLP('debugSolution.lp')

# the constraint you show in the SO problem is:
# _C3833: - x_2_3 + x_2_7 + x_3_7 <= 1

'x_2_7' in vars_value
# True, so x_2_7 has value 1

'x_3_7' in vars_value
# False, so x_3_7 has value 0

'x_2_3' in vars_value
# False, so x_2_3 has value 0

所以-0 + 1 + 0 <= 1意味着约束得到遵守。在某处带回 x_3_7 的值一定有问题，因为你认为它是 1，而在纸浆中它是 0。

纸浆整数规划约束被忽略

Pulp Integer Programming Constraint ignored

python

pulp