0
Моя бинарная проблема программирования:в реальном масштабе времени Integer/Binary программирование (микросекунды вычисления времени)
max: (a1 * x1) + (a2 * x2) + ..... + (an * xn)
при условии:
(c1 * x1) + (c2 * x2) + ..... + (cn * xn) < C
n = 10
a1, ... an, c1, ... cn, C are known
x1, ... xn are binary
Это проблема процесс назначения задач. В моем случае накладные расходы на решение проблемы двоичного/целочисленного программирования должны быть очень маленькими (< 1 миллисекунда). Когда я запускаю это с помощью CBC solver/lpsolve, он сообщает время 2ms - 7ms. У меня нет SCIP/Gurobi. Есть ли способ решить это менее чем за миллисекунду? Кажется ли разумным ожидать решения этого менее чем за миллисекунду?
(я отключить PRINTF-х в CBC. Но я не уверен, если есть какие-либо другие операции системы, что он застрял с .... все файлы журналов, это написание)
просто комментарий, но большой коммерческий решатели (Gurobi, CPLEX, Xpress) приложили свои усилия к R & D для решения более сложных и сложных задач - они могут быть не намного лучше, чем открытые/бесплатные решатели для очень маленьких экземпляров. Если вы знаете, что у вас есть определенная структура проблем, вы можете получить более простую реализацию, чтобы работать быстрее, поскольку ей не нужно предоставлять все возможные функции, которые предоставляют общие решатели. Подумайте о том, чтобы ограничить предварительное решение, удалив большинство или все сокращения и эвристики, если они действительно не помогут в вашей проблеме, отключении любых обратных вызовов и т. Д. Сортировка RISC MIP-решателя. – TimChippingtonDerrick
Вы имеете в виду макс? Решение вышеизложенного всегда должно быть нулевым вектором. – cdhagmann
Спасибо TimChippingtonDerrick за ответ. После копания в большей степени я понял, что это стандартная проблема с ранцем, которую можно эффективно решить с помощью динамического программирования. Реализация C++ реализует ~ 20us. Я отправлю ответ с этим. – ctrlAltDel