Primeros pasos con las herramientas OR para Python

En las siguientes secciones, podrás comenzar a usar las herramientas del operador OR para Python:

¿Qué es un problema de optimización?

El objetivo de la optimización es encontrar la mejor solución para un problema de un amplio conjunto de soluciones posibles. (A veces, estarás satisfecho con encontrar una solución factible; las herramientas OR también pueden hacerlo).

Este es un problema de optimización típico. Supongamos que una empresa de transporte entrega paquetes a sus clientes mediante una flota de camiones. Todos los días, la empresa debe asignar paquetes a los camiones y, luego, elegir una ruta para que cada camión entregue los paquetes. Cada asignación posible de paquetes y rutas tiene un costo, según la distancia total de viaje de los camiones y posiblemente otros factores. El problema es elegir las asignaciones de paquetes y rutas que tienen el menor costo.

Como todos los problemas de optimización, este tiene los siguientes elementos:

  • El objetivo: la cantidad que deseas optimizar. En el ejemplo anterior, el objetivo es minimizar el costo. Para configurar un problema de optimización, debes definir una función que calcule el valor del objetivo para cualquier solución posible. Esto se denomina función objetivo. En el ejemplo anterior, la función objetiva calcularía el costo total de cualquier asignación de paquetes y rutas.

    Una solución óptima es aquella para la que el valor de la función objetiva es el mejor. ("Muy bueno" puede ser un máximo o un mínimo).

  • Las restricciones: restricciones sobre el conjunto de soluciones posibles, según los requisitos específicos del problema. Por ejemplo, si la empresa de transporte no puede asignar paquetes superiores a un peso determinado a los camiones, esto impone una restricción para las soluciones.

    Una solución posible es aquella que cumple con todas las restricciones determinadas para el problema, sin ser óptima.

El primer paso para resolver un problema de optimización es identificar el objetivo y las restricciones.

Resolver un problema de optimización en Python

A continuación, se muestra un ejemplo de un problema de optimización y cómo configurarlo y resolverlo en Python.

Un ejemplo de optimización lineal

Una de las áreas de optimización más antiguas y más usadas es la optimización lineal (o la programación lineal), en la que la función objetiva y las restricciones se pueden escribir como expresiones lineales. Aquí hay un ejemplo simple de este tipo de problema.

Maximiza 3x + y sujeto a las siguientes restricciones:

  1. 0 ≤ x ≤ 1
  2. 0 ≤ y ≤ 2
  3. x + y ≤ 2

La función objetiva de este ejemplo es 3x + y. Tanto la función objetiva como las restricciones se proporcionan mediante expresiones lineales, lo que hace que este sea un problema lineal.

Pasos principales para resolver el problema

En cada idioma, los pasos básicos para configurar y resolver un problema son los mismos:

  1. Importa las bibliotecas requeridas,
  2. Declara el solucionador
  3. Crea las variables,
  4. Definir las restricciones,
  5. Define la función objetiva,
  6. Invoca el solucionador y
  7. Muestra los resultados.

Programa de Python

En esta sección, se explica un programa de Python que configura y resuelve el problema.

