[SCIP] Branch price cut algorithm -> price again after adding cuts
Schrotenboer, A.H.
a.h.schrotenboer at rug.nl
Mon Jan 23 16:26:47 CET 2017
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> 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> 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/20170123/2a6e8d87/attachment.html>
More information about the Scip
mailing list