Can this be formulated as one inequality

Question

I have two binary variables $x_1$ and $x_2$ and a non-negative continuous variable $y$. In addition, I have the following two parameters $u>q>0$. I would like to formulate the following implications

1. $x_1=0 \implies y=0$
2. $(x_1,x_2)=(1,0) \implies y\leq u-q$
3. $(x_1,x_2)=(1,1) \implies y\leq u$

I have managed to formulate these relations using the following two inequalities \begin{align} &y\leq ux_1\\ &y\leq (u-q)x_1 + qx_2 \end{align} However, I am wondering whether it can be achieved using only one inequality?

Answer 1

It is not possible as a linear inequality in the variables that you provide.

Without loss of generality, this linear inequality would be of the form $$y \le \alpha x_1 + \beta x_2 + \gamma.$$

Condition 1 says that for $x_1=0$, the right-hand side must be zero for both $x_2=0$, which implies $\gamma=0$, and for $x_2=1$, which then implies $\beta = 0$ as well.

Condition 3 says that for $x_1=x_2=1$, the right-hand side must be $u$, which implies $\alpha = u$.

You end up with the constraint $y\le ux_1$, which clearly does not satisfy condition 2. So you cannot formulate your implications as a single linear constraint.

If you are not concerned about linearity, you can formulate quadratically as proposed by Oguz. Even simpler you could just say $$y \le \min\{ux_1, (u-q)x_1 + qx_2\},$$ which is a single constraint. From a computational standpoint, this is unlikely to bring you anything, and linear inequalities would typically be strongly preferred. Having more of them is not necessarily worse, and is often better.

Answer 2

As @OguzToragay mentioned, you can do it with one quadratic inequality: $$y \le (u-q)x_1 + q x_1 x_2,$$ which you can linearize as follows: \begin{align} y &\le (u-q)x_1 + q z \tag1 \\ z &\le x_1 \tag2 \\ z &\le x_2 \tag3 \end{align} This linearization is at least as tight as your original formulation because $(1)$ and $(2)$ imply your first constraint and $(1)$ and $(3)$ imply your second constraint. In fact, this linearization has the same strength, as you can see by considering the two mutually exclusive cases $x_1 < x_2$ and $x_1 \ge x_2$.

Answer 3

If you are willing to introduce an additional binary variable and your goal is to have only a single constraint on $y$, you could do the following:

Introduce three binary variables $\zeta_{10}$, $\zeta_{01}$ and $\zeta_{11}$. Now you need the constraint $\zeta_{10} + \zeta_{01} + \zeta_{11} \leq 1$ (note that this constraint does not involve $y$). In your model, you then have to substitute all occurences of $x_1$ with $\zeta_{10} + \zeta_{11}$ and all occurences of $x_2$ with $\zeta_{01} + \zeta_{11}$, effectively getting rid of $x_1$ and $x_2$ from your model (thus the number of binary variables in the model only increases by one). Note that this substitution should not introduce non-linearities (although you may have to be careful if you have some big-M type of constraints or some other rewriting tricks to deal with non-linear constraints).

Now you can easily define a single linear constraint on $y$ as follows: $y \leq \zeta_{10} (u-q) + \zeta_{11} q$.

I am not sure if this makes any sense in practice, and I don't think it is more efficient than having multiple constraints on $y$ in most cases.

Answer 4

I don't think there is a linear inequality covering all the cases or at least I couldn't find any linear inequality for that but the following can be considered: $$y\le ux_1-x_1(1-x_2)q$$