Consistencia de los sistemas de desigualdades que sólo implican diferencias

Question

Tengo un número muy grande (670 mil millones) de sistemas de desigualdades de la forma

$C_1 - C_2 < C_4 - C_3 \wedge C_3 - C_2 < C_5 - C_3 \wedge ...$

donde el $C_i > 0$ . Es decir, cada sistema de inecuaciones consiste en las comparaciones de diferencias entre números reales positivos que deben ser todas verdaderas al mismo tiempo.

Ahora quiero encontrar el subconjunto de sistemas que son consistentes, es decir, existe una opción de $C_i$ de manera que se satisfagan todas las desigualdades.

Dado el gran número de sistemas, este método tendría que ser automatizado. Por lo tanto, mi pregunta es:

¿Existe un algoritmo para decidir si un sistema de desigualdades de la forma descrita anteriormente es consistente?

Answer 1

¡¡¡Hola!!!

Esto podría hacerse con un solucionador lineal... ¡hasta cierto punto! Un programa lineal acepta un conjunto de restricciones de la forma (función lineal >= 0), y le dice si existe una asignación de valores a sus variables tal que se satisfagan todas las restricciones.

La "única diferencia" entre su problema y lo que puede hacer un solucionador de LP es que el solucionador de LP no puede entender las desigualdades estrictas. Por lo tanto, tendría que añadir restricciones lineales de la forma variable >= algún_valor_muy_pequeño.

Creo que estas respuestas podrían seguir siendo útiles para ti. Teóricamente, incluso se puede obtener un certificado de inviabilidad (un conjunto de restricciones que afectan), pero es más difícil de obtener en la práctica.

Si quieres probarlo, deberías buscar solucionadores de programas lineales como GLPK (gratuito), CPLEX(propietario), Coin (gratuito), Gurobi (propietario). Estos programas aceptan como entrada un archivo .mps o .lp que describe su conjunto de restricciones (espero que esto aparezca en la documentación de cada uno de estos solucionadores).

También puede hacer este cálculo a través de Sage ( http://www.sagemath.org ), y mirando este breve tutorial sobre LP (¡para aplicaciones gráficas!) http://steinertriples.fr/ncohen/tut/LP/

¡Buena suerte! ;-)

Nathann