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

Question

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

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

Answer 1

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

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

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

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

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

Скорее всего, я

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

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

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

Answer 2

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

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

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

Answer 3

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

Eсть руководство что вас может заинтересовать.

Answer 4

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

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