¿Mis limitaciones son lineales?

Question

Escribí diferentes restricciones para un problema y algunas personas dicen que estas restricciones no son lineales.

Mi sensación es que mis limitaciones son lineales. ¿Puede ayudarme a demostrarlo?

Mi primera restricción: $$ \sum_{i=1}^{g} \prod_{k=1}^{n} X_{ijk} = 1 ;\forall j=1\dots m $$ con esta variable booleana: $$ X_{ijk} = \begin{cases} 1 & \text{ if true } \\ 0 & \text{ otherwise} \end{cases} $$

Mi segunda limitación: $$ \sum_{i=1}^{g} \sum_{j=1}^{m} \prod_{k=1}^{n} X_{ijk} = 1 $$

Como estas restricciones se basan en la variable booleana {0;1}, entonces estas restricciones son lineales porque cada miembro de las multiplicaciones no puede tener un valor mayor que 1. ¿Es esta prueba correcta?

Answer 1

Obviamente, un producto de variables de decisión no es lineal. Es decir, no se le puede dar a un solucionador de programación lineal (PL). Sin embargo, un producto de variables binarias puede linealizarse fácilmente. La expresión $v_{i,j}=\prod_{k=1}^n x_{i,j,k}$ con $x_{i,j,k}\in \{0,1\}$ puede expresarse como un conjunto de inecuaciones lineales: $$\begin{align} &v_{i,j}\le x_{i,j,k}\\ &v_{i,j}\ge \sum_{k=1}^n x_{i,j,k}-(n-1)\\ &v_{i,j} \in \{0,1\} \end{align}$$ Incluso podemos relajarnos $v_{i,j}$ sea continua entre cero y uno: $v_{i,j}\in[0,1]$ .