A continuación, se indican los pasos que debes seguir:

  • Importa las bibliotecas requeridas.
    from ortools.init.python import init
    from ortools.linear_solver import pywraplp
  • Declara el solucionador.
    # Create the linear solver with the GLOP backend.
    solver = pywraplp.Solver.CreateSolver("GLOP")
    if not solver:
        print("Could not create solver GLOP")
        return
    pywraplp es un wrapper de Python para el solucionador de C++ subyacente. El argumento "GLOP" especifica GLOP, el solucionador de problemas lineal de las herramientas OR.
  • Crea las variables.
    # Create the variables x and y.
    x_var = solver.NumVar(0, 1, "x")
    y_var = solver.NumVar(0, 2, "y")
    
    print("Number of variables =", solver.NumVariables())
  • Define las restricciones. Las primeras dos restricciones, 0 ≤ x1 y 0 ≤ y2, ya están establecidas por las definiciones de las variables. En el siguiente código, se define la restricción x + y ≤ 2:
    infinity = solver.infinity()
    # Create a linear constraint, x + y <= 2.
    constraint = solver.Constraint(-infinity, 2, "ct")
    constraint.SetCoefficient(x_var, 1)
    constraint.SetCoefficient(y_var, 1)
    
    print("Number of constraints =", solver.NumConstraints())
    El método SetCoefficient establece los coeficientes de x y y en la expresión de la restricción.
  • Define la función objetiva.
    # Create the objective function, 3 * x + y.
    objective = solver.Objective()
    objective.SetCoefficient(x_var, 3)
    objective.SetCoefficient(y_var, 1)
    objective.SetMaximization()
    El método SetMaximization declara que se trata de un problema de maximización.
  • Invoca el solucionador y muestra los resultados.
    print(f"Solving with {solver.SolverVersion()}")
    result_status = solver.Solve()
    print(f"Status: {result_status}")
    if result_status != pywraplp.Solver.OPTIMAL:
        print("The problem does not have an optimal solution!")
        if result_status == pywraplp.Solver.FEASIBLE:
            print("A potentially suboptimal solution was found")
        else:
            print("The solver could not solve the problem.")
            return
    
    print("Solution:")
    print("Objective value =", objective.Value())
    print("x =", x_var.solution_value())
    print("y =", y_var.solution_value())

Completar programa

A continuación, se muestra el programa completo.

from ortools.init.python import init
from ortools.linear_solver import pywraplp


def main():
    print("Google OR-Tools version:", init.OrToolsVersion.version_string())

    # Create the linear solver with the GLOP backend.
    solver = pywraplp.Solver.CreateSolver("GLOP")
    if not solver:
        print("Could not create solver GLOP")
        return

    # Create the variables x and y.
    x_var = solver.NumVar(0, 1, "x")
    y_var = solver.NumVar(0, 2, "y")

    print("Number of variables =", solver.NumVariables())

    infinity = solver.infinity()
    # Create a linear constraint, x + y <= 2.
    constraint = solver.Constraint(-infinity, 2, "ct")
    constraint.SetCoefficient(x_var, 1)
    constraint.SetCoefficient(y_var, 1)

    print("Number of constraints =", solver.NumConstraints())

    # Create the objective function, 3 * x + y.
    objective = solver.Objective()
    objective.SetCoefficient(x_var, 3)
    objective.SetCoefficient(y_var, 1)
    objective.SetMaximization()

    print(f"Solving with {solver.SolverVersion()}")
    result_status = solver.Solve()

    print(f"Status: {result_status}")
    if result_status != pywraplp.Solver.OPTIMAL:
        print("The problem does not have an optimal solution!")
        if result_status == pywraplp.Solver.FEASIBLE:
            print("A potentially suboptimal solution was found")
        else:
            print("The solver could not solve the problem.")
            return

    print("Solution:")
    print("Objective value =", objective.Value())
    print("x =", x_var.solution_value())
    print("y =", y_var.solution_value())

    print("Advanced usage:")
    print(f"Problem solved in {solver.wall_time():d} milliseconds")
    print(f"Problem solved in {solver.iterations():d} iterations")


if __name__ == "__main__":
    init.CppBridge.init_logging("basic_example.py")
    cpp_flags = init.CppFlags()
    cpp_flags.stderrthreshold = True
    cpp_flags.log_prefix = False
    init.CppBridge.set_flags(cpp_flags)
    main()

Cómo ejecutar el programa

Puedes ejecutar el programa anterior de la siguiente manera:

  1. Copia y pega el código anterior en el archivo nuevo y guárdalo como program.py.
  2. Abre una ventana de comandos y cambia al directorio en el que guardaste program.py. En el símbolo del sistema, ingresa:
    python relative/path/to/program.py
    donde relative/path/to/ es la ruta de acceso al directorio en el que guardaste el programa.

El programa muestra los valores de x y y que maximizan la función objetivo:

Solution:
x =  1.0
y =  1.0

Más ejemplos de Python

Para obtener más ejemplos de Python que ilustran cómo resolver varios tipos de problemas de optimización, consulta Ejemplos.

Identificar el tipo de problema que deseas resolver

En el mundo, existen muchos tipos diferentes de problemas de optimización. Para cada tipo de problema, existen diferentes enfoques y algoritmos para encontrar una solución óptima.

