18-5. Комбинаторные методы

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

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

Основное содержание этих методов составляют динамическое программирование и совокупность способов решения, объединенных общим термином - метод "ветвей и границ".