[SCIP] propagation with set partitioning constraints

[James Cussens]

Hi Marc,

Thanks for this. It makes sense that this propagation does not happen automatically. Presolving does not help me since my actual set partitioning constraints are modifiable and most of their variables are added in by pricing.

I was able to get the propagations I wanted by adding in some (non-initial, non-separating) "redundant" set partitioning constraints, which works fine.

James

James Cussens
Dept of Computer Science, University of Bristol
https://jcussens.github.io/
Funded PhDs available in Bristol in the following areas: Data Science<http://www.bristol.ac.uk/cdt/compass/>, Interactive AI<http://www.bristol.ac.uk/cdt/interactive-ai/>, Cyber Security<http://www.bristol.ac.uk/cdt/cyber-security/> or Digital Health<http://www.bristol.ac.uk/cdt/digital-health/>.
________________________________
From: Scip <scip-bounces at zib.de> on behalf of Marc Pfetsch <pfetsch at mathematik.tu-darmstadt.de>
Sent: 28 January 2021 19:03
To: scip at zib.de <scip at zib.de>
Subject: Re: [SCIP] propagation with set partitioning constraints



Hi James!

> Suppose I have two set partitioning constraints:
>
> a + b + c + d = 1
> a + b + e = 1
>
> Suppose I were to branch on "e" and let's consider the branch where e=0
> So locally we have a+b=1 and so both c and d can be set to 0 (even
> though we don't know yet which of a or b will be 1).
>
> Does this propagation happen in SCIP?

I am pretty sure that this will not happen in propagation, because to
test this, would be quite expensive in general. This would be something
that would need to be prepared (or only performed) in preprocessing.

> From my reading of the source code
> (and Achterberg's thesis) it seems that not. But perhaps I have missed
> something.

I have looked at the code and have not found a technique like this, not
even in presolving.

Note, however, that if the constraints would be

a + b + c = 1
a + b + e = 1

as far as I can see, SCIP would replace a + b by a new variable binary
variable in preprocessing and then fixing e would also fix c. Thus, your
idea would be possible to implement using this replacement.

Best

Marc
_______________________________________________
Scip mailing list
Scip at zib.de
https://listserv.zib.de/mailman/listinfo/scip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20210129/9f3026e3/attachment.html>