[Scip] Overly motivated presolver?

Julian Lamberty julian.lamberty at mytum.de
Tue Sep 23 16:18:56 MEST 2008


Hi Tobias!

I'm the student working with Moritz on the reported column-generation 
problem.

Now I found out, that our variables "disappear" from the constraints 
when activating either

presolving/trivial

or

presolving/probing

The other presolvers do obviously not affect the constraints.
I think one of these presolvers tries to use the "empty" constraint to 
set bounds on the variables u and then deletes u from the constraint.

Can we somehow protect these constraints?

Regards,
Julian

Tobias Achterberg schrieb:
> Hi Moritz,
> 
> the constraint creation you are using is correct. In particular, you are setting 
> "modifiable" to TRUE, which is necessary for column generation approaches.
> 
> I don't see the issue right now, so we have to dig a little deeper. The first task for you 
> is to find out which presolver does this reduction. Therefore, I suggest to disable 
> presolving step by step.
> 
> The relevant settings in your case are:
> 
> constraints/linear/maxprerounds = 0
> presolving/dualfix/maxrounds = 0
> presolving/probing/maxrounds = 0
> presolving/implics/maxrounds = 0
> presolving/inttobinary/maxrounds = 0
> presolving/trivial/maxrounds = 0
> 
> Try to set all of them (i.e., to disable all relevant presolving methods) and see whether 
> this helps. It should, and it should be identical to "presolving/maxrounds = 0", at least 
> if all of your constraints are linear.
> 
> If you verified this, enable one of the presolvers after the other (i.e., remove again the 
> setting of the parameter to 0) to see which presolver messes up your model.
> 
> I would start to enable the presolvers in the above order. This is my assumption on how 
> likely it is that this particular presolver could be the reason for the issue.
> 
> 
> After you have identified the bad presolver, verify this by activating everything except 
> the bad one. If we are lucky, the issue disappears by only deactivating a single 
> presolver. Then, come back and report your findings, and I can give you further 
> instructions on what to do to find the cause of the problem.
> 
> 
> Best, Tobias
> 
> Moritz Kiese wrote:
>> Greetings,
>>
>> we are trying to implement a Column-Generation Algorithm within a
>> branch-and-bound tree.
>> In our problem we have constraints of a structure like
>>    0 <= u_e - f_1 - f_2 - ... <= infinity
>>
>> where the u_e represents the used capacity on an edge in a graph and
>> f_i are the path-flow variables (SCIP_VARTYPE_CONTINUOUS) of paths
>> using that edge.
>>
>> These u_e are coupled with binary variables in the form of
>>    0 <= l_e * maxdemand - u_e <= infinity
>> e.g. when we want to use link e, l_e has to be 1.
>>
>> We only want to generate continuous variable, e.g. all integer
>> variables are included in our problem from the very beginning.
>>
>> What can happen now, when we start the problem with just a few paths (more
>> paths can be added via pricing), that some of these edges are not used
>> at all e.g. the constraints have the form
>>    0 <= u_e <= infinity
>> . The constraints are created via
>> 		SCIP_CALL(SCIPcreateConsLinear(scip, &new_c_e[pE], tmpr.c_str(), 0, NULL, NULL, 0, SCIPinfinity(scip), TRUE, FALSE, TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE ));
>> 		SCIP_CALL(SCIPaddCons(scip, new_c_e[pE]));
>>
>> Now the funny part: In our pricer we see those 'empty' constraints as
>>     0 <= u_e <= SCIPinfinity
>> in the scip_init method of our derived class, however when
>> scip_redcost is called in the root node, these constraints look like
>>     0 <= 0
>> which makes adding new paths quite useless, because that will look
>> like
>>     0 <= -f_1 -f_2 <= 0
>> Turning off the presolver via 
>>     SCIP_CALL( SCIPsetIntParam( scip, "presolving/maxrounds", 0 ) );
>> helps, but of course slows the whole thing down a bit.
>>
>> Are we missing something? Any hints & suggestions highly
>> appreciated, TIA,
>>         Moritz.
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/x-pkcs7-signature
Size: 5909 bytes
Desc: S/MIME Cryptographic Signature
Url : http://listserv.zib.de/mailman/private/scip/attachments/20080923/96ae3ad9/smime.bin


More information about the Scip mailing list