[SCIP] Branch price cut algorithm -> price again after adding cuts
Schrotenboer, A.H.
a.h.schrotenboer at rug.nl
Mon Jan 16 12:59:45 CET 2017
Dear Jakob,
Using the separator works completely fine! Thank you for your help. I think
i might have had a bug in my code that causes that it not enters the
pricing round again.
Cheers,
Albert
On Mon, Jan 16, 2017 at 12:19 PM, Jakob Witzig <witzig at zib.de> wrote:
> Hi Albert,
>
> using constraints is absolutely fine, I just wanted to point out that
> there are differences between constraints and cuts in SCIP.
>
> It is hard to say what caused the segfault without looking at the code.
> You can try to compile SCIP in debug mode (make OPT=dbg LPS=cpx) to enable
> all asserts and to check if your code works correctly.
>
> W.r.t. your pricing: Are you sure that SCIP does not call your pricer
> after adding the constraints? Maybe your price doesn't find a new variable
> to price in?! (Which would be a bug in your code).
>
> Cheers,
> Jakob
>
>
>
> Am 16.01.2017 um 10:54 schrieb Schrotenboer, A.H.:
>
>> Dear Jakob,
>>
>> Thank you for your quick response.
>>
>> First on the LP error messages: I made a small mistake in the
>> formulation of the added constraints, so this is solved. It however does
>> not solve the strange behaviour of not entering a pricing round again
>> after adding constraints/cuts.
>>
>> On the constraints adding: Actually I use the constraint handler to
>> handle constraints belonging to branching decisions. So i actually
>> 'misuse' the sepalp call to add additional valid inequalities to the
>> problem. I set the initial flag to true as you mentioned, so that could
>> not cause the strange behaviour.
>>
>> I implemented it now by adding rows instead of constraints, and added
>> them by SCIP_CALL( SCIPaddCut(scip_, NULL, row, FALSE, &infeasible) );
>> This gives me a segfault:
>>
>> ==25272== Process terminating with default action of signal 11 (SIGSEGV)
>> ==25272== Access not within mapped region at address 0x40
>> ==25272== at 0x4F6760: SCIPconshdlrIncNAppliedCuts (in
>> /home/p267375/Github/bpc/SCIP_project/bin/vrp.linux.x86_64.gnu.opt.cpx)
>> ==25272== by 0x5ED1E0: sepastoreApplyCut (in
>> /home/p267375/Github/bpc/SCIP_project/bin/vrp.linux.x86_64.gnu.opt.cpx)
>> ==25272== by 0x5EE751: SCIPsepastoreApplyCuts (in
>> /home/p267375/Github/bpc/SCIP_project/bin/vrp.linux.x86_64.gnu.opt.cpx)
>> ==25272== by 0x60C283: priceAndCutLoop.isra.14 (in
>> /home/p267375/Github/bpc/SCIP_project/bin/vrp.linux.x86_64.gnu.opt.cpx)
>> ==25272== by 0x60ED50: propAndSolve.isra.16 (in
>> /home/p267375/Github/bpc/SCIP_project/bin/vrp.linux.x86_64.gnu.opt.cpx)
>> ==25272== by 0x60F9F9: SCIPsolveCIP (in
>> /home/p267375/Github/bpc/SCIP_project/bin/vrp.linux.x86_64.gnu.opt.cpx)
>> ==25272== by 0x5E2DE2: SCIPsolve (in
>> /home/p267375/Github/bpc/SCIP_project/bin/vrp.linux.x86_64.gnu.opt.cpx)
>>
>>
>> So I thought it is better to create an Sepa Class and implement the
>> execlp method to do the same thing. I add them as constraints and this
>> seems to work :))
>> I by the way intended to use constraints instead of cuts since I need
>> the dual values of the added inequalities for my pricing process.
>>
>> Cheers,
>>
>> Albert
>>
>>
>>
>>
>>
>>
>>
>>
>> On Mon, Jan 16, 2017 at 9:09 AM, Jakob Witzig <witzig at zib.de
>> <mailto:witzig at zib.de>> wrote:
>>
>> Hi Albert,
>>
>> when you implement the SCIP_DECL_CONSSEPA callback for your
>> branch-price-and-cut approach you could think about adding a cut
>> (SCIP_ROW) instead of a constraint (SCIP_CONS). Within SCIP there is
>> are slight differences between both types, e.g., a constraint can be
>> propagated and a cut not. When you decide to add cuts instead of
>> constraints, the result pointer needs to be set to SCIP_SEPARATED.
>>
>> Moreover, you should make sure that your constraints (in your
>> current implementation) enter the LP, i.e., set initial flag to TRUE.
>>
>> The warnings are printed by SCIP (see lp.c) and just say that your
>> LP is numerically unstable and the LP solver struggles with solving
>> them. You should have a look at your formulation and the
>> constraints/cuts you generate.
>>
>> Cheers,
>> Jakob
>>
>>
>> Am 14.01.2017 um 22:06 schrieb Schrotenboer, A.H.:
>>
>> Hello all,
>>
>> I'm using the c++ wrapper classes of scip to implement a branch
>> & price
>> & cut algorithm. So in each node of the branch and bound tree i do
>> column generation. After that is finished, i want to add cuts
>> (valid
>> inequalities actually). I did that by implementing the function
>> of my
>> constraint handler:
>> SCIP_DECL_CONSSEPALP(ObjConshdlrMSPRP::scip_sepalp),
>> where ObjConshdlrMSPRP denotes my own Constraint Handler class.
>>
>> After it has added constraints to the LP via multiple calls of
>> SCIP_CALL(SCIPaddCons(scip_, cons)), where 'cons' is a simple
>> linear
>> constraint, it sets ' *result = SCIP_CONSADDED'.
>>
>> After the cuts are added, it should redo the column generation
>> process,
>> since there are possibly new columns of negative reduced costs
>> that
>> should enter the LP relaxation. This however does not happen. I
>> get the
>> following strange calls of (i think cplex)
>>
>> (node 2) numerical troubles in LP 21 -- solve again with dual
>> simplex
>> without scaling
>> (node 2) numerical troubles in LP 22 -- solve again with dual
>> simplex
>> without presolving
>> (node 2) numerical troubles in LP 23 -- solve again with dual
>> simplex
>> with tighter primal and dual feasibility tolerance
>> (node 2) numerical troubles in LP 24 -- solve again from scratch
>> with
>> dual simplex
>>
>> Does someone know why this happens and/or why my pricing problem
>> is not
>> entered again at the same node?
>>
>> Thanks in advance,
>>
>> Albert Schrotenboer
>>
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de <mailto:Scip at zib.de>
>> http://listserv.zib.de/mailman/listinfo/scip
>> <http://listserv.zib.de/mailman/listinfo/scip>
>>
>>
>>
>> --
>> Jakob Witzig
>>
>> Zuse Institute Berlin (ZIB)
>>
>> Division Mathematical Optimization and Scientific Information
>> Research Group Mathematical Optimization Methods
>>
>> Takustrasse 7
>> 14195 Berlin
>>
>> Tel. : +49 (0)30 84185-416
>> Fax : +49 (0)30 84185-269
>> email: witzig at zib.de <mailto:witzig at zib.de>
>>
>>
>>
>
> --
> Jakob Witzig
>
> Zuse Institute Berlin (ZIB)
>
> Division Mathematical Optimization and Scientific Information
> Research Group Mathematical Optimization Methods
>
> Takustrasse 7
> 14195 Berlin
>
> Tel. : +49 (0)30 84185-416
> Fax : +49 (0)30 84185-269
> email: witzig at zib.de
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20170116/6c045c0b/attachment.html>
More information about the Scip
mailing list