Полиэдральный подход в задачам комбинаторной оптимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ИНСТИТУТ МАТЕМАТИКИ АКАДЕМИИ НАУК БЕЛАРУСИ

■ i о m есз

УДК 519.1:8

ктииньскА ноашА

полиэдральный подход к задачах йомбинаторноя оптимизации

01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата фиаико-штеяатических наук

Минск - 1995-

Работа выполнена в Белорусском государственном университет!

Научный руководитель: кандидат физико-математических наук,

доцент ИСАЧЕНКО А. Н.

Официальные оппоненты: доктор физико-математических наук.

профессор ЩГЕЛЬСКШ Н. Е

кандидат физико-математических наук, старший научный сотрудник КРАВЦОВ и. К

Оппонирующая организация: Институт технической кибернетики

АН Беларуси

Защита состоится "2.в" Ак^о^Я 1996 года в " часов заседании совета по защите диссертаций Л 01.02.02, в Институ математики АН Беларуси по адресу: 220072, г. Шнек, ул. Сурганов 11, Институт математики АН Беларуси.

С диссертацией можно ознакомиться в библиотеке Института м тематики АН Беларуси.

Ученый секретарь совета по защите диссертации

А. И. Астровси

огдая характеристика работы

Анализ допустимого мне жеста решений и использование релаксационных задач позволяют либо повысить эффективность известных методов ренения, либо разработать новые методы решения задач дискретной и комбинаторной оптимизации. В диссертационной работе исследуется ЛП-релаксационная задача для задачи безусловного квадратичного программирования с -1,1-леременнными и задача на пересекающихся отрезках. Задача безусловной квадратичной оптимизации с -1,1-пёременными представляет интерес в связи с сводимостью к ней ряда известных НР-полных задач комбинаторной оптимизации и задач теории твердого тела по определению устойчивого состояния кристаллических решеток. Задача на непересекающихся отрезках является задачей на специальном классе комбинаторных конфигураций и обобщением задач на множестве перестановок. Она возникает в области проектирования интегральных схем и связывающих сетей.

Для обеих задач в качестве аппарата исследования применяются современные подходы полиэдральной комбинаторики по анализу структуры выпуклых оболочек допустимых множеств решений.

Сказанное и определяет актуальность теш диссертации. Работа является продолжением исследований, проводимых в Белорусском государственном университете на факультете прикладной математики и информатики и выполнена в соответствии с индивидуальным планом аспирантской подготовки, госбюджетной темой "Разработка методов и алгоритмов решения задач оптимизации информационных потоков, распознавания образов и обработки естественно-языковой информации как модулей интеллектуальных автоматизированных систем", номер гос. регистрации 01920001546, выполняемой по плану АН Беларуси, и госбюджетной темой "Разработка теории устойчивого математического моделирования систем, логико-комбинаторных и вероятностно-статистических методов оптимизации и распараллеливания вычислительно-информационных процессов", план Бедгосуниверситета. приказ БГУ ОТ 25.09.91, N 97-Д.

Целью работы является: 1) описание множества вершин ре;, .кса-ционного многогранника с полиномиальным числом ограничений для

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

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

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

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

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

ляемого целевой функцией и ограничениями исходной задачи. Лается определение релаксационной задачи через множество гиперграней многогранника эквивалентной задачи линейного программирования.

Центральное место занимает исследование релаксационной задачи с полиномиальным числом ограничений. Вводится понятие остовно-го релаксационного многогранника. Рассматривается многогранник релаксационной задачи и изучается множество его вершин. Показано, что он является оетовным для многогранника эквивалентной задачи линейного программирования. Указано семейство его нецелочисленных вершин. Приводятся результаты численного эксперимента для релаксационной задачи.

