Now I want to do something on the branch and bound using SCIP, and begin from the branching rule. While I tracking the branching process I found something I cannot understand. Begining from getting the branching variable candidates using SCIPgetLPBranchCands, I get the SCIP_VAR** lpcands, then I select the first variable to branch using SCIPbranchVar. This branching rule works on each focused node.
Consider the branch decision at the number 1 node (the root node), after executing SCIPbranchVar function, SCIPgetChildren return two child nodes (2 and 3), but the child node number of root node changed, two or more child node appeared. Suppose node selector selected the node of number 2 to branch, SCIPgetSiblings return 3 siblings (3, 4, and 5).
To make it clear that what happened, I print the branching decision path using SCIPprintNodeRootPath, and print the relationship between nodes. The result shows that after I branching at a node on the selected variable, the SCIIP branching at the same node on another variable which I don't know.
I have print these information generated by scipoptsuite-7.0.1/scip/examples/Binpacking, no more branching decision is made. But more child nodes appearing after I replace the ryanfoster rule using the branching on the first variable. After that, I try the create child node branching style for my procedure, extra nodes appeared anyway.
I cannot find out what happened and how to totally control the branching process, it is very important for my work in the future for it determined how to design the branching rule. I have even try to read the source code of SCIP, unfortunately, it's too hard for me to read.
My procedure as follows:
main.cpp
/* standard library includes */
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
/* scip includes */
#include "objscip/objscip.h"
#include "objscip/objscipdefplugins.h"
/*user file includes*/
#include "branch_rule.h"
/* namespace usage */
using namespace std;
using namespace scip;
static
SCIP_RETCODE execmain()
{
SCIP* scip = NULL;
/* initialize SCIP environment */
SCIP_CALL( SCIPcreate(&scip) );
SCIP_CALL( SCIPincludeBranchRrule(scip) );
/* include default plugins */
SCIP_CALL( SCIPincludeDefaultPlugins(scip) );
SCIP_CALL( SCIPsetIntParam(scip,"presolving/maxrestarts",0) );
SCIP_CALL( SCIPsetSeparating(scip, SCIP_PARAMSETTING_OFF, TRUE) );
SCIP_CALL(SCIPreadProb(scip, "map18.mps.gz", NULL));
SCIP_CALL( SCIPsolve(scip) );
return SCIP_OKAY;
}
int main(int argc, char** argv)
{
return execmain() != SCIP_OKAY ? 1 : 0;
}
branch_rule.h
#ifndef VRP_BRANCH_RULE_H
#define VRP_BRANCH_RULE_H
#include "scip/scip.h"
#include <vector>
SCIP_RETCODE SCIPincludeBranchRrule(
SCIP* scip
);
#endif //VRP_BRANCH_RULE_H
branch_rule.cpp
#include "branch_rule.h"
#include <assert.h>
#include <string.h>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <fstream>
#include "scip/struct_tree.h"
#include "scip/type_var.h"
using namespace std;
/**@name Branching rule properties
*
* @{
*/
#define BRANCHRULE_NAME "branch rule test"
#define BRANCHRULE_DESC "branch rule test"
#define BRANCHRULE_PRIORITY 50000
#define BRANCHRULE_MAXDEPTH -1
#define BRANCHRULE_MAXBOUNDDIST 1.0
void printBranchTreeNode(SCIP_NODE *node, SCIP_NODE **siblings, int nsiblings){
ofstream f1("branch_path/node_information.txt", ios::app);
if(!f1)return;
f1 << "node number：" << node->number << ", sibling number: " << nsiblings;
if(NULL==node->parent)
f1 << std::endl;
else{
f1 << ", parent number: " << node->parent->number << std::endl;
}
f1 << setw(20) << "siblings：" << std::endl;
for(int i = 0; i < nsiblings; ++i){
f1 << setw(20) << "node number：" << siblings[i]->number << ", sibling number: " << nsiblings << ", parent number: " << siblings[i]->parent->number << endl;
}
f1.close();
}
static
SCIP_DECL_BRANCHEXECLP(branchExeclpTest)
{
assert(scip != NULL);
assert(branchrule != NULL);
assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
assert(result != NULL);
SCIP_NODE *current_node = SCIPgetCurrentNode(scip) ;
SCIP_NODE **leaves = NULL;
int nleaves;
SCIP_CALL( SCIPgetLeaves (scip, &leaves, &nleaves) );
std::vector<SCIP_NODE*> leaves_vector;
for(int i =0; i < nleaves; ++i){
leaves_vector.push_back(leaves[i]);
}
SCIP_NODE **current_node_slibings = NULL;
int ncurrent_node_slibings;
SCIP_CALL( SCIPgetSiblings(scip, ¤t_node_slibings, &ncurrent_node_slibings) );
std::vector<SCIP_NODE*> slibings_vector;
for(int i =0; i < ncurrent_node_slibings; ++i){
slibings_vector.push_back(current_node_slibings[i]);
}
printBranchTreeNode(current_node, current_node_slibings, ncurrent_node_slibings);
SCIP_NODE **childrens;
int nchildrens;
SCIP_CALL( SCIPgetChildren(scip, &childrens, &nchildrens) );
std::vector<SCIP_NODE*> childrens_vector;
for(int i =0; i < nchildrens; ++i){
childrens_vector.push_back(childrens[i]);
}
stringstream filename;
filename.str("");
filename << "branch_path/branch_path_to_node_" << current_node->number <<".dat";
std::string stringFileName = filename.str();
FILE *fp = fopen(stringFileName.c_str(), "wt+");
SCIP_CALL( SCIPprintNodeRootPath(scip, current_node, fp) );
fclose(fp);
// create child node branching style
SCIP_NODE *childsame;
SCIP_NODE *childdiffer;
SCIP_CALL( SCIPcreateChild(scip, &childsame, 0.0, SCIPgetLocalTransEstimate(scip)) );
SCIP_CALL( SCIPcreateChild(scip, &childdiffer, 0.0, SCIPgetLocalTransEstimate(scip)) );
/*
// SCIPbranchVar branching style
SCIP_VAR** lpcands;
SCIP_Real* lpcandssol;
SCIP_Real* lpcandsfrac;
int nlpcands;
int npriolpcands;
int nfracimplvars;
SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, &npriolpcands, &nfracimplvars) );
SCIP_NODE* downchild;
SCIP_NODE* eqchild;
SCIP_NODE* upchild;
SCIP_CALL( SCIPbranchVar(scip, lpcands[0], &downchild, &eqchild, &upchild) );
// SCIP_CALL( SCIPbranchVar(scip, var, NULL, NULL, NULL) );
SCIP_CALL( SCIPgetLeaves (scip, &leaves, &nleaves) );
int numLeaves = SCIPgetNLeaves(scip);
SCIP_CALL( SCIPgetSiblings(scip, ¤t_node_slibings, &ncurrent_node_slibings) );
slibings_vector.clear();
for(int i =0; i < ncurrent_node_slibings; ++i){
slibings_vector.push_back(current_node_slibings[i]);
}
SCIP_CALL( SCIPgetChildren(scip, &childrens, &nchildrens) );
childrens_vector.clear();
for(int i =0; i < nchildrens; ++i){
childrens_vector.push_back(childrens[i]);
}
*/
return SCIP_OKAY;
}
SCIP_RETCODE SCIPincludeBranchRrule(
SCIP* scip /**< SCIP data structure */
){
SCIP_BRANCHRULEDATA* branchruledata;
SCIP_BRANCHRULE* branchrule;
branchruledata = NULL;
branchrule = NULL;
// include branching rule
SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY, BRANCHRULE_MAXDEPTH,
BRANCHRULE_MAXBOUNDDIST, branchruledata) );
assert(branchrule != NULL);
SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpTest) );
return SCIP_OKAY;
}
Does anyone can help me to solve this problem?
so the first thing I notice when looking at your code is that you do not set the result pointer. After branching, you need to set *result = SCIP_BRANCHED;.
Can you please try that and check if it fixes your problem?