[Scip] Overly motivated presolver?

Moritz Kiese mbk at mytum.de
Tue Sep 23 15:37:26 MEST 2008


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.


More information about the Scip mailing list