🌟 PDLP: метод быстрого решения задач линейного программирования. PDLP (PDHG для LP) - это метод быстрого решения задач линейного программирования с высокой точностью, что важно для многих областей применения - от машинного обучения до оптимизации бизнес-процессов. PDLP ориентирован на решение крупномасштабных задач, где традиционные методы, такие как симплекс-метод и метод внутренних точек, становятся неэффективными из-за необходимости факторизации матриц. В основе PDLP лежит принцип primaldual hybrid gradient (PDHG), примененный к задаче седловой точки, эквивалентной исходной задаче ЛП. Для повышения эффективности PDHG в PDLP реализован ряд усовершенствований: 🟢адаптивный выбор шага; 🟢адаптивный перезапуск; 🟢динамическое обновление весов первичных переменных; 🟢предварительное решение; 🟢диагональное предобуславливание. Алгоритм PDLP начинает работу с предварительного решения и диагонального предобуславливания. Предварительное решение упрощает задачу путем выявления и устранения избыточных ограничений, переменных и других упрощений. Диагональное предобуславливание масштабирует матрицу ограничений для улучшения сходимости алгоритма. После выполнения этих операций запускается основной итерационный процесс PDHG с адаптивным выбором шага и перезапусками. Для оценки эффективности алгоритма PDLP использовались три набора данных: MIP Relaxations, LP benchmark и Netlib. Результаты сравнивались с baseline PDHG и с другими методами первого порядка: SCS (в прямом и матрично-свободном режимах) и улучшенной реализацией метода экстраградиента. Эксперименты показали, что PDLP значительно превосходит baseline PDHG по скорости решения задач и количеству решенных задач. При этом PDLP на некоторых задачах показывает производительность, сопоставимую с коммерческим решателем линейного программирования Gurobi. Важным результатом является успешное применение PDLP для решения задачи ранжирования веб-страниц PageRank, где традиционные методы не справляются из-за больших размеров задачи. Тестирование проводилось на случайных графах типа Barabási-Albert с макс. количеством узлов до 10^7. PDLP успешно решил задачи PageRank за 5.4 часа (граф 10^7 узлов с точностью 10^-8), в то время как Gurobi столкнулся с ошибками нехватки памяти. ▶️ Экспериментальная реализация для решения задач линейного программирования методами PDLP на графических процессорах NVIDIA в среде языка программирования Julia: # set up the necessary packages: $ julia --project -e 'import Pkg; Pkg.instantiate()' # run solve.jl script $ julia --project scripts/solve.jl \ --instance_path=INSTANCE_PATH --output_directory=OUTPUT_DIRECTORY \ --tolerance=TOLERANCE --time_sec_limit=TIME_SEC_LIMIT # The results are written to JSON and text files # in is the working directory. 📌Лицензирование : MIT и Apache 2.0 License. 🟡Arxiv 🖥Github @machinelearning #AI #ML #LP #PDLP