автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:О выделении полиномиальных подклассов в задаче целочисленного линейного программирования

НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ при НИЖЕГОРОДСКОМ ГОСУДАРСТВЕННОМ УНИВЕРСИТЕТЕ им. Н. И. ЛОБАЧЕВСКОГО

На правах рукописи

„Зб1

Экз. Лз_

ЧИРКОВ Александр Юрьевич

О ВЫДЕЛЕНИИ ПОЛИНОМИАЛЬНЫХ ПОДКЛАССОВ В ЗАДАЧЕ ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

05.13.17—Теоретические основы информатики

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Нижний Новгород 1993

Работа выполнена на кафедре математической логики и пысшей алгебры факультета вычислительной математики и кибернетики Нижегородского государственного университета им. Н. И. Лобачевского.

Научный руководитель:

доктор физико-математических наук, профессор В. Н. Шевченко.

Официальные оппоненты:

доктор физико-математических паук, ведущий научный сотрудник В. К. Леонтьев;

кандидат технкческЕх наук, руководитель ИЩИ Шведов Б.К.

Ведущая организация — ЦЭМИ РАН.

.о Г -

Защита состоится « Рб > 4 ¿и&'^р/ 1993 г. п__/&час. па заседании специализированного совета ССК. 063.43.01 при научно-исследовательском институте прикладной математики и кибернетики по адресу: 603005, г. Нижний Новгород, ул. Ульянова, 10.

С диссертацией можно ознакомиться в библиотеке НИИПМК. Автореферат разослан « & » ноября 1993 г.

Ученый секретарь специализированного совета доктор технических наук Ю. Л. Кетков.

Актуальность раОоты. МНОГОЧИСЛеННЫв ПрЭКТИЧвСКИ ВЭЖНЫв

задачи экономики и производства при математическом моделировании сводятся к задаче целочисленного линейного программирования (ЗЩШ) или нахоящению целочисленных решения системы линейных неравенств и уравнений. Известно, что ЗЦЛП является КР - полной. Поэтому вряд ли существуют полиномиальные алгоритмы ей решения. В связи с этим возникает задача выделения подклассов ЗЦЛП, для которых такие алгоритмы имеются. Существует большое количество работ советских и зарубежных математиков, посвященных этой тематике. В предлагаемой диссертации рассматриваются некоторые из подходов к выделению подклассов ЗЦЛП, для решения которых существуют полиномиальные алгоритмы.

Цели раРаты. 1 . ИзучеНИв СТрОвНИЯ ВЫПУКЛОЙ ОбОЛОЧКИ горесечения полиэдра с целочисленной решеткой и ввдэлениэ случаев еб полиномиального описания в виде системы неравенств и списка вершин.

г. Выделение новых подклассов ЗЦЛП. душ решения которых существуют полиномиальные алгоритмы.

Методы исследования. В рабОТв ИСПОЛЬЗУЮТСЯ МвТОДЫ

геометрии чисел, целочисленного линейного программирования и комбинаторной теории многогранников.

Научная новизна. В ДИССвртаЦИИ ПОЛуЧвНЫ СЛвДУХВДИЭ

результаты:

- выделен ряд новых полиномиальных подклассов ЗЦЛП,

- доказано, что при любой фиксированной размерности п

г

полиэдра М выпуклая оболочка точек из имеет полиномиальное описание,

- полученные результаты перенесены на частично цэлочислзшый случая,

