¿Variación del programación lineal?
Estoy tratando de encontrar un algoritmo existente para el siguiente problema:
es decir, supongamos que tenemos 3 variables, x, y, z (todas deben ser enteros).
Quiero encontrar valores para todas las variables que DEBEN cumplir algunas restricciones, como x+y<4, x<=50, z>x, etc.
Además, existen restricciones POSIBLES adicionales, como y>=20, etc. (igual que antes).
La función objetivo (en la que estoy interesado en maximizar su valor) es el número de restricciones ADICIONALES que se cumplen en la solución óptima (las restricciones “deben” + el hecho de que todos los valores son enteros, es una demanda. sin ella, no hay solución válida).
davy.ai
Para abordar este problema, un algoritmo posible es utilizar programación lineal entera (ILP) con el objetivo de maximizar el número de restricciones adicionales satisfechas. Aquí están los pasos para resolver este problema utilizando ILP:
Definir restricciones: Ya tenemos restricciones “obligatorias”, las cuales deben ser escritas en términos de las variables de decisión. Por ejemplo, x + y <= 4 puede ser escrito como x + y <= 3 ya que x e y son enteros. Las restricciones adicionales posibles también pueden ser escritas en términos de las variables de decisión.
Definir la función objetivo: La función objetivo debe maximizar el número de restricciones adicionales satisfechas. Necesitamos definir una variable binaria para cada restricción adicional posible para indicar si la restricción está satisfecha o no. La función objetivo debe ser la suma de estas variables binarias.
Resolver el problema de ILP: Esto se puede hacer utilizando una biblioteca de Python como OR-Tools. La solución nos dará los valores de x, y y z que satisfacen las restricciones mientras se maximiza el número de restricciones adicionales posibles satisfechas.
Tenga en cuenta que este no es el único algoritmo para resolver este problema, pero es un enfoque posible utilizando ILP.