Disjunction of conjunction in linear programming I'm trying to get my model working with less variable/constraints possible. I want the binary variable $R$ to store the result of this Boolean expression:
R = (a1 and b1) or (a2 and b2) or (a3 and b3) ... or (aN and bN)
I'm perfectly aware of the solution which consists in having $N$ helpers binary variables, each of one store the result of one and.
$ c_k \leq (a_k+b_k) / 2    \quad k = 0,\ldots,N$
and then maximize the value of $R$ subject to the constraint
$R \leq \sum_{k=1}^N c_k$
This approach introduces $N$ extra variables and $N$ extra constraints. Does exist any better solution in terms of number of variables/constraints? If not, anyone could help me to understand why?
I'm writing the model in AMPL, but I believe that this problem is not language dependent. Thank you very much!
 A: I think that in a more general setting, i.e. in which you want your variables/constraints to be part of a more complex model, your approach is limiting. So you can start with
$$ (a_k + b_k)-1 \leq R \quad \forall k=1,\ldots,N$$
that force $R$ to be one if any of the clauses are true. Then you need to force $R$ to zero when all are false. You cannot reduce the number of variables because you must model two different things: the OR and the AND. They are basically independent.I would avoid playing with rounding. You first model the OR
$$R\leq \sum_{k=1}^N c_k$$
and then you define what is $c_k$: 
$$ 2c_k \leq a_k+b_k \quad \forall k=1,\ldots,N$$
you cannot do much better without loosing information. Note also that $c_k$ does not actually model AND: if two clauses are true, say $i,j$, $R$ is $1$ but only one among $i,j$ is required to be one itself. For instance $c_i=0,c_j=1$ is feasible for $R=1$ and $a_i=a_j=b_j=b_i=1$.
A: A tighter formulation is
\begin{align}
R &\ge a_k+b_k-1 &\text{for all $k$}\\
R &\le \sum_k c_k\\
c_k &\le a_k&\text{for all $k$}\\
c_k &\le b_k&\text{for all $k$}
\end{align}
You can alternatively get by with only the original $2N+1$ variables at the expense of an exponential number ($2^N+N$) of constraints:
\begin{align}
R &\ge a_k+b_k-1 &\text{for all $k$}\\
R &\le \sum_k \left\{{a_k \atop b_k}\right\}
\end{align}
where $\left\{{a_k \atop b_k}\right\}$ means that either $a_k$ or $b_k$ appears.  For example, if $N=5$, one of these constraints is
$$R \le a_1 + a_2 + b_3 + a_4 + b_5$$