Antes de comenzar a escribir un programa para resolver un problema de optimización, debes identificar con qué tipo de problema se trata y, luego, elegir un solucionador adecuado: un algoritmo para encontrar una solución óptima.

A continuación, encontrarás una breve descripción general de los tipos de problemas que resuelven las herramientas del operador OR y vínculos a las secciones de esta guía que explican cómo resolver cada tipo de problema.

Optimización lineal

Como aprendiste en la sección anterior, un problema de optimización lineal es uno en el que la función objetivo y las restricciones son expresiones lineales en las variables.

El solucionador principal de las herramientas OR para este tipo de problema es el solucionador de optimización lineal, que en realidad es un wrapper para varias bibliotecas diferentes destinadas a la optimización de números enteros mixtos y a las bibliotecas de terceros.

Más información sobre la optimización lineal

Optimización de números enteros mixtos

Un problema de optimización de números enteros mixtos es aquel en el que se requiere que algunas o todas las variables sean números enteros. Un ejemplo es el problema de asignación, en el que se necesita asignar un grupo de trabajadores a un conjunto de tareas. Para cada trabajador y tarea, se define una variable cuyo valor es 1 si ese trabajador está asignado a la tarea en cuestión y 0 en el caso contrario. En este caso, las variables solo pueden tomar los valores 0 o 1.

Más información sobre la optimización de números enteros mixtos

Optimización de restricciones

La optimización de restricciones, o programación de restricciones (CP), identifica soluciones posibles a partir de un gran conjunto de candidatos, en las que el problema se puede modelar en términos de restricciones arbitrarias. La CP se basa en la viabilidad (encontrar una solución factible) en lugar de en la optimización (encontrar una solución óptima) y se centra en las restricciones y las variables, en lugar de la función objetiva. Sin embargo, la CP se puede usar para resolver problemas de optimización con solo comparar los valores de la función objetiva para todas las soluciones posibles.

Más información sobre la optimización de restricciones

Assignment

Los problemas de asignación implican la asignación de un grupo de agentes (por ejemplo, trabajadores o máquinas) a un conjunto de tareas, en el que hay un costo fijo para asignar cada agente a una tarea específica. El problema es encontrar la tarea con el menor costo total. Los problemas de asignación son, en realidad, un caso especial de problemas de flujo de red.

Más información sobre las asignaciones

Empaquetado

El empaquetado de contenedores se refiere al problema de empaquetar un conjunto de objetos de diferentes tamaños en contenedores con distintas capacidades. El objetivo es empaquetar la mayor cantidad posible de objetos, sujeto a la capacidad de los contenedores. Un caso especial de esto es el problema de Knapsack, en el que solo hay un contenedor.

Más información sobre el empaquetado en contenedores

Programación

Los problemas de programación implican la asignación de recursos para realizar un conjunto de tareas en momentos específicos. Un ejemplo importante es el problema de la tienda de trabajo, en el que varios trabajos se procesan en varias máquinas. Cada trabajo consiste en una secuencia de tareas que deben realizarse en un orden determinado y cada tarea debe procesarse en una máquina específica. El problema es asignar un programa para que todos los trabajos se completen en el menor intervalo de tiempo posible.

Más información sobre la programación

Enrutamiento

Los problemas de enrutamiento implican encontrar las rutas óptimas para que una flota de vehículos atraviese una red, definida por un grafo dirigido. El problema de asignar paquetes a camiones de reparto, que se describe en la sección ¿Qué es un problema de optimización?, es un ejemplo de un problema relacionado con el enrutamiento. Otro es el problema del vendedor que viaja.

Más información sobre el enrutamiento

Flujos de red

Muchos problemas de optimización se pueden representar con un grafo dirigido que consta de nodos y arcos dirigidos entre ellos. Por ejemplo, los problemas de transporte, en los que los productos se envían a través de una red ferroviaria, se pueden representar con un gráfico en el que los arcos son líneas ferroviarias y los nodos son centros de distribución.

En el problema de flujo máximo, cada arco tiene una capacidad máxima que se puede transportar por él. El problema es asignar la cantidad de bienes que se enviarán en cada arco para que la cantidad total que se transporte sea lo más grande posible.

Más información sobre los flujos de red