[SCIP] Branch price cut algorithm -> price again after adding cuts
Jakob Witzig
witzig at zib.de
Mon Jan 16 12:19:08 CET 2017
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
More information about the Scip
mailing list