[SCIP] lp error when adding locally constraint

Tue May 5 16:12:43 CEST 2020

Hi Yunzhuang,

Am 05.05.20 um 08:55 schrieb Yunzhuang Shen:
> Hi Ambros,
> 
> I see. Achterberg's thesis does helps me know deeper about scip.
> 
> My current task is to introduce some locally valid cuts to split a 
> search space.
> For instance, I need to split the root node into multiple nodes where 
> the union of them is the original search space. And I need to solve the 
> whole subtree rooted at a node once  at a time in a certain order.
> _
> It likes doing local branching. I read the implementation of local 
> branching in the given examples, which is done by copy the problem to 
> subscip and solve it.

Yes, the reason is that we implemented local branching as a primal 
heuristic, not as a branching scheme.

> However in my case, it adds too much additional cost since I need to 
> solve lots of such subscip.
> I am currently implementing my own node selector for doing this but it 
> is complicated.
> Is there a feasible approch for doing local branching within the scip?

There is no available implementation of local branching as branching 
scheme, but the binpacking example contains and implementation of 
Ryan-Foster-Branching, this should show you software-wise how to create 
a branching by adding locally valid constraints:

https://scip.zib.de/doc-7.0.0/html/branch__ryanfoster_8c.php

Best,
Ambros

