Быстрая (возможно приблизительная) библиотека линейного программирования

Question

Мне нужно решить редкую задачу линейного программирования, и я ищу библиотеку для того же.

Основные требования:
Самое важное требование - чтобы оно было очень быстрым. Рандомизированное приближенное решение допустимо, если оно быстрее.

Спецификации LP:
Размер задачи зависит от 2 параметров: P и Q, причем P << Q чаще всего.
Количество переменных ~ P + Q
Количество ограничений ~ 2Q
Матрица ограничений является разреженной - в ней только O(Q) ненулевых записей.

Решения пробовали
1) MATLAB: функция linprog в MATLAB не особенно полезна в наших настройках, так как решение LP занимает очень много времени.
2) GLPK: glpk_simplex также работает не так быстро, как ожидалось - для проблемы с P=15, Q=15,000 мне нужно получить ответ максимум за 10 секунд, но glpk_simplex занимает 20-25 минут. У glpk_interior недостаточно памяти для проблемы вышеупомянутого размера.

Кто-нибудь может предложить несколько эффективных библиотек? Пожалуйста, предложите как бесплатные, так и коммерчески доступные, которые могут быть использованы для точного или приблизительного решения проблемы.

Answer 1

Что касается других вариантов решения, вот два SO вопроса, на которые вы должны обратить внимание, если вы еще не проверили их:

1. ТАК Вопрос о том, какие решатели использовать

2. Опции Java Solver

Но причина, по которой я публикую сообщения, состоит в том, что у меня есть пара других предложений для вас, а не для решающей скорости. (Что-то может сработать для Q ~ 15K в вашей задаче, но если Q станет больше, вам придется искать еще более быстрые решатели.)

Другие предложения, чтобы попробовать

1. Ты играл с солвером? options в MATLAB или GLPK? Есть довольно много вещей, которые вы можете попробовать: iteration limit, или же Timelimit (до 10000 миллисекунд).

2. Посмотрите на разложение и расслабление вашей формулировки. Как правило, в этих больших LP есть хорошая базовая структура, но несколько жестких ограничений играют в спойл-спорт, и именно они доставляют решающую проблему. Если вы можете идентифицировать их, вы можете расслабить их, и, возможно, даже бросить в целевую функцию с помощью множителя.

   Чтобы сделать это немного более конкретным, вы рассматриваете лагранжеву релаксацию для "проблемных ограничений". (Как одна из ссылок на то, что я имею в виду, чтобы увидеть, как проблема 12.3 становится 12.4 здесь после того, как вы расслаблены. Вы можете сделать то же самое для нескольких плотных ограничений в вашей проблеме.

Надеюсь, это поможет вам двигаться вперед.