Support cardinality clauses within more complex logic

[dovallev]

It would be useful to support expressions of the type:

$$ [AtLeast(1,Y_i) \wedge AtLeast(1,Z_j)] \Leftrightarrow W $$

Where Y and Z are Boolean variables associated to unrelated disjuncts. This is expression would be currently supported in Pyomo.GDP as:

@m.LogicalConstraint()
def foo(m):
return equivalent(land(atleast(1, m.Y[:].indicator_var), atleast(1, m.Z[:].indicator_var)), m.W)

[hdavid16]

@dovallev does this mean that

• you have a disjunction for Y's and another for Z's, and there is no cardinality (eg, Exactly(1)) constraint imposed on either of these?
• You are not going to enforce your AtLeast constraints, but rather, if it so happens that AtLeast 1 disjunct is selected in both disjunctions, make W true?

[pulsipher]

@hdavid16 here is a simple illustrative use case:

$$\begin{gathered} \left[\begin{gathered} Y_i(\xi)\\\ x_i(\xi) \leq 0 \end{gathered}\right] \vee \left[\begin{gathered} \neg Y_i(\xi)\\\ x_i(\xi) \geq 0 \end{gathered}\right], \ \ i \in I, \xi \in D_\xi \\ \left[\begin{gathered} Z_j(\xi)\\\ q_j(\xi) \leq 0 \end{gathered}\right] \vee \left[\begin{gathered} \neg Z_j(\xi)\\\ q_j(\xi) \geq 0 \end{gathered}\right], \ \ j \in J, \xi \in D_\xi \\ \text{atleast}(2, Y(\xi)) \wedge \text{atleast}(1, Z(\xi)) \iff W(\xi), \ \xi \in D_\xi\\\ \mathbb{E}_\xi[W(\xi)] \geq \alpha \\\ \end{gathered}$$

[hdavid16]

@pulsipher this is an interesting application because you are suggesting using cardinality constraints in a conditional fashion. The current modeling paradigm in GDP is that cardinality constraints are global and are always true. What you propose is some hybrid logical constraints that includes Boolean (0th order) logic and Cardinality (1st order) logic. Will have to give this some thought...

AtLeast is currently a set for a logical constraint. It looks like it would need to be an operator, rather than a set, for this to work. Thus adding a cardinality constraint would have to look like: @constraint(m, AtLeast(2, Y) := true) as opposed to @constraint(m, Y in AtLeast(2)).

[pulsipher]

@pulsipher this is an interesting application because you are suggesting using cardinality constraints in a conditional fashion. The current modeling paradigm in GDP is that cardinality constraints are global and are always true. What you propose is some hybrid logical constraints that includes Boolean (0th order) logic and Cardinality (1st order) logic. Will have to give this some thought...

Exactly right.

AtLeast is currently a set for a logical constraint. It looks like it would need to be an operator, rather than a set, for this to work. Thus adding a cardinality constraint would have to look like: @constraint(m, AtLeast(2, Y) := true) as opposed to @constraint(m, Y in AtLeast(2)).

Yep, I agree. This is what pyomo.gdp does. To me, the key question is what is the "best" way to reformulate cardinality operators behind the scenes?

Once we know how we'd like to reformulate it, adding the cardinality operators as a feature addition should be a relatively straightforward PR. I am interested in this for a paper we are trying to wrap up and use DisjunctiveProgramming instead of pyomo.gdp.

[dovallev]

Hello @hdavid16

I think an easy way to support this (at least initially) is to allow modeling with binary variables inside disjunctions. In that way, the following formulation:

$$ \begin{gathered} {\left[\begin{array}{c} Y_i(\xi) \\ x_i(\xi) \leq 0 \end{array}\right] \vee\left[\begin{array}{c} \neg Y_i(\xi) \\ x_i(\xi) \geq 0 \end{array}\right], i \in I, \xi \in D_{\xi}} \\ \text { atleast }(k, Y(\xi)) \Longleftrightarrow W(\xi), \xi \in D_{\xi} \end{gathered} $$

could be formulated as:

$$ \begin{gathered} {\left[\begin{array}{c} Y_i(\xi) \\ x_i(\xi) \leq 0 \end{array}\right] \vee\left[\begin{array}{c} \neg Y_i(\xi) \\ x_i(\xi) \geq 0 \end{array}\right], i \in I, \xi \in D_{\xi}} \\ {\left[\begin{array}{c} P(\xi) \\ \sum_{i \in I}y_i(\xi) \geq k \end{array}\right] \vee\left[\begin{array}{c} \neg P(\xi) \\ \sum_{i \in I}y_i(\xi) \leq k-1 \end{array}\right], \xi \in D_{\xi}} \\ P(\xi) \Longleftrightarrow W(\xi), \xi \in D_{\xi} \end{gathered} $$

In the previous small example, the relation between $P$ and $W$ is trivial. However, in the example that @pulsipher proposed, various $P_j$ can be operated and then related with $W$.

From a philosophical point of view, I understand that there is almost no need of having binaries inside disjunctions, as logic can be represented in Boolean algebra. Still there are a few examples in MIP where binaries are not used as indicators. More importantly, GDP is a rich modeling framework and there is no need for constraining it. It should be the modeler's decision to use Boolean or binary when they consider appropriate (no?).

[hdavid16]

@pulsipher and I have discussed a way to support conditional cardinality constraints in the package by reformulating them always with big M, since it is likely not the best idea to start lifting binaries with a Hull reformulation. That way, you can still reformulate your model with Hull without lifting binaries for this more advanced 1st order logic. We just need to find some clones to add this to the package 😆.

The current hack is just to add the reformulation directly to the model for these cardinality constraints.