9848 подписчиков

🌟 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

2 минуты

23 сентября