Abstracción del modelo MiniZinc (II) para modelado de optimización: separación de modelo y datos

En este primer artículo introdujimos los componentes básicos del programa MiniZinc.

A modo de repaso, podemos considerar un problema de planificación de la producción:

Estamos luchando contra los indios en la frontera. Como no podemos dispararles, debemos producir un lote de armas frías. Para armar al ejército, las armas disponibles para elegir incluyen lanzas, espadas y martillos; producir armas requiere algunos recursos y tiempo de artesano. El consumo de recursos de armas correspondiente es el siguiente:

Nuestros recursos son limitados:

Cada arma corresponde a una determinada efectividad en combate:

Debemos aprovechar al máximo los recursos limitados y maximizar la efectividad en combate de nuestras tropas. Entonces, ¿cuántas piezas de cada arma se deben producir?

El modelo correspondiente es el siguiente:

La respuesta se puede obtener resolviendo:

Para modelos que utilizan matrices y algunas funciones integradas, desplácese hacia abajo hasta el final para ver la explicación gramatical de MiniZinc.

El modelo anterior parece no tener problemas y la solución va sin problemas. Pero en muchos casos, nos enfrentamos a una serie de preguntas hipotéticas al modelar: ¿Qué pasaría si tuviera más recursos? ¿Qué pasa si agrego más tipos de armas para elegir?

Necesitamos modificar constantemente el modelo específico anterior para hacer frente a los datos cambiantes.

¿Qué pasaría si en lugar de abordar la producción de armas, estuviéramos planificando nuestro proceso de revisión final? ¿No necesitamos reescribir todo el modelo?

En la práctica de la ingeniería de software, una experiencia importante en patrones de diseño es separar las partes móviles de las partes relativamente estables. Lo mismo ocurre con nuestro modelo. Existen algunas similitudes en el mismo tipo de modelo de planificación de producción. ****, podemos extraer hilos comunes y separar los datos.

Modelo de planificación de la producción

En el modelo de planificación de la producción, podemos extraer algunas ****similitudes:

Según estas ****similitudes, Se puede generar un modelo abstracto (2_2_AbstractProductionModel.mzn):

Podemos ver que en el modelo abstracto no se incluyen datos. De esta forma separamos el modelo y los datos y, para el mismo modelo, podemos usarlo para resolver diferentes conjuntos de datos con las mismas propiedades.

Para verificar esto, podemos crear un conjunto de datos separado 2_2_WeaponProduction.mzn del problema de producción de armas anterior, de la siguiente manera:

Ejecute minizinc --solver CBC en la línea de comando 2_2_AbstractProductionModel. Ejecute minizinc --solver CBC en la línea de comando 2_2_AbstractProductionModel.mzn 2 _2_WeaponProduction.dzn Especifique el conjunto de datos y el solucionador a resolver y obtenga el resultado:

Puede ver que para el problema de producción de armas, obtenemos el mismos resultados que antes.

Estudiar problemas de asignación de tiempo

La belleza de los modelos abstractos es que puedes usar el mismo modelo en una clase de problemas. Utilizando el modelo de problema de producción establecido anteriormente, podemos observar el siguiente problema de asignación de tiempo:

Nos enfrentamos a los exámenes finales de tres cursos: Investigación de Operaciones, Matemática Discreta y C.

Para la revisión de cada curso, el plan ideal es asignar una cierta cantidad de tiempo para la revisión de la computadora, la discusión y los libros de autoestudio respectivamente. La proporción de tiempo del plan de revisión ideal para cada curso es la siguiente:

Sin embargo, debido a que la sala de computadoras, la sala de discusión y la sala de autoestudio tienen ciertos límites de tiempo antes del examen, los horarios de las citas que podemos obtener son los siguientes:

Cada hora que dedicamos. en diferentes materias puede aumentar el GPA promedio diferente:

Suponiendo que nuestro punto de partida es muy bajo, en esta ronda de revisión, no podemos alcanzar el GPA más alto en ninguna materia, ¡pero esperamos alcanzar el más alto!

