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!


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


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.