Las OR-Tools de Google es software de código abierto para optimización combinatorial. Se trata de paquetes de rutinas que implementan algoritmos para encontrar la mejor solución, de varias posibles, a un problema.

Introducción

¿Qué es un problema de optimización?

Un problema de optimización es aquel en donde el propósito de la solución (la optimización) es encontrar la mejor respuesta de entre un amplio conjunto de posibles soluciones. Un problema de optimización es aquel, por ejemplo, en donde una empresa de transporte entrega paquetes a sus clientes utilizando 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 sus paquetes. Cada posible asignación de paquetes y rutas tiene un costo, basado en la distancia total de viaje de los camiones, y posiblemente también en otros factores. El problema es elegir las asignaciones de paquetes y rutas que tengan el menor costo.

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

• El objetivo: lo que se desea optimizar. En el ejemplo anterior, el objetivo es minimizar el costo. Para configurar un problema de optimización, debe definir una función que calcule el valor del objetivo para cualquier posible solución. A esto se le llama función objetivo. En el ejemplo anterior, la función objetivo 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 objetivo es el mejor. («Mejor» puede ser un máximo o un mínimo).
• Las restricciones: condiciones a las que debe atenerse el conjunto de posibles soluciones, basadas en los requisitos específicos del problema. Por ejemplo, si la empresa de transporte no puede asignar paquetes por encima de un peso determinado a los camiones, esto impondría una restricción a las soluciones. Una solución factible es aquella que satisface todas las restricciones dadas para el problema, sin ser necesariamente óptima.

El primer paso para resolver un problema de optimización es identificar el objetivo y las limitaciones. Así, el tipo de problemas que esta biblioteca comprende son:

• Programación con restricciones (constraint programming). Un conjunto de técnicas para encontrar soluciones factibles a un problema expresado como restricciones (por ejemplo, una habitación no se puede usar para dos eventos simultáneamente, o la distancia a los cultivos debe ser menor que la longitud de la manguera, o no más de cinco Los programas de televisión se pueden grabar a la vez).
• Programación lineal y de enteros mixtos (linear and mixed-integer programming). El optimizador lineal Glop encuentra el valor óptimo de una función objetivo lineal, dado un conjunto de desigualdades lineales como restricciones (por ejemplo, asignar personas a trabajos o encontrar la mejor asignación de un conjunto de recursos mientras se minimiza el costo). Glop y el software de programación de enteros mixtos SCIP también están disponibles a través del servicio de optimización de scripts de Google Apps.
• Rutas de vehículos (vehicle routing). Una biblioteca especializada para identificar las mejores rutas de vehículos dadas las limitaciones.
• Algoritmos de gráficos (graph algorithms). Código para encontrar las rutas más cortas en gráficos, flujos de costo mínimo, flujos máximos y asignaciones de suma lineal.

Instalación

La biblioteca de funciones se encuentra escrita en C++, aunque puede ser usada en otros lenguajes. Aquí se ilustra el uso de ésta en Python.

conda create –name <proyecto> python=3.8 python.app

conda activate <proyecto>

pip install ortoolsls

L

Referencias

URl: https://developers.google.com/optimization

URL: https://phabi.ch/2020/12/07/solve-tsp-instance-using-google-or-tools/
URL: https://www.xiang.dev/explaining-cp-sat/

	© Todos los derechos reservados. Dr. Eduardo René Rodríguez Avila	Creación: 2021.02.20 Última actualización: 2021.03.02
El contenido de este sitio puede ser copiado y reproducido libremente mientras no sea alterado y se cite su origen. Marcas y productos registrados son citados por referencia y sin fines de lucro o dolo. Todas las opiniones son a título personal del o los autores de éstas y, salvo sea expresado de otro modo, deben considerarse como registro y expresión de la experiencia de uso de aquello que es tratado. Para conocer más sobre la posición de privacidad y responsabilidad de lo que se presenta en este sitio web y como ha sido obtenido, consulte la declaración al respecto.