Adding a combination of and + or operator constraint in Linear Programming

Question

I have a list of paired variables(paired_list) like below and a resultant variable(my_res). paired_list = [[a,b],[c,d],[e,f],...].

Here a,b,c,d,e,f are also binary decision variables.

I have to set a constraint which is a combination of and and or operator as below

my_res = [(a and b) or (c and d) or (e and f)...].

How can I translate this into a ILP constraint?

In general, if $x_i \in \{0, 1\}$, you can write the constraint $x_i \wedge x_j$ as $x_i x_j = 1$ and the constraint $x_i \vee x_j$ as $x_i + x_j = 1$. In your case, you would have $x_a x_b + x_c x_d + x_e x_f = 1$. — VHarisop
– VHarisop, Commented May 11, 2018 at 16:48

prubin · Accepted Answer · 2018-05-12 15:53:39Z

0

Assume $x$, $y$ and $z$ are binary variables.

For $z$ to be $x$ OR $y$ (inclusive or): $z\le x + y$; $z\ge x$; $z\ge y$.
For $z$ to be $x$ XOR $y$ (exclusive or): $z\le x + y$; $z\le 2 - (x + y)$; $z\ge x - y$; $z\ge y - x$.
For $z$ to be $x$ AND $y$: $z\ge x + y - 1$; $z\le x$; $z\le y$.

answered May 12, 2018 at 15:53

prubin

5,4881 gold badge10 silver badges15 bronze badges

1 Answer 1