在一个简单的 TSP 问题中消除 subtours

Question

我正在尝试解决一个非常简单的 TSP 问题，但 SCIP 的 TSP 示例有点吓人。

我只想像 GuRoBi 那样添加简单的 Lazy 约束。

我可能需要一些帮助来了解某些地方发生的事情。

我假设我不必实施 SCIP_DECL_CONSSEPALP SCIP_DECL_CONSENFOLP 和 SCIP_DECL_CONSENFOPS。我只需要实现一个简单的循环检测功能并将其添加为剪辑即可。

如果我理解正确，我可以在 SCIP_DECL_CONSCHECK 中编写函数进行循环检测，但我不确定它实际上是如何工作的。

assert(result != NULL);
   *result = SCIP_FEASIBLE;

   for( int i = 0; i < nconss; ++i )
   {
      SCIP_CONSDATA* consdata;
      GRAPH* graph;
      SCIP_Bool found;

      assert(conss != NULL);
      assert(conss[i] != NULL);
      consdata = SCIPconsGetData(conss[i]);
      assert(consdata != NULL);
      graph = consdata->graph;
      assert(graph != NULL);

      // if a subtour is found, the solution must be infeasible
      found = findSubtour(scip, graph, sol);
      if( found )
      {
         *result = SCIP_INFEASIBLE;
         if( printreason )
         {
            SCIP_CALL( SCIPprintCons(scip, conss[i], NULL) );
            SCIPinfoMessage(scip, NULL, "violation: graph has a subtour\n");
         }
      }
   }

   return SCIP_OKAY;

如果我只有一个约束处理程序，我还应该使用 nconss 吗？在我找到一个 subtour 之后究竟会发生什么？ *result 设置为 SCIP_INFEASIBLE 后调用了哪个函数？

我怎样才能将我在 SCIP_DECL_CONSCHECK 中找到的子路线（路线中的顶点）传递给那个函数，这样我就不必再次找到循环并添加实际的切割？

Answer 1

您实际上需要实现两个回调。 SCIP_DECL_CONSCHECK 和 SCIP_DECL_CONSENFOLP.

在检查回调中，您只需要检测是否找到了子路线，如果是，则将结果设置为 SCIP_INFEASIBLE（就像您所做的那样）。您不必使用 nconss，因为您的 subtour 约束处理程序没有任何约束。

在执行回调中 SCIP_DECL_CONSENFOLP 您必须通过添加新的 subtour 消除约束来真正解决这些不可行性问题。

如果您想详细了解这些 SCIP 回调的工作原理，可以听听我去年 CO@Work 暑期学校的演讲（运行示例是 TSP）on youtube。另外，当天的练习 Programming plugins 是在 PySCIPott 中实现 TSP，您可以在 Co@Work 网页上找到解决方案。

在一个简单的 TSP 问题中消除 subtours

Eliminating subtours in a simple TSP problem

linear-programming

scip

mixed-integer-programming