# Can this be formulated as one inequality

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?

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.

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

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.

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