[SCIP] Problems in heuristics

Thu Nov 7 14:58:49 CET 2019

Hi Eddie,

in general, the heuristics within SCIP are not specifically designed for 
branch-and-price, so switching them to aggressive might not be wat you 
want to do in terms of performance. But of course, nothing should break, 
anyway.

Your pricer should not be called within sub-SCIP heuristics. The output 
message that you got can also happen if there are some variables not 
present in the LP that the SCIP internal pricer may price later. Did you 
check whether your pricer is actually called in the sub-SCIP?

The assertion about the lazy bounds is strange and something we should 
definitely look into. Based on the backtrack alone, it is hard to pin 
down, can you perhaps share (parts of) your code that allows to 
reproduce this? If so, please send it to me directly.

Finally, it is right now not possible to alternate between pricing and 
cutting in the way you suggest. I guess the original idea was that you 
would normally like to cut off the optimal LP solution with cuts and not 
some intermediate one (when not finishing pricing first). You might 
experiment with the following, though: check within your pricer if there 
is a cut that you would like to apply; in that case, just return 
SCIP_DIDNOTRUN. SCIP will then not use the LP value as a dual bound and 
should call separation next. If there is no (good enough) cut, you 
probably just want to continue pricing until the master problem is 
solved to optimality.

Best,
Gerald

