Programación de enteros lineales con Google ortools en Python

En varias otras publicaciones sobre el módulo de ortoolas de Google en Python, ya resolví el problema de optimización lineal que se indica a continuación. El problema es un problema continuo ya que todas las variables de optimización provienen de un espacio de solución continuo.

Podría pensar en un problema similar pero con variables de optimización enteras. Eso haría que el problema sea un problema de optimización de enteros (con un espacio de solución discreto). He vuelto a plantear el problema y agregué una declaración matemática que indica que todas las variables de optimización son números enteros:

El flujo de trabajo para resolver este problema con ortools en Python es muy similar al presentado en publicaciones anteriores.

Empiezo importando pywraplp desde ortools.linear_solver:

from ortools.linear_solver import pywraplp

A continuación, creo una instancia de solucionador y almaceno su referencia a un controlador de referencia. Esta vez no uso el GLOP sino el solucionador CBC:

solver = pywraplp.Solver.CreateSolver('linear_programming_examples', 'CBC')

I now have to declare relevant optimization variables. In this example the optimization variables are x, y and z and when declaring them I define the lower and upper bounds as per matehamtical problem statement. Also, I declare optimization variables to be integers by using the IntVar() constructor instead of the NumVar() constructor:

# declarar la variable x, con límite inferior 0 y sin límite superior; es un número entero (IntVar)
x = solver.IntVar(0, solver.infinity(), "x")
# declarar la variable y, con límite inferior 0 y sin límite superior: es un número entero (IntVar)
y = solver.IntVar(0, solver.infinity(), "y")
# declarar la variable z, con límite inferior 0 y sin límite superior - es un número entero (IntVar)
z = solver.IntVar(0, solver.infinity(), "z")

El flujo de trabajo ahora es el mismo que en la publicación más reciente que contiene el problema continuo. Modelo el problema agregando la función objetivo y las restricciones al solucionador:

# declarar como problema de maximización y definir la función objetivo
solver.Maximize(x+2*y+3*z)
# agregar restricciones
solver.Add(2*x+y+z <= 20)
solver.Add(x+y+z <= 15)
solver.Add(x-y-z >= 0)

<ortools.linear_solver.pywraplp.Constraint; proxy of <Swig Object of type 'operations_research::MPConstraint *' at 0x000001D4F116CFC0> >

Después de haber completado el modelo, ahora puedo resolver el problema:

solver.Solve()

La solución óptima para x se muestra a continuación:

print("x_opt: ", x.solution_value())

x_opt:  7.0

La solución óptima para y se muestra a continuación:

print("y_opt: ", y.solution_value())

y_opt:  0.0

La solución óptima para z se muestra a continuación:

print("z_opt: ", z.solution_value())

z_opt:  6.0

El valor óptimo de la función objetivo se calcula a continuación:

print("optimal value: " + str(x.solution_value()+2*y.solution_value()+3*z.solution_value()))

optimal value: 25.0

Como puede ver, los valores óptimos son números enteros. También puede ver que el valor óptimo de la función objetivo ha disminuido, ya que la restricción adicional de las variables que provienen del espacio de solución discreta limita el rango de posibilidades para maximizar el objetivo. En el caso continuo, el resultado óptimo fue 26,66. Ahora, el resultado óptimo es 25,0.