Сколько переменных решения можно решить для смешанного целочисленного программирования?

У меня проблема смешанного целочисленного программирования (двоичные целочисленные переменные), сколько переменных я могу решить, то есть верхний предел и сколько времени потребуется?

Задача будет иметь максимум 5 ограничений и функцию минимизации стоимости, но переменные представлены в виде матрицы m * n. Итак, вопрос в том, какими могут быть максимальные значения m и n, а также время, необходимое для завершения вычислений?

Использование стандартного программного обеспечения / библиотек, таких как COIN CBC, GLPK, CPLEX, GUROBI.


glpk coin-or-cbc linear-programming integer-programming cplex
person Yashwanth Remidi    schedule 16.03.2016    source источник
comment
Если у вас есть максимум 5 ограничений, то что такое m и n?   -  person vcp    schedule 16.03.2016
comment
m * n - это матрица переменных решения, а не ограничения, я определяю ограничения, а решатель решает проблему с m n переменными и дает мне лучшие переменные в качестве решения. Каков максимальный размер m n, который может решить имеющийся на рынке решатель?   -  person Yashwanth Remidi    schedule 16.03.2016

Ответы (1)


arrow_upward
1
arrow_downward

Действительно ли возможно использовать доступные на рынке решатели с открытым исходным кодом / коммерческие решатели, чтобы решить эту проблему?

Краткий ответ: Да, можно решить MIP с миллионами переменных решения.

Теория

В целом MIP - это NP-трудная проблема и не может быть решена за полиномиальное время O (n ^ k). Кроме того, НЕ просто определить, что вводится «n» для проблемы MIP. Неужели нет? строк, столбцов или их произведений, природа матрицы A, природа переменных решения, разрыв между MIP и ослабленным LP?

Если формулировка IP (Ax = b), матрица A полностью унимодулярна, и все коэффициенты целые числа, то решение LP-релаксации также является решением IP, и, таким образом, сложность вашей проблемы является полиномиальной.

Если нет, то вы должны ожидать, что проблема будет NP-трудной в общем случае. Как правило, чем больше переменных и ограничений, тем сложнее проблема.

Практика

Решатели MIP / LP могут использовать различные методы / алгоритмы для решения любой проблемы в разумные сроки (в часах), особенно если вы не ищете «оптимальное целочисленное решение» и готовы принять решение, близкое к оптимальному.

Нет ограничений по фиксированному размеру - Gurobi Optimizer регулярно решает модели с миллионами переменных и ограничений, даже на стандартных портативных и настольных компьютерах. Что еще более важно, вы можете увидеть результаты в производительности Gurobi, особенно на более крупных и сложных моделях. Фактически, Гуроби недавно решил 11 моделей в библиотеке MIPLIB2010, которые ранее не решались никаким другим решателем.

Источник: http://www.gurobi.com/products/gurobi-optimizer.

Особые проблемы MIP

Доступны специальные методы для решения особых случаев MIP.

Я написал простой алгоритм генерации столбцов для решения задач раскроя материала. См. https://github.com/vcphub/cspsol.

person vcp    schedule 16.03.2016
comment
Да, именно то, о чем я хотел спросить, у меня есть проблема MIP, которую я пытался решить с помощью Excel, и она достигла максимума после 200 переменных (~ 50 минут), но я хотел бы масштабировать ее до 1M + переменных решения (примерно за 2 -3 часа). Действительно ли возможно использовать доступные на рынке решатели с открытым исходным кодом / коммерческие решатели, чтобы решить эту проблему? - person Yashwanth Remidi; 16.03.2016
comment
Да, это может быть возможным. Но если вы используете бесплатную решающую программу с открытым исходным кодом, вам придется решить ее «из коробки». Если ваша задача имеет красивую структуру и хорошие числовые характеристики, все в порядке. Но это может и не быть - в настоящее время у меня есть проблема, в которой всего около 27k целочисленных переменных, а CPLEX на разумном сервере не может найти целочисленное решение за 8 часов для некоторых случаев. Если вы готовы реализовать некоторые умные методы с помощью решателя (например, генерация столбцов, Benders или VLNS), вы можете повысить производительность и решить более крупные проблемы. Кстати: решатель Excel очень слаб. - person TimChippingtonDerrick; 16.03.2016
comment
Да, excel - более слабый вариант среди других коммерческих решателей, у меня более простая задача меньшей сложности, но объем данных просто огромен. У меня есть матрица затрат (A), и я хочу сгенерировать двоичную целочисленную матрицу (B). Итак, я хочу минимизировать AxB, и единственное ограничение - это сумма каждой строки в переменной matrix is, что означает, что только одно значение в строке должно быть 1, а другие должны быть нулевыми. - person Yashwanth Remidi; 16.03.2016
comment
вы работаете с проблемой упаковки контейнеров? en.wikipedia.org/wiki/Bin_packing_problem - person vcp; 16.03.2016
comment
Неа. Это проблема распределения порядка хранения. Но я тоже работал над упаковкой контейнеров, которая фактически использует двоичное дерево поиска для эффективной 2D-упаковки. Он очень похож на метод ветвей и отсечений, используемый для MIP. - person Yashwanth Remidi; 16.03.2016
comment
Взгляните на это: stackoverflow .com / questions / 27848828 / - person vcp; 16.03.2016
comment
Если только одна двоичная переменная может быть 1 (остаточный ноль) в строке, и у вас есть 5 строк, это кажется мне очень выполнимым делом. Просто бросьте его в хороший решатель MIP и посмотрите, что произойдет. Вы можете попробовать что-то по адресу NEOS. - person Erwin Kalvelagen; 16.03.2016
comment
Спасибо за помощь, сейчас пытаюсь сделать то же самое. Я собираюсь использовать COIN-cbc и Gurobi (если возможно), так как они кажутся лучшими в своем классе для MIP. И, @ErwinKalvelagen, ограничения - 5, а не строки. У меня как минимум 1000 столбцов и 4000 строк - person Yashwanth Remidi; 17.03.2016
comment
Строка - это другое слово для ограничения - person Erwin Kalvelagen; 17.03.2016
comment
А столбец - это другое слово для переменной. - person Erwin Kalvelagen; 17.03.2016