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's gravatar image

accept rate: 0%

edited 27 Dec '17, 12:45

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%20Pratt's gravatar image

Rob Pratt
accept rate: 28%

edited 27 Dec '17, 15:45

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%20L%20Stone's gravatar image

Mark L Stone
accept rate: 15%

edited 27 Dec '17, 16:37

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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



Asked: 27 Dec '17, 11:34

Seen: 303 times

Last updated: 27 Dec '17, 16:37

OR-Exchange! Your site for questions, answers, and announcements about operations research.