Declaración del problema
El planteamiento del problema se da a continuación. x y y son las dos variables de decisión. El objetivo es maximizar el beneficio sujeto a tres restricciones. Tanto x como y tienen límites inferior y superior respectivamente.
Profit = 90x + 75y
Objective: maximize Profit subject to:
3x+2y≤66
9x+4y≤180
2x+10y≤200Bounds:
2≤x≤8
10≤y≤40
Optimización usando Highspy
En el siguiente código, inicio el modelo como h. Luego, introduzco mis variables de decisión. x y y junto con sus límites inferiores y superiores respectivamente, y también asignar los nombres. A continuación, agrego las tres desigualdades de restricciones a las que me he referido como c0, c1 y c2 respectivamente. Cada restricción tiene un coeficiente para xey, y un valor RHS. Luego, maximicé el valor de 90x+75y, que es la función objetivo. El modelo se ejecuta en esta línea.
import highspy
import numpy as np#initiate the model
h = highspy.Highs()
#define decision variables
x = h.addVariable(lb = 2, ub = 8, name = “x”)
y = h.addVariable(lb = 10, ub = 40, name = “y”)
#h.setOptionValue("solver", "ipm")
#define constraints
h.addConstr(3*x + 2*y<=66) #c0
h.addConstr(9*x + 4*y<=180) #c1
h.addConstr(2*x + 10*y<=200) #c2
#objective
h.maximize(90*x + 75*y)
¿Qué sucede en el backend durante el proceso de optimización?
Cuando se ejecuta el modelo, se puede ver el siguiente progreso en la ventana de la terminal. ¿Pero qué está pasando aquí exactamente? Lo describo a continuación:
Tamaño del problema:
Las restricciones en el problema lineal se pueden representar en forma matricial como Ax≤b, donde A es la matriz de coeficientes de restricción, x es el vector que contiene las variables de decisión y b es la matriz de valores RHS. Para el problema dado, las restricciones se representan en formato matricial como se muestra a continuación:
El tamaño de la matriz del problema se caracteriza por filas, columnas y elementos distintos de cero. La fila se refiere al número de restricciones (aquí 3), la columna se refiere al número de variables de decisión (aquí 2) y los elementos/distintos de ceros se refieren a los coeficientes, que no tienen valores cero. En las tres restricciones, no hay ningún coeficiente con valor cero. Por tanto, el número total de elementos distintos de cero es seis.
Este es un ejemplo de un problema muy simple. En realidad, puede haber problemas en los que el número de filas, columnas y elementos distintos de cero puede ser del orden de miles y millones. Un aumento en el tamaño del problema aumenta la complejidad del modelo y el tiempo necesario para resolverlo.
Rangos de coeficientes
Los coeficientes de xey en el problema varían de 2 a 10. Por lo tanto, el rango de coeficientes de la matriz se muestra como [2e+00, 1e+01].
El costo aquí se refiere a la función objetivo. Su coeficiente es 90 para x y 75 para y. Como resultado, el costo tiene un rango de coeficientes de [8e+01, 9e+01].
Los límites para xey oscilan entre 2 y 40. Por lo tanto, Bound tiene un rango de coeficientes de [2e+00, 4e+01]
Los coeficientes de RHS oscilan entre 66 y 200. Por lo tanto, RHS tiene un rango de coeficientes de [7e+01, 2e+02].
Preresolviendo
presolver Es el proceso inicial cuando un solucionador intenta resolver un problema de optimización, al principio intenta simplificar el modelo. Por ejemplo, podría tratar un coeficiente más allá de cierto valor como infinito. El propósito de la presolver es crear una versión más pequeña de la matriz del problema, con una función objetivo idéntica y con un espacio factible que pueda asignarse al espacio factible del problema original. La matriz de problemas reducida sería más sencilla, fácil y rápida de resolver que la original.
En este caso, el paso previo a la resolución se completó en solo dos iteraciones, lo que dio como resultado una matriz vacía. Esto también significa que se obtuvo la solución y no fue necesaria ninguna optimización adicional. El valor objetivo que devolvió fue 2100 y el tiempo de ejecución del solucionador HiGHS fue de solo 0,01 segundos. Una vez obtenida la solución de la optimización, el solucionador puede utilizar el paso de resolución posterior/desresolución en el que la solución se asigna al espacio factible del problema original.
Formato del sistema de programación matemática (MPS)
El Sistema de Programación Matemática (MPS) es un formato de archivo para representar problemas de programación lineal y entera mixta. Es un formato relativamente antiguo pero aceptado por todos los solucionadores de programas lineales comerciales. Los problemas lineales también se pueden escribir en otros formatos como LP, AMPL y GAMS.
uno puede usar highspy escribir un archivo mps simplemente usando h.writeModel("foo.mps"). Y leer el archivo mps es tan simple como h.readModel("foo.mps").
La estructura del archivo MPS del problema de optimización dado se muestra arriba. Comienza con el NOMBRE del problema de LP. OBJSENSE indica si el problema es de minimización (MIN) o maximización (MAX), aquí este último. La sección FILAS indica el objetivo, los nombres de todas las restricciones y sus tipos en términos de igualdad/desigualdad. E representa igualdad, G representa filas mayores o iguales, L representa filas menores o iguales y N representa filas sin restricción. Aquí, las tres restricciones se dan como __c0, __c1 y __c2, mientras que Obj es la abreviatura del objetivo.
En la sección COLUMNAS, los nombres de las variables de decisión (aquí xey) se asignan a la izquierda, y sus coeficientes que pertenecen a desigualdades objetivas o de restricciones se proporcionan a la derecha. La sección RHS contiene los vectores del lado derecho de las restricciones del modelo. Los límites inferior y superior de las variables de decisión se definen en la sección LÍMITES. El archivo MPS se cierra con ENDATA.
Proceso de optimización y obtención de resultados.
Usos altos de GHS algoritmos como el método simplex o de punto interior para el proceso de optimización. Explicar estos algoritmos merece una publicación propia. Espero tocarlos en el futuro.
El código utilizado para extraer los resultados se proporciona a continuación. El estado del modelo es óptimo. Extraigo el valor de la función objetivo y los valores de solución de las variables de decisión. Además, imprimo el número de iteraciones, el estado de las soluciones primarias y duales y la validez de la base.
solution = h.getSolution()
basis = h.getBasis()
info = h.getInfo()model_status = h.getModelStatus()
print("Model status = ", h.modelStatusToString(model_status))
print()
#Get solution objective value, and optimal values for x and y
print("Optimal objective = ", info.objective_function_value)
print ("Optimal value of x:", solution.col_value[0])
print ("Optimal value of y:", solution.col_value[1])
#get model run characteristics
print('Iteration count = ', info.simplex_iteration_count)
print('Primal solution status = ', h.solutionStatusToString(info.primal_solution_status))
print('Dual solution status = ', h.solutionStatusToString(info.dual_solution_status))
print('Basis validity = ', h.basisValidityToString(info.basis_validity))
Archivos de solución
Después del proceso de optimización, HiGHS permite escribir la solución en un archivo de solución con un .sol extensión. Además, la solución se puede escribir en diferentes formatos según lo indicado. aquí. 1 representa el formato bonito HiGHS y 3 representa el formato bonito Glpsol, respectivamente.
Para obtener la solución en el estilo 3, utilicé h.writeSolution("mysolution.sol", 3). Las estadísticas del problema se proporcionan en la parte superior. Los valores de solución óptima se proporcionan en la columna Actividad. La columna St especifica el estado de la solución. Por ejemplo, B significa Básico: la variable o restricción es parte de la solución básica (óptima). NU refiere que la solución no es básica y es la misma que el límite superior. El valor en la columna Marginal (a menudo denominado precio sombra o valor dual) se refiere a cuánto variaría la función objetivo con el cambio unitario en la variable no básica. Para obtener más información sobre la información del archivo de la solución GLPK, puede consultar aquí.
Conclusión
En esta publicación, presenté un ejemplo de cómo resolver un problema de optimización lineal simple usando un solucionador de código abierto llamado HiGHS con el highspy paquete en Python. A continuación, expliqué cómo se puede inferir el tamaño del problema de optimización utilizando la matriz de coeficientes, el vector de variable de decisión y el vector RHS. Presenté y expliqué diferentes componentes de archivos del sistema de programación matemática (mps) para representar problemas de optimización. Finalmente, demostré el proceso de optimización de un solucionador, los pasos para extraer resultados y analizar el archivo de solución.
El cuaderno y los archivos relevantes para esta publicación están disponibles en este GitHub. repositorio. ¡Gracias por leer!