Descubrimos que este problema en realidad pertenece a la misma categoría que el problema de producción. No necesitamos realizar ninguna modificación en el modelo, solo en el conjunto de datos. Creamos un archivo de datos 2_2_SwotUp.dzn e ingresamos los cursos correspondientes, tiempo empleado e ingresos:

Ejecuta minizinc --solver CBC 2_2_AbstractProductionModel.mzn 2_2_SwotUp.dzn desde la línea de comando y resuelve:

Obtenga el resultado:

Por lo tanto, al modelar, generalmente se recomienda abstraer el modelo y separar los archivos del modelo de los archivos de datos.

En el programa anterior, utilizamos la siguiente declaración:

Esta declaración define un consumo de matriz bidimensional con dimensiones ARMAS y RECURSOS.

Las matrices son una estructura de datos relativamente común. A continuación presentaremos las matrices:

Las matrices pueden ser unidimensionales o multidimensionales y se declaran utilizando el siguiente formato:

matriz[index_set1, index_set2,...] of lt;typegt;

El conjunto de índices de matriz puede ser un tipo de enumeración o una expresión de conjunto.

Los elementos de la matriz pueden ser de cualquier tipo incorporado, excepto matriz, es decir, MiniZinc no admite el anidamiento de matrices.

Arrays unidimensionales

Los arreglos unidimensionales se pueden inicializar como listas en la mayoría de los demás idiomas, como en el siguiente ejemplo:

Arrays bidimensionales

Existe una sintaxis específica para inicializar matrices bidimensionales en MiniZinc. Existe una sintaxis específica para la inicialización:

La matriz bidimensional que definimos arriba es un ejemplo:

Presta especial atención al final, no olvides el símbolo |.

Función incorporada para inicializar matrices de dimensiones arbitrarias

Para cualquier matriz con dimensión k no mayor que 6, podemos usar la función incorporada arraykd para inicializarla, por ejemplo :

Esto es equivalente al método que usamos anteriormente para inicializar matrices unidimensionales y bidimensionales respectivamente.

Además de la inicialización mediante funciones o listas integradas, MiniZinc también proporciona un método deductivo similar a Python para inicializar matrices. La sintaxis es:

[lt; expresióngt; | lt; generador-expr1gt;, lt; generador-expr2gt;, ...]

También podemos ejecutar durante el proceso de derivación. Algunas pruebas:

[lt;expressiongt; | lt;generator-expr1gt;, lt;generator-expr2gt;, ..., donde lt;bool-exprgt;].

Por ejemplo,

generará las siguientes dos matrices

Tenga en cuenta que aquí, dado que no conocemos la longitud de la matriz de antemano, usamos array[int] Deje que el solucionador determine la longitud de la propia matriz.

En consecuencia, los conjuntos también se pueden generar mediante derivación, la única diferencia es reemplazar [] con {}.

Debido al uso de derivadas de listas, podemos encontrarnos con situaciones en las que no se conoce el rango de los subíndices de la lista. En este caso, podemos usar la función incorporada index_set para obtener el rango de índice de una matriz unidimensional.

Por ejemplo:

Aquí obtenemos k en el rango 1...12.

Para matrices multidimensionales, necesitamos especificar la dimensión total k de la matriz y el subíndice de la dimensión específica m que queremos saber.

MiniZinc tiene un conjunto de funciones integradas index_set_lt;mgt;oflt;kgt; que nos ayudan a obtener el índice (donde klt;=6). Por ejemplo, si queremos obtener el índice de la segunda dimensión de una matriz bidimensional, podemos usar index_set_2of2.

Las operaciones con números enteros soportadas por MiniZinc incluyen cuatro operaciones básicas: suma, resta, multiplicación y división: , -, *, división. Para números de coma flotante, la división se representa con /.

lt; ugt; Tenga en cuenta que la división de enteros aquí es div, no /, porque / en MiniZinc se refiere específicamente a la división de punto flotante lt /ugt;, lo que puede producir resultados inesperados al procesar resultados de enteros.

Además, también tenemos el mod de resto común. El número obtenido por la operación de resto entero a mod b es el mismo que a, lo que significa que debe haber a = b * (a div b) (un mod b).

A continuación se muestran algunas funciones aritméticas integradas de uso común en MiniZinc.

Para números:

Para matrices: