Алгоритм минимизации в целочисленном программировании

Question

Я понимаю, что минимизация в целочисленном программировании - очень сложная проблема. Но что делает эту проблему такой сложной?

Если бы я (попытался) написать алгоритм для его решения, что мне нужно было бы принять во внимание? Я знаком только с техникой ветвления и ограничения для ее решения, и мне интересно, с какими препятствиями я столкнусь, пытаясь применить эту технику программно.

Answer 1

Мне интересно, с какими препятствиями я столкнусь при попытке применить эту технику программно.

Нет, в частности (при условии довольно простой реализации без множества хитростей). Алгоритмы не сложные - они сложные , в этом принципиальная разница.

Такие методы, как разветвление и связывание или разветвление и обрезка, пытаются обрезать дерево поиска и, таким образом, ускорять время выполнения. Но все дерево проблем, тем не менее, экспоненциально велико, поэтому проблема.

Answer 2

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

«Классический» способ решения этой проблемы - выполнить ветвление и привязку и применить симплексный алгоритм в каждом узле, как вы говорите в своем вопросе. Однако я бы не рекомендовал реализовывать это самостоятельно, если вы не являетесь экспертом.

Что касается многих численных методов, очень трудно сделать это правильно (хорошие значения параметров, хорошие оптимизации), и многое было сделано (см. CPLEX, COIN_OR и т. Д.).

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

Кроме того, вам понадобится симплексная реализация, и это не то, что вы хотите делать самостоятельно: вам все равно придется использовать третью часть библиотеки.

Скорее всего, мокрый

• если ваш набор данных не такой большой (попробуйте!), И вы не заинтересованы в его быстром решении: используйте что-то вроде COIN-OR или lp_solve с методом по умолчанию, он будет работать;
• если ваш набор данных действительно большой (и / или вам нужно каждый раз быстро находить решение), вам нужно работать с экспертом в этой области.

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

Если вас интересуют эти проблемы, я бы порекомендовал эту книгу для введения в математику, стоящую за всем этим (с большим количеством примеров). Он невероятно дорогой, поэтому вы можете пойти в библиотеку, а не покупать ее: Nemhauser и Wolsey .

Answer 3

Целочисленное программирование - NP-hard .Вот почему это так сложно.

Существует учебник , который может вас заинтересовать.

Answer 4

Первое, что вы делаете перед тем, как решить математическую задачу оптимизации, - это классифицируете ее.За исключением особых случаев, в большинстве случаев проблемы целочисленного программирования будут сложными.Таким образом, вместо использования «алгоритма», вы будете использовать «эвристику».Окончательное решение, которое вы найдете, не будет гарантированным оптимумом, но будет довольно хорошим решением для реальных проблем.

Основным препятствием на пути станут ваши навыки программирования.Эвристическое программирование требует хорошего уровня понимания программирования.Поэтому вместо программирования своей собственной эвристики лучше использовать хорошо известный пакет (например, COIN-OR, бесплатный).Таким образом, вы можете сосредоточиться на своей проблеме, а не на эвристике.