I was initially trying to implement a branch and price algorithm and I was mostly successful in implementing it. I implemented a pricer plugin and everything seems to work. But I want to strengthen this model by adding some cuts. Instead of the usual branch-cut-price scheme, I only want to add cuts at the root node (after all the columns are added at the root-node and before branching starts and adds further columns) and not any further cuts once branching starts (at least this is the plan for now).
I implemented a rudimentary constraint handler which at this moment doesn't do much but has some placeholders to check whether the appropriate functions are being called properly or not. I copied most of it from the TSP source code. For brevity's sake I had removed the extensive comments and documentation
The ConshdlrSCO.hpp is as follows
#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
The ConshdlrSCO.cpp file is as follows
#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;
}
I added the pricer and constraint handler one after the other like this
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) );
I only want to add cuts after the root node is obtained and before branching starts. Right now there is no branching (I disabled it by changing all the vars to continuous so that the algorithm stops at root-node)
So my questions are:
1) how to add the cuts only after the root node is solved (root node is obtained by adding columns using a pricer) and before branching starts
I might have been a bit imprecise with the terminology and language. Apologies for that.
Your program is not trying to add cuts, it checks the solution in lines 16,20,31. The first is the check for the pseudo solution (no constraints all variables set to their best bounds), the second for the lp solution and the last is the final check in the original space. Now to your questions:
1) I think your program does not separate because it does not need to. Your primal solution value is immediately equal to the dual bound (after you finished pricing). So there really is no need to separate anything.
2) The warning is there because the .lp has very strict limitations what you are allowed to print. I don't know how your constraints will look. If they are linear, you can just create linear Constraints in your constraint handler and you will be able to print them in a .lp file. Otherwise, you can implement the consPrint callback and print as a .cip file.