Supongamos que tenemos un programa entero o entero con un par de miles de restricciones.
¿Cómo podemos determinar si esta IP / MIP es factible?
Respuestas
3 para la respuesta № 1Supongamos que tenemos un problema de programación de enteros o enteros mixtos con un par de miles de restricciones.
los número de restricción No es necesario escalar con la inviabilidad: en general, las restricciones limitan la cantidad de posibilidades que se deben enumerar. Otro problema relacionado es aleatorio 3-SAT, donde, por ejemplo, los problemas más difíciles son aquellos en los que el número de restricciones se escala aproximadamente con un factor cuatro en comparación con el número de variables.
¿Cómo podemos darnos cuenta de que este problema es factible?
Hay buenas programaciones enteras (mixtas) Solucionadores Disponible que puede resolver algunos problemas (difíciles) en un tiempo razonable. Sin embargo, se sabe que los problemas genéricos de programación de enteros son NP-duro. Esto significa que no es muy probable encontrarAlgoritmo que resuelve estos problemas en general en un tiempo razonable. A veces tenemos suerte y el problema de Programación Integral tiene una estructura que podemos explotar para encontrar una solución de manera eficiente, pero como se dijo: en general es un problema difícil.
Los solucionadores suelen trabajar con un ramificación y límite donde a través de la relajación los dominios de laLas variables están restringidas, hasta que se alcanza una condición estable. Luego, el solucionador elige un valor para una de las variables (qué variable y qué valor primero se investigan en gran medida, ya que tienen un gran impacto en la búsqueda de la solución). Entonces, el problema se relajará aún más hasta que se pruebe que no existe una solución con ese valor, o que el sistema tiene que asignar un nuevo valor. Si se demuestra que un modelo no es satisfactorio con un conjunto dado de variables asignadas, el sistema atrasos: deshace "s algunas variables que se asignan yreasigna valores a estos y continúa la búsqueda. Eventualmente, se encontrará una solución (pero puede llevar mucho tiempo), o el solucionador puede probar que el problema no es satisfactorio (no existe ninguna solución). En caso de que se encuentre una solución, aún no hemos terminado: ya que generalmente estamos interesados en una óptimo Solución con respecto a alguna optimización.función. En ese caso, agregamos una restricción que a partir de ahora, buscamos soluciones que sean mejores que las fundadas hasta ahora. Continuamos haciendo esto hasta que nos quedemos sin nuevas soluciones, en cuyo caso hemos demostrado ser óptimos.
En caso de que sea fácil encontrar las soluciones correctas (con respecto a las restricciones difíciles), pero difícil obtener la mejor solución, se puede usar metaheurística a aproximado la mejor solucion. Aquí se considera una "espacio de solución"De soluciones que satisfacen las duras restricciones. Al construir una serie de "funciones de mutación" que toman una solución válida y la convierten en otra solución, uno puede generar un algoritmo que busque la mejor solución, manipulando de manera iterativa la solución. Si nos quedamos sin tiempo, devolvemos la mejor solución hasta el momento. Aunque nunca tenemos garantías de que tenemos la óptimo Solución, generalmente las metaheurísticas funcionan bastante bien, y devuelven un cerca de óptimo solución. Algunas metaheurísticas como Recocido Simulado Puede realizar garantías estadísticas respecto a la calidad de la solución.
3 para la respuesta № 2
Una cosa que puede decir con seguridad es que si la relajación lineal del problema ya no es factible, también lo es el problema de la programación de enteros.