How to model iff and union statements in MILP?

Question

I am trying to model $\{Ax\leq b\}\iff\{Bx\leq c\}$. How different is this from $\{Ax\leq b\}\wedge\{Bx\leq c\}$?

1. How to model with binary variables when $b$ and $c$ are $0$ vectors.

2. I am also trying to model $\{Ax\leq 0\}\cup\{Bx\leq 0\}$.

To model union if $b$ and $c$ were $non$-$zero$ then simply introduce binary variables $z_1,z_2\in\{0,1\}$ and introduce the criteria:

1. $z_1+z_2=1$

2. $x_1$ is vector such that $Ax_1\leq bz_1$ and $x_1$ is vector such that $Bx_2\leq cz_2$.

3. $x=x_1+x_2$.

If $b$ and/or $c$ are $0$ vectors then this trick fails.

Is there a better way?

Answer 1

Too see the difference look at an example. For $x=(x_1\:x_2)$, $A=\begin{pmatrix} 1 & 0\\0 & 0\end{pmatrix}$, $b=0$, $B=\begin{pmatrix} 0 & 0\\0 & 1\end{pmatrix}$, $c=0$ you have

with the equivalence on the left and the conjunction on the right. So in general $\{Ax\leq b\}\iff\{Bx\leq c\}$ is not convex and cannot be modeled without binary variables.

Answer 2

I deleted my first answer because it was completely wrong. (I negated a vector inequality incorrectly.)

You can come close to the desired result using a gaggle of binary variables, assuming that (a) the set of feasible $x$ is bounded and (b) you are willing to ignore some feasible solutions. The latter is necessary because the negation of a weak inequality is a strong inequality, and MIP models (and solvers) abhor strong inequalities.

Let $m$ and $n$ be the dimensions of $b$ and $c$ respectively, let $M$ and $\epsilon$ be sufficiently large and small (respectively) positive constants, and let $z_1,\dots,z_m$ and $y_1,\dots,y_n$ be binary variables. Add the constraints$$b_i+\epsilon-M(1-z_i)\le (Ax)_i \le b_i + Mz_i\,(i=1,\dots,m)$$and$$c_i+\epsilon-M(1-y_i)\le (Bx)_i\le c_i + My_i\, (i=1,\dots,n).$$Observe that $z_i=0\implies (Ax)_i \le b_i$ and $z_i=1\implies (Ax)_i \ge b_i + \epsilon$. Banished from the feasible region is any solution where $b_i \lt (Ax)_i \lt b_i + \epsilon$, which is the cost of doing business. Similar observations hold for the second set of constraints.

To enforce $Ax\le b \iff Bx\le c$, we need to require that $\sum_{i=1}^m z_i \ge 1 \iff \sum_{j=1}^n y_j \ge 1$. There are various ways to do this, trading off more constraints for (possibly) tighter relaxations. One way is to add the constraints$$n\sum_{i=1}^m z_i\ge \sum_{j=1}^n y_j$$and$$m\sum_{j=1}^n y_j \ge \sum_{i=1}^m z_i.$$

I used a single parameter $\epsilon$ and a single parameter $M$, but you may want to look for appropriate values on a row by row basis (particularly for $M$, as larger values of $M$ will tend to weaken relaxations).

Disjunctions are easier. You need just two binary variables ($z_1$ and $z_2$), with the inequalities$$Ax \le b + M_1z_1$$and $$Bx \le c +M_2z_2.$$Here $M_1$ and $M_2$ are vectors of large constant values. To get your disjunction, you need either $z_1=0$ or $z_2=0$ (or both). That can be enforced by the constraint $z_1 + z_2 \le 1$.