求解VRP问题时加cut

Question

求解MIP问题时，不及时删除无效的cut会让求解整数解变得更加困难吗？无效cut的存在会产生更多的非整数解极点吗？

为什么求解器在求解时在树节点和根节点都实现了对cut的动态添加和删除，但求解mip问题速度仍然非常非常慢？这种情况下，针对具体问题添加新的cut会帮助我们加快求解速度吗？比如对于VRP问题而言，有哪些cut是我们可以手动添加来加快求解速度的呢？

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

回答：

1. 不及时删除无效的cut会让求解整数解变得更加困难，因为无效的cut会占据求解器的时间和空间，导致分支界定树中的节点数量增加，从而增加求解整数解的难度。无效cut的存在也会产生更多的非整数解极点，因为它们可能会降低求解器的性能并阻碍求解器找到最优的整数解。因此，尽可能删除无效的cut是一个非常重要的优化策略。
2. 求解器实现对cut的动态添加和删除并不能保证求解速度的提高，因为cut的添加和删除是一种启发式方法，它可能会带来利益也可能会带来损失，需要依据具体问题进行考虑。例如，在VRP问题中，添加一些不必要的cut可能会降低求解速度，因为它可能会增加求解器的负担和分支界定树中的节点数量。但有些特定类型的cut可以有效地提高求解速度，例如流量约束cut、车辆容量约束cut、子集划分cut等。 针对具体问题添加新的cut需要深入理解问题的特点和结构，并根据cut的性质从数学上证明它的有效性。在VRP问题中，可以手动添加以下cut来提高求解速度： (1)流量约束cut：在每个节点上，对每个货物类型i累计到达的数量进行约束。这可以防止超载和回程等不合法情况的发生。 (2)车辆容量约束cut：在每个节点上，对每个车辆的容量进行约束。这可以防止在一个节点上装载过多的货物导致车辆容量的超限。 (3)子集划分cut：将订单划分为子集，每个子集对应一个集合。对于每个集合，需要至少分配一个车辆来满足其需求。这可以有效地限制车辆的数量并提高求解速度。 以下是添加流量约束cut的代码实现：

for (int i = 0; i < num_customers; i++) {
  GRBLinExpr expr = 0;
  for (int j = 0; j < num_vehicles; j++) {
    for (int k = 0; k < num_customers; k++) {
      if (k != i) {
        expr += x[i][k][j];
      }
    }
  }
  for (int h = 0; h < num_cargos; h++) {
    model.addConstr(expr <= q[h]*y[i][h]);
  }
}

其中，num_customers表示节点数，num_vehicles表示车辆数，num_cargos表示货物类型数，q[h]表示第h种货物的容积，x[i][k][j]表示从节点i到节点k是否由车辆j运输，y[i][h]表示节点i是否装载了h种货物。