python - Pulp 整数编程约束被忽略

问题描述

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

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

在该链接中，您将看到我的变量定义为 x_ij = 1 如果学生 i 将与学生 j 在一起，否则 x_i_j = 0。此外，在该链接中，我询问了我在使用 Pulp 实现时遇到问题的约束：如果 x_i_j = 1 和 x_j_k = 1，则通过传递属性 x_i_k = 1。换句话说，如果学生 i 和学生 j 在一起，并且学生 j 与学生 k 在一起，那么学生 i 将与学生 k 天生在一起。

我的目标是最大化在输入矩阵和变量矩阵之间执行 Hadamard 乘积时获得的矩阵的所有元素的总和。换句话说，我想尽可能多地考虑学生的要求。

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

输入（只是一个样本：真实矩阵是 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 个变量），它的行为似乎很奇怪。求解器得出了一个解决方案，但它似乎忽略了一些约束。

很感谢任何形式的帮助！先感谢您。

标签： pythonpulp

python - Pulp 整数编程约束被忽略

问题描述

解决方案

推荐阅读