Автоматика и телемеханика, № 9, 2014
Анализ данных
© 2014 г. В.А. БОНДАРЕНКО, д-р физ.-мат. наук (bond@bond.edu.yar.ru), А.В. НИКОЛАЕВ, канд. физ.-мат. наук (werdan.nik@gmail.com),
М.Э. СЫМАНОВИЧ (maxbrainrus@gmail.com), (Ярославский государственный университет им. П.Г. Демидова),
Р.О. ШЕМЯКИН (ramon93i7@gmail.com) (Московский государственный университет им. М.В. Ломоносова)
ОБ ОДНОЙ ЗАДАЧЕ РАСПОЗНАВАНИЯ НА РЕЛАКСАЦИЯХ РАЗРЕЗНОГО МНОГОГРАННИКА1
Исследуется сложность задачи распознавания целочисленности на релаксациях разрезного многогранника. Устанавливаются характерные свойства точек релаксаций, которые препятствуют эффективному решению задачи. Приводятся примеры подобных точек.
1. Введение
Широко известно, что разнообразные вопросы управления сложными системами, как правило, сводятся к решению задач дискретной или комбинаторной оптимизации, которые, в свою очередь, часто представляют в виде моделей линейного и целочисленного программирования. Этим в значительной мере объясняется тот факт, что с различными аспектами линейного и целочисленного программирования связано большое число исследований, направленных на разработку эффективных по трудоемкости алгоритмов.
Рассматриваются две задачи, связанные с оптимизацией линейной целевой функции на целых вершинах некоторого выпуклого многогранника.
Первая задача - это хорошо известная задача целочисленного программирования
max f (x) = (c, x) : Ax ^ b,
где b € Zm, c € Zn, матрица A € Zmxn.
Вторая задача описана в [1] (см. также [2]), где получила название задачи 'распознавания целочисленности. Ее постановку можно сформулировать в следующем виде:
Задача 1. Пусть M - некоторый класс выпуклых многогранников, определяемых линейными ограничениями. Пусть M € M, а Z - множество всех целых точек из M. Обозначим через f (x) = (c,x) линейную целевую функцию. Требуется выяснить, выполняется ли равенство
max f (x) = max f (z).
xeM zez
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект № 14-01-00333\14) и гранта Правительства РФ, договор 11.G34.31.0053.
Таким образом, учитывая, что максимум линейной целевой функции всегда достигается в вершине многогранника, задача распознавания целочис-ленности направлена на вопрос: «Есть ли среди вершин многогранника, на которых заданная целевая функция достигает своего максимума, хотя бы одна целая?»
Нетрудно заметить, что решение задачи целочисленного программирования автоматически предполагает получение ответа для задачи распознавания целочисленности, в то время как обратное, строго говоря, не верно. Действительно, если в задаче распознавания целочисленности ответ положителен, то и задача целочисленного программирования будет решена. Однако если максимум целевой функции не достигается в целой вершине, то ответ для задачи целочисленного программирования остается по-прежнему неизвестен. Таким образом, в некотором смысле распознавание целочисленности является более простой задачей, нежели целочисленное программирование.
Тем не менее в общем случае обе задачи относятся к труднорешаемым задачам, а именно: к классам КР-полных и КР-трудных задач соответственно. В то же время в некоторых частных случаях, например на п-мерном единичном гиперкубе, обе задачи могут быть решены за полиномиальное время. Таким образом, интерес для изучения представляет некоторый «пограничный» пример многогранника, для которого эти две задачи относились бы к принципиально различным классам сложности.
В [1] было доказано, что известный [3, 4] класс корневых полуметрических многогранников Мп удовлетворяет предъявленным требованиям. К задаче целочисленного программирования на корневом полуметрическом многограннике сводится известная КР-полная задача о максимальном разрезе графа [5], и поэтому она относится к классу КР-трудных задач. В то же время задача распознавания целочисленности на корневом полуметрическом многограннике полиномиально разрешима [1].
В основе полиномиальной разрешимости задачи распознавания целочис-ленности на корневом полуметрическом многограннике Мп лежит следующее свойство Мп,з - еще одной, отличной от Мп, релаксации разрезного многогранника.
Утверждение 1. Каждая точка многогранника Мп,3 является выпуклой комбинацией вершин многогранника Мп, среди которых есть хотя бы одна целая.
Действительно, в силу данного утверждения для решения задачи распознавания целочисленности на корневом полуметрическом многограннике Мп достаточно сравнить максимумы заданной целевой функции на Мп и на Мп,з (двойное решение задачи линейного программирования, полиномиальные алгоритмы для которой хорошо известны), тогда в случае равенства значений задача распознавания целочисленности предполагает ответ «да», а в случае различия - ответ «нет».
Данная статья посвящена изучению задачи распознавания целочисленно-сти на многограннике Мп,3. Впервые этот вопрос был поставлен в [6], где были анонсированы некоторые результаты относительно поставленной задачи. Ниже полученные ранее результаты будут значительно улучшены, кроме
того будут приведены принципиально новые доказательства ранее известных фактов.
2. Релаксации разрезного многогранника
Объектом исследования в статье являются релаксационные многогранники задачи о максимальном разрезе, поэтому предварительно напомним классический вариант построения многогранника задачи о максимальном разрезе.
Задача 2. Заданы неориентированный граф С = (V, Е) и некоторая функция С : Е — Z+7 каждому ребру е € Е сопоставляющая неотрицательное целое число С(е), называемое весом ребра.
Требуется найти такое разбиение множества вершин V на два непересекающихся подмножества Р и Q (разрез), чтобы сумма весов ребер из Е, соединяющих вершины из множеств Р и Q, была максимальной.
Каждому подмножеству Б С Мп = {1,... ,п} (каждому разрезу) сопоставляется характеристический (0/1) вектор по следующему правилу:
6(S) € {0,1}d, d = C2, где для всех 1 ^ i < j ^ n : 1, если |S П {i, j}| = 1,
6(S)i j = „ v 7 1 0 в противном случае.
Тогда разрезной многогранник CUT(n) представляет собой выпуклую оболочку всех характеристических (разрезных) векторов
CUT(n) = conv{5(S) : S € Nra} С Rd.
Таким образом, вершинами разрезного многогранника CUT(n) являются характеристические векторы всех возможных разрезов полного графа на n вершинах.
Задача о максимальном разрезе графа на n вершинах в оптимизационной форме сводится к задаче линейного программирования на разрезном многограннике CUT(n) с целевой функцией, содержащей веса ребер [5, 7]. Однако применение эффективных алгоритмов линейного программирования требует полного внешнего описания разрезного многогранника: построения всех его фасет (гиперграней). Эта задача до сих пор не решена, и полное описание содержит, судя по всему, сверхэкспоненциальное количество линейных ограничений, не говоря о том, что каждая фасета может иметь сверхэкспоненциально большие коэффициенты в своем описании [5, 7].
Таким образом, интерес представляют так называемые релаксационные многогранники задачи о максимальном разрезе, которые обладают значительно более простым внешним описанием, но по-прежнему оставляют возможность рассматривать на них задачу о максимальном разрезе как оптимизацию линейной функции. К ним, в частности, относится известный корневой полуметрический многогранник [1, 3, 5], внешние ограничения которого име-
ют вид:
(1) xi,j + yi,j + zi,j + ti,j - 1
(2) xi,j + yi,j — xk,j + yk,j,
(3) xi,j + zi,j — xi,l + zi,h
(4) Xi,j — ^jti? ti,j — tj,i, yi,j — ^j^'
(5) yi,i — Zi,i — 0,
(6) Xi,j ^ 0, yi,j ^ 0, Zi,j ^ 0, ti,j ^ 0,
где г, j, к, I независимо пробегают значения 1,... ,п.
Заметим, что координаты точек многогранника Мп удобно представлять в виде блочной матрицы (см. табл. 1).
Таблица 1. Блок координат
Zi,j
Многогранник MZ, порождаемый выпуклой оболочкой целых вершин корневого полуметрического многогранника Mn, совпадает с разрезным многогранником CUT(n + 1) [3, 5], поэтому Mn является релаксационным многогранником задачи о максимальном разрезе, или релаксацией разрезного многогранника, а сама задача о разрезе сводится к задаче целочисленного программирования на Mn.
Однако это не единственный способ построения релаксационного многогранника задачи о максимальном разрезе. Определим, следуя [5, 6], релаксации разрезного многогранника более высоких уровней. С этой целью выберем натуральное к (к ^ n) и рассмотрим систему неравенств S, задающую многогранник M^; обозначим через В число этих неравенств. Далее для каждого k-элементного подмножества v — {vi,...,vk} множества Nn рассмотрим систему Sv, получающуюся из системы неравенств S заменой переменных Xi,j, yi,j, Zi,j и ti,j соответственно на xVi>Vj, yvi,vj, Zvi,vj и tvi,vj. Дополним систему (1)—(6) совокупностью всех В ■ СП указанных неравенств, а многогранник, который задается расширенной системой ограничений, обозначим через Mn,k. Таким образом, релаксации Mn>k представляют собой последовательность вложенных друг в друга многогранников:
CUT(n + 1) — MZ — Mnn С Mn,n-1 С ...
... С Mn,k С ... С Mn,3 С Mn,2 — Mn,1 — Mn.
Следует отметить, что непосредственное построение полного внешнего описания релаксационных многогранников Mn,k является весьма трудоемкой задачей, так как требует полного описания фасет MZ, совпадающего с
разрезным многогранником CUT(k + 1), которое известно лишь для сравнительно небольших значений k [7].
Первая, отличная от корневого полуметрического многогранника, релаксация Mn,3 разрезного многогранника была подробно описана в [1]. Она определяется системой (1)—(6) и дополнительными ограничениями:
xi,j + ^i,j + xi,k + + yj,k + zj,k ^ 2 xi,j + ^i,j + yi,k + zi,k + xj,k + tj,k ^ 2 yi,j + zi,j + xi,k + ti,k + xj,k + tj,k ^ 2J
yi,j + Zi,j + yi,k + Zi,k + yj,k + Zj,k ^ 2
для каждой тройки i,j,k € Nn, где i < j < k.
Выберем одно из дополнительных ограничений Mn,3 и преобразуем его следующим образом:
yi,j + Zi,j + yi,k + Zi,k + yj,k + Zj,k ^ 2, yi,j + zi,j + yi,k + zi,k + yj,k + zj,k + 2(xi,j + xi,k + xj, k) < 2 + 2(x i,j + xi,k +
+ zi,j + 2xij — xi,i + xj,j, 2(xi,i + xj,j + xk
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.