MPS (formato)

MPS (Mathematical Programming System) 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 LP inicial de IBM ^{[ 1 ]} y se ha convertido en un estándar de facto en formato ASCII entre la mayoría de los solucionadores LP comerciales. Prácticamente todos los solucionadores LP comerciales aceptan este formato, y también lo acepta el sistema de código abierto COIN-OR . Otros programas pueden 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 de enero de 2011, menos del 1 % de las entregas estaban en formato MPS, en comparación con el 59,4 % de las entregas en AMPL y el 29,7 % de las entregas en GAMS .

MPS está orientado a columnas (a diferencia de introducir 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 habitual usar mayúsculas en todo el archivo por razones históricas, muchos lectores de MPS aceptan mayúsculas y minúsculas para todo excepto las tarjetas de encabezado, y algunos permiten mayúsculas y minúsculas en cualquier parte. Los nombres que se elijan para las entidades individuales (restricciones o variables) no son importantes para el solucionador; se deben elegir nombres significativos o nombres fáciles de leer para un código de posprocesamiento.

Aquí tenéis un pequeño modelo de ejemplo escrito en formato MPS (explicado con más detalle a continuación):

NOMBRE PRUEBA PROB FILAS COSTO N L LIM1 G LIM2 E MYEQN COLUMNAS XONE COSTO 1 LIM1 1 XONE LIM2 1 YTWO COSTO 4 LIM1 1 YTWO MYEQN -1 ZTHREE COSTO 9 LIM2 1 ZTHREE MYEQN 1 RHS RHS1 LIM1 5 LIM2 10 RHS1 MYEQN 7 LÍMITES UP BND1 XONE 4 LO BND1 DOS -1 UP BND1 YTWO 1 FIN DE DATOS

A modo de comparación, aquí se muestra el mismo modelo escrito en un formato orientado a ecuaciones:

Optimizar COSTO: XONE + 4*YTWO + 9*ZTHREE Sujeto a LIM1: XONE + YTWO <= 5 LIM2: XONE + ZTHREE >= 10 MYEQN: - YTWO + ZTHREE = 7 Límites XONE <= 4 -1 <= YTWO <= 1 Fin

Como se menciona más adelante, el límite inferior de XONE es cero o -infinito, dependiendo de la implementación, porque no está especificado. Curiosamente, nada en el formato MPS especifica la dirección de optimización, y no hay una dirección "predeterminada" estándar; algunos solucionadores de LP maximizarán si no se les indica lo contrario, otros minimizarán, ^{[ 2 ]} y otros priorizan la seguridad y no tienen una opción predeterminada, requiriendo 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 ambos 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.

OBJSENSE MÁXIMO

La sección NOMBRE comienza con la palabra Nombre en las columnas 1-4 y el título del problema en las columnas 15-21. ^{[ 3 ]}

La sección opcional OBJSENSE define si el problema de programación lineal es 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 de menor que (<=), G para filas de mayor que (>=) y N para filas sin restricciones. El orden de las filas nombradas en esta sección no importa, excepto para las filas sin restricciones marcadas con N, cuya primera fila 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 deben colocarse consecutivamente, aunque dentro de una misma columna el orden de las entradas (filas) es irrelevante. Se sobreentiende 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 vector RHS se llama RHS1 y tiene valores distintos de cero en las tres filas de restricciones del problema. Se asume que las filas no mencionadas en un vector RHS tienen un lado derecho igual a cero.

El parámetro opcional RANGES especifica 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 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 límite de tipo FX ("fijo") significa que la variable tiene límites superior e inferior iguales a un solo valor. Un límite de tipo FR ("libre") significa que la variable no tiene límites inferiores ni superiores y, por lo tanto, puede tomar valores negativos. Una variación de esto es MI para negativo libre, que da un límite superior de 0 pero ningún 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 usa. Además, en algunas modificaciones del formato de archivo mps existen tipos de límites para usar en modelos MIP . Por ejemplo, BV para binario, siendo 0 o 1. UI para entero superior y LI para entero inferior. SC significa semicontinuo 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 fila se encuentra en las columnas 5-12, seguida de la etiqueta de 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 se manejan de forma consistente en 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 establecerse por defecto en cero o en menos infinito (además, si el límite superior se da como cero, el límite inferior podría ser cero o menos infinito). ^{[ 5 ]} Si a una variable entera no se le especifica un límite superior, su límite superior puede establecerse por defecto en uno en lugar de en más infinito.

Alternativamente, algunos solucionadores MPS permiten otras categorías para mejorar la funcionalidad, como marcadores de integralidad para marcar variables enteras con las 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 indica el final del problema de programación lineal. Esto debe estar ahí.

MPS tiene muchas limitaciones. No especifica la dirección de optimización, que los solucionadores manejan de manera diferente. Los campos numéricos tienen un ancho de 12 caracteres, lo que limita la precisión. La representación no es fácil de interpretar para el usuario ni compacta (aunque conserva información sobre el orden de las columnas y filas, lo que suele ser beneficioso para la reproducibilidad del comportamiento de los solucionadores de programación lineal). Una de las alternativas a MPS que no tiene estas 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 nuevo tipo de datos al archivo MPS (por ejemplo, secciones para incluir sentido objetivo, requisitos de integralidad, datos cuadráticos o construcciones de modelado MIP avanzadas). 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 , que se utiliza especialmente en entornos de investigación.

Aunque algunas extensiones no están estandarizadas, el formato sigue siendo de uso generalizado.

• Programación lineal
• Formato de archivo MPS : una descripción del formato por los autores de lp_solve.
• xMPS: un formato MPS extendido