- получен ряд результатов о строении выпуклой оболочки точек из {х\Ах5Ь>пгп, когда матрица А - Синодулярвзя (т.е. ев миноры максимального порядка по абсолютной величине не превосходят 2).

- построен строго полиномиальный алгоритм решения ЗЦЛП пои фиксированной размерности,

Практическая ценность. Результаты рзбОТЫ МОГУТ бЫТЬ

использованы как в теории (например, при создании точных и приближенных алгоритмов), так и на практике (в разработке соответствующего программного продукта).

Публикации ц о пронация работы. Содержание диссертации отрааено в публикациях [1-19]. Основные результаты докладывались на итоговых научных конференциях и научных семинарах Нижегородского университета, на всесоюзном семинаре по диофетной математике и ее приложениям (Москва, 1881), на межгосударственной конференции по проблемам теоретической кибернетики (Горький, 1092), на всесоюзных конференциях по проблемам теоретической кибернетики (Горький 1868, Волгоград 1990), на конференциях "Математическое программированию и приложения" (Свердловск 1990, 1992), на международном семинаре по дискретной оптимизации (Минск 1893).

Структур? ц оСт.ом работы. ДИССврТаЦИЯ СОСТОИТ ИЗ

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

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

В первой главе рассматривается задача покрытия многогранника М симплексами (под п-мерным симплексом понимается выпуклая оболочка (п+1) аффинно независимых точек). Пусть *(М) - наименьшее число симплексов среди всех покрытия М, и(М) - наименьшее число симплексов среди тех покрытий М, в которых размерность пересечения любых двух различных симплексов меньше п, з - число вершин многогранника М, а ш - число гиперграней (т.е. граней максимальной размерности) многогранника М, Га1 ~ ближайшее

(г-|<п-1)/г]-11

Гп'21 \

Г Г-Гг^!-]-. •)

+ р,,-»,^-] в 1.1 доказаны неравенства

*(М)<ггп(з), (1)

^(М)<п1гп(ш) (2)

Указаны п-мерные многогранники, имевшие з вершин, для которых *(М)>ггп(з)/(п+1). Описаны п-мерные многогранники, имеющие т гиперграней, для которых *Ш)>?п(т)/(п+1).

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

Во второй главе рассматривается строение выпуклой оболочки пересечения полиэдра с целочисленной решеткой. Пусть А -целочисленная матрица размерами ш*п ранга п, &г(А) - наибольший по абсолютной величине минор г-го порядка матрицы А, ыг"1, М={х\ Ах<Ь>. В 2.1 изучается строение

выпуклой оболочки точек из в предположении, что матрица А - бимодулярная (т.е. еб миноры п-го порядка равны О, ±1, ±2). Показано, что в этом случае имеет место

Теорема 1.

ребрах Ст,е. одномерных гранях) полиэдра М-

Там же показано, что при \(к)>3 оба утверждения теоремы 1 перестают быть верными. Полученные результаты позволили построить полиномиальный алгоритм проверки пустоты множества МгЯп при условии бимодулярности матрицы А.

Пусть Б - множество вершин полиэдра М, С - выпуклая оболочка точек из М^г", V - множество вершин полиэдра С, Г -множество гиперграней С. Для множества индексов I определим матрицу А(1), образованную строчками матрицы А с номерами из I, и вектор Ь(1), образованный компонентами вектора Ъ с номерами из I. Положим М(1)=(х\ А(1)х<Ь(1)>. Для числа V и точки ш из М определим множество номеров неравенств Ки.с), величина невязки которых в точке ш меньше у-дп(А). Положим М^=Ы(1(и,у/)). Обозначим через С* выпуклую оболочку точек из М^пг", через У^ - множество вершин С*. Г* - множество гиперграней С*. В 2.2 доказана

Там шэ показано, что при у<1 утверждения теоремы 2 перестают быть верными.

В 2.3 результаты о строении множества М-Я" переносятся

1. Если М " телесно, то множество М'~>2П не пусто.

2. Все вершины выпуклой оболочки точек из МГ\Х" лежат на

Теорема 2- Пусть у-П- Тогда имеют место соотношения

(3)

(4)

(5)

на случай, когда полиэдр М задан как множество неотрицательных решений системы линейных уравнений. Пусть Й={у\ уА=с, у>0}, где ceZ". Аналогом теорем о близости 1 является

Теорема 3. Пусть HnZm*{0}, deR™, у=Ш-П, тогда 1 . Для любой точки V иэ fit найдется такая точка Z иэ RnZ7 что выполняются неравенства

(6)

|dy-flz|<vAn+1G). (Т)

2. Для любой точки У иэ Й, в которой достигается

ШОХ dX. найдется такая точка Z из iiinZm» что на ней

хеМ

достигается ШВХ ЙХ, и выполняются неравенства (6)«(7)<

