[SCIP] Questions about branch-price-cut
Gregor Hendel
hendel at zib.de
Wed Nov 27 15:05:58 CET 2019
Hi Oliver,
sorry for the delayed answer.
Am 20.11.19 um 02:17 schrieb Oliver Zier:
> Hi SCIPers,
> I am implementing branch-price-cut using SCIP and I ran into several
> problems:
> 1. For subproblems, I do not free the problem after solving but only free
> the transformed problem (sing SCIPfreeTransform). After branching I will
> add constraints into subscip to enforce the branching deicison in the
> subproblem using SCIPaddCons as I read from several other threads in the
> mailing list. However, it seems like the new constraint in subproblem is
> not enforced and not active in the subscip. There is no error returned
> from SCIPaddCons but it just didn't do what is expected. What am I missing
> here?
Most likely this is a bug in your implementation. When you create the
constraint to the sub-SCIP, make sure you actually set its "check"
constraint to TRUE. It will be automatically active (as are all original
model constraints).
Then try to figure out when/why it is deactivated using a debugger.
Probably it is presolved away because it is redundant (which it
shouldn't be, of course)?
It also often helps to write out the entire sub-SCIP after adding the
constraints.
>
> 2. For one of the subproblem, I got a solution like this:
> objective value: -2.8
> x_Act_10_Eve_7 1 (obj:0)
> y_Act_10_Eve_8 1 (obj:0)
> x_Act_10_Eve_8 1 (obj:0)
> y_Act_10_Eve_9 1 (obj:0)
> x_Act_10_Eve_9 1 (obj:0)
> y_Act_10_Eve_10 1 (obj:0)
> x_Act_10_Eve_10 1 (obj:0)
> OneCol_10 1 (obj:-2.)
> q_1_Act_10_Eve_7 13.9285714285714 (obj:-0)
> e_Act_10_Eve_7 41.7857142857143 (obj:-0)
> So basically I can increase / decrease q and e to certain extent and get
> another solution with the same objective value. The constraints for q and
> e are: q >= 1, 42 * q >= 4*e and 42 * q <= 14*e so I would say there are
> infinitely many solutions with the same objective but somehow scip only
> returns me this solution (using SCIPgetSols). Is there any criteria that
> SCIP uses internally to choose which solution to return?
The main criterion is optimality. Concretely, if the first solution that
SCIP finds happens to be one with optimal objective value, it does not
necessarily generate any further solutions. It is hard to say who is
responsible for the particular values of q and e in your solution. You
can query if this solution was found by a heuristic or by the LP
relaxation (in which case SCIPsolGetHeur(sol) == NULL).
Finally SCIP offers the functionality to count solutions, but only for
integer, not for mixed integer problems.
>
> 3. I am using reoptimization for subproblems and get here the error:
> scipoptsuite-6.0.2/scip/src/scip/presol_symmetry.c:778:
> computeSymmetryGroup: Assertion `nhandleconss <= nactiveconss' failed.
> The problem seems to be, that in a previous call to SCIPfreeReoptSolve the
> number of active constraint in scip->stat is set to zero but not
> nactiveconss of the constraint handlers. Here is a backtrace:
Sorry about that. This bug has been (hopefully) fixed in the meantime.
At least some related bugs related to Reoptimization have been fixed
recently, and reoptimization has been integrated better into our testing.
As a workaround, does it help in your case to set misc/usesymmetry to FALSE?
Kind regards,
Gregor
>
> #0 0x00007ffff3b2e0d1 in raise () from /lib64/libc.so.6
> #1 0x00007ffff3b1755d in abort () from /lib64/libc.so.6
> #2 0x00007ffff3b17431 in __assert_fail_base.cold () from /lib64/libc.so.6
> #3 0x00007ffff3b26592 in __assert_fail () from /lib64/libc.so.6
> #4 0x00007ffff4ea0000 in computeSymmetryGroup
> at scip/src/scip/presol_symmetry.c:778
> #5 0x00007ffff4ea3c7b in determineSymmetry
> at scip/src/scip/presol_symmetry.c:1502
> #6 0x00007ffff4ea4eac in SCIPgetGeneratorsSymmetry
> at scip/src/scip/presol_symmetry.c:1811
> #7 0x00007ffff4ec410e in getSymmetries
> at /scip/src/scip/prop_orbitalfixing.c:184
> #8 0x00007ffff4ec4d49 in propagateOrbitalFixing
> at /scip/src/scip/prop_orbitalfixing.c:470
> #9 0x00007ffff4ec60e8 in propExecOrbitalfixing
> at scip/src/scip/prop_orbitalfixing.c:821
> #10 0x00007ffff524d5c9 in SCIPpropExec at scip/src/scip/prop.c:674
> #11 0x00007ffff5342554 in propagationRound at scip/src/scip/solve.c:531
> #12 0x00007ffff5342898 in propagateDomains
> at scip/src/scip/solve.c:609
> #13 0x00007ffff534e603 in propAndSolve
> at scip/solve.c:3761
>
> #14 0x00007ffff535004f in solveNode
> at scip/src/scip/solve.c:4190
> #15 0x00007ffff535384d in SCIPsolveCIP
> at scip/src/scip/solve.c:4974
> #16 0x00007ffff52e15bd in SCIPsolve at scip/src/scip/scip_solve.c:2652
> #17 0x000000000074a456 in ObjPricerRCPSP::scip_redcost(Scip*,
> SCIP_Pricer*, double*, unsigned int*, SCIP_Result*) ()
> #18 0x00007ffff53d2df1 in pricerRedcostObj at
> scip/src/objscip/objpricer.cpp:182
> #19 0x00007ffff523d801 in SCIPpricerRedcost at scip/src/scip/pricer.c:410
> #20 0x00007ffff523dbb4 in SCIPpricerExec
> at scip/src/scip/pricer.c:494
> #21 0x00007ffff5347c44 in SCIPpriceLoop
> at scip/src/scip/solve.c:2121
> #22 0x00007ffff5348f0c in priceAndCutLoop at scip/src/scip/solve.c:2382
> #23 0x00007ffff534c049 in solveNodeLP
> at scip/src/scip/solve.c:3086
> #24 0x00007ffff534ef60 in propAndSolve
> at scip/src/scip/solve.c:3890
> #25 0x00007ffff535004f in solveNode
> at scip/src/scip/solve.c:4190
> #26 0x00007ffff535384d in SCIPsolveCIP
> at scip/src/scip/solve.c:4974
> #27 0x00007ffff52e15bd in SCIPsolve at scip/src/scip/scip_solve.c:2652
> #28 0x00000000006f4cdf in RCPSP::solve(int) ()
> #29 0x00000000007aa9e6 in main ()
>
>
> Best,
> Oliver
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
More information about the Scip
mailing list