# How to model iff and union statements in MILP?

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?

• It is not possible to model implication in convex form in general. May 21, 2019 at 9:10
• This is a very general question. In my view it would be better to specify your question to get a good answer. Btw, are you aware that answers can be accepted $(\color{limegreen}{\checkmark})$? You have asked $440$ questions, only a handful have accepted answers. May 21, 2019 at 9:11
• @Brout You should follow advice of callculus and explain specifically what you want to do. Of course you could replace iff with a simple = but I guess that's not what you need. May 21, 2019 at 9:30
• The option that both conditions are false is what makes the set nonconvex. You will need integer variables. May 21, 2019 at 10:02
• @MichalAdamaszek However I am not able to make that trick work when $b$ and/or $c$ are $0$ vectors. May 21, 2019 at 10:03

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.

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