# How to model a constraint with existential quantification

 0 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 27 Dec '17, 11:34 zbir 17●1●4 accept rate: 0%

 2 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 27 Dec '17, 14:41 Rob Pratt 1.2k●2●6 accept rate: 28%
 1 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{i}, there is a corresponding collection of N{i} x_{jk}'s (all sums immediately below are over this collection). You want u_{i} = 1 iff at least one of the N_{i} x_{jk}'s in the corresponding collection = 1. This is achieved with u_i <= sum(x_jk) sum(x_jk) / N_i <= u_i  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. sum(x_jk) - (number of elements of sub-collection - 1) <= c_ij c_ij <= sum(x_jk) / (number of elements of 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 27 Dec '17, 16:16 Mark L Stone 447●3●10 accept rate: 15%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: