代码之家  ›  专栏  ›  技术社区  ›  Morpheus

消除简单TSP问题中的子问题

  •  0
  • Morpheus  · 技术社区  · 4 年前

    我试图解决一个非常简单的TSP问题,但SCIP的TSP示例有点吓人。

    我只想添加简单的Lazy约束,就像GuRoBi一样。

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

    我想我不必实施 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 ? 找到字幕后,具体会发生什么?设置后调用哪个函数 *result SCIP_INFEASIBLE ?

    我如何传递我在中找到的子图(教程中的顶点) SCIP_DECL_CONSCHECK 这样我就不必再次找到循环并添加实际切割了吗?

    0 回复  |  直到 4 年前
        1
  •  2
  •   Leon    4 年前

    实际上,您需要实现两个回调。这个 SCIP_DECL_CONSCHECK 以及 SCIP_DECL_CONSENFOLP .

    在检查回调中,您只需要检测是否找到子线程,如果是这样,则将结果设置为 SCIP_INFEASIBLE (正如你所做的那样)。 您不必使用 nconss 因为您的子线程约束处理程序没有任何约束。

    在执行回调中 SCIP_DECL_CONSENFOLP 你必须通过添加一个新的子库消除约束来解决这些不可行性。

    如果你想了解更多关于这些SCIP回调是如何工作的,你可以听我去年的演讲CO@Work暑期学校(以TSP为例) on youtube . 此外,当天的练习编程插件是PySCIPopt中TSP的实现,您可以在Co@Work网页。