67
$\begingroup$

I have an integer linear program (ILP) with some variables $x_i$ that are intended to represent boolean values. The $x_i$'s are constrained to be integers and to hold either 0 or 1 ($0 \le x_i \le 1$).

I want to express boolean operations on these 0/1-valued variables, using linear constraints. How can I do this?

More specifically, I want to set $y_1 = x_1 \land x_2$ (boolean AND), $y_2 = x_1 \lor x_2$ (boolean OR), and $y_3 = \neg x_1$ (boolean NOT). I am using the obvious interpretation of 0/1 as Boolean values: 0 = false, 1 = true. How do I write ILP constraints to ensure that the $y_i$'s are related to the $x_i$'s as desired?

(This could be viewed as asking for a reduction from CircuitSAT to ILP, or asking for a way to express SAT as an ILP, but here I want to see an explicit way to encode the logical operations shown above.)

$\endgroup$
75
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ 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. $\endgroup$ – boxi Mar 25 '15 at 14:31
  • 4
    $\begingroup$ @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. $\endgroup$ – D.W. Mar 25 '15 at 19:44
  • $\begingroup$ -i checked it again. lp_solve can solve it, but for example qsopt can't. i don't know why. but thanks <3 $\endgroup$ – boxi Mar 25 '15 at 19:46
  • $\begingroup$ @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. $\endgroup$ – D.W. Mar 25 '15 at 20:16
  • 1
    $\begingroup$ @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. $\endgroup$ – D.W. Dec 22 '15 at 4:04
22
$\begingroup$

The logical AND relation can be modeled in one range constraint instead of three constraints (as in the other solution). So instead of the three constraints $$y_1\geq x_1+x_2−1,\qquad y_1\leq x_1,\qquad y_1\leq x_2\,,$$ it can be written using the single range constraint $$0 \leq x_1 + x_2-2y_1 \leq 1\,.$$ Similarly, for logical OR: $$0 \leq 2y_1 - x_1 - x_2 ≤ 1\,.$$

For NOT, no such improvement is available, because NOT is restricted to one argument.

In general for $y=x_1 \land x_2 \land \dots \land x_n$ ($n$-way AND) the constraint will be: $$0 \leq \sum x_i -ny \leq n-1\,.$$ Similarly for OR: $$0 \leq ny -\sum x_i \leq n-1\,.$$

$\endgroup$
2
  • $\begingroup$ A very simillar approach is in this paper: ncbi.nlm.nih.gov/pmc/articles/PMC1865583 $\endgroup$ – Abdelmonem Mahmoud Amer Jun 24 '15 at 10:57
  • 1
    $\begingroup$ Keep in mind that size isn't everything when looking at integer programming! The downside of the shorter constraints you suggest is that the LP relaxation that is solved as a subproblem for the MILP problem is not strong. You can see that by noting that, e.g., the upper bounding inequality for 'AND' becomes active (i.e., equality holds) for the non integral points (x1, x2, y) = (0, 1, 0.5) or (1, 0, 0.5) or (1, 1, 0.5). $\endgroup$ – mrclng Dec 26 '20 at 18:38
3
$\begingroup$

I found shorter solution for XOR y=x1⊕x2 (x and y are binary 0, 1)

just one line: x1 + x2 - 2*z = y (z is any integer)

$\endgroup$
2
  • 1
    $\begingroup$ To express the equality in ILP, you need two inequalities. Further, to avoid solution $x_1=1,x_2=0,z=200,y=-199$, you need two more inequalities, $0\leq y \leq 1$. So this answer has four inequalities and an extra variable compared to six inequalities in D.W.'s answer. $\endgroup$ – JiK Mar 9 '17 at 15:22
  • 2
    $\begingroup$ To express an equality in ILP only needs one equation, this is true in both LP theory and in software such Gurobi or CPLEX . @jIk, I guess you mean "expressing "a $\neq b$" needs two inequalities. " $\endgroup$ – whitegreen Jan 18 '18 at 3:11
0
$\begingroup$

I can not believe that below is a "fresh result" in mathematical programming ... But my rather intensive search over literature did not bring reference to any similar assertion... I will appreciate any hint to relevant references!

Recently, I understood how to represent any boolean function $f(x)$ as a system of linear inequalities in the following sense.

Let $B^n{\doteq}\left\{(x_1,x_2, ..., x_n): x_k{\in}\{0,1\}\right\}\subset R^n$ be a set of all vertices of n-dimensional unit cube, i.e. the set of all 0-1 arguments of some boolean function $f: B^n{\to}\{0,1\}$.

Then there exist a system of linear inequalities of $n{+}1$ variables $(x,y)$: $$S(x,y)=\{a_i {+} l_i(x) {+} b_iy \geqslant 0: i{=}1{:}m\}$$ (where $a_i, b_i$, $b_i{\neq}0$ are scalars, and $l_i(x)$ are linear functions of $n$ variables) such that $$\forall x{\in}B^n{:} ~ \left(f(x){=}y \Leftrightarrow a_i {+} l_i(x) {+} b_iy \geqslant 0 \left(i{=}1{:}m\right)\right) $$ i.e for any $x{\in}B^n$, $f(x){=}y$ if and only if $S(x,y)$ holds.

It is important that we do not need to assume that $y$ is a discrete, 0-1, variable! For any 0-1 vector $x$, the system $S(x,y)$ has the only solution $(x, y{=}f(x))$.

And I can explicitly produce the system $S(x,y)$ (in vector-matrix form) for any function $f(x)$ given either by formula or in tabular form.

Of course, there are computing limitations for a large number of variables... But we can always express $f(x)$ as composition of functions of less number of variables.

Can you tell me any reference on this subject?

$\endgroup$
3
  • $\begingroup$ You basically encode the clauses $x \neq x_0 \lor y$ for all $x_0$ such that $f(x_0) = 1$, and $x \neq x_0 \lor \lnot y$ for all $x_0$ such that $f(x_0) = 0$, together with $0 \leq y \leq 1$. $\endgroup$ – Yuval Filmus May 4 at 22:15
  • $\begingroup$ I don't see how this answers the question that was asked, as it doesn't describe how to find the system $S$. If you want to ask a question (i.e., to ask for references), please do that by posting this as a new question, using the 'Ask Question' button. If you want to answer this question, I encourage you to revise this answer to describe specifically how to find $S$ (not just that it exists). $\endgroup$ – D.W. May 4 at 23:09
  • $\begingroup$ Dear D.W., I agree that my "answer" is rather an another question and I already posted it here. But above question concerns special cases of representation of boolean functions as inequalities... $\endgroup$ – Vladimir VV May 5 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.