Не линейное целочисленное программирование
Я хотел бы знать, существует ли пакет в R, обрабатывающем не линейная целочисленная оптимизация.
"В основном" я хотел бы решить следующую проблему:
max f(x) s.t x in (0,10) and x is integer.
Я знаю, что некоторые алгоритмы ветвления могут обработать линейную версию этой проблемы, но здесь мою функцию f() могло бы быть более сложным. (Я не могу даже удостовериться, что это было бы квадратично из формы f(x)=xQx).
Я предполагаю, что существует всегда решение для грубой силы протестировать все возможности, пока они ограничены, но я задавался вопросом, не было ли ничего более умного.
3 ответа
У меня есть несколько вариантов для вас, но ни один из них не серебряная пуля, хотя похоже, что ваша серебряная пуля находится в разработке в рамках проекта rino : http://r-forge.r-project.org/projects/rino/ .
Поскольку ваша функция сложна, вы можете использовать генетический алгоритм (т.е. оптимизаторы на основе градиента могут быть ненадежными). genoud в библиотеке rgenoud может помочь ( текст ссылки ). Если вы установите data.type.int = TRUE , это должно сработать. Я не использовал эту библиотеку, но имею некоторый опыт работы с GA в Matlab, и время до конвергенции зависит от настроек, так что вам будет полезно прочитать справочную страницу несколько раз.
Или, если ваша функция строго вогнута (маловероятно, поскольку вы говорите, что это может быть сложно), вы можете решить ее с помощью градиентного решателя (например, optim ), затем проверьте окрестность вокруг оптимума (может ' t должно быть больше 2 ^ n точек для проверки).
Извините, я ничем не могу больше помочь.
Если функция почти нелинейная, то нет лучшего метода, чем перебор (вы никогда не узнаете, является ли минимум локальным, или если какой-то плоский на вид фрагмент не имеет узких и глубоких долин), кроме, конечно, символьных вычислений (которые, вероятно, не будут работать, потому что функция слишком сложна) или мягких вычислений, я имею в виду такие вещи, как генетические алгоритмы, Монте-Карло, рои и т.д. (здесь вы не можете знать, является ли минимум локальным). (здесь у вас нет гарантии, что он найдет самый глобальный минимум, и поскольку у вас целое число x, это может быть медленнее, чем перебор).
http://cran.r-project.org/web/views/Optimization.html списки пакеты Rdonlp2 и Rsolnp , которые могут быть подходящими.