6
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

| improve this answer | |
$\endgroup$
6
$\begingroup$

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

| improve this answer | |
$\endgroup$
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$
3
$\begingroup$

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

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.