Целочисленное/двоичное программирование в реальном времени (микросекундное время вычислений)

Моя проблема с бинарным программированием:

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 / lpsolve, он сообщает о времени от 2 мс до 7 мс. У меня нет SCIP/Gurobi. Есть ли способ решить это менее чем за миллисекунду? Кажется ли вообще разумным ожидать решения этой проблемы менее чем за миллисекунду?

(Я отключил printf в CBC. Но я не уверен, есть ли какие-либо другие системные операции, с которыми он застрял .... какие-либо файлы журналов, которые он пишет)


real-time knapsack-problem integer-programming
person ctrlAltDel    schedule 30.04.2015    source источник
comment
Просто комментарий, но большие коммерческие решатели (Gurobi, CPLEX, Xpress) направляют свои усилия в области исследований и разработок на решение более крупных и сложных проблем - они могут быть ненамного лучше, чем открытые/бесплатные решатели для очень маленьких экземпляров. Если вы знаете, что у вас есть определенная структура проблемы, вы можете получить более простую реализацию, которая будет работать быстрее, поскольку ей не нужно предоставлять все возможные функции, которые предоставляют общие решатели. Подумайте об ограничении предварительного решения, удалении большинства или всех сокращений и эвристик, если они действительно не помогают вашей проблеме, отключении любых обратных вызовов и т. д. Что-то вроде решателя RISC MIP.   -  person TimChippingtonDerrick    schedule 01.05.2015
comment
Ты имеешь в виду макс? Решение выше всегда должно быть нулевым вектором.   -  person cdhagmann    schedule 01.05.2015
comment
Спасибо TimChipppingtonDerrick за ответ. Покопавшись дальше, я понял, что это стандартная задача о рюкзаке, которую можно эффективно решить с помощью динамического программирования. Реализация C++ измеряет ~20 мкс. Я опубликую ответ с этим.   -  person ctrlAltDel    schedule 01.05.2015
comment
привет, Кристофер, упс, да, это должно было быть "макс". Редактирование вопроса сейчас.   -  person ctrlAltDel    schedule 01.05.2015

Ответы (1)


arrow_upward
0
arrow_downward

Это стандартная задача о рюкзаке, которую можно эффективно решить с помощью динамического программирования. Это хорошо обсуждалось в вики о рюкзаке (а также в нескольких сообщениях о переполнении стека, например, здесь алгоритм DP для рюкзака и здесь рекурсивный рюкзак)

Реализация С++ измеряет ~ 20 мкс на моем ядре i7 @ 3Ghz

person ctrlAltDel    schedule 02.05.2015