Метод ветвей и границ в задачах дискретной оптимизации

Решение задач оптимизации является, несомненно, актуальной проблемой. Подобные задачи возникают в самых различных областях человеческой деятельности (экономике, геологии, химии, биологии, физике и т.д.). Для гарантированного поиска оптимума обычно пользуются интервальными методами, однако, подобные методы имеют, как правило, низкую скорость сходимости.

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

Большое число задач планирования техники являются по своей природе дискретными и, как правило, обладают множеством допустимых решений. Сложность таких задач заключается в том, что они имеют конечное множество решений, но это множество может иметь очень большую размерность. Обнаружить лучшее из решений путем перебора всех вариантов невозможно в разумные сроки, даже применяя электронно-вычислительные машины. Такие задачи получили название NP-трудные. Традиционный метод решения задач оптимизации метод линейного программирования в данном случае не работает, так как предполагает, что переменные задачи xi являются непрерывными, на которые только иногда накладывается ограничение неотрицательности. Рассматриваемые задачи характеризуются дискретностью, т.е. xi принимает только целые положительные значения. При этом, как показано В.Н. Бурковым и С.Е. Ловецким в их работе «Комбинаторика и развитие техники», решение такой задачи без учета ограничений на целостность переменных с последующим округлением до целых значений не приводит к оптимуму. Поэтому для дискретных задач используются специальные методы, к которым относится рассматриваемый в работе метод ветвей и границ. Он позволяет избежать некоторых недостатков известных методов оптимизации и существенно уменьшить время решения.

Метод ветвей и границ – это общий метод поиска решения. Метод начинает работу с определения нижней и верхней границ для исходной задачи. Если верхняя и нижняя границы совпадают, то полученный результат является оптимальным значением, и алгоритм прекращает работу. Иначе, множество переменных разбивается на несколько собственных подмножеств, объединение которых совпадает с исходным множеством. Эти подзадачи становятся потомками исходной. Далее алгоритм применяется рекурсивно* к каждой из подзадач, создавая дерево подзадач. Если оптимальное решение найдено для некоторой подзадачи, то оно является достижимым для исходной задачи (не обязательно оптимальным), но так как оно достижимо, его можно использовать для обрезания ветвей у исходного дерева. Процесс поиска продолжается до тех пор, пока каждая из подзадач не будет решена или выкинута или до тех пор, пока не будет достигнут заданный порог между лучшим из найденных решений и нижней границей f(x) для всех нерешенных задач.

Цель научно-исследовательской работы: исследование методов комбинаторного программирования для применения к оптимизации трафика обмена потока информации в телекоммуникационных сетях.

Задачи, решаемые для исследования:

• Оптимизация трафика обмена потока информации в телекоммуникационных сетях
• Разработка алгоритма описания работы метода ветвей и границ
• Создание математической модели метода ветвей и границ с целью описания ее на языке программирования высокого уровня
• Разработка программной модели метода ветвей и границ
• Изучение специализированных математических функций выбранного языка программирования
• Создание интерфейсной части программного обеспечения для метода ветвей и границ

Гипотеза: возможность сокращения трафика потока информации в телекоммуникационных сетях за счет передачи наиболее приоритетной информации, содержащейся в одном SMS-сообщении в максимальной степени.

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

Метод ветвей и границ в задачах дискретной оптимизации

Идею метода поясним на задаче с фальшивой монетой. Допустим, у нас 27 монет. Среди них одна фальшивая. Мы знаем только, что она легче остальных. Требуется найти ее за минимальное число взвешиваний.

Разделим монеты на три равные группы по 9 монет и взвесим любые две группы. Если весы окажутся в равновесии, то, очевидно, фальшивая монета находится в оставшейся группе. Если одна из групп перевешивает, то фальшивая монета в более легкой группе. Таким образом, после одного взвешивания нам остается искать легкую монету уже среди 9, а не 27 монет. Разобьем оставшиеся монеты опять на три группы по 3 монеты, повторим процесс взвешивания и т.д. (Рис.1) Как видите, достаточно всего трех взвешиваний.

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

Проще всего при сравнении рассматривать группы парами. В этом случае оценка типа «эта группа лучше» вполне нас устраивает. «Лучше» следует понимать в том смысле, что в данной группе больше шансов обнаружить достаточно хорошее решение. Допустим, задача имеет 64 возможных решения. Если их разбить на восемь групп по восемь решений в каждой, то необходимо произвести семь попарных сравнений для выбора определенной группы. Разбивая отобранную группу снова на восемь групп (теперь каждая из них состоит из одного решения) и сделав еще семь попарных сравнений (при каждом сравнении исключается одна группа), решим задачу, получив в результате 14 попарных сравнений, т.е. 14 раз ответим на вопрос «какая группа лучше?». Теперь попробуем разбивать не на восемь, а на четыре группы по 16 решений в каждой. Произведя три таких разбиения, мы найдем решение, сделав только 3x3 = 9 попарных сравнений. Однако еще меньше попарных сравнений потребуется, если каждый раз разбивать на две группы. Действительно, для выбора конкретного решения нужно сделать шесть разбиений (шесть шагов), а значит и шесть попарных сравнений, так как для выбора одной группы из двух достаточно одного сравнения.

Поскольку каждое сравнение и выбор группы требует определенного времени, то естественно желание уменьшить общее число таких сравнений. Этому требованию соответствует схема разбиения каждой группы на две новые, что вполне отвечает и житейской практике. Спрашивающий всегда стремится поставить вопрос, требующий ответа «да» или «нет», хотя отвечающий, чтобы выиграть время, предпочитает менее категорический ответ «может быть». Схема разбиения на две группы удобна еще и по другой причине. Пусть мы произвели разбиение на три группы А, В, С, причем группа А для нас лучше В, В лучше С, а С лучше А (например, если А, В и С шахматисты, то А выиграл у В, В у С, а С обыграл А). Если, производя попарное сравнение, мы возьмем сначала пару А, В, то в результате будет выбрана группа С, если же для первого сравнения взять пару А, С, то останется группа В (вряд ли этот способ определения чемпиона устроит шахматистов). Разбивая каждую группу на две, мы гарантированы от попадания в такое неудобное положение. Исходя из сказанного, во всех последующих примерах мы будем применять только схему разбиения на две группы.

Вместо слов «лучше» или «хуже» можно получать численную оценку каждой группы, так что лучшей считается группа с меньшей оценкой. Иногда в качестве численной оценки удается взять нижнюю границу значений критерия f(n) для всех решений группы. Нижней границей или оценкой снизу называется число, меньшее значения критерия для любого решения данной группы. Если среди решений группы существует решение, значение критерия которого равно величине оценки, то оценка называется достижимой. Выбирая группу с меньшей величиной достижимой оценки, вы имеете гарантию, что среди решений этой группы находится наилучшее.

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

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

Остановимся еще на некоторых особенностях метода ветвей и границ. Нам известно, что чем ближе нижняя оценка группы решений к достижимой, тем больше шансов получить оптимальное или достаточно хорошее решение. Однако для получения хорошей оценки поиск займет много времени. Может быть, лучше ограничиться грубой оценкой, которую можно получить быстро, но зато перебрать больше решений. В этом случае, получив первое решение, следует выбрать новую группу с минимальной оценкой (естественно, если эта оценка меньше значения критерия в полученном решении) и повторить процесс ветвления, начиная с этой группы. Если время на принятие решения ограничено, то, применяя грубую оценку, мы сумеем перебрать больше решений, чем в случае хорошей оценки, получение которой требует больших затрат времени. Конкретное решение этого вопроса определяется спецификой задачи.

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

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