Problem with big-M logical constraints

integer programmingmixed-integer programmingoptimization

Consider a linear optimization problem with two variables $u_1, u_2$:

$$\begin{array}{rl}
\max_{u_1, u_2} & k_1 u_1 + k_2 u_2\\
\text{s.t.}\\
& 0 \leq u_1 \leq a_1\\
& 0 \leq u_2 \leq a_2
\end{array},$$

where $k_1, k_2, a_1$ and $a_2$ are fixed parameters.

I'm struggling to add also logical constraints to the problem. Specifically, a couple $(u_1, u_2)$ is feasible if:

$$\begin{cases}
0 \leq u_1 \leq a_1\\
0 \leq u_2 \leq a_2\\
\color{red}{u_1 > 0 \vee u_2 = 0}
\end{cases}.$$

To account for the latter, I'm studying the Big-M method. According to this method, the logical constraint $u_1 > 0 \vee u_2 = 0$ can be accounted by introducing two integer variables, $y_1 \in \{0, 1\}$ and $y_2 \in \{0, 1\}$, and adding the following linear constraints to the problem:

$$\begin{array}{l}
u_1 \leq M y_1\\
u_2 \leq M y_2\\
y_1 + (1-y_2) \geq 1
\end{array}.$$

Anyway, this new formulation does not guarantee that the logical constraint $u_1 > 0 \vee u_2 = 0$ is always satisfied. For example, consider $a_2 = 1, M = 100, u_1 = 0, u_2 =0.8, y_1 = 1, y_2 = 1.$

In this case the big-M constraints are satisfied:

$$\begin{array}{ll}
u_1 \leq M y_1 \Rightarrow 0 \leq 100 \cdot 1 &\text{OK}\\
u_2 \leq M y_2 \Rightarrow 0.8 \leq 100 \cdot 1 &\text{OK}\\
y_1 + (1-y_2) \geq 1 \Rightarrow 1 + (1-1) \geq 1 &\text{OK}
\end{array},$$

but obviously $(0 > 0) \vee (0.8 = 0)$ is false.

What is wrong with my formulation? Am I missing something?

Best Answer

You were on the right track with two additional binary variables and two big-M constraints. For the implication $y_1=1 \implies u_1>0$, you can enforce instead $y_1=1 \implies u_1\ge \epsilon$ for some small tolerance $\epsilon>0$. The full linearization is: \begin{align} u_1 &\ge \epsilon y_1\\ u_2 &\le a_2 (1-y_2)\\ y_1 + y_2 &\ge 1 \end{align} If $y_1=1$, then the first constraint forces $u_1 \ge \epsilon$. If $y_2=1$, then the second constraint forces $u_2 \le 0$, hence $u_2=0$.

Related Question