Logical AND: Use the linear constraints $y_1 \ge x_1 + x_2 - 1$, $y_1 \le x_1$, $y_1 \le x_2$, $0 \le y_1 \le 1$, where $y_1$ is constrained to be an integer. This enforces the desired relationship. (Pretty neat that you can do it with just linear inequalities, huh?)
Logical OR: Use the linear constraints $y_2 \le x_1 + x_2$, $y_2 \ge x_1$, $y_2 \ge x_2$, $0 \le y_2 \le 1$, where $y_2$ is constrained to be an integer.
Logical NOT: Use $y_3 = 1-x_1$.
Logical implication: To express $y_4 = (x_1 \Rightarrow x_2)$ (i.e., $y_4 = \neg x_1 \lor x_2$), we can adapt the construction for logical OR. In particular, use the linear constraints $y_4 \le 1-x_1 + x_2$, $y_4 \ge 1-x_1$, $y_4 \ge x_2$, $0 \le y_4 \le 1$, where $y_4$ is constrained to be an integer.
Forced logical implication: To express that $x_1 \Rightarrow x_2$ must hold, simply use the linear constraint $x_1 \le x_2$ (assuming that $x_1$ and $x_2$ are already constrained to boolean values).
XOR: To express $y_5 = x_1 \oplus x_2$ (the exclusive-or of $x_1$ and $x_2$), use linear inequalities $y_5 \le x_1 + x_2$, $y_5 \ge x_1-x_2$, $y_5 \ge x_2-x_1$, $y_5 \le 2-x_1-x_2$, $0 \le y_5 \le 1$, where $y_5$ is constrained to be an integer.
And, as a bonus, one more technique that often helps when formulating problems that contain a mixture of zero-one (boolean) variables and integer variables:
Cast to boolean (version 1): Suppose you have an integer variable $x$, and you want to define $y$ so that $y=1$ if $x \ne 0$ and $y=0$ if $x=0$. If you additionally know that $0 \le x \le U$, then you can use the linear inequalities $0 \le y \le 1$, $y \le x$, $x \le Uy$; however, this only works if you know an upper and lower bound on $x$.
Alternatively, if you know that $|x| \le U$ (that is, $-U \le x \le U$) for some constant $U$, then you can use the method described here. This is only applicable if you know an upper bound on $|x|$.
Cast to boolean (version 2): Let's consider the same goal, but now we don't know an upper bound on $x$. However, assume we do know that $x \ge 0$. Here's how you might be able to express that constraint in a linear system. First, introduce a new integer variable $t$. Add inequalities $0 \le y \le 1$, $y \le x$, $t=x-y$. Then, choose the objective function so that you minimize $t$. This only works if you didn't already have an objective function. If you have $n$ non-negative integer variables $x_1,\dots,x_n$ and you want to cast all of them to booleans, so that $y_i=1$ if $x_i\ge 1$ and $y_i=0$ if $x_i=0$, then you can introduce $n$ variables $t_1,\dots,t_n$ with inequalities $0 \le y_i \le 1$, $y_i \le x_i$, $t_i=x_i-y_i$ and define the objective function to minimize $t_1+\dots + t_n$. Again, this only works nothing else needs to define an objective function (if, apart from the casts to boolean, you were planning to just check the feasibility of the resulting ILP, not try to minimize/maximize some function of the variables).
For some excellent practice problems and worked examples, I recommend Formulating Integer Linear Programs:
A Rogues' Gallery.
I think the constraints for $y = 1 \iff x \neq 0$ when $-U \leq x \leq U$ are bogus. Consider $x=0$, then both $y=0$ and $y=1$ satisfy $-Uy \leq x $ and $ x \leq Uy$. – Pramod – 2015-12-21T20:40:44.537
1
@Pramod, good catch! Thank you for spotting that error. You're absolutely right. I've asked a new question about how to model that case and I'll update this answer when we get an answer to that one.
– D.W. – 2015-12-22T04:04:45.107Thanks, DW. I ran into this specific problem today and came up with a really messy solution which I've posted. It'll be great if someone can come up with something cleaner. – Pramod – 2015-12-22T05:12:30.407
Is there any citable reference of these techniques ? – Neel Basu – 2018-01-04T11:36:24.660
@NeelBasu, not that I know of. Most of these are standard and not something that would need citation. If you want to find something you can cite, you could look at the link in my answer and in other comments. – D.W. – 2018-01-04T17:48:33.373
Is there a typo in the Logical OR solution? I think it should say "where y2 is constrained to be an integer" not "... y1 ..." – Adam Spiers – 2019-01-21T00:11:33.660
@AdamSpiers, oh yeah! Good catch. Fixed. Thanks for catching that. – D.W. – 2019-01-21T04:04:47.703
which linear programming solver can solve this? becouse in *.lp or *.mps-format one side of the constraint has to be an fixed integer and not an variable. – boxi – 2015-03-25T14:31:42.887
4@boxi, I don't know anything about *.lp or *.mps format, but every integer linear programming solver should be able to solve this. Note that if you have something like $x \le y$, this is equivalent to $y -x \ge 0$, which may be in the format you wanted. – D.W. – 2015-03-25T19:44:33.160
-i checked it again. lp_solve can solve it, but for example qsopt can't. i don't know why. but thanks <3 – boxi – 2015-03-25T19:46:59.147
@boxi, I just checked the QSopt online applet GUI and it could handle these kinds of constraints once I changed $x \le y$ to $x - y \le 0$, so I'm not sure what's going on. (I used *.lp format.) I would be surprised if any ILP solver was unable to handle these systems. If you have further questions about QSopt you should probably take them to the QSopt support forums. – D.W. – 2015-03-25T20:16:57.707