使用定价器在根节点播出后，如何在 SCIP 中使用约束处理程序添加分隔符？

Question

我最初尝试实现一个分支和价格算法，并且我在实现它方面取得了很大成功。我实施了一个定价器插件，一切似乎都正常。但我想通过添加一些削减来加强这个模型。而不是通常的分支削减价格方案，我只想在根节点添加削减（在所有列都添加到根节点之后，在分支开始并添加更多列之前），而不是在分支开始后进一步削减（至少这是目前的计划）。

我实现了一个基本的约束处理程序，目前它做的不多，但有一些占位符来检查是否正确调用了适当的函数。我从 TSP 源代码中复制了大部分内容。为了简洁起见，我删除了广泛的评论和文档

ConshdlrSCO.hpp如下

#ifndef __SCOCONSHDLRSCO_HPP__
#define __SCOCONSHDLRSCO_HPP__

#include "objscip/objscip.h"

namespace SCO
{
class ConshdlrSCO : public scip::ObjConshdlr
{
public:
   ConshdlrSCO(SCIP* scip)
      : ObjConshdlr(scip, "SCO", "SCO OR constraints",
         1000000, -2000000, -2000000, 1, -1, 1, 0,
         FALSE, FALSE, TRUE, SCIP_PROPTIMING_BEFORELP, SCIP_PRESOLTIMING_FAST)
    {}

   virtual ~ConshdlrSCO(){}

   virtual SCIP_DECL_CONSDELETE(scip_delete);

   virtual SCIP_DECL_CONSTRANS(scip_trans);

   virtual SCIP_DECL_CONSSEPALP(scip_sepalp);

   virtual SCIP_DECL_CONSSEPASOL(scip_sepasol);

   virtual SCIP_DECL_CONSENFOLP(scip_enfolp);

   virtual SCIP_DECL_CONSENFOPS(scip_enfops);

   virtual SCIP_DECL_CONSCHECK(scip_check);

   virtual SCIP_DECL_CONSPROP(scip_prop);

   virtual SCIP_DECL_CONSLOCK(scip_lock);

   virtual SCIP_DECL_CONSDELVARS(scip_delvars);

   virtual SCIP_DECL_CONSPRINT(scip_print);

   virtual SCIP_DECL_CONSHDLRISCLONEABLE(iscloneable)
   {
      return true;
   }

   virtual SCIP_DECL_CONSHDLRCLONE(scip::ObjProbCloneable* clone); /*lint !e665*/

   virtual SCIP_DECL_CONSCOPY(scip_copy);
}; 
SCIP_RETCODE SCIPcreateConsSCO(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
   const char*           name,               /**< name of constraint */
   SCIP_Bool             initial,            /**< should the LP relaxation of constraint be in the initial LP? */
   SCIP_Bool             separate,           /**< should the constraint be separated during LP processing? */
   SCIP_Bool             enforce,            /**< should the constraint be enforced during node processing? */
   SCIP_Bool             check,              /**< should the constraint be checked for feasibility? */
   SCIP_Bool             propagate,          /**< should the constraint be propagated during node processing? */
   SCIP_Bool             local,              /**< is constraint only valid locally? */
   SCIP_Bool             modifiable,         /**< is constraint modifiable (subject to column generation)? */
   SCIP_Bool             dynamic,            /**< is constraint dynamic? */
   SCIP_Bool             removable           /**< should the constraint be removed from the LP due to aging or cleanup? */
   );
}

#endif

ConshdlrSCO.cpp文件如下

#include <cassert>
#include <string>
#include <iostream>
#include "ConshdlrSCO.hpp"

#include "objscip/objscip.h"
#include "scip/cons_linear.h"


/* checks whether proposed solution contains a valid SCO OR in the graph */
static
SCIP_Bool find_SCO_OR(
   SCIP*              scip,               /**< SCIP data structure */
   SCIP_SOL*          sol                 /**< proposed solution */
   )
{  
    return false;
}

/* separates SCO  cuts */
static
SCIP_RETCODE sepaSCO(
   SCIP*              scip,               /**< SCIP data structure */
   SCIP_CONSHDLR*     conshdlr,           /**< the constraint handler itself */
   SCIP_CONS**        conss,              /**< array of constraints to process */
   int                nconss,             /**< number of constraints to process */
   int                nusefulconss,       /**< number of useful (non-obsolete) constraints to process */
   SCIP_SOL*          sol,                /**< primal solution that should be separated */
   SCIP_RESULT*       result              /**< pointer to store the result of the separation call */
   )
{
   std::cout << "sepaSCO seems to work!" << "\n";
   return SCIP_OKAY;
} 


SCIP_DECL_CONSDELETE(SCO::ConshdlrSCO::scip_delete)
{
   return SCIP_OKAY;
}


SCIP_DECL_CONSTRANS(SCO::ConshdlrSCO::scip_trans)
{

    std::cout << "scip_trans has started working!" << "\n";

    /* create target constraint */
    SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, nullptr,
          SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
          SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),  SCIPconsIsLocal(sourcecons),
          SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons),
          SCIPconsIsStickingAtNode(sourcecons)) );

   std::cout << "scip_trans has finished working!" << "\n";
   return SCIP_OKAY;
}


SCIP_DECL_CONSSEPALP(SCO::ConshdlrSCO::scip_sepalp)
{
   std::cout << "SCIP_sepalp is working till here!" << "\n";
   SCIP_CALL( sepaSCO(scip, conshdlr, conss, nconss, nusefulconss, NULL, result) );
   return SCIP_OKAY;
}