Рассматривается также оптимизационная задача на множестве непересекающихся отрезков. Дается постановка практической задачи геометрического проектирования, приводящей к ней. Еводится в рассмотрение многогранник непересекающихся отрезков. Определена его размерность, описывается множество вершин и исследуется отношение смежности между вершинами. Приводится семейство гиперграней для многогранника на непересекающихся отрезков. Предлагается полиномиальный по сложности алгоритм для линейной задачи на непере-секащихся отрезках. Алгоритм иллюстрируется примерами.

Все основные результаты диссертационной работы получены автором сашс то яте ль но.

Апробация результатов диссертации. Результаты диссертационной работы докладывались на:

- Международной конференции "Новые предприятия в процессе строительства Большой Европы", сентябрь 1983 г.. Минск;

- Межгосударственной научно-практической конференции творческой молодежи "Актуальные проблемы информатики: математическое, программное и информационное обеспечение", 16-20 мая 1994 года, Минск;

- Республиканской научно-методической конференции, посвященной 25-летию ФПМИ Белгосуниверситета, 10-14 апреля 1995 года, Минск.

Результаты диссертационной работы опубликованы в шести работах.

Структура и объем диссертации. Диссертация состоит из введе-

ния, общей характеристики работы, трех глав, выводов и спис:<а использованных источников.

Объем диссертационной работы - 61 страница, включая две таблицы и список использованной литератур«, который содержит 137 наименований.

основное содержание

В первой главе дается краткий обзор результатов полиэдральной комбинаторики. Глава состоит из трех параграфов. Здесь определяется основной объект исследования полиэдральной комбинаторики. Таким объектом является выпуклый многогранник, который можно определить двумя эквивалентными способами: как выпуклую оболочку конечного множества точек или как ограниченное пересечение замкнутых пространств. Все рассуждения ведутся в Евклидовом пространстве. Полиэдральную комбинаторику можно понимать в широком смысле слова и в узком. В широком смысле слова полиэдральная комбинаторика включает в себя следующие три основные проблемы: 1) определение комбинаторных характеристик многогранников; 2) описание графов многогранников; 3) переход от одной формы задания многогранника к другой. Напомним, что если Р многогранник, то его размерность dim Р есть размерность аффинной оболочки Р. Если И -опорная к Р гиперплоскость, то F - Р Н является гранью многогранника, которая называется i-гранью, если dim F - i. 0-мерная гран] - это вершина, 1-мерная - ребро и (dim Р - 1)-мерная - гипергран! многогранника Р. Основной задачей раздела полиэдральной комбинаторики, связанного с комбинаторными характеристиками, является исследование возможных реализаций числа i-граней. Под графом многогранника понимается совокупность его вершин и ребер, фундаментальными здесь являются теоремы Е. Шгейница и А. Балинского. Отметим, что многие графовые характеристики, такие как радиус, диаметр, плотность, могут служить косвенными оценками сложности решаемых задач и эффектив"ости используемых алгоритмов, если допустимая область решаемой задачи является многогранником.

В настоящее время под полиэдральной комбинаторикой обычно

А*«Ь}

юнимаюгг метод изучения комбинаторных задач и задач дискретной »птимизации с помощью многогранников и линейного программирова-гия. Ее подход заключается в том, что по исходной задаче комбинаторной или дискретной оптимизации строится эквивалентная задача мнейного программирования

