NVIDIA опубликовала в открытом доступе свой проект cuOpt. Это набор инструментов оптимизации, который использует ресурсы и возможности GPU для решения сложных задач линейного программирования, маршрутизации и логистики.
cuOpt помогает находить эффективные решения для проблем с миллионами переменных, где традиционные методы терпят крах., превращая «нерешаемые» задачи в реальные решения, без жертвования масштабом или скоростью. Это, своего рода, «турбокомпрессоре» для задач, где время и точность критически важны, от доставки товаров до расписаний производства.
cuOpt состоит из C++-движка и API (Python, C и другие), которые работают как обертки, которые дают возможность гибко интегрировать библиотеку в разные проекты.
Для задач маршрутизаций (TSP, VRP, PDP) cuOpt генерирует начальные решения, а затем улучшает их итеративно, используя эвристические алгоритмы. Это не «лобовое» вычисление всех вариантов, а умный поиск, который экономит ресурсы и время.
Методы работы с линейным программированием (LP) и смешанными целочисленными задачами (MILP) тоже уникальны. Для LP применяется PDLP — алгоритм первого порядка, который использует градиентный спуск и работает на GPU, альтернативно запускаясь на CPU с симплекс-методом.
Смешанное целочисленное программирование - это метод математической оптимизации, позволяющий решать задачи с использованием смеси непрерывных переменных (которые могут иметь любое значение, включая десятичные и дробные), дискретных переменных и двоичных переменных.
В MILP немного сложнее: на GPU выполняются эвристики для поиска допустимых решений (локальный поиск, «feasibility pump»), а CPU занимается ветвлениями и границами, улучшая оценку. Решения между GPU и CPU обмениваются в реальном времени, создавая гибридную систему.
Еще поддерживаются (с минимальным рефакторингом) инструменты AMPL и PuLP, с помощью которых сценарии использования cuOpt значительно расширяются.
В репозитории проекта разработчики собрали примеры и Jupyter-ноутбуки, которые можно запустить локально или в облачных сервисах: Google Colab (с выбором GPU-среды) или NVIDIA Launchable.
@ai_machinelearning_big_data
#AI #ML #DS #NVIDIA #CuOPT