xeMnZm

3. Для любой точки Z из BnZ™, в которой достигается ШаХ dX. найдется такая точка V из Й, что на ней достигается

xeMnZ"

Ш8Х dX и выполняются неравенства (6) ,(7).

хеМ

Пусть 5 - множество вершин полиэдра Н, С - выпуклая оболочка точек из finZm, 7 - множество вершин полиэдра Й, ? - множество гигорграней полиэдра Й. Дяя числа v и точки w из В определим множество индексов I(w,v)=ti\ v\(A)<w1}, и положим Й^={у\ утА=с, у1>0 при iel(w.v)}. Обозначим через Й* выпуклую оболочку точек из множества BJnZ", через -множество вершин полиэдра Й*, через - множество гиперграней полиэдра С*, через 5 - множество вершин полиэдра

1 Cook W., Gerards А.М.Н., Schrljyer А., Tardos I. Sensitivity theorem In Integer linear programming.//Math, progr.- 1986-v34-p.251-264.

е

в. Аналогом теоремы 2 является

Теорема 4• Пусть У-Щ—П. Тогда имеют место соотношения

и (8)

«еО

е= и^, о)

меО

и Г». (10)

«еО

В 2.4, развивая идеи В.Н. Шевченко2, оценивается число вершин полиэдров С и Й. Используя построения главы 1, выводится неравенство

| У|<п!гп (и+1) (1+п1о8гдп (А)+п1оаг (п+1) 1. (11)

Опираясь на результаты 2.2 о строении выпуклой оболочки даресечения полиэдра с узлочисленной решёткой, в неравенстве (11) можно избавиться от влияния Ь. При этом получается неравенство

|7|£п1гп(т)?п(т+1 )(1+2п1о^ (п+1 )дп(А))п. (12)

Из (12) вытекает

Теорема 5- Число вершин выпуклой оБолочки точек из Ып2П при фиксированном П ограничено сверху некоторым полиномом от Щ и 10£гДп(А).

Аналогичные результаты получены и для числа вершин полиэдра С. Аналогом соотношений (11), (12) являются наравенства

о

О числе крайних точек в малочисленном программировании. //Кибернетика.-1981 .-Ю-с. 133-134; Алгебраический подход в целочисленном линейном программировании.// Кибернетика.-1984.-И4-с.36-41; Верхниэ оцэнки числа крайних точек в цалочисленном программировании.// Математические вопросы киЗернетики.-1992-Вып.4.-е.65-72.

|7|<(ш-п)!? т_п(т)!гт__^пн-1 )(1 + (ш-п)1о^ап [а] )т~" (13),

|У(Й)|5(т-п)!?п.^т)ет_|;т+1 )(1+2(т-п)1о82(т-п+1 )лда)Г~п (14),

а аналогом теоремы 5 является

Теорема б. Число вершин выпуклой оболочки точек из Йп2™ при фиксированном Ш-П ограничено сверху некоторый полиномом от Ш и 1о^А (А).

Полученные результаты в 2.5 распространяются на частично целочисленный случай. Пусть В - целочисленная размерами шхк матрица, М={(х,у)\ Ах+Ву<Ь, х^й", уеВ*}, С -выпукла." комбинация тех точек (х,у) из М, у которых Хег", 7 - множество вершин полиэдра С. Показано, что имеет место неравенство

|7|<п!^]?|(т-к)^т-к+1)(1+гп1оЕг(п+1)лп^А,В)Ак(В)п-,)п (15), из которого вытекает

Теорема 7. При лкСых фиксированных Пик число вершин и граней полиэдра С ограничено сверху некоторым полиномом от

т. к, Ю82Дп+к(АВ), Ю^дк(В).

Пусть С - цэлочисленная размерами "Кхп матрица ранга з, с«^", Й=((х,у)\ хе1Г, уе^, хА+уС=с, х>0, у>0>, С - выпуклая оболочка точек ИЗ Йп{(Х,У)\ ХсЯ™, уеИ*}, V - множество вершин полиэдра С, 1=т+з-п. Имеет место неравенство

< (д) 11? 1 (1+п+1 )?х (1+п) (1+21 • (1+1 )дп (а)а, (С)" )* (16),

из которого вытекает

Теорема 8 . При фиксированном (Ш+З-П) число термин и граней полиэдра Й ограничено сверху некоторым полиномом от

т. к, Ю^Ап[д], 10^.(0.

Прежде чем приступить к обзору материала главы 3,

напомним некоторые понятия теории сложности3. Под длиной целого числа а будем понимать 1о^(|а|+1> (т.е. количество знаков необходимых для его записи). Под длиной входа задачи Ф будем понимать сумму длин еб параметров. Для алгоритма ад, решающего задачу ¡р, определим функции: т(ад) - число элементарных операций (сложение, умножение, сравнение, деление), необходимых алгоритму ад при решении задачи ц>: л(и) - максимальная длина чисел, с которыми алгоритм ад производит вычисления при решении задачи ¡р. Алгоритм ад называется полиномиальным, если функции -г(ад) и Л(ад) можно ограничить некоторыми полиномами от длины входа задачи Ф.

Подкласс задач, заданный системой ограничений на входные данные задачи обозначим ч> (ограничение 1; ограничение 2; ...). Если для решения задач из подкласса ?> (ограничение 1; ограничение 2; ...) существует полиномиальный алгоритм, то этот подкласс назовём полиномиальным.

В третьей главе основное внимание удаляется задачам Найти точку из множества Мог", *>ж: Найти точку из множества Йог™, Найти шах сх.

Найти шах сх,

хсйгсг"1

И некоторым их обобщениям. Пусть а - наибольший по абсолютной величине элемент матрицы А, ^=шах{а,|Ь|т), о=оах{/э,|с|ш). Длина входа задачи (1=1,..,4) определяется

^эри М. .Дконсон Дк. Вычислительные машины и труднорешаемые вадачи.-М.:Ынр,1982-416с.

величинами ш, п, а, р и с. Естественно рассмотреть подклассы, получающиеся ограничением этих параметров.

Полиномиальный алгоритм к решения задачи р назовем строго полиномиальным, если т (<и) зависит только от m,n и а.

Одно из направлений выделения полиномиальных подклассов связано с ограничением размерности п. Полиномиальность подклассов jp4 (n=2) и ip3(n=2) показана несколькими авторами Веселовым С.И.4, Feit S.D.3 и Kannan R.6. Ленстра7 предложил алгоритм редукции n-мерной ЗВДП к аналогичным задачам меньшей размерности, число которых ограничено константой Фп, зависящей только от п. Таким образом он показал полиномиальность подклассов Ф4 (п-фиксировано) и Рг (п-фиксировано). За счет уменьшения величины Фп показана полиномиальность подклассов ^t(nso(inklw)) и Ps(n£0(lnkln")) при к=1/3 (см.[31), при к=1/28 (и,

4 Строение множества допустимых решений в

некоторых задачах дискретного программирования: Автореф.

дис... канд.физ.-мат.наук.-Минск,1985.-14с.

R

A last algorithm for the two - variable Integer programing ргоЫетз.// J. ACM.-1984.-v.31 .-p99-113.

e A polynomial algorithm for the two varlably-lnteger programming// J. oi ACM.-1980.v.27. pi 18-122.

7 Integer programming with a fixed number oi variables/ Dep.Math.Unlv.Amsterdam,Amsterdam,1981,20p Report 81-03

8 benstra A.K., Lenstra H.W., Lovaaz I. Factoring pollnomlals with rational coefficients.//Math. Ann.,1982, v.261, p513-534.

независимо, в [10]), при к=1-«9, где с>0 - любая константа. Задача уменьшения Фп тесно связана с задачей приведения квадратичной формы хтСх, которая рассматривается в 3.1 и 3.2. Напомним, что 3-м минимумом квадратичной формы хтСх называется такое число М., что

а) линейная оболочка векторов из множества <х\ хтСх£М.,хе2п> имеет размерность не меньше 3.

б) линейная оболочка векторов из множества (х\ хтСх<М.,хегп) имеет размерность меньше

В 3.3 показывается ЫР-полнота задач

Найти такие линейно независимые векторы г1,г2,... ,гп,

что г1Сг1=М1 при 1=1,2.......

По заданному вектору у найти целочисленный вектор г-, дая котрого величина (у-г)тС(у-г) принимает наименьшее значение - тесно связанны с приведением квадратичной формы. В 3.4 выделяется ряд новых полиномиальных подклассов ЗЦЛП, получающихся ограничением размерности п. Показано, что имеет место

Теорема 9. Подклассы ¡Р4 (п£0(1п1<:1па) ),

¡^(т-п^оип^Ша)), ^(гагоЦп'"^»»)) и ф4(т-п£о(1п,"с1па))

при любом фиксированном с>0, - строго полиномиальные.

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

Ра: Построить все вершины и гишрграни выпуклой оболочки точек из Йпг™.

Q

Kannan R. Minkowski's Conex body theorem and integer .programming problems.//J. ACM.-1987.-v.30,No1.- p.133-145.

Имеет место

Теорема 1 0* Подклассы (П~"фиксировано) и П-фиксировано) — полиномиальные.

Обобщением поставленных выше задач на частично целочисленный случай являются задачи ;р?: Найти точку из множества С.

¡рв: Найти точку из множества Й. <рр: Найти решение тах сх.

хеС

¡Р10: Найти решение шах сх,

хеС

Ф41: Построить все вершины и гидарграни полиэдра С. Ф12: Построить все вершины и гиперграни полиэдра Й. Имеет место

Теорема 11. Подклассы ф

Фв(т+з-п<о(1п'"£1по1)), рр(а<о(1п1"£1па)) и

при любом фиксированном £>0, и подклассы (П+к—фиксировано ) и ф^ (т+З-П-фиксировано ) — строго полиномиальные.

Другой подход к выделению полиномиальных подклассов связан с понятием псевдополиномиального алгоритма. Алгоритм « решения задачи Ф называется псевдополиномиальным, если функции т(<ц) и л(<ц) можно ограничить полиномами от п,т,а,/э и а. Очевидно, что из существования псевдополиномиального алгоритма вытекает полиномиальность подклассов Ф(°^р(п,т)), где р(п,т) - любой фиксированный полином. Известно10, что

10 Papadlmitrion С.Н. On the complexity of Integer programming// J. of ACM.-198I.-v.28,No4 - p765-768.

существует псевдополиномиальный алгоритм для подклассов *Р2(п - фиксировано) и ¡Р4(п - фиксировано). В.Н. Шевченко усилил этот результат, а именно показал полиномиальность подклассов ¡ра(п - фиксировано; «<р(т)) и ч»4(п-фиксировано; а<р(т)). В 3.5 показывается полиномиальность подклассов Р2(п -фиксировано; дп(А)<р(т)), Ф4(п-фиксировано; дп(А)<р(т)), ^(т-п - фиксировано; дп(А)<р(т)) и Фэ(т-п - фиксировано; дп(А)<р(т)).

Отметим, что существует гипотеза, принадлежащая В.Н. Шевченко, о полиномиальное™ подклассов Фх(Дп(А) -фиксированно), где 1=1,..,4. В подтверждение этой гипотезы доказана полиномиальность подклассов Ф1(Дп(А)<2) и ¡Ра(Дп(А)52).

В заключение хочу выразить искреннюю благодарность В.Н. Шевченко за руководство моей работой и С.И. Веселову за обсуждение и ряд полезных замечаний. Список литературы.

1. Веселов С.И., Чирков А.Ю. О задаче целочисленного линейного программирования с бимодулярной матрицей// Комбинаторно-алгебраические и вероятностные метода и их применение: Межвуз. сб. -Горький, 1990. -с. 1СГГ-110.

2. Веселов С.И., Чирков А.Ю. О строении многогранника задачи целочисленного линейного программирования с бимодулярной матрицей// Тез.докл. 11 Всесоюз.конф. Проблемы теоретической кибернетики.Часть 1(3).-Волгоград,1990.-с.15.

3. Гаряев Я.Е., Шевченко В.Н., Чирков А.Ю. Об алгоритме Ленстры приведения базиса решетки/Горьковский гос. ун-т им. H.H. Лобачевского.-Горький,1985.-12с.-Деп.в ВИНИТИ 10.10.85, NT165-B85.

4.Чирков А.Ю. О нахождении вектора решётки, ближайшего к гиперплоскости пространства// Тез.докл.Всероссийской научной студ.конф.-Омск,1985-с.3-4.

5. Чирков А.Ю. Полиномиальный алгоритм выпуклого программирования //Тез.докл.8 Всесоюз.конф. Проблемы теоретической кибернетики.Часть 2-Горький,1988.-с.165.

6. Чирков А.Ю. О сложности решения задачи целочисленного линейного программирования//Комбинаторно-алгебраические методы в дискретной оптимизации: Межвуз.сб.-Н.Новгород,1991. с.133-139.

7. Чирков А.Ю. О числе крайних точек в задаче целочисленного линейного программирования// Там же.-с.157-159.

8. Чирков А.Ю. Теорема Каратеодори и покрытие многогранника симплексами/Нижегор. ун-т им. Н.И.Лобачевского -Нижний Новгород, 1993-12с.-Деп.в ВИНИТИ 19.ОЗ.93,N668-693.

9. Чирков А.Ю., Шевченко В.Н. О квазиполиномиальных алгоритмах для некоторых задач целочисленного программирования //Тез.докл.Бесп.семинара по дискретной оптимизации.Ужгород, 28-30 мая 1985г.- Киев Ин-т кибернетики АН УССР, 1985.-с.124-125.

10. Чирков А.Ю,, Шевченко В.Н. О нахождении последовательных минимумов целочисленной решётки и вектора решётки, ближайшего к данному// Кибернетика.-1987,N4.-с.46-49.

11. Чирков А.Ю., Шевченко В.Н. О разбиении конуса на унимодулярные и построении двойственно-допустимых баз в целочисленном программировании//Комбинаторно-алгебраическиэ метода в дискретной оптимизации: Межвуз.сб.-Н.Новгород, 1991.-с.119-133.

12. Чирков А.Ю., Шевченко В.Н. Задача о разбиении конуса на

элементарные и ее приложения в цэлочисленном линейном программировании//Тез.докл.научной конф.Математическое программирование и приложения.-Свердловск: УрО АН СССР, 1991.-с. 145-146.

13. Чирков А.Ю, Шевченко В.Н. О построении множества крайних точек в задаче малочисленного линейного программирования //Тез.докл. межгосударственной научной конф. "Экстремальные задачи и их приложения" Н.Новгород, 1992.-с.124

14. Чирков А.Ю., Шевченко В.Н. О числе вершин выпуклой оболочки пересечения полиэдра с целочисленной решеткой/ Нижегор.ун-т им.Н.И.Лобачевского -Нижний Новгород, 1993-12с.-Дзп. в ВИНИТИ 29.ОТ.93, N2165-B93.

15. Шевченко В.Н., Чирков А.Ю. О нахождении вектора решётки, наименее уклоняющегося от нуля//Принятие оптимальных решений в экономических системах: Межвуз.сб.-Горький,1986.-с.18-22.

16.Шевченко В.Н., Чирков А.Ю. Очисле крайних точек ЭЗЦЛП с булевыми ограничениями//Тез.докл.Респ.семинара по дискретной оптимизации.Ужгород, 1990г.- Киев Ин-т кибернетики АН УССР, 1990.-c.77.

17. Шевченко В.Н., Чирков А.Ю. О сложности решения задачи целочисленного линейного программирования// Тез.докл. Системы программного обеспечения решения экономических задач.-М.:ЦЭМИ АН СССР, 1992.-с.61-62.

18. Шевченко В.Н., Чирков А.Ю. О сложности решения задачи целочисленного линейного программирования// Методы и системы технической диагностики: Межвуз.сб.-Саратов,1993.с. 189-190

19. Chlrkov A.Ju., Shevchenko V.N. On complexity of the description of the Intersection of the polyhedral and Zn// Workshop on Discrete Optimization.-Minsk,1993.-p56.