Este equipo de redactores ha pasado horas investigando para darle soluciones a tus dudas, te brindamos la solución y esperamos resultarte de mucha ayuda.
Solución:
Esto puede ser un poco exhaustivo, pero intentaré proporcionar toda la información para cubrir un buen alcance de este tema. Empezaré con un ejemplo y la información correspondiente tendrá más sentido.
Ejemplo: Digamos que necesitamos secuenciar un conjunto de tareas en una máquina. Cada tarea i tiene un tiempo de procesamiento fijo específico pI. Cada tarea se puede iniciar después de su fecha de lanzamiento rI , y debe completarse antes de su fecha límite dI. Las tareas no pueden superponerse en el tiempo. El tiempo se representa como un conjunto discreto de puntos de tiempo, digamos 1, 2,…, H (H significa horizonte)
Modelo MIP:
- Variables: variable binaria xij representa si la tarea i comienza en el período de tiempo j
- Restricciones:
- Cada tarea comienza exactamente en un punto temporal
- ∑j Xij = 1 para todas las tareas i
- Respete la fecha de lanzamiento y el plazo
- j * xij = 0 para todas las tareas i y (j
- j * xij = 0 para todas las tareas i y (j
- Las tareas no se pueden superponer
- Variante 1: ∑I Xij ≤ 1 para todos los puntos de tiempo j también debemos tener en cuenta los tiempos de procesamiento; esto se vuelve complicado
- Variante 2: introduzca la variable binaria bI que representa si la tarea i viene antes que la tarea k debe estar vinculada axij; esto se vuelve desordenado. Los modelos MIP consisten en funciones de optimización lineales / cuadráticas, restricciones de optimización lineales / cuadráticas y variables binarias / enteras.
- Cada tarea comienza exactamente en un punto temporal
Modelo CP:
- Variables: * EmpecemosI representa la hora de inicio de la tarea i toma un valor del dominio 1,2,…, H – esto asegura inmediatamente que cada tarea comience exactamente en un punto de tiempo
- Restricciones: * Respete la fecha de lanzamiento y la fecha límite
rI ≤ inicioI ≤ dI – pagI
* Las tareas no pueden superponerse: para todas las tareas i y j (iniciarI + pI
¡y eso es todo!
Probablemente se podría decir que la estructura de los modelos de CP y de los modelos de MIP es la misma: utilizando variables de decisión, función objetivo y un conjunto de restricciones. Tanto los problemas MIP como los CP no son convexos y utilizan algunos algoritmos de búsqueda sistemáticos y exhaustivos.
Sin embargo, vemos la principal diferencia en la capacidad de modelado. Con CP tenemos n variables y una restricción. En MIP tenemos nm variables y n + m restricciones. Esta forma de mapear las restricciones globales a las restricciones de MIP utilizando variables binarias es bastante genérica
CP y MIP resuelven problemas de una manera diferente. Ambos utilizan un enfoque de divide y vencerás, donde el problema a resolver se divide recursivamente en subproblemas fijando valores de una variable a la vez. La principal diferencia radica en lo que sucede en cada nodo del árbol de problemas resultante. En MIP, uno generalmente resuelve una relajación lineal del problema y usa el resultado para guiar la búsqueda. Esta es una búsqueda de bifurcaciones y límites. En CP, se realizan inferencias lógicas basadas en la naturaleza combinatoria de cada restricción global. Esta es una búsqueda de enumeración implícita.
Diferencias de optimización:
- Un motor de programación de restricciones toma decisiones sobre variables y valores y, después de cada decisión, realiza un conjunto de inferencias lógicas para reducir las opciones disponibles para los dominios de las variables restantes. Por el contrario, un motor de programación matemática, en el contexto de la optimización discreta, utiliza una combinación de relajaciones (reforzadas por planos de corte) y “ramificación y acotación”.
- Un motor de programación de restricciones demuestra la optimización al mostrar que no se puede encontrar una solución mejor que la actual, mientras que un motor de programación matemática utiliza una prueba de límite inferior proporcionada por cortes y relajación lineal.
- Un motor de programación de restricciones no hace suposiciones sobre las propiedades matemáticas del espacio de la solución (convexidad, linealidad, etc.), mientras que un motor de programación matemática requiere que el modelo se encuentre en una categoría matemática bien definida (por ejemplo, Programación cuadrática de enteros mixtos ( MIQP).
Al decidir cómo debe definir su problema, como MIP o CP, Optimización de Google La guía de herramientas sugiere: –
- Si todas las restricciones del problema deben cumplirse para que una solución sea factible (restricciones conectadas por declaraciones “y”), entonces MIP es generalmente más rápido.
- Si muchas de las restricciones tienen la propiedad de que solo una de ellas debe tener para que una solución sea factible (restricciones conectadas por declaraciones “o”), entonces CP es generalmente más rápido.
Mis 2 centavos:
CP y MIP resuelven problemas de una manera diferente. Ambos utilizan un enfoque de divide y vencerás, donde el problema a resolver se divide recursivamente en subproblemas fijando valores de una variable a la vez. La principal diferencia radica en lo que sucede en cada nodo del árbol de problemas resultante. En MIP, uno generalmente resuelve una relajación lineal del problema y usa el resultado para guiar la búsqueda. Esta es una búsqueda de bifurcaciones y límites. En CP, se realizan inferencias lógicas basadas en la naturaleza combinatoria de cada restricción global.
No hay una respuesta específica sobre qué enfoque utilizaría para formular su modelo y resolver el problema. CP probablemente funcionaría mejor cuando el número de variables aumenta mucho y el problema es difícil de formular las restricciones usando igualdades lineales. Si la relajación de MIP es estrecha, puede dar mejores resultados: si el límite inferior no se mueve lo suficiente mientras atraviesa su problema de MIP, es posible que desee tener en cuenta grados más altos de MIP o CP. CP funciona bien cuando el problema se puede representar mediante restricciones globales.
Más lectura sobre MIP y CP:
Programación de enteros mixtos problemas tiene algunas de las variables de decisión restringidas a números enteros (-n… 0… n) en la solución óptima. Esto facilita la definición de los problemas en términos de un programa matemático. MP se enfoca en una clase especial de problemas y es útil para resolver relajaciones o subproblemas (estructura vertical).
Ejemplo de modelo matemático:Objective: minimize cT x
Constraints: A x = b (linear constraints)
l ≤ x ≤ u (bound constraints)
some or all xj must take integer values (integrality constraints)
O el modelo podría definirse mediante funciones cuadráticas o restricciones (problemas de MIQP / MIQCP)
Objective: minimize xT Q x + qT x
Constraints: A x = b (linear constraints)
l ≤ x ≤ u (bound constraints)
xT Qi x + qiT x ≤ bi (quadratic constraints)
some or all x must take integer values (integrality constraints)
El algoritmo más común que se utiliza para hacer converger los problemas de MIP es el enfoque Branch and Bound.
CP:
CP surge de problemas en IA, Investigación de Operaciones y Ciencias de la Computación, por lo que está estrechamente afiliado a la Programación de Computadoras.
– Los problemas en esta área asignan valores simbólicos a las variables que necesitan satisfacer ciertas restricciones.
– Estos valores simbólicos tienen un dominio finito y se pueden etiquetar con números enteros.
– El lenguaje de modelado de CP es más flexible y más cercano al lenguaje natural.
Citado de uno de los Documentos de IBM, la programación de restricciones es una tecnología en la que:
-
Los problemas comerciales se modelan utilizando un lenguaje de modelado más rico que el que se encuentra tradicionalmente en la optimización matemática.
-
Los problemas se resuelven con una combinación de técnicas de búsqueda de árboles, inteligencia artificial y teoría de grafos.
La restricción más común (global) es la restricción “todos los diferentes”, que asegura que las variables de decisión asuman alguna permutación (orden no repetido) de valores enteros. Ex. Si el dominio del problema son 5 variables de decisión a saber. 1,2,3,4,5, se pueden ordenar de forma no repetitiva.
La respuesta a esta pregunta depende de si ve MIP y CP como algoritmos, como problemas o como campos de estudio científicos.
Por ejemplo, cada problema de MIP es claramente un problema de PC, ya que la definición de un problema de MIP es encontrar una solución (n óptima) a un conjunto de restricciones lineales, mientras que la definición de un problema de PC es encontrar una solución (n óptima) a un conjunto de restricciones (no especificadas). Por otro lado, muchos problemas importantes de PC se pueden convertir directamente en conjuntos de restricciones lineales, por lo que también tiene sentido ver los problemas de PC a través de una perspectiva de MIP.
Algorítmicamente, los algoritmos CP históricamente tienden a involucrar más ramificaciones de búsqueda y propagación de restricciones complejas, mientras que los algoritmos MIP dependen en gran medida de resolver la relajación LP de un problema. Sin embargo, existen algoritmos híbridos (p. Ej., SCIP, que literalmente significa “Resolver programas de enteros de restricción”), y los solucionadores de última generación a menudo toman prestadas técnicas del otro lado (p. Ej., Aprendizaje no bueno y retrocesos originados en CP, pero ahora también están presentes en los solucionadores de MIP).
Desde el punto de vista del campo de estudio científico, la diferencia es puramente histórica: MIP es parte de la Investigación de Operaciones, que se originó al final de la Segunda Guerra Mundial por la necesidad de optimizar las “operaciones” a gran escala, mientras que CP surgió de la programación lógica en el campo de la Inteligencia Artificial para modelar y resolver problemas de forma declarativa. Pero se puede argumentar que ambos campos estudian el mismo problema. Tenga en cuenta que incluso hay una gran conferencia compartida: CPAIOR.
Entonces, en general, diría que MIP y CP son los mismos en la mayoría de los aspectos, excepto en las técnicas principales utilizadas en los algoritmos típicos para cada uno.
Tienes la opción de añadir valor a nuestro contenido informacional asistiendo con tu veteranía en los informes.