Disjunction of conjunction in linear programming

Question

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!

Answer 1

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$.

Answer 2

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$$