Я понимаю, что минимизация в целочисленном программировании - очень сложная проблема. Но что делает эту проблему такой сложной?
Если бы мне пришлось (попытаться) написать алгоритм для ее решения, что мне нужно было бы принять во внимание? Я знаком только с техникой ветвей и границ для ее решения, и мне интересно, с какими препятствиями я столкнусь при попытке применить эту технику программно.
Как и другие, эти проблемы очень сложны, и не существует простого решения или простого алгоритма, применимых ко всем классам проблем.
«Классический» способ решения этой проблемы - выполнить ветвление и привязать и применить симплексный алгоритм к каждому узлу, как вы говорите в своем вопросе. Однако я бы не рекомендовал реализовывать это самостоятельно, если вы не являетесь экспертом.
Что касается многих численных методов, очень сложно сделать это правильно (хорошие значения параметров, хорошая оптимизация), и многое было сделано (см. CPLEX, COIN_OR и т. Д.).
Дело не в том, что вы не можете этого сделать: часть ветвления и привязки довольно проста, но без всех уловок ваша программа будет действительно медленной.
Кроме того, вам понадобится симплексная реализация, и это не то, что вы хотите делать самостоятельно: вам все равно придется использовать стороннюю библиотеку.
Скорее всего,
Я хочу сказать, что только опытные люди будут знать, какой алгоритм лучше справится с вашей проблемой, какую форму модели будет легче всего решить, какой метод применить и какие оптимизации вы можете попробовать. .
Если вас интересуют эти задачи, я бы порекомендовал эту книгу для введения в математику, лежащую в основе всего этого (с большим количеством примеров). Он невероятно обширен, поэтому вы можете пойти в библиотеку, а не покупать ее: Немхаузер и Вулси.
Мне интересно, с какими препятствиями я столкнусь, пытаясь применить эту технику программно.
В частности, нет (при условии довольно простой реализации без множества уловок). Алгоритмы не сложные - они сложные, и это фундаментальное отличие.
Такие методы, как «ветвление и привязка» или «ветвление и разрез», пытаются сократить дерево поиска и, таким образом, сократить время выполнения. Но все дерево проблем, тем не менее, экспоненциально велико, отсюда и проблема.
lp_solve (оба Открытый исходный код) сделайте это.
- person Konrad Rudolph; 05.09.2011
Прежде чем решать любую задачу математической оптимизации, вы в первую очередь классифицируете ее. За исключением особых случаев, в большинстве случаев задачи целочисленного программирования будут непростыми. Поэтому вместо использования «алгоритма» вы будете использовать «эвристику». Окончательное решение, которое вы найдете, не будет гарантированно оптимальным, но это будет довольно хорошее решение реальных проблем.
Вашим главным препятствием будут ваши навыки программирования. Эвристическое программирование требует хорошего уровня понимания программирования. Поэтому вместо программирования собственной эвристики лучше использовать хорошо известный пакет (например, COIN-OR, бесплатно). Таким образом, вы можете сосредоточиться на своей проблеме, а не на эвристике.
