[Scip] Tentative branching not working

[Tobias Achterberg]

Hi Nikolaj,

First of all, you need to pass SCIPgetLocalTransEstimate(scip) (or any reasonable estimate
in terms of the *transformed* problem) to SCIPcreateChild(). This is also wrong in the
coloring example, and it could be documented better in the SCIPcreateChild() call.

SCIP Team: Please fix this!


Your code is correct. If I understand correctly, the issue you are seeing is that in the
LP relaxation of the child node, your constraint is not (yet) present.

I think the problem is that you set
(a) initial == FALSE in your SCIPcreateConsLinear() call, and
(b) the separation frequency of the linear constraint handler to 0, which is the default
value.

Both using initial == TRUE and constraints/linear/sepafreq = 1 should fix your problem.
Most probably, initial == TRUE is what you want.


Best,

Tobias


nikolaj at crt.umontreal.ca wrote:
> Hi all,
> 
> I'm using SCIP to branch and cut. In the B&C process, I use my own defined
> branching rule (scip::ObjBranchrule). What I would like to do is pretty
> simple but I can't get it done right in SCIP.
> 
> My branching strategy is to define two children, each with a new local
> constraint on several variables. I read in this mailing list that this
> could be done by defining the two constaints and adding them locally to
> the children.
> 
> Here is a snipet of my code of the method scip_execlp of my branching rule :
> 
> ------------------------------------------------------------------------------
> SCIP_RETCODE MyOwnLittleBranchingRule::scip_execlp
> (
>  	    SCIP *   	 scip,
> 		SCIP_BRANCHRULE *  	branchrule,
> 		SCIP_Bool  	allowaddcons,
> 		SCIP_RESULT *  	result
> )
> {
> //added constraints
> SCIP_CONS * cons1;
> SCIP_CONS * cons2;
> 
> //the two nodes in the B&B tree which are created
> SCIP_NODE * child1;
> SCIP_NODE * child2;
> 
> //find best candidate to branch on (basically, an edge of a graph).
> [code omitted]
> 
> //create child 1 : serve edge from i to j
> SCIP_CALL_EXC(SCIPcreateChild(scip,&child1,0.0,SCIPgetLocalOrigEstimate(scip)));
> //create child 2 : serve edge from j to i
> //SCIP_CALL_EXC(SCIPcreateChild(scip,&child2,0.0,SCIPgetLocalOrigEstimate(scip)));
> 
> SCIP_CALL_EXC(SCIPcreateConsLinear(scip, & cons1, "name_cons1", 0, NULL,
> NULL, 1.0, 1.0,
> FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE));
> 
> //construct the linear constraint
> //loop on S,i,k, model_->y_[S][i][k] is a pointer on the right variable
> [code omitted]
> SCIP_CALL_EXC(SCIPaddCoefLinear(scip,cons1,model_->y_[S][i][k],1.0));
> 
> //add constraint to node
> SCIP_CALL_EXC(SCIPaddConsNode(scip,child1,cons1,NULL));
> 
> //release constraint
> SCIP_CALL_EXC(SCIPreleaseCons(scip,&cons1));
> 
> //the same is done for child2 with another similar linear constraint
> [code omitted]
> 
> *result = SCIP_BRANCHED;
> 
> return SCIP_OKAY;
> }
> ------------------------------------------------------------------------------
> 
> SCIP doesn't seem to take into account the added constraint.
> For example, in the optimal solution of the linear relaxation of the LP at
> a node with the linear constraint added, the flow is not 1 as expected
> (i.e., the added constraint is violated).
> 
> The constraint added fixes the flow on an edge of a graph and is to be
> kept in the search while in the subtree rooted at the nood where the cut
> was added.
> 
> Any idea on what is going wrong ?
> 
> Best regards,
> Nikolaj
> 
> 
> 
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip