Как добавить разделители с помощью обработчиков ограничений в SCIP после выхода в эфир на узле root по цене? - PullRequest
Новая
       82

Как добавить разделители с помощью обработчиков ограничений в SCIP после выхода в эфир на узле root по цене?

0 голосов
/ 28 февраля 2020

Первоначально я пытался реализовать алгоритм ветвления и цены, и я в основном преуспел в его реализации. Я реализовал плагин ценовой политики, и все, кажется, работает. Но я хочу усилить эту модель, добавив несколько сокращений. Вместо обычной схемы цены перехода по веткам я хочу добавить только сокращения в узле root (после добавления всех столбцов в узле root и до начала ветвления и добавления дополнительных столбцов), а не дальше обрезается, как только начинается ветвление (по крайней мере, это план на данный момент).

Я реализовал элементарный обработчик ограничений, который в данный момент мало что делает, но имеет некоторые заполнители для проверки правильности вызова соответствующих функций. или нет. Я скопировал большую часть из исходного кода 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) );

Я хочу добавлять срезы только после получения узла root и до начала ветвления. Прямо сейчас нет ветвления (я отключил его, изменив все переменные на непрерывные, чтобы алгоритм останавливался на root -узле)

Итак, мои вопросы:

1) как добавлять срезы только после того, как узел root будет решен (узел root получен путем добавления столбцов с использованием оценщика) и перед началом ветвления

Я мог бы быть немного неточным с терминологией и языком. Извиняюсь за это.

1 Ответ

1 голос
/ 28 февраля 2020

Ваша программа не пытается добавлять срезы, она проверяет решение в строках 16,20,31. Первая - это проверка псевдо-решения (без ограничений для всех переменных, устанавливающих свои лучшие границы), вторая - для решения lp, а последняя - последняя проверка в исходном пространстве. Теперь к вашим вопросам:

1) Я думаю, что ваша программа не разделяется, потому что это не нужно. Ваше первичное значение решения сразу равно двойной границе (после того, как вы закончили ценообразование). Так что на самом деле не нужно ничего отделять.

2) Предупреждение здесь, потому что .lp имеет очень строгие ограничения на то, что вам разрешено печатать. Я не знаю, как будут выглядеть ваши ограничения. Если они являются линейными, вы можете просто создать линейные ограничения в обработчике ограничений, и вы сможете распечатать их в файле .lp. В противном случае вы можете реализовать обратный вызов consPrint и распечатать его как файл .cip.

...