I have constraint of the form: \[u_{i} = 1 \iff \exists j \in J \text{ such that: } x_{jk}=1 \text{ for } k \in K_{ij}.\] Here \(u_i, x_{jk}\) are binary variables and \(J\) and \(K_{ij}\) are known sets given \(i\) and \(j\). I do not know how to model such constraints in a linear binary program.
asked
zbir |

Introduce a binary variable \(y_{ij}\). You can model the left-to-right implication with \(u_i \le \sum_{j \in J} y_{ij}\) and \(y_{ij} \le x_{jk}, j \in J, k \in K_{ij}\). For the right-to-left implication, take \(\sum_{k \in K_{ij}} x_{jk} - \mid K_{ij}\mid + 1 \le y_{ij}\) and \(y_{ij} \le u_i\). Alternatively, you can enforce the right-to-left implication without \(y_{ij}\) as follows: \(\sum_{k \in K_{ij}} x_{jk} - \mid K_{ij}\mid + 1 \le u_i\).
answered
Rob Pratt |

EDIT: I didn't see the answer by @Rob Pratt until after I posted mine. Although mine is uglier, it is a more complete answer due to addressing two different possible interpretations of what your problem is. I don't know how to get the blasted MathJax to work on this site, so I will use generic "sum" instead. My first (easy) interpretation of your problem is that for each u{
If this is the correct interpretation, you're done. Otherwise, read on. My second (more complicated) interpretation of your problem is that for each u_{i}, there are N_{i} corresponding collections, each consisting of sub-collections of x_{jk}'s; and that you want u_{i} = 1 iff at least one of the N_{i} collections has x_{jk} = 1 for all elements of its sub-collection (as opposed to the first interpretation being that at least one x{jk} = 1 in the sub-collection). In order to handle this, introduce a binary random variable c_{ij} for each sub-collection, and add constraints so that it is 1 iff all its member x_{jk} = 1. All sums immediately below are over the corresponding sub-collection.
Now add the constraints in the first interpretation, except use the c_{ij} in place of the x_{ij} and set N_{i} to be the number of collections.
answered
Mark L Stone |