[Scip] 'redundant' constraints and variable deletion

James Cussens james.cussens at york.ac.uk
Fri Jul 6 12:13:30 MEST 2012


Dear Gerald,

Thanks for your help. I'm sure you're right that the  set2 variables
are all getting set to 0. (I haven't actually checked this.) Once this
is done it is indeed the case that the set packing constraints linking
them to the set1 variables are redundant, and I assume SCIP is smart
enough to notice this, removes these constraints, and so we end up
only with set1 variables.

However, I'm sure the locks in the dagcluster constraint are set
right: all variables only get an uplock. This is correct since setting
any of them to zero corresponds to removing edges and will never lead
to infeasibility, setting all to zero corresponds to an empty graph
which certainly has no cycles. All variables in the dagcluster
constraint have positive objective coefficient. Now, I'm *maximising*,
so setting all these set1 variables to zero although leading to a
feasible solution is certainly not optimal (actually the worst
possible feasible solution!)

The more important issue for me is how to get the behaviour I'm
looking for without resorting to nasty hacks. The set1 variables
encode a directed graph - each one specifies a non-empty set of
parents for a vertex. The set2 variables encodes a linear ordering.
The dagcluster constraint on the set1 variables ensure that  only
acyclic graphs are feasible. Clearly for any acyclic graph there is
some linear ordering consistent with that graph (parents come earlier
than children), but if either the enforcing or checking callback of
cons_dagcluster tells me I have an acyclic graph it will typically not
be the case that the set2 variables encode a linear ordering
consistent with that acyclic graph (since not all triangle
inequalities have yet been added) and I don't want to make the effort
to find such a consistent linear ordering.

So why bother with the set2 variables? To answer your first question
they are not crucial for my problem which can be solved with just the
set1 variables. The answer to your second question is yes. Basically
I'm using the set2 variable as 'auxiliary' variables to help me do
propagation on the set1 variables. If a set1 variable such as
I(2<-{3,4}))  - which means that 2 has 3 and 4 (and no others) as
parents - is *set* to 1 by branching or as the result of earlier
propagation I want the order variables I(3<2) and I(4<2) to also be
set to 1, thus setting I(2<3) and I(2<4) to 0 which forces e.g.
I(4-{2}) to zero. I also want the propagation on set2 variables
resulting from transitivity.

So I'm using the nice cons_linearordering propagation callback
(together with the simple set packing propagator) to do the hard work
of propagating for me. (My constraint handler currently has no
propagation). Doing this via my hack does improve performance
considerably.

James

On 5 July 2012 13:00, Gerald Gamrath <gamrath at zib.de> wrote:
> 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
>>
>
>



-- 
James Cussens
Dept of Computer Science &
York Centre for Complex Systems Analysis
Room 326, The Hub, Deramore Lane            Tel    +44 (0)1904 325371
University of York                                        Fax  +44
(0)1904 500159
York YO10 5GE, UK                               http://www.cs.york.ac.uk/~jc


More information about the Scip mailing list