Нелинейное целочисленное программирование

Question

Я хотел бы знать, есть ли в R пакет для обработки нелинейной целочисленной оптимизации.

«В основном», я бы хотел решить следующую проблему:

max f(x) s.t x in (0,10) and x is integer.

Я знаю, что некоторые алгоритмы ветвления способны обрабатывать линейную версию этой проблемы, но здесь моя функция f() может быть более сложной. (Я даже не могу убедиться, что он будет квадратичным в виде f(x)=xQx).

Я думаю, что всегда есть решение грубой силы, чтобы проверить все возможности, пока они ограничены, но мне было интересно, не было ли что-нибудь умнее.

Answer 1

У меня есть несколько вариантов для вас, но ни один из них не является серебряной пулей, хотя похоже, что ваша серебряная пуля находится в разработке в рамках проекта rino: http://r -forge.r-project .org / проекты / Rino / . * * 1005

Поскольку ваша функция сложна, вы можете использовать генетический алгоритм (т. Е. Оптимизаторы на основе градиента могут быть ненадежными). genoud в библиотеке rgenoud может помочь ( текст ссылки ). Если вы установите data.type.int=TRUE, это должно сработать. Я не использовал эту библиотеку, но у меня есть некоторый опыт работы с GA в matlab, и время конвергенции чувствительно к настройкам, поэтому вам будет полезно несколько раз прочитать справочную страницу.

Или, если ваша функция строго вогнута (маловероятно, поскольку вы говорите, что она может быть сложной), вы можете решить ее с помощью решателя градиента (например, optim), а затем проверить окрестность вокруг оптимума (не более 2 ^ n очков для проверки).

Извините, я не могу вам помочь.

Answer 2

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

Answer 3

http://cran.r -project.org / web / views / Optimization.html содержит список пакетов Rdonlp2 и Rsolnp, которые могут быть подходящими.

Answer 4

Метод дискретных заполненных функций является одним из последних методов, который может найти глобальное решение нелинейного целочисленного программирования с около 100 ограничениями и переменными.