Am 04.11.19 um 11:00 schrieb Edward Lam:
> Hi all,
>
> I’m doing branch-and-cut-and-price in SCIP 6.0.2 and I’m having 
> problems with the heuristics. I turned on aggressive heuristics:
>
> SCIP_CALL(SCIPsetHeuristics(scip, SCIP_PARAMSETTING_AGGRESSIVE, TRUE));
>
> I’m getting:
>
> WARNING: pricing has been interrupted -- LP of current node is invalid
>
> at this backtrace:
> The warning seems to suggest the proximity heuristic is calling my 
> pricer. I think I don't want that? Nevertheless, the final solution is 
> correct.
>
> I’m also having a problem with the twoopt heuristic, and the final 
> solution is NOT correct. I get this error:
> SCIP Status        : problem is solved [optimal solution found]
> Solving Time (sec) : 14.09
> Solving Nodes      : 162
> Primal Bound       : +1.57000000000000e+03 (7 solutions, 3 respecting 
> the objective limit)
> Dual Bound         : +1.57000000000000e+03
> Gap                : 0.00 %
> violation: integrality condition of variable <> = 0.666666666666667
> best solution is not feasible in original problem
>
> Using SCIPgetBestSol(scip), I have verified that the solution twoopt 
> finds is fractional. The integer optimal solution should be 1572. This 
> problem occurs in the release build. In the debug build, I’m getting 
> an assertion error:
>
> scipoptsuite-6.0.2/scip/src/scip/lp.c:12181: updateLazyBounds: 
> Assertion `lp->divinglazyapplied || SCIPsetIsLT(set, col->ub, 
> col->lazyub) || (col->flushedub == SCIPlpiInfinity(lp->lpi))' failed.
>
> with this backtrace:
>
> #0  0x00002aaaadfb0fd7 in __GI_raise (sig=sig at entry=6) at 
> ../sysdeps/unix/sysv/linux/raise.c:55
> #1  0x00002aaaadfb23aa in __GI_abort () at abort.c:78
> #2  0x00002aaaadfa9dc6 in __assert_fail_base (fmt=0x2aaaae0e8ee0 
> "%s%s%s:%u: %s%sAssertion `%s' failed.\n%n",
>     assertion=assertion at entry=0x2aaaad130530 "lp->divinglazyapplied || 
> SCIPsetIsLT(set, col->ub, col->lazyub) || (col->flushedub == 
> SCIPlpiInfinity(lp->lpi))", file=file at entry=0x2aaaad12ad00 
> "/tmp/scipoptsuite-6.0.2/scip/src/scip/lp.c", line=line at entry=12181,
>     function=function at entry=0x2aaaad133c40 <__PRETTY_FUNCTION__.22154> 
> "updateLazyBounds") at assert.c:92
> #3  0x00002aaaadfa9e72 in __GI___assert_fail (
>     assertion=0x2aaaad130530 "lp->divinglazyapplied || 
> SCIPsetIsLT(set, col->ub, col->lazyub) || (col->flushedub == 
> SCIPlpiInfinity(lp->lpi))",
>     file=0x2aaaad12ad00 "/tmp/scipoptsuite-6.0.2/scip/src/scip/lp.c", 
> line=12181,
>     function=0x2aaaad133c40 <__PRETTY_FUNCTION__.22154> 
> "updateLazyBounds") at assert.c:101
> #4  0x00002aaaab64afe9 in updateLazyBounds (lp=0x96ff10, set=0x743520)
>     at /tmp/scipoptsuite-6.0.2/scip/src/scip/lp.c:12181
> #5  0x00002aaaab64b493 in SCIPlpSolveAndEval (lp=0x96ff10, 
> set=0x743520, messagehdlr=0x73ea20, blkmem=0x7414e0, stat=0x883290,
>     eventqueue=0x87f550, eventfilter=0x812ec0, prob=0x974c80, 
> itlim=-1, limitresolveiters=0, aging=0, keepsol=0, lperror=0x7fffffffbb90)
>     at /tmp/scipoptsuite-6.0.2/scip/src/scip/lp.c:12274
> #6  0x00002aaaab803b05 in SCIPsolveDiveLP (scip=0x73b4e0, itlim=-1, 
> lperror=0x7fffffffbb90, cutoff=0x0)
>     at /tmp/scipoptsuite-6.0.2/scip/src/scip/scip_lp.c:2519
> #7  0x00002aaaab3b8f51 in heurExecTwoopt (scip=0x73b4e0, 
> heur=0x85e5c0, heurtiming=8, nodeinfeasible=0, result=0x7fffffffbd40)
>     at /tmp/scipoptsuite-6.0.2/scip/src/scip/heur_twoopt.c:1709
> #8  0x00002aaaab5fb9b9 in SCIPheurExec (heur=0x85e5c0, set=0x743520, 
> primal=0x9745f0, depth=20, lpstateforkdepth=19, heurtiming=8,
>     nodeinfeasible=0, ndelayedheurs=0x7fffffffbd3c, result=0x7fffffffbd40)
>     at /tmp/scipoptsuite-6.0.2/scip/src/scip/heur.c:1116
> #9  0x00002aaaab8ab63d in SCIPprimalHeuristics (set=0x743520, 
> stat=0x883290, prob=0x974c80, primal=0x9745f0, tree=0x974670, 
> lp=0x96ff10,
>     nextnode=0xe5b1d8, heurtiming=8, nodeinfeasible=0, 
> foundsol=0x7fffffffbe3c, unbounded=0x7fffffffbe44)
>     at /tmp/scipoptsuite-6.0.2/scip/src/scip/solve.c:353
> #10 0x00002aaaab8be320 in SCIPsolveCIP (blkmem=0x7414e0, set=0x743520, 
> messagehdlr=0x73ea20, stat=0x883290, mem=0x73ac90, origprob=0x87f850,
>     transprob=0x974c80, primal=0x9745f0, tree=0x974670, reopt=0x0, 
> lp=0x96ff10, relaxation=0x974820, pricestore=0x880e90, 
> sepastore=0xb1a870,
>     cutpool=0xb1a8f0, delayedcutpool=0xb29150, branchcand=0x7d3210, 
> conflict=0x974840, conflictstore=0x880bb0, eventfilter=0x812ec0,
>     eventqueue=0x87f550, cliquetable=0x974c20, restart=0x7fffffffc0a4)
>     at /tmp/scipoptsuite-6.0.2/scip/src/scip/solve.c:5159
> #11 0x00002aaaab84aeb7 in SCIPsolve (scip=0x73b4e0) at 
> /tmp/scipoptsuite-6.0.2/scip/src/scip/scip_solve.c:2648
>
> Another question while I’m here. As I understand, the pricing loop is 
> inside the cutting loop. Is there a way to run them both in the same 
> loop level, i.e. price, cut, price, cut? Instead of ((price, 
> price, price), cut), ((price, price, price), cut).
>
> Cheers
> Eddie
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20191107/da77edbc/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bt.png
Type: image/png
Size: 26445 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20191107/da77edbc/attachment.png>