SCIP_DECL_CONSSEPASOL(SCO::ConshdlrSCO::scip_sepasol)
{
   return SCIP_OKAY;
}


SCIP_DECL_CONSENFOLP(SCO::ConshdlrSCO::scip_enfolp)
{
   return SCIP_OKAY;
}

SCIP_DECL_CONSENFOPS(SCO::ConshdlrSCO::scip_enfops)
{
   return SCIP_OKAY;
} 


SCIP_DECL_CONSCHECK(SCO::ConshdlrSCO::scip_check)
{
   std::cout << "SCIp_check_ works till here!" << "\n";
   return SCIP_OKAY;
} 


SCIP_DECL_CONSPROP(SCO::ConshdlrSCO::scip_prop)
{
    return SCIP_OKAY;
} 


SCIP_DECL_CONSLOCK(SCO::ConshdlrSCO::scip_lock)
{
   return SCIP_OKAY;
} 


SCIP_DECL_CONSDELVARS(SCO::ConshdlrSCO::scip_delvars)
{
   return SCIP_OKAY;
} 


SCIP_DECL_CONSPRINT(SCO::ConshdlrSCO::scip_print)
{
   return SCIP_OKAY;
} 

SCIP_DECL_CONSHDLRCLONE(scip::ObjProbCloneable* SCO::ConshdlrSCO::clone) 
{
   *valid = true;
   return new ConshdlrSCO(scip);
}


SCIP_DECL_CONSCOPY(SCO::ConshdlrSCO::scip_copy)
{
   return SCIP_OKAY;
} 

SCIP_RETCODE SCO::SCIPcreateConsSCO(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
   const char*           name,               /**< name of constraint */
   SCIP_Bool             initial,            /**< should the LP relaxation of constraint be in the initial LP? */
   SCIP_Bool             separate,           /**< should the constraint be separated during LP processing? */
   SCIP_Bool             enforce,            /**< should the constraint be enforced during node processing? */
   SCIP_Bool             check,              /**< should the constraint be checked for feasibility? */
   SCIP_Bool             propagate,          /**< should the constraint be propagated during node processing? */
   SCIP_Bool             local,              /**< is constraint only valid locally? */
   SCIP_Bool             modifiable,         /**< is constraint modifiable (subject to column generation)? */
   SCIP_Bool             dynamic,            /**< is constraint dynamic? */
   SCIP_Bool             removable           /**< should the constraint be removed from the LP due to aging or cleanup? */
   )
{
    SCIP_CONSHDLR* conshdlr;

    /* create constraint */
    conshdlr = SCIPfindConshdlr(scip, "SCO");
      if( conshdlr == NULL )
      {
         SCIPerrorMessage("SCO constraint handler not found\n");
         return SCIP_PLUGINNOTFOUND;
      }

    auto consdata = nullptr;

    SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
            local, modifiable, dynamic, removable, FALSE) );

    std::cout << "SCIPcreateConsSCO is working!" << "\n";

   return SCIP_OKAY;
}

我像这样一个接一个地添加了定价器和约束处理程序

ObjPricerSCO* SCO_pricer_ptr = new ObjPricerSCO(scip, SCO_PRICER_NAME, instance, z_vars, ..., , env2);\
SCIP_CALL( SCIPincludeObjPricer(scip, SCO_pricer_ptr, true) );

/* activate pricer */
SCIP_CALL( SCIPactivatePricer(scip, SCIPfindPricer(scip, SCO_PRICER_NAME)) );

SCO::ConshdlrSCO* SCO_cons_hdlr_ptr = new SCO::ConshdlrSCO(scip);
SCIP_CALL( SCIPincludeObjConshdlr(scip, SCO_cons_hdlr_ptr, true) );

//Adding the OR cut
SCIP_CONS* cons;
SCIP_CALL( SCO::SCIPcreateConsSCO(scip, &cons, "OR_SCO_cut", FALSE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE ) );
SCIP_CALL( SCIPaddCons(scip, cons) );
SCIP_CALL( SCIPreleaseCons(scip, &cons) );

我只想在获得根节点之后和分支开始之前添加切割。现在没有分支（我通过将所有变量更改为连续来禁用它，以便算法在根节点停止）

所以我的问题是：

1）如何在根节点求解后（根节点是通过使用价格器添加列获得的）和分支开始之前添加切割

我可能对术语和语言有点不准确。对此表示歉意。

Answer 1

您的程序并未尝试添加切割，它会检查第 16、20、31 行中的解决方案。第一个是对伪解的检查（没有约束所有变量都设置为它们的最佳边界），第二个是对 lp 解的检查，最后一个是原始 space 中的最终检查。现在回答您的问题：

1) 我认为你的程序没有分离，因为它不需要。您的原始解决方案值立即等于对偶边界（在您完成定价后）。所以真的没有必要分开任何东西。

2) 出现警告是因为 .lp 对允许打印的内容有非常严格的限制。我不知道你的约束会是什么样子。如果它们是线性的，您只需在约束处理程序中创建线性约束，您就可以将它们打印在 .lp 文件中。否则，您可以实施 consPrint 回调并打印为 .cip 文件。

使用定价器在根节点播出后，如何在 SCIP 中使用约束处理程序添加分隔符？

How to add separators using constraint handlers in SCIP after airing at the root node using a pricer?

c++

linear-programming

scip

mixed-integer-programming