[SCIP] Branch price cut algorithm -> price again after adding cuts
Jakob Witzig
witzig at zib.de
Mon Jan 23 16:48:09 CET 2017
Hi Albert,
can you try to set enforce = true?
Cheers,
Jakob
Am 23.01.2017 um 16:26 schrieb Schrotenboer, A.H.:
> Dear Jakob (and others),
>
> The Node root now works exactly as I supposed it should be. It enters
> nicely in a loop of pricing cutting pricing cutting... until no new cuts
> can be found etc. But if i add the cuts *not* at the root node, i *never
> ever* see the pricing problem being repeated, although I add cuts that
> make the current LP solution infeasible (so it is not very likely that
> dual values are unchanged). I add them in the following way:
>
>
> SCIP_CALL(SCIPcreateConsLinear(scip_, &cons, "separated", nvars, vars,
> value, 2, SCIPinfinity(scip_),
> true, /* initial */
> true, /* separate */
> false, /* enforce */
> false, /* check */
> true, /* propagate */
> true, /* local */
> true, /* modifiable */
> true, /* dynamic */
> false, /* removable */
> false /* stickingatnode */
> )
> );
>
> After analyzing a run of my algorithm, it appears that those cuts
> (although violating the LP solution) are never added when I make them
> NOT at the root node..?!? How is that possible? I must be missing
> something :)
>
>
> Thanks in advance,
>
> Albert
>
>
>
> On Mon, Jan 16, 2017 at 12:59 PM, Schrotenboer, A.H.
> <a.h.schrotenboer at rug.nl <mailto:a.h.schrotenboer at rug.nl>> wrote:
>
> 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
> <mailto: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>
> <mailto: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> <mailto:Scip at zib.de
> <mailto:Scip at zib.de>>
> http://listserv.zib.de/mailman/listinfo/scip
> <http://listserv.zib.de/mailman/listinfo/scip>
> <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>
> <mailto: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 <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