¿Hay alguna manera de permitir una opción "o" en un programa lineal?

Question

Estoy buscando una forma de expresar una opción "o" en un sistema de inecuaciones lineales para un programa lineal en el que estoy trabajando.

Voy a explicar lo que quiero decir con precisión: Digamos que tengo un conjunto de desigualdades $eq_1$ a $eq_n$ que se debe mantener. Pero, además, tengo varias desigualdades más $eqa_1,....,eqa_k$ y $eqb_1,...,eqb_k$ que se puede dividir en parejas (de la forma $\left< eqa_i ,\, eqb_i\right>$ para todos $1\leq i \leq k$ ), de manera que $eqa_i$ se mantiene o si no lo hace entonces $eqb_i$ . Sin embargo, también es posible que ambos se mantengan. Lo que busco es una opción para codificar tal condición "o" en un conjunto de desigualdades.

Por supuesto, si decimos que $eqa_i$ es digamos $f\left(...\right) \leq K$ y $eqb_i$ es $g\left(...\right) \leq M$ Puedo escribir $f\left(...\right)+g\left(...\right) \leq K+M$ pero esta exigencia es demasiado fuerte, porque en mi problema original puedo permitir $f\left(...\right) > K+M$ (por ejemplo) siempre que $g\left(...\right) \leq M$ pero luego $f\left(...\right)+g\left(...\right) > K+M$ . Por lo que se requiere $f\left(...\right)+g\left(...\right) \leq K+M$ es demasiado fuerte para mí.

Mi pregunta se puede dividir en 2 preguntas:

1. ¿Hay alguna idea para un buen truco aquí o para algún tipo de reducción a la Programación Lineal? (Una reducción de una instancia en la que se tienen parejas de desigualdades con una o, a una instancia regular de LP)
2. ¿Quizás exista un software o un sitio en línea que permita este tipo de "o"? Estoy utilizando este sitio: https://online-optimizer.appspot.com/ . Sin embargo, si hay otros sitios o software que tengan esa opción incorporada para un "o", sería genial también.

Si mis desigualdades son demasiado genéricas, sé que la mayoría parecen de la forma $x_{i_1}+x_{i_2}+x_{i_3} \leq K$ , donde $K$ es el mismo $K$ para todas las desigualdades, y el resto son $x_{i_1}+x_{i_2} \leq K$ o $x_{i_1}+x_{i_2}+x_{i_3}+x_{i_4} \leq K$ .

Answer 1

Puede hacer que se cumpla $f \le K \lor g \le M$ introduciendo una variable de decisión binaria $x$ y las restricciones lineales de la "gran M": \begin{align} f - K &\le M_1 x \tag1 \\ g - M &\le M_2(1-x) \tag2 \end{align} Aquí $M_1$ es un límite superior constante en $f-K$ cuando $x=1$ y $M_2$ es un límite superior constante en $g-M$ cuando $x=0$ .

Si $x=0$ , entonces la restricción $(1)$ fuerzas $f \le K$ y la restricción $(2)$ es redundante. Si $x=1$ , entonces la restricción $(2)$ fuerzas $g \le M$ y la restricción $(1)$ es redundante.