Метод приближения непрерывными
задачами. В соответствии с ним
сначала решается задача линейного программирования без учета целочисленности, а
затем в окрестности оптимального решения ищутся целочисленные точки.
Методы направленного перебора.
Из них наиболее известен метод ветвей и границ. Суть метода такова. Каждому
подмножеству Х множества возможных решений Х0 ставится в
соответствие число - "граница" А(Х). При решении задачи минимизации
необходимо, чтобы А(Х1) ≥ А(Х2), если Х1 входит
в Х2 или совпадает с Х2 .
Каждый шаг метода ветвей и границ
состоит в делении выбранного на предыдущем шаге множества ХС на два - Х1С и Х2С . При этом пересечение Х1С и Х2С пусто, а их объединение совпадает с ХС . Затем вычисляют границы А(Х1С ) и А(Х2С) и
выделяют "ветвь" ХС +1 - то из множеств Х1С и Х2С , для которого граница меньше. Алгоритм прекращает работу, когда
диаметр вновь выделенной ветви оказывается меньше заранее заданного малого
числа
Для каждой конкретной задачи целочисленного
программирования (другими словами, дискретной оптимизации) метод ветвей и границ
реализуется по-своему. Есть много модификаций этого метода.