Isso pode ser formulado como uma desigualdade

Question

Eu tenho duas variáveis ​​binárias $x_1$ e $x_2$ e uma variável contínua não negativa $y$. Além disso, tenho os seguintes dois parâmetros$u>q>0$. Eu gostaria de formular as seguintes implicações

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$

Consegui formular essas relações usando as seguintes duas desigualdades \begin{align} &y\leq ux_1\\ &y\leq (u-q)x_1 + qx_2 \end{align} No entanto, estou me perguntando se isso pode ser alcançado usando apenas uma desigualdade.

Answer 1

Não é possível como uma desigualdade linear nas variáveis ​​que você fornece.

Sem perda de generalidade, esta desigualdade linear seria da forma $$y \le \alpha x_1 + \beta x_2 + \gamma.$$

A condição 1 diz que para $x_1=0$, o lado direito deve ser zero para ambos $x_2=0$, que implica $\gamma=0$, e para $x_2=1$, o que então implica $\beta = 0$ também.

Condição 3 diz que para $x_1=x_2=1$, o lado direito deve ser $u$, que implica $\alpha = u$.

Você acaba com a restrição $y\le ux_1$, que claramente não satisfaz a condição 2. Portanto, você não pode formular suas implicações como uma única restrição linear.

Se você não está preocupado com a linearidade, você pode formular quadraticamente como proposto por Oguz. Ainda mais simples, você poderia simplesmente dizer$$y \le \min\{ux_1, (u-q)x_1 + qx_2\},$$que é uma única restrição. Do ponto de vista computacional, é improvável que isso traga alguma coisa, e as desigualdades lineares normalmente seriam fortemente preferidas. Ter mais deles não é necessariamente pior e muitas vezes é melhor.

Answer 2

Como @OguzToragay mencionou, você pode fazer isso com uma desigualdade quadrática: $$y \le (u-q)x_1 + q x_1 x_2,$$ que você pode linearizar da seguinte maneira: \begin{align} y &\le (u-q)x_1 + q z \tag1 \\ z &\le x_1 \tag2 \\ z &\le x_2 \tag3 \end{align} Esta linearização é pelo menos tão rígida quanto sua formulação original porque $(1)$ e $(2)$ implica sua primeira restrição e $(1)$ e $(3)$implica sua segunda restrição. Na verdade, essa linearização tem a mesma força, como você pode ver ao considerar os dois casos mutuamente exclusivos$x_1 < x_2$ e $x_1 \ge x_2$.

Answer 3

Se você está disposto a introduzir uma variável binária adicional e seu objetivo é ter apenas uma única restrição em $y$, você poderia fazer o seguinte:

Apresente três variáveis ​​binárias $\zeta_{10}$, $\zeta_{01}$ e $\zeta_{11}$. Agora você precisa da restrição$\zeta_{10} + \zeta_{01} + \zeta_{11} \leq 1$ (note que esta restrição não envolve $y$) Em seu modelo, você deve substituir todas as ocorrências de$x_1$ com $\zeta_{10} + \zeta_{11}$ e todas as ocorrências de $x_2$ com $\zeta_{01} + \zeta_{11}$, efetivamente se livrando de $x_1$ e $x_2$do seu modelo (portanto, o número de variáveis ​​binárias no modelo só aumenta em um). Observe que essa substituição não deve introduzir não linearidades (embora você possa ter que ter cuidado se tiver algum tipo de restrição big-M ou alguns outros truques de reescrita para lidar com restrições não lineares).

Agora você pode definir facilmente uma única restrição linear em $y$ do seguinte modo: $y \leq \zeta_{10} (u-q) + \zeta_{11} q$.

Não tenho certeza se isso faz algum sentido na prática, e não acho que seja mais eficiente do que ter várias restrições $y$ na maioria dos casos.

Answer 4

Não acho que haja uma desigualdade linear cobrindo todos os casos ou pelo menos não consegui encontrar nenhuma desigualdade linear para isso, mas o seguinte pode ser considerado: $$y\le ux_1-x_1(1-x_2)q$$