scip - 为什么 scip 在调用 SCIPincludeBranchRrule 后做出额外的分支决定？

问题描述

现在我想在分支上做一些事情，并使用 SCIP 进行绑定，并从分支规则开始。当我跟踪分支过程时，我发现了一些我无法理解的东西。从使用获取分支变量候选者开始SCIPgetLPBranchCands，我得到SCIP_VAR** lpcands，然后我选择第一个变量以使用进行分支SCIPbranchVar。此分支规则适用于每个焦点节点。

考虑1号节点（根节点）的分支决策，执行SCIPbranchVar函数后，SCIPgetChildren返回两个子节点（2和3），但是根节点的子节点号改变了，出现了两个或多个子节点。假设节点选择器选择了编号为 2 的节点进行分支，SCIPgetSiblings返回 3 个兄弟节点（3、4 和 5）。

为了弄清楚发生了什么，我使用打印分支决策路径SCIPprintNodeRootPath，并打印节点之间的关系。结果表明，在我在所选变量上的一个节点处分支后，SCIIP 在另一个我不知道的变量上的同一节点处分支。

我已经打印了scipoptsuite-7.0.1/scip/examples/Binpacking生成的这些信息，不再做出分支决定。但是在我使用第一个变量上的分支替换ryanfoster规则后，出现了更多的子节点。之后，我尝试为我的程序创建子节点分支样式，但还是出现了额外的节点。

我不知道发生了什么以及如何完全控制分支过程，这对我以后的工作非常重要，因为它决定了如何设计分支规则。我什至尝试阅读 SCIP 的源代码，不幸的是，它对我来说太难阅读了。

我的程序如下：

主文件

/* 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;
}

分支规则.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

分支规则.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：&quot; << 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：&quot; << std::endl;
    for(int i = 0; i < nsiblings; ++i){
        f1 << setw(20) << "node number：&quot; << 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, &current_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, &current_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;
}

有谁可以帮我解决这个问题？

标签： scip

scip - 为什么 scip 在调用 SCIPincludeBranchRrule 后做出额外的分支决定？

问题描述

解决方案

推荐阅读