> 
> Thanks,
> yunzhuang
> _
> ------------------------------------------------------------------------
> *From:* Ambros Gleixner <gleixner at zib.de>
> *Sent:* Wednesday, April 29, 2020 1:01 AM
> *To:* Yunzhuang Shen <s3640365 at student.rmit.edu.au>; scip at zib.de 
> <scip at zib.de>
> *Subject:* Re: [SCIP] lp error when adding locally constraint
> Hi Yunzhuang,
> 
> 
> Am 23.04.20 um 16:36 schrieb Yunzhuang Shen:
>> Hi Ambros,
>> 
>> Thanks for your quick response.
>> 
>> After I compiled SCIP and SOPLEX to under debug mode, I cannot reproduce 
>> the error because the problem did not pass an assertion in the SCIP. The 
>> backtrace is the following: >
>> CO: /home/joey/Downloads/scip-6.0.1/src/scip/tree.c:2403: 
>> SCIPnodeSetEstimate: Assertion `SCIPsetIsRelGE(set, newestimate, 
>> node->lowerbound)' failed.
>> ==15345==
>> ==15345== Process terminating with default action of signal 6 (SIGABRT)
>> ==15345==    at 0x69BAE97: raise (raise.c:51)
>> ==15345==    by 0x69BC800: abort (abort.c:79)
>> ==15345==    by 0x69AC399: __assert_fail_base (assert.c:92)
>> ==15345==    by 0x69AC411: __assert_fail (assert.c:101)
>> ==15345==    by 0x587623D: SCIPnodeSetEstimate (tree.c:2403)
>> ==15345==    by 0x5870E9C: SCIPnodeCreateChild (tree.c:1016)
>> ==15345==    by 0x1984F9: 
>> COML::Branching::split_space_ml_symetric(Scip*, bool) 
>> (branching_policy.cpp:499)
>> ==15345==    by 0x19665B: COML::Branching::scip_execlp(Scip*, 
>> SCIP_Branchrule*, unsigned int, SCIP_Result*) (branching_policy.cpp:233)
>> ==15345==    by 0x199E5F: branchExeclpDynamicBranching 
>> (branching_policy.cpp:804)
>> ==15345==    by 0x54FE318: SCIPbranchruleExecLPSol (branch.c:1589)
>> ==15345==    by 0x5500D06: SCIPbranchExecLP (branch.c:2538)
>> ==15345==    by 0x578FD2C: SCIPbranchLP (scip_branch.c:1183)
>> 
>> I think I did not pass the correct estimate value when I create the 
>> child node.
> 
> Good.  The assert tells you that the estimate you give should be at
> least as large as the lower bound of the current node, on which you
> created the branching.  You can query the lower bound with
> SCIPnodeGetLowerbound.
> 
> 
>> One other thing I need to ask is that the meaning of several 
>> boolean parameters when create a local constraint. Specifically, do I 
>> need to change them to other values when I create locally valid 
>> constraint? (my observation from binpack and tsp example is that some of 
>> the boolean paramters are different comparing to creating the global 
>> constraint). My application senario is as the following: right after the 
>> root node is solved, I create two chlid nodes splited by local 
>> constraints.
> 
> The local flag of SCIPcreateCons (or more specialized ones like
> SCIPcreateConsLinear) must be changed.  The other flags are independent,
> the usual values should be fine.
> 
> 
>> Then I want to put an order on solving those two nodes.
> 
> This could mean many things.  Maybe the parameter
> "nodeselection/childsel" helps you, see also Chapter 6 of Tobias
> Achterberg's thesis
> 
> https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fnbn-resolving.de%2Furn%3Anbn%3Ade%3A0297-zib-11129&data=02%7C01%7C%7Ce6bf1ce4b93a42a0553f08d7eb852096%7Cd1323671cdbe4417b4d4bdb24b51316b%7C0%7C0%7C637236829377421172&sdata=Gfy88YOosDIvTxCBvQMGJWCkkyG6UM668YZqV33Sw0o%3D&reserved=0
> 
> If you want to fully force your own node processing order in SCIP, then
> it might be necessary to implement your own node selector, see
> 
> https://aus01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fscip.zib.de%2Fdoc-7.0.0%2Fhtml%2FNODESEL.php&data=02%7C01%7C%7Ce6bf1ce4b93a42a0553f08d7eb852096%7Cd1323671cdbe4417b4d4bdb24b51316b%7C0%7C0%7C637236829377421172&sdata=PZNO4XzG%2BClVerOD127N2ExoIGbn9L3QY9df%2FZt%2Blus%3D&reserved=0
> 
> Best,
> Ambros
> 
> 
>> 
>> Thank you,
>> yunzhuang
>> ------------------------------------------------------------------------
>> *From:* Scip <scip-bounces at zib.de> on behalf of Ambros Gleixner 
>> <gleixner at zib.de>
>> *Sent:* Thursday, April 23, 2020 11:30 PM
>> *To:* scip at zib.de <scip at zib.de>
>> *Subject:* Re: [SCIP] lp error when adding locally constraint
>> Dear Yunzhuang,
>> 
>> We would need more details in order to help you with this issue.
>> Ideally, you
>> 
>> - compile both SoPlex and SCIP in debug mode and provide us with a
>> backtrace, and
>> 
>> - run your code through valgrind to check whether there is any memory
>> corruption.
>> 
>> I assume you are developing under linux.  It is much easier for us to
>> support debugging on linux than on other operating systems.
>> 
>> Best,
>> Ambros
>> 
>> 
>> 
>> 
>> Am 23.04.20 um 10:51 schrieb Yunzhuang Shen:
>>> Hi there,
>>> 
>>> I am using scip-6.0.1 for my research work. After creating local 
>>> constraints by setting paramter <local> to true and adding them to 
>>> nodes, the SCIP terminates after processing a number of nodes. The error 
>>> is "corrupted size vs. prev_size" and is in inside the soplex solver. My 
>>> workaround is setting the parameter initial to false so that the 
>>> constraint is not added to lp. It works but I don't know whether that 
>>> local constraint is still effective (prune all nodes that is invalid 
>>> under this local constraint by propagation or other checks). I need to 
>>> make sure the local contraint is fully effective over the tree whose 
>>> root is added that local constraint.
>>> 
>>> Thanks,
>>> yunzhuang
>>> 
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de
>>> https://aus01.safelinks.protection.outlook.com/?url=https%3A%2F%2Flistserv.zib.de%2Fmailman%2Flistinfo%2Fscip&data=02%7C01%7C%7Ce6bf1ce4b93a42a0553f08d7eb852096%7Cd1323671cdbe4417b4d4bdb24b51316b%7C0%7C0%7C637236829377421172&sdata=I%2FGbdFyYS1lydZNnLngJCLoyS3FI5uN8eiCXOM%2F%2BdZ0%3D&reserved=0
>>> 
>> 
>> -- 
>> Ambros Gleixner, Research Group Mathematical Optimization Methods at
>> Zuse Institute Berlin, 
>> https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.zib.de%2Fgleixner&data=02%7C01%7C%7Ce6bf1ce4b93a42a0553f08d7eb852096%7Cd1323671cdbe4417b4d4bdb24b51316b%7C0%7C0%7C637236829377431168&sdata=Ukf37Mpd6sm7cjNJdDFbRdtm%2FordHsfYmvn381e1tJk%3D&reserved=0
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> https://aus01.safelinks.protection.outlook.com/?url=https%3A%2F%2Flistserv.zib.de%2Fmailman%2Flistinfo%2Fscip&data=02%7C01%7C%7Ce6bf1ce4b93a42a0553f08d7eb852096%7Cd1323671cdbe4417b4d4bdb24b51316b%7C0%7C0%7C637236829377431168&sdata=r7QVmBjPR0Pu9UVE1u0BdGBAbmXSWqu5ms%2FGxnAdG8U%3D&reserved=0
>> 
> 
> -- 
> Ambros Gleixner, Research Group Mathematical Optimization Methods at
> Zuse Institute Berlin, 
> https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.zib.de%2Fgleixner&data=02%7C01%7C%7Ce6bf1ce4b93a42a0553f08d7eb852096%7Cd1323671cdbe4417b4d4bdb24b51316b%7C0%7C0%7C637236829377431168&sdata=Ukf37Mpd6sm7cjNJdDFbRdtm%2FordHsfYmvn381e1tJk%3D&reserved=0
> 

-- 
Ambros Gleixner, Research Group Mathematical Optimization Methods at 
Zuse Institute Berlin, http://www.zib.de/gleixner