тах (стХ 1

&тя очевидно, что система А~Х- ^ Ь существует для любой задачи декретной или комбинаторной оптимизации, ее размерность для многих задач является слишком большой и ее полное описание сопряжено ; рядом принципиальных трудностей. Поиск А матрицы и вектора Ь да конкретной задачи комбинаторной или дискретной оптимизации и ¡оставляет основную теоретическую проблему полиэдральной комбинаторики.

Заметим, что для любой нр-полной задачи не получено полное эписаше соответствующего многогранника. Это объясняется тем фактом, что, как показали Р. М. Карп и X Пападимитриу, задачи получения гиперграни, опорной гиперплоскости для многогранников кр-пол-пых задач также являются по крайней мере нр-полными.

Основными методами решения нр-полных задач дискретной и ком-Зинаторной оптимизации являются различные модификации метода ветвей и границ и метода отсекающих плоскостей. В обоих методах существенную роль играет построение релаксационной задачи, определяемой целевой функцией и релаксацией допустимой. области исходной • задачи. Релаксация в большинстве случаев ищется в виде выпуклой оболочки некоторого множества решений, а релаксационная задача - в виде задачи линейного программирования. Использование ЛИ-релаксаций важно также при построении приближенных методов решения задач дискретной и комбинаторной оптимизации. Само решение Ш-релаксационной задачи может служгь приближенным решением. В связи с вышеизложенным представляется целесообразным исследование полиэдральных характеристик и релаксаций для конкретных' задач дискретной и !томбинаторной оптимизации.

Во второй главе рассматривается "следушая задача квардратич-ного программирования

(х(Ахт) +СЬ,хт)*с1 хе[-1.*]п (1)

Здесь А - л* п -матрица, Ь - л -вектор, Ы. - скаляр. (-1,1)' - множество п.-мерных векторов с компонентами, равными -1 ид 1. Одной из наиболее известных проблем, приводящих к задаче (1) является проблема Айзинга в теории твердого тела по определени устойчивого состояния кристалличесгой решетки металла с незначи тельным содержанием магнитной примеси. Задача покрытия матрицы задача определения максимального разреза для полного неориентиро ванного графа являются частными случаями задачи (1). Следователь но, задача (1) является НР-трудной в сильном смысле.

Запишем для задачи (1) эквивалентную задачу линейного прог раммирования. Для этого 'введем в рассмотрение новые переменны

Тогда задача (1) примет вид

+ (2)

, I а/ <v __

X^j-ijj , / , ¿t} (3)

где ID - Л* а - матрица с элементами dcj - Q.^, i.l(j = TjZ f ifj, du^bi; L= d^rZ ( C*d '¿сии,

^•"'■^•J £тт -p, 4 . - скалярное произведение матриц.

Пусть М„. - множество п-*п- -матриц, удовлетворяющих уело вию (3), a CK(M-n,)3Ccm'M(i. Задача (1) эквивалентна задаче ли нейного программирования с целевой функцией (2) и условием Х^СНОДфсновние характеристики многогранника

скал

rv ) являютс

известными. Так установлено *), что vert СН(М.О- -М-г., dimCKCNiL) - i)n./z, СК(ЯУ

Известно также следующее семейство гиперграней для СК(Мп.)*). ТЕОРЕМ 1. Для п. >2. каждое из неравенств

*) Исаченко А. Е , Махибулла Абдулла. Вестник Белорус, ун-та Сер 1.: физ., мат., мех. - 1989, N 2. - с. 61-64.

Xcj -Xi.*, ^ ^¿i "■^"Ji^ -Xij + 4 i, -Xa OC- ¿i,

""^¿j -Х^к —-^jiî 'i, "Xii. ^

L с j< к: 4 a. , определяет гиперграна многогранника CKfM Заметим, что общее число гиперграней СН-(Мп.)экспоненциаль-о зависит от гь .

Дадим строгое определение релаксационной задачи. Пусть J^JB', В>2*),.. ;&m lj - последовательность о* п.-матриц, . Ь- пь- вектор, определяйте полную неприводимую систему линей-:ых неравенств для СКСМ-.».). Тогда задача (1) эквивалентна зада-

te ли у, s [Г, BCi, ... ; Bi"6 - подпоследовательность последова-■ельности Ъ , то задачу

С&ЧХ^к, к-U,

[азовей. релаксационной. для задачи С1). Соответственно многогран-1ик Р( , определяемый ограничениями релаксационной задачи, [азывают релаксационным для Р('|3)=СК(Мл). Естественно к репарационному многограннику предъявлять следующие_требования:

1) число линейных неравенств, задающих Р С Jb} ограничено ¡верху полиномом от гь- ;

2) PCb) является выпуклым многогранником, то есть ограничен;

3) vert Р(|) П vert P(jb) # ф.

Назовем Р( jj) остовным релаксационнш многогранником, если vert Р(|) 3 vert j>(j5),

"о есть если каждая вершина РСр) является вершиной Р0Ç).

Во второй главе исследуется релаксационный многогранник, оп-)еделяемый системой из 2/3 1) линейных неравенств теоремы

1. Обозначим его через

ТЕОРЕМА 2. £-L.(Miv) является остовным релаксационным многогранником для СК(Ма)-

Наряду с теоремой 2 получено более сильное утверждение, а

именно

ТЕОРЕМ 3. Любой релаксационный для СК(М^ многогранник включающий ограничения

является остовным.

Показано совпадение множества целочисленных вершин многогранника К-ЦМ^с множеством вершин многогранника СК(М.*.]. Данный факт устанавливает ^»п.

ЛЕММА 1. Симметрическая л-хп.-матрип'1 при

надлежит Мц, тогда и только тогда, когда X удовлетворяет следующим неравенствам

^ «V. ^ ' ~ХЧ* *

и

ТЕОРЕМА 4. Если У1 целочисленная вершина

ЛЦМО.

то

ХеМ

Многогранник ЯЬ (Мл.) имеет вершины, отличные от вершин многогранника СН(М«-)- Получено следующее семейство полностью нецелочисленных вершин.

ТЕОРЕМА 5. При ^ 4 для любого {'Лу-.^З симмет рическая л-у гъ матрица с элементами

хи= Цз.Ьеы, эсу6 --4/3, ] е^^

является вершиной К-ЬОЛ.^.).

Непосредственно из теорем 2, 4, 5 вытекает, что число верши релаксационного многогранника £Ь(.М.„] не меньше 2.

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

ихь rru.ru ,

В качестве коэффициентов , ¿. 4 ^ , бргишсь равномерно

распределенные на интервале [-10 , 10 ] случайные числа. Решено 50 задач для а . равного 5, 10, 11, 12. Во всех 50 задачах оптимальное решение получено на матрице множества М.^ причем для задач одной размерности совпадающих решений нет.

В третьей главе "Задача на непересекающихся отрезках" рассматривается следующая задача ^

Пусть А-- (а1, ■■••/Оп.)- фиксированный вектор в Я ,

причем сы-а^-Д >0 , ¿.г2,л- . обозначим через М % к множество векторов в^ о координатами из множества чисел..^О.^ , которые удовлетворяют следующим условиям:

или ггь1'п.(У:г.1.11х:21 <) > тах (Х2Р.11Х-2?), или та* [Х^.^Хи] < ^^[Хг^Хг.?] , для каждой пары индексов •••/'Л И-ЛП . Р -На мно-

жестве М-^ задана некоторая функция г . Задача записывается в

Еоли функция Р является линейной или вогнутой, то (2) эквивалентна задаче Рл/-\ ..

та* Г(ХЛ Х^Мгк

гдеСН(МД|4) есть выпуклая оболочка множества Мгц.

Если пару Хгй-1 . рассматривать как координаты отрезка

на прямой, то условия, накладываемые на векторы из М-2к,, означают, что отрезки LЗ¿Гi^>i/X1¿]t СХгр-^ХдрЗ не должны пересекаться для любых .

Для вектора А. через обозначим пару его компонент

(€¡.¿,0.^). При а: => для простоты записываем как Ас .

Если - множество всех перестановок на ¿4,2.,..., К^ , то для 2.К-вектора V" и перестановки Я векторУШ)=(У"п\{гг-1,2*.))

представляет из себя вектор, полученный перестановкой II пар его компонент "^12.,Уз.Ч)К • Каждой перестановке Цбр* мы можем поставить в соответствие перестановку X &$гк. о условием Очевидно, что при этомУ^.^; Размерность многогранника устанавливает

ТЕОРЕМА б.

при г\- = к . при

Множество вершин многогранника СКСМ^к) Дает

ТЕОРЕМА 7. Вектор и,6.М21, является вершиной СК(МЛк,) тогда и только тогда, когда юеЛСП.) • яля некоторого вектора

А*.)

С (¿.¡) б [(?.?>> Сп-к+р,^, Сп-^р,п-ч*р)],

I ё, р ^ К , и некоторой перестановки .

Согласно теореме 7 мы можем разбить множество хг^ СгГ(М2к) на два подмножества и , отнеся к У] все^вершины. удовлетворяюще системе уравнений , 1,к. , и положив - 1гвг1 СКСМ-гь;) ^ХГ^ • Заметим при этом, что в случае п--к: ,

Исследуем отношение смежности для множества .

ТЕОРЕМА 8. Пусть 1Л бЛ/^ и определяется перестановки Д. пар — Тогда, если для у- выполня-

ется одно из следующих трех условий: •

6У2. и отличается от и> транспозицией пар компонент где или п.-к+р+14 Ь^хь'1 •

2) у6"Чг. и получена заменой в и, нечетного числа 25-* , где 4.4 , компонент, равных о-р-^+х^^+г •••/ ^р на компоненты , Ап.^рсоответственно;

3) Ц&Уг. и получена заменой в и. нечетного числа 2.3-,1 , гдеА*54*-р , компонент, равных . ,.,А «-«^р**-^.^ на компоненты 0р+5 соответственно; г то вершина у смежна с вершиной и, .

ТЕОРЕМА 9. Пусть и определяется перестановкой Л

пар где

Тогда, если для у выполняется одно из следующих трех условий:

1)1^6."^ и получено из и- заменой четного числа 2.^, ¿¿¿¿р, компонент, равных -Др-«, р-ь-»!,.А р-1 А р на компоненты, равные Апп-к+р-.з+х,.--//^соответственно;

2) ^* ;ЛГг и получено из и заменой четного числа -14 ^^ р.

и

компонент, равных Л n-c+p+jfl.-*»ptsHa компоненты, равные -/lpp-ii^ ..Ap+s-i pts соответственно;

3) и ¿чг и получено из и- транспозицией пар , где

ItLtp-l иж n-r+p-H £ t 4 IV ; то вершина t| смежна с вершиной и- . Рассмотрим задачу

J? Ci^Ci mi. п., М-г* •

£*i _.

Не нарушая общности будем считать, что CLi>0, ¿-»4,п., >и все &liO . Определим свойства оптимального решения, которое обозна-

Xttot

{/tot

свойство 1. Если UgnC^.^sign ( то Х^-Х^-. СВОЙСТВО 2. Если sign Cji.i" Sign , то

rnu(£6Lx.L (Xe MiK 1 -- naru[¿fiXt j •

СВОЙСТВО 3. Пусть П.¿St. - перестановка,. упорядочивающая пары ( Qzi-i., C-2.L) коэффициентов линейной функции по неубыванию их суш, а Х- соответствующая ей перестановка из , и при этом

Тогда вектор JC с компонентами у' --г'

является оптимальным решением задачи

^CiX-L-* Пи-чХ^.

На основании свойств 1-3 предлагается следующий алгоритм решения линейной задачи на непересекающихся отрезках. Обозначим через лучшее текущее решение задачи и пусть для вектора X С С

¿»I

ВХОД. Коэффициенты линейной целевой функции ...,Сгк

и последовательность чисел cui,a2 ,. . Q.^, с Qc-is

йс>0.

1/-9/>С

ВЫХОД. Оптимальное решение X МЕГОМ- лг

Этап 1 (поиск оптимального решения на множестве п ). Шаг 1. Упорядочиваем пары (С, С^ ) коэффициентов целевой функции по неубыванию их сумм

Сха; * С-лш-^^я-С**) ■

Шаг 2. Полагаем

I I

Этап 2 (поиск оптимального решения задачи) Шаг 2. Полагаем р = 0-Шаг 2. р: = р+4..

Шаг 3. Если ^¿дп С-я ир-х) - (¿.р)

Шаг 4. Полагаем ^ ** С>-

О-л.-^ , если

а.ч^ • если Сц^-ц + Схы^о,

то идем к шагу 9.

Шаг 5. = ^ +1 • Шаг 6. Полагаем

X

<

X'

=Х

лСи-1) ^я(хс) Шаг 7. Полагаем

если С-хър-¡.)>0' если

если если если

если ¿¿р! ус ¿р,

■ к. _

. если

, если ¿¿р, с , если с > ^пах ^, р].

. при СОс'ХСОс), , при СО

Шаг 8. Если ^ С К , то идем к шагу 5.

Шаг 9. Если р<£ К .то идем к шагу 2. Если рг К , то алгоритм заканчивает работу и Х^^Х*" .

ТЕОРЕМА 10. Алгоритм находит оптимальное решение и занимает не более времени.

Пусть К множество пар индексов 2), (3,4),.. .,(2 к,

i ^ООеемейство всех частичных трансверсалей |С .

ТЕОРЕМА 11. При каждое из следующих неравенств опре-

деляет гипергрань многогранника

La оо ¿» i |

2 Х- ^ ¿?an_t4l-

выводи

Итак, в диссертационной работе получены следующие основные результаты.

1. фи задачи безусловного квадратичного программирования с -1,1-переменными введена в рассмотрение ЛП-релаксационная задача с 2/34(11^-1) ограничениями, где л - размерность исходной задачи, и релаксационный многогранник RlXUfJ, определяющий множество ее допустимых решений.

2. Введено понятие остовного релаксационного многогранника и показано, что ЛЦЫп) является остовным для многогранника задачи квадратичного программирования с -1,1-переменными.

3. Исследовано множество вершин многогранника ИЦН„). Опре-" делено множество целочисленных вершин и семейство полностью нецелочисленных вершин.

4. Проведен численный эксперимент для ЛП-релаксационной задачи при условии равномерного распределения коэффициентов целевой функции.

. 5. Введена в рассмотрение задача на непересекающихся отрезках и соответствующий ей многогранник непересекающихся отрезков.

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

7. Выявлены свойства оптимальных решений линейной задачи на непересекающихся отрезках и предложен квадратичный по времени алгоритм ее решения.

список опубликованных работ

1. Исаченко АН., Ешеминьска И. Многогранник непересекающихся отрезков // Ред. жури. "Вестн. Белорус, ун-та. Сер. 1.: физ. , мат., мех." - Минск, 1994. - 11 с. - Деп. в ВИНИТИ 02.03.94, N 524-В94.

2. Исаченко А. Е, Кшетньска И. Линейная задача на непересекающихся отрезках // Материалы Республиканской научно-методической конференции, посвященной 25-летию ФПМИ Белгосуниверситета 1014 апреля 1995 года, Минск, Республика Беларусь. - Минск; Велго-суниверситет, 1995. - с. 79.

3. Исаченко А. Н., Кшеыиньска И., Раевская Л А. Релаксация задачи квадратичного программирования с -1,1-переменными // Ред. журн. "Вестн. Белорус, ун-та. Сер. 1.: физ., мат., мех." - Минск, 1995. - 21 с. - Деп. В ВИНИТИ 25.01.95, N 218-В95.

4. Кшетньска И. Смежность вершин многогранника неперересаю-щихся отрезков // Актуальные проблемы информатики: математическое, программное и информационное обеспечение. Материалы Межгосударственной научно-практической конференции творческой молодела 16-20 мая 1994 года, Минск, Республика Беларусь. - Минск: Белго-суниверситет, 1994. - с. 75-76.

5. Кшеминьска И., Раевская JL А. Экспериментальное исследование релаксации квадратичной задачи с -1,1-переменными // Материалы Республиканской научно-методической конференции, посвященноЯ 25-летию ФПМИ Белгосуниверситета 10-14 апреля 1995 года, Минск, Республика Беларусь. - Минск: Белгосуниверситет, 1995. - с. 80.

6. Isachenko AN., Krzeminska I. Mathematical models ir control design // In: New Venture in the Process of Grand Europe. Economic Development. II Congress. September. - 1993. Minsk. -p. 48.

РЗЗЙМЭ КШЕМПШЖА 1АЛАНТА

ШШЭДРЛЛЬНЫ ПАДЫХОД да ЗАДАЧ камб1нлторная аптышзацы1

Ключавыя словы. Аптым1зацня, камбшаторыка, пал1эдр, пал1эд->альная камбшаторыка, мнагагранмк, памернасць, вяршыня» сумеж-1асдь, грань, ппергрань, въшчалъная складанасць, рэлаксацыя, икавы эксперимент.

Аб'екты даследвання. Даследваюцца дзве задачы камбшаторнай штьшзацьн: задача бязумоуната квадратычнага праграмавання з ■1,1-эменнья.и 1 задача на адрэзках, ятя не перасякаюцца.

Мэта працы. Будаванне ЛП-рэлаксацыйнай задачы з палшашаль-(ай колькасцю абмежаванняу для першай з ¡х ! вы;значэнне характа->ыстык выпуглай абалонк! дапушчальнага мноства развязак для дру-■ой.

Мэтади даследвання. У якаст метада даследвання выкарыс-■оуваецца падыход пал1эдральнай камб^наторыкк

Атрыманыя вын!К1 1 нав!зна. АШсаны мноства цэлал^кавых вяр-инь 1 сям'я цапкам нецэлашкавых вярпинь для рэлаксацыйнага мна-■агранн1ка. Уведена паняцце каркаснага мнагаграяшка 1 указана :ям'я пперграняу, уключэнме ЯК1Х у с1стэму абмежаванняу гарантуе аркаснасць рэлаксацыйнага мнагагранниса. Вызначаны асноуныя ха-1актарыстыкг вьлуклай абалонк1 мноства дапушчальных развязак за-[ачы на неперасякальных адрэзках. Даецца пал1номны па часу алга-|ытм развязання лхнейнай задачы. Усе вьпнк! атрыманы упершыню.

, Гал1на прымянення. Атрыманыя вынж1 магчыма прымяняць для ¡азвязания навукова-прыкладных задач тэорьа цвёрдага цела 1 прак-'авання 1нтэгральных схем, як^я укладваюцца у рамк1 разглядаемых вдэляу.

РЕЗКЫЭ

ШЕШШЬСКА ИОЛАНТА

полиэдралыш подход к .'задачам к01ши1{аг0р1юя оптимизации

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

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

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

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

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

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

summary

KRZEMINSKA JOLANTA

POLYHEDRAL approach to ockbinatorial optimisation problems

Keywords. Optimisation, "combinatorics, polyhedron, polyhedral combinatorics, polytopy, dimension, vertex, adjacency, face, facet, computational complexity, relaxation, computational experiment.

Objects of research. Two combinatorial optimisation problems, the unconditional quadratic problem with -1,1-variables and the problem of minimising over the set of non-intersecting segments, are investigated.

A purpose of work. The purpose is to construct LP-relaxation problem with polynomial number of restrictions for first of them and to give a characterisation for the convex hull of feasible solutions for second problem.

Methods of research. The polyhedral approach is used for investigation.

The results obtained and novelty. The main results contain description of integer vertices and non-integer vertices of the relaxation polytope, definition of spanning polytope and some conditions for spanning polytope, main characteristics for convex hull of non-intersecting segments set and polynomial time algorithm for linear functions. All results are given for the first time.

. Fields of application. The results can se used in solid state physics and in design of integrating network.