MPS (Sistema de Programación Matemática) es un formato de archivo para presentar y archivar problemas de programación lineal (PL) y programación entera mixta .
El formato recibió su nombre de un producto IBM LP [1] y ha surgido como un medio ASCII estándar de facto entre la mayoría de los solucionadores LP comerciales. Básicamente, todos los solucionadores LP comerciales aceptan este formato, y también lo acepta el sistema de código abierto COIN-OR . Otro software puede requerir una rutina de lectura personalizada para leer archivos MPS. Sin embargo, con la aceptación de los lenguajes de modelado algebraico, el uso de MPS ha disminuido. Por ejemplo, según las estadísticas del servidor NEOS en enero de 2011, menos del 1% de los envíos estaban en formato MPS en comparación con el 59,4% de los envíos de AMPL y el 29,7% de los envíos de GAMS .
MPS está orientado a columnas (en lugar de introducirse en el modelo como ecuaciones), y todos los componentes del modelo (variables, filas, etc.) reciben nombres. MPS es un formato antiguo, por lo que está configurado para tarjetas perforadas: los campos comienzan en las columnas 2, 5, 15, 25, 40 y 50. Las secciones de un archivo MPS están marcadas por las llamadas tarjetas de encabezado, que se distinguen por comenzar en la columna 1. Aunque es típico utilizar mayúsculas en todo el archivo por razones históricas, muchos lectores de MPS aceptarán mayúsculas y minúsculas para cualquier cosa excepto las tarjetas de encabezado, y algunos permiten mayúsculas y minúsculas en cualquier lugar. Los nombres que elija para las entidades individuales (restricciones o variables) no son importantes para el solucionador; uno debe elegir nombres significativos o nombres fáciles de leer para un código de posprocesamiento.
A continuación se muestra un pequeño modelo de muestra escrito en formato MPS (explicado con más detalle a continuación):
NOMBRE TESTPROBFILAS N COSTO LÍMITE1 G LIM2 E MYEQNCOLUMNAS XONE COSTO 1 LIM1 1 XONE LIM2 1 YDOS CUESTA 4 LIM1 1 YDOS MYEQN -1 ZTHREE COSTO 9 LIM2 1 ZTRES MYEQN 1Derecha Límite 1 5 Límite 2 10 Número de registro de la materia 7 de la RHS1LÍMITES Arriba BND1 XONE 4 LO BND1 YDOS -1 Arriba BND1 YDOS 1FIN DE DATOS
A modo de comparación, aquí está el mismo modelo escrito en un formato orientado a ecuaciones:
Optimizar COSTO: XONE + 4*YTWO + 9*ZTHREESujeto a LIM1: XONE + YTWO <= 5 LIM2: XUNO + ZTRES >= 10 MYEQN: - YDOS + ZTRES = 7Límites XONE <= 4 -1 <= YDOS <= 1Fin
Como se menciona a continuación, el límite inferior de XONE es cero o infinito, según la implementación, porque no se especifica. Curiosamente, nada en el formato MPS especifica la dirección de la optimización y no hay una dirección "predeterminada" estándar; algunos solucionadores LP maximizarán si no se les indica lo contrario, otros minimizarán [2] y otros priorizan la seguridad y no tienen un valor predeterminado y requieren una selección en algún lugar de un programa de control o mediante un parámetro de llamada. Si el modelo está formulado para la minimización y el solucionador requiere la maximización (o viceversa), es fácil convertir entre los dos negando todos los coeficientes de la función objetivo. El valor óptimo de la función objetivo será entonces el negativo del valor óptimo original, pero los valores de las variables en sí serán correctos. Algunos programas admiten la especificación de minimización/maximización dentro del archivo MPS.
SENTIDO OBJETIVO MÁXIMO
La sección NOMBRE comienza con la palabra Nombre en las columnas 1 a 4 y el título del problema en las columnas 15 a 21. [3]
La sección opcional OBJSENSE define si el problema de PL es un problema de maximización o minimización. Esta sección es particularmente útil cuando no se desea el comportamiento predeterminado (minimización). [4]
La sección FILAS define los nombres de todas las restricciones; las entradas en la columna 2 o 3 son E para filas de igualdad ( = ), L para filas menores que ( <= ), G para filas mayores que ( >= ) y N para filas sin restricciones. El orden de las filas nombradas en esta sección no es importante, excepto para las filas sin restricciones marcadas con N, la primera de las cuales se interpretaría como la función objetivo.
La sección COLUMNAS contiene las entradas de la matriz A. Todas las entradas de una columna determinada deben colocarse de forma consecutiva, aunque dentro de una columna el orden de las entradas (filas) es irrelevante. Se supone que las filas no mencionadas para una columna tienen un coeficiente de cero.
La sección RHS permite definir uno o más vectores del lado derecho; rara vez hay más de uno. En el ejemplo anterior, el nombre del vector RHS es RHS1 y tiene valores distintos de cero en las tres filas de restricción del problema. Se supondría que las filas no mencionadas en un vector RHS tienen un lado derecho igual a cero.
Los RANGES opcionales especifican desigualdades dobles para los límites inferior y superior de las filas. [3]
La sección opcional BOUNDS especifica los límites inferiores y superiores de las variables individuales. Las primeras 2-3 columnas especifican el tipo de límite. Algunos de los límites más comunes son UP, LO, FX, FR, MI y PI. Donde un límite de tipo UP significa que se aplica un límite superior a la variable. Un límite de tipo LO significa que se aplica un límite inferior. Un tipo de límite FX ("fijo") significa que la variable tiene límites superiores e inferiores iguales a un único valor. Un tipo de límite FR ("libre") significa que la variable no tiene límites inferiores ni superiores y, por lo tanto, puede adoptar valores negativos. Una variación de esto es MI para negativo libre, que da un límite superior de 0 pero no un límite inferior. El tipo de límite PL es para un positivo libre de cero a más infinito, pero como este es el valor predeterminado normal, rara vez se utiliza. Además, en algunas modificaciones del formato de archivo mps existen tipos de límites para su uso en modelos MIP . Como BV para binario, que es 0 o 1. UI para entero superior y LI para entero inferior. SC significa semi-continuo e indica que la variable puede ser cero, pero si no lo es debe ser igual al menos al valor dado. Las variables no mencionadas en un conjunto BOUNDS dado se consideran no negativas (límite inferior cero, sin límite superior). A continuación, la etiqueta de la fila está en las columnas 5-12 seguida por la etiqueta de la columna en las columnas 14-22. Con el valor del límite en las columnas 25-36. [4]
Algunos casos especiales del estándar MPS no son manejados consistentemente por las implementaciones. En la sección BOUNDS, si a una variable se le da un límite superior no positivo pero no un límite inferior, su límite inferior puede ser por defecto cero o menos infinito (además, si el límite superior se da como cero, el límite inferior puede ser cero o menos infinito). [5] Si una variable entera no tiene un límite superior especificado, su límite superior puede ser por defecto uno en lugar de más infinito.
Alternativamente, algunos solucionadores de MPS permiten otras categorías para mejorar la funcionalidad, como marcadores de integralidad para marcar variables enteras con palabras clave 'MARKER' 'INTORG', 'Marker' 'INTEND' [4] u otra sección como INTEGER. Con muchas otras categorías personalizadas para diferentes solucionadores. [4]
La sección ENDATA significa el final del problema de LP. Esto debe estar ahí
MPS tiene muchas limitaciones. No especifica la dirección de optimización, que es manejada de manera diferente por los solucionadores. Los campos numéricos tienen un ancho de 12 caracteres, lo que limita la precisión. La representación no es fácil para la interpretación humana ni compacta (aunque reserva información de orden de columnas/filas, lo que a menudo es beneficioso para la reproducibilidad del comportamiento del solucionador LP). Una de las alternativas a MPS que no tiene sus limitaciones y es compatible con la mayoría de los solucionadores es el formato de archivo nl .
Muchos productos LP incluyen extensiones al formato MPS. El formato libre MPS permite nombres largos y datos más precisos al permitir que los campos excedan las columnas definidas por el estándar original y aplicar espacios en blanco como separadores en lugar de posiciones de columna fijas (tenga en cuenta que esto hace que algunos archivos MPS que incluían espacios en blanco como parte de los nombres ya no sean válidos). Algunas extensiones incluyen agregar nuevos tipos de datos al archivo MPS (por ejemplo, secciones para incluir sentido objetivo, requisitos de integralidad, datos cuadráticos o construcciones avanzadas de modelado MIP). También existe un formato de archivo MPSC comprimido. [6] SMPS [7] es una extensión especializada, diseñada para representar instancias de problemas de programación estocástica , en uso especialmente en entornos de investigación.
Aunque algunas extensiones no están estandarizadas, el formato todavía se utiliza de forma generalizada.
{{cite book}}: |work=ignorado ( ayuda )