[Scip] 'redundant' constraints and variable deletion

[Gerald Gamrath]

Dear James,

I think I have an idea what might have happened. Since you marked the 
linearordering constraints not to be checked (and thus redundant), the 
set2 variables don't get rounding locks from these constraints (an 
explanation of locks can be found in the documentation concerning the 
CONSLOCK callback here: http://scip.zib.de/doc/html/CONS.html). Thus, 
the set2 variables have only uplocks from your set packing constraints 
and if they have a non-negative objective coefficient, dual fixing will 
fix them to 0 in presolving. Depending on how your set packing 
constraints look like, they might be redundant now and only the set1 
variables and your dagcluster constraints remain.
Now, either you did not set the locks in your dagcluster constraints 
correctly and SCIP wrongly fixes also the set1 variables or just the 
set1 variables and the dagcluster constraints are a (nearly) trivial 
problem that can be solved in presolving (e.g. if the variables get only 
uplocks and have a non-negative objective coefficient, or only downlocks 
and non-positive coefficient).

The thing is as you already noticed, that you marked the linearordering 
constraints as redundant. Why did you do this and why do you have the 
constraints at all, if they are not crucial for your problem? The way 
you do it (also with your "hack" mentioned at the end), these 
constraints do not need to be fulfilled for a solution to be declared 
feasible. Is it ok in your model, that a solution does not fulfill these 
and propagating the constraints should increase the probability of 
solutions fulfilling the linear order?

Best,
Gerald

Am 05.07.2012 13:19, schrieb James Cussens:
> I have a problem with two sets of Boolean variables. Set1 encodes a
> directed graph. Set2 encodes a linear order for the nodes of the
> graph.
>
> I have a constraint "cons_dagcluster" which applies exclusively to
> variables in Set1 and which rules out cyclic graphs.
>
> I was experimenting and applied the cons_linearordering constraint
> (from the SCIP examples) to Set2 and also made an approriate (set
> packing) constraint linking Set1 and Set2 variables.
>
> Since I just wanted access to the cons_linearordering propagation, I
> decided to set enforce and check to FALSE on the the
> cons_linearordering constraint. Upon doing this, SCIP presolving
> proceeds to delete all my variables (after 241 rounds), including all
> the Set1 variables (which are constrained by the cons_dagcluster
> constraint).
>
> You could argue that it was "wrong" to declare cons_linearordering as
> effectively redundant, but I can't see how it should lead to all
> variables being deleted.
>
> I have got round the problem by (1) setting  enforce and check to TRUE
> when creating the linearordering constraint (2) adding the following
> lines at the top of the CONSCHECK and CONSENFOLP callbacks in
> cons_linearordering.c
>
>   *result = SCIP_FEASIBLE;
>     return SCIP_OKAY;
>
> This is hardly an elegant solution but on the other hand I'm getting
> great performance!
>
> Does anyone know what's going on here?
>
> James
>