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

• Симанчев Руслан Юрьевич
• доктор наук
• 2020

Оглавление диссертации доктор наук Симанчев Руслан Юрьевич

регулярный алгоритм

2. Полиэдральный подход и процедура отсечения

2.1. Полиэдральная постановка ЭКЗ, процедура

отсечения и задача идентификации

2.2. Необходимые условия фасетности опорных

неравенств

2.3. Достаточные условия фасетности опорных

неравенств

3. Вершины и фасеты многогранника Ь-факторов

3.1. Полиэдральная релаксация и нецелочисленные вершины

3.2. Критерий смежности вершин релаксации

многогранника Ь-факторов

3.3. Кликовое число многогранника связных

к-факторов

3.4. Линейные симметрии многогранника

паросочетаний

3.5. Многогранник связных к-факторов

3.6. Фасеты многогранника связных к-факторов

3.6.1. Тривиальные фасеты

3.6.2. Кликовые фасеты

3.6.3. Неравенства Эдмондса

3.7. Задача идентификации для класса кликовых

неравенств

3.7.1. Полиномиальная разрешимость при четных к

3.7.2. Алгоритм отсечения и результаты численного эксперимента

4. Схема ветвей и отсечений для задачи

разбиения на клики

4.1. Полиэдральная релаксация

4.2. Опорные и фасетные неравенства

4.2.1. к-парашюты: условия опорности

4.2.2. к-парашюты: условия фасетности

4.3. Сложность идентификации к-парашютов

4.4. Эвристики для идентификации 1-парашютов

4.5. Верхние оценки (рекорды)

4.5.1. Начальный рекорд

4.5.2. Округления

4.6. Алгоритм отсечения и нижние оценки

4.7. Алгоритм ветвей и отсечений

4.8. Вычислительный эксперимент

5. Полиэдральный подход в теории расписаний

5.1. Обслуживание требований параллельными приборами

5.1.1. Многогранник задачи и целевая функция

5.1.2. Классы отсечений

5.1.3. Сравнение отсечений

5.1.4. Полиэдральные свойства неравенств

5.1.5. Полиномиальность идентификации неравенств

классов 1 и

5.2. Алгоритмы отсечения для задачи обслуживания требований параллельными приборами

5.2.1. Алгоритмы и их апробация

5.2.2. Схема дихотомии с отсечениями

5.2.3. О коэффициентах целевой функции

5.3. Обслуживание требований одним прибором

с прерываниями

5.3.1. Полиэдральные релаксации

5.3.2. Классы правильных неравенств

5.3.3. Экспериментальное сравнение релаксаций

Заключение

Литература

Введение диссертации (часть автореферата) на тему «Полиэдральные методы анализа и решения задач комбинаторной оптимизации»

Введение

Актуальность темы. Объектом исследования настоящей диссертации являются экстремальные комбинаторные задачи (ЭКЗ) в следующей постановке. Среди множеств некоторого семейства подмножеств Не 2е конечного множества Е, на котором задан аддитивный вещественный функционал с : Е ^ Я, найти множество, максимизирующее (минимизирующее) функцию с(Б) = ^ее£ с(е), Б С Е. Подобную формализацию допускают комбинаторные задачи, типичные для таких областей как стратегическое и сетевое планирование, маршрутизация и логистика, кластерный анализ и др. Предметом исследования является полиэдральная структура таких задач и, как следствие, полиэдральные методы поиска оптимальных решений. Принципиальная возможность использования свойств евклидова пространства для анализа и решения комбинаторных задач вытекает из классической теоремы Вейля-Минковского, согласно которой выпуклая оболочка конечного числа точек в Яп (многогранник) может быть представлена как множество решений системы линейных уравнений и неравенств с п переменными (полиэдр). Этот факт позволяет увидеть связь между комбинаторной оптимизацией и линейным и целочисленным линейным программированием (ЛП и ЦЛП).

Выбор данного подхода неслучаен. Полиэдральный подход к решению ЭКЗ, как и полиэдральная комбинаторика в целом, в известной степени возник на стыке комбинаторных и алгебраических методов. Сочетание теории графов с геометрическими, в первую очередь аффинными свойствами евклидова пространства, существенно расширяет диапазон алгоритмических возможностей [6, 8, 13, 17, 18, 72, 87, 89, 90, 156, 173, 174, 179]. Комбинаторные методы решения ЭКЗ, то есть методы, основанные на разум-

ном переборе комбинаторных объектов, являющихся допустимыми решениями задачи, как правило, эффективны на задачах относительно небольшой размерности. Более того, при малой размерности они существенно обгоняют по времени полиэдральные методы, такие как методы отсечения, ветвей и границ. С другой стороны, поскольку ЭКЗ чаще всего ЖР-трудны, рост размерности задач делает комбинаторные методы практически неприменимыми (по времени) при большой длине входа. В таких ситуациях полиэдральные методы ведут себя гораздо эффективнее. Наиболее впечатляющие рекорды при точном решении индивидуальных ЭКЗ получены именно с применением полиэдральных постановок (см., например, [12, 39, 66, 96, 110, 125, 140, 142, 144, 145, 146, 168, 171, 179] и др.). Основная идея полиэдрального подхода заключается в использовании так называемых отсекающих гиперплоскостей. Одними из первых алгоритмов такого типа стали несколько конкретизаций алгоритма Гомори [134, 135, 136, 137]. Однако, отсечения Гомори - это неравенства, применимые к самой общей постановке задачи ЦЛП, и они не учитывают структуры выпуклой оболочки допустимых целочисленных решений. Полиэдральный подход, в отличие от этого, ставит своей целью использовать при построении отсекающих плоскостей комбинаторную структуру элементов семейства Н С 2е. С семейством Н связывается многогранник Р%, являющийся выпуклой оболочкой векторов инциденций множеств из Н. Наиболее эффективными в алгоритмическом плане отсекающими плоскостями принято считать неравенства, которые порождают гиперграни (фасеты) многогранника Р%.

К сожалению, теоретических результатов сравнительного характера в пользу использования фасетных неравенств в алгоритмах на сегодняшний день не существует. Имеется большое количество работ, в которых получено частичное фасетное описание различных ЭКЗ [7, 99, 101, 102, 117, 119, 120, 121, 122, 140, 141, 146, 149, 169]. Тем не менее, помимо алгоритмической эффективности фасетные неравенства актуальны в следующем смысле. Всякое описание многогранника РН в виде полиэдра в обязательном порядке содержит все его фасеты (с точностью до эквивалентности). Более того, фасетных неравенств достаточно для полного описания мно-

гогранника. Это приводит к идее сведения ЭКЗ к задаче ЛП как таковой. Кроме того, одним из эмпирических аргументов в пользу фасетных неравенств является то, что фасетные неравенства наиболее тонко учитывают комбинаторную структуру семейства Н и, как следствие, структуру многогранника Р%. Всякую гиперплоскость, отличную от фасетной, можно "подправить", положить на грань большей размерности.

Однако, на пути использования полиэдральной постановки ЭКЗ встают следующие весьма масштабные проблемы.

1) Часто, несмотря на относительно несложную комбинаторную структуру семейства Н, поиск линейных неравенств, задающих соответствующий полиэдр, труден не только в общем случае, но и при рассмотрении конкретных комбинаторных многогранников. В целом, переход от вершинного описания к линейному полиномиален по числу вершин многогранника [41]. Однако, число вершин многогранника, ассоциированного с ЭКЗ, есть мощность семейства Н, которая в реальных комбинаторных задачах экспоненциальна по |Е |.

2) Даже наличие требуемого полиэдра, как правило, не делает возможным непосредственное практическое применение аппарата ЛП из-за экспоненциального по | Е| числа фасет многогранника РН.

Что касается первой из перечисленных трудностей, то первые результаты в этом направлении принадлежат Хоффману, Краскалу, Эдмондсу, Джайлсу и др. Ими были введены в рассмотрение два класса линейных систем Ах < Ь, множества решений которых являются целочисленными многогранниками (многогранниками с целочисленными вершинами). Первый класс образуют системы с так называемыми вполне унимодулярными матрицами, то есть матрицами, любой минор которых равен 0 или ±1. Хофф-маном и Краскалом [153] было показано, что целочисленная матрица А вполне унимодулярна тогда и только тогда, когда для любого целочисленного вектора Ь полиэдр {х | х > 0, Ах < Ь} является целочисленным. Это означает, что для решения задачи ЦЛП с вполне унимодулярной матрицей и целочисленной правой частью применимы методы линейного программирования. Эффект от этого результата наиболее заметен на потоковых

задачах и задачах о паросочетаниях на двудольных графах. Следует сказать, что для паросочетаний и потоков известны и другие эффективные алгоритмы решения, имеющие чисто комбинаторный характер. Принципиальным следствием этого результата стал вывод о том, что задачи комбинаторной оптимизации и целочисленные задачи в евклидовом пространстве на самом деле близки по своей природе. Следующим более общим классом систем Ax < b, обеспечивающим целочисленность полиэдра {x | Ax < b}, являются вполне двойственно целочисленные системы (total dual integrality systems, TDI-системы). Отправным моментом здесь является результат Эд-мондса и Джайлса [128]: если для заданной рациональной системы Ax < b и любого целочисленного вектора c величина max{cTx | Ax < b} есть целое число, то для любого c этот максимум достигается на целочисленном векторе. Этот результат позволил связать ЦЛП с теорией двойственности в ЛП, а именно: система Ax < b называется вполне двойственно целочисленной (TDI-системой), если задача min{bTy | y > 0, ATy = c} имеет целочисленное оптимальное решение для любого целочисленного вектора c, которому соответствует конечное значение минимума. Таким образом, если Ax < b - TDI-система и вектор b - целочисленный, то и только то полиэдр {x | Ax < b} является целочисленным. Одним из первых результатов по вполне двойственной целочисленности стало линейное описание многогранника паросочетаний в произвольном графе. Позже этот результат с небольшими изменениями в правой части системы был обобщен на b-сочетания. Принципиально важно отметить, что оптимизационные постановки этих задач разрешимы за полиномиальное время. TDI-систем, описывающих многогранники NP-трудных задач, на сегодняшний день не известно.

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

ных неравенств, либо неравенством общего вида, типа неравенств Гомори, формирующимся на основании информации об этом текущем оптимуме. На этом этапе на передний план выходит задача идентификации (separation problem) неравенств из имеющегося класса фасетных неравентсв, которая заключается в том, чтобы найти в нем неравенство, отсекающее текущий оптимум, либо доказать, что в данном классе такого неравенства нет. Карп и Пападимитриу в [158] показали, что при NP = co — NP для полиэдра общего вида (не обязательно целочисленного) и класса неравенств, определяющих все фасеты выпуклой оболочки его целочисленных точек, не существует полиномиального алгоритма решения задачи идентификации. Тем не менее, фасетные неравенства можно включать в алгоритм и не имея полного линейного описания многогранника. При рассмотрении многогранников конкретных массовых ЭКЗ задача идентификации может оказаться полиномиально разрешимой. Это, например, так для многогранника паро-сочетаний [127]. Кроме того, применительно к алгоритмам отсечения имеет смысл рассматривать и частичные фасетные описания многогранников, то есть относительно узкие классы фасетных неравенств. Например, идентификация кликовых фасет для многогранника симметричной задачи коммивояжера полиномиально разрешима [171], а идентификация неравенств дерева клик для той же задачи NP-трудна [145]. В случае NP-трудности задачи идентификации для данного класса неравенств часто бывают эффективны эвристические процедуры [34] поиска отсекающего фасетного неравенства. Эффективность эвристик в данной ситуации обусловлена тем, что нам, как правило, не требуется искать наилучшее значение левой части неравенства, а лишь сравнивать его с некоторым граничным значением.

Таким образом, для применения полиэдрального подхода к решению конкретной массовой ЭКЗ необходимо пройти через три основных этапа. Во-первых, нужно найти "хорошую" систему линейных уравнений и неравенств, которая 1) содержит многогранник задачи, 2) либо не содержит целочисленных точек, отличных от векторов инциденций множеств из семейства H, либо имеется "недорогая" процедура исключения таких целочисленных точек и 3) состоит из полиномиального по |E | числа ограни-

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

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

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

Научная новизна. Оригинальность и научная новизна полученных результатов заключается в следующем.

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

2) Разработан общий подход к доказательству фасетности неравенств, опорных к комбинаторным многогранникам. Особенностью подхода является интенсивное использование комбинаторной структуры элементов допустимых множеств задач. Этот подход позволил найти новые фасетные неравенства для ряда многогранников, ассоциированных с ЭКЗ.

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

4) Предложены новые процедуры отсечения и ветвей и границ для решения рассматриваемых задач. Помимо применения фасетных неравенств

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

5) Установлена вычислительная сложность задачи идентификации как для новых, так и некоторых известных классов опорных неравенств.

6) Предпринята "полиэдральная атака" на задачи теории расписаний.

Практическая и теоретическая ценность. Работа носит теоретический характер. Полученные в ней результаты позволяют лучше понять связь между комбинаторным и полиэдральным подходами к решению экстремальных комбинаторных задач. Разработанные методы общего характера апробированы на конкретных задачах, найденные новые нервенства встроены в алгоритмы отсечения. По всем новым алгоритмам проведен вычислительный эксперимент, подтверждающий их эффективность в сравнении с существующими пакетами решения задач ЦЛП. Результаты диссертации также могут быть использованы при преподавании университетских курсов "Методы оптимизации" и "Теория алгоритмов". Задачи большой размерности с найденными точными решениями могут быть использованы при разработке и оценке эффективности приближенных алгоритмов решения задач.

Апробация работы. Все разделы диссертации прошли апробацию на следующих конференциях в России и за рубежом:

- Всесоюзная конференция "Математическое программирование и программное обеспечение". Свердловск, 1989, 1991;

- Всероссийская конференция "Математическое программирование и приложения". Екатеринбург, 1993, 1997, 1999, 2003, 2015;

- Байкальская международная школа-семинар "Методы оптимизации и их приложения". Иркутск, 1995, 2008, 2014, 2017;

- Сибирский конгресс по индустриальной и прикладной математике (ИНПРИМ). Новосибирск, 1996.

- Всероссийская конференция "Проблемы оптимизации и экономические приложения". Омск, 1997, 2003, 2009, 2012, 2015, 2017;

- Международная конференция "Optimal Discrete Structures and

Algorithms". Росток, 1997 (Германия).

- Международная конференция "Optimization and Applications" (OPTIMA), 2011, 2014, 2015, 2017 (Черногория);

- Всероссийская научно-практическая конференция "Статистика. Моделирование. Оптимизация". Челябинск, 2011;

- Международная конференция "Дискретная оптимизация и исследование операций". Новосибирск, 2013;

- Международная конференция "Дискретная оптимизация и исследование операций". Владивосток, 2016;

- Всероссийская конференция "Математические методы распознавания образов". Светлогорск, 2015;

- Международная конференция "Intelligent Data Processing: Theory and Applications". 2016 (Испания);

- Международный симпозиум по математическому программированию, ISMP 2018 (Франция).

Результаты диссертации докладывались на семинарах:

- Институт математики им. С.Л.Соболева СО РАН (Новосибирск)

- Омский филиал Института математики им. С.Л.Соболева СО РАН (Омск)

- Нижегородский государственный университет им. Н.И.Лобачевского (Нижний Новгород)

- Институт математики и механики им. Н.Н.Красовского УрО РАН (Екатеринбург)

- Омский государственный университет им. Ф.М.Достоевского (Омск)

Личный вклад. Диссертационная работа представляет собой единый

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

рами отсутствует.

На защиту выносятся совокупность результатов по применению полиэдрального подхода к решению экстремальных комбинаторных задач, методы доказательства фасетности опорных неравенств, использования эвристических процедур как подпрограмм в точных алгоритмах решения ЭКЗ.

Публикации. По теме диссертации автором опубликовано 55 работ, в том числе 26 статей, среди них 16 в изданиях из списка ВАК, одна монография, 28 работ в трудах российских и международных конференций.

Основные результаты диссертации

1. Для задачи ЦЛП в лексикографической постановке получено полное линейное описание целочисленных точек параллелепипеда, лексикографически меньших заданной, что позволило выделить наискорейший по числу итераций алгоритм в классе вполне регулярных алгоритмов отсечения.

2. Введено понятие комбинаторно полных семейств подмножеств конечного множества. Разработан общий подход к доказательству фасетности неравенств, опорных к многограннику, ассоциированному с комбинаторно полным семейством. Основой подхода является понятие ЬН-базиса, определенное для комбинаторно полного семейства Н и опорного к соответствующему многограннику неравенства Ьтх < Ь0. В терминах ЬН-базисов получены ряд необходимых условий и достаточное условие фасетности неравенств, опорных к многограннику, ассоциированному с комбинаторно полным семейством. Разработанный подход является одним из основных теоретических результатов диссертации и существенно расширяет диапазон методов доказательства фасетности неравенств.

3. Исследована полиэдральная структура семейства Ь-факторов произвольного графа. Именно:

- описана графовая структура нецелочисленных вершин полиэдральной релаксации многогранника Ь-факторов;

- найден критерий смежности вершин релаксации, что позволило получить достаточные условия смежности Ь-факторов как таковых;

- для многогранника связных ^факторов доказана ЖР-полнота проверки

несмежности вершин и построена экспоненциальная нижняя оценка клико-вого числа, что является продолжением классических результатов из [172] и [6], соответственно;

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

4. С помощью техники ЬН-базисов, упомянутой в п.2, получены новые классы фасетных неравенств для многогранника связных к-факторов: тривиальные фасеты, кликовые фасеты, неравенства Эдмондса. Доказана полиномиальная разрешимость задачи идентификации кликовых фасет при четных к. Разработана процедура отсечения для задачи о связном к-факторе, основанная на полученных фасетных неравенствах, проведен ее экспериментальный анализ.

5. Для задачи о разбиении на клики предложен новый класс опорных неравенств, для которых в терминах ЬН-базисов найдены необходимые и достаточные условия фасетности. Дано доказательство ЖР-трудности задачи идентификации неравенств этого класса, в связи с чем разработаны процедуры локального поиска для ее решения. Предложена процедура отсечения, основанная на этих неравенствах, которая является как самостоятельным методом решения задачи аппроксимации графа, так и используется для получения нижних оценок в схеме ветвей и границ. Проведено детальное экспериментальное исследование разработанной процедуры ветвей и границ, включающее анализ эвристик для рекордов, эвристик для задачи идентификации фасет, особенности структуры целевой функции задачи аппроксимации графа.

6. Исследована полиэдральная структура двух задач теории расписаний

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

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

Объем и структура диссертации. Диссертация состоит из введения, пяти глав, заключения и списка литературы (192 наименования). Объем диссертации 255 страниц.

Содержание работы

Первая глава содержит основные понятия теории выпуклых многогранников и систем линейных неравенств, актуальных для полиэдральной комбинаторики в целом и создания полиэдральных методов анализа и решения экстремальных комбинаторных задач. В разделах 1.1 и 1.2 даются определения и свойства основных конструкций, посредством которых формализуется аффинная структура евклидова пространства. Определяются ключевые понятия "многогранник" (- выпуклая оболочка конечного числа точек) и "полиэдр" (- множество решений конечной системы линейных уравнений и неравенств, если оно ограничено). Следует отметить, что на сегодняшний день, несмотря на простоту определений, в публикациях весьма часто наблюдаются существенные различия в использовании этих понятий. Связь между вершинным (комбинаторным) и линейным (полиэдральным) описанием многогранника рассмотрена в разделе 1.3. Эти три раздела следует понимать как описание аппарата, который является основным для настоящей диссертации.

Результаты разделов 1.4 и 1.5, принадлежащие автору, являются иллюстрацией использования полиэдрального подхода к лексикографической постановке задачи выпуклого целочисленного программирования. Лексикографическая постановка заключается в максимизации (минимизации) линейной целевой функции на целочисленных точках выпуклого замкнутого множества в Яп

1ехтах{стх | х Е ^ П 2п},

где Zn - целочисленная решетка в пространстве Яп. Поскольку речь идет о целочисленных решениях, то от выпуклого множества О можно перейти к многогранику Р = сопи (О П 2п), и та же задача может рассматриваться в полиэдральной постановке на многограннике Р. Как следствие возникает задача нахождения полного или частичного линейного описания этого многогранника. В работах [26, 27] был предложен подход к решению задачи на О, основанный на погружении множества О в ограниченный сверху параллелепипед и выделении класса так называемых вполне регулярных отсечений, которые вместе с текущим нецелочисленным лексикографическим оптимумом гарантированно отрезают определенную "измеримую" часть параллелепипеда. Этот подход, в частности, позволил получить нижние оценки числа итераций вполне регулярных алгоритмов отсечения [24]. В разделе 1.4 дается полное линейное описание выпуклой оболочки целочисленных точек параллелепипеда, лесикографически меньших заданной точки (теорема 5). В силу того, что параллелепипед устроен достаточно просто, для описания этой выпуклой оболочки оказалось достаточно полиномиального по размерности пространства числа ограничений. При этом оказалось, что эти ограничения (без ограничений параллелепипеда) образуют вполне регулярную совокупность отсечений, что позволило (см. раздел 1.5) найти наискорейший по числу итераций алгоритм отсечения в классе вполне регулярных алгоритмов (теорема 8), введенных в [26, 27]. Этот класс содержит, в частности, алгоритм Ю.Ю.Червака [85] и В-алгоритм Ю.Ю.Финкельштейна [31] .

Во второй главе описан переход от комбинаторной постановки экстремальной задачи к полиэдральной постановке, дана общая схема процедуры отсечения, в рамках введенной терминологии формализована задача идентификации правильных неравенств. Многогранник Рн, ассоциированный с семейством подмножеств Н С 2е конечного множества Е, определяется как выпуклая оболочка векторов инциденций множеств из Н.

Основным содержанием главы является разработка нового подхода к доказательству фасетности опорных неравенств. Введено понятие комбинаторно полных семейств Н, то есть семейств, удовлетворяющих аксиоме:

для любых el, e2 Е Б найдется такое И Е Н, что el Е И и e2 Е И. Комбинаторно полными являются, например, такие семейства подграфов полного графа на более, чем четырех вершинах, как паросочетания, гамильтоновы циклы, М-графы [67] и многие другие комбинаторные объекты.

Как правило, доказательство фасетности опорного к многогранику неравенства основывается на понятии аффинной независимости точек евклидова пространства. При этом существенно используется информация об аффинной оболочке многогранника. Структура множеств семейства Н, векторы инциденций которых обращают неравенства в равенство, используется глубоко внутри доказательств. В диссертации выявлены общие комбинаторные свойства этих множеств и на основании этих свойств получены ряд необходимых и достаточное условия фасетности. Необходимые условия определяются взаимным пересечением этих множеств (теорема 9). Для формулировки достаточного условия фасетности введено понятие ЬН-базиса, которое, по сути, является комбинаторным аналогом процедуры выделения квадратной невырожденной подсистемы системы линейных уравнений, определяющих аффинную оболочку многогранника. Пусть Ьтх < Ь0 - опорное к Р% неравенство и

аЦРн = {х Е ЯЕ | Атх = а},

- аффинная оболочка многогранника Р%, причем матрица А имеет полный ранг.

Определение 1. Непустое множество Б С Б будем называть ЬН-переключением, если существуют такие И1,И2 Е Н, что

Список литературы диссертационного исследования доктор наук Симанчев Руслан Юрьевич, 2020 год

Литература

[1] Агеев А.А., Ильев В.П., Кононов А.В., Талевнин А.С. Вычислительная сложность задачи аппроксимации графа // Дискретный анализ и исследование операций. Серия 1. — 2006. — Т. 13. — №1. — С. 3-11.

[2] Бабурин А.Е., Гимади Э.Х. Приближенный алгоритм поиска d-однородного связного остовного подграфа максимального веса в полном графе со случайными весами ребер // Дискретный анализ и исследование операций. Серия 2. — 2006. — Т. 13. — №2. — С. 3-20.

[3] Баптист Ф., Карлье Ж., Кононов А. В., Керан М., Севастьянов С. В., Свириденко М. Структурные свойства оптимальных расписаний с прерываниями операций // Дискретный анализ и исследование операций. — 2009. — Т. 16. — №1. — С. 3-36.

[4] Беллман Р. Динамическое программирование. — Москва: ИЛ, 1960. — 400 с.

[5] Бондаренко В.А. Неполиномиальная нижняя оценка сложности задачи коммивояжёра в одном классе алгоритмов // Автоматика и телемеханика. — 1983. — №9. — C. 45-50.

[6] Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. — М.: ЛКИ, 2008. — 184 с.

[7] Бондаренко В.А., Николаев А.В., Сыманович М.Э., Шемякин Р.О. Об одной задаче распознавания на релаксациях разрезного многогранника // Автоматика и телемеханика. — 2014. — №9. — С. 108-121.

[8] Веселов С.И., Чирков А.Ю. Оценки числа вершин целых полиэдров // Дискретный анализ и исследование операций. Серия 2. — 2007. — Т. 14. — №2. — С. 14-31.

[9] Гимади Э.Х. О некоторых математических моделях и методах планирования крупномасштабных проектов // Модели и методы оптимизации. — Новосибирск: Наука, 1988. — С. 89-115.

[10] Гимади Э.Х., Залюбовский В.В., Севастьянов С.В. Полиномиальная разрешимость задач календарного планирования со складируемыми ресурсами и директивными сроками // Дискретный анализ и исследование операций. Серия 2. — 2000. — Т. 7. — №1. — С. 9-34.

[11] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982. — 416 с.

[12] Дергунова Т.В., Симанчев Р.Ю. Задача о связном k-факторе: идентификация кликовых фасет и алгоритм отсечения // Фунд. и прикл. математика. — Омск: ОмГУ, 1994. — С. 71-80.

[13] Емеличев В.А., Ковалев М.М. Полиэдральные аспекты дискретной оптимизации // Кибернетика. — 1982. — №6. — С. 54-62.

[14] Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. — М.: Наука, 1981. — 344 с.

[15] Емеличев В. А. и др. Лекции по теории графов. — М.: Наука, 1990. — 384 с.

[16] Еремеев А.В., Романова А.А., Сервах В.В., Чаухан С.С. Приближенное решение одной задачи управления поставками // Дискретный анализ и исследование операций. Сер. 2. — 2006. — Т. 13. — №1. — С. 27-39.

[17] Еремин И.И. Теория линейной оптимизации. — Екатеринбург: УрО РАН, 1998. — 248 с.

[18] Жадан В. Г. Об одном варианте симплекс-метода для линейной задачи полуопределенного программирования // Труды ИММ УрО РАН. — 2015. — Т. 21. — №3. — С. 117-127.

[19] Заблоцкая О.А., Колоколов А.А. Вполне регулярные отсечения в булевом программировании // Управляемые системы. - Новосибирск: ИМ СО АН СССР, 1983. — Вып. 23. — С. 55-63.

[20] Ильев В.П., Ильева С.Д., Навроцкая А.А. Приближенные алгоритмы для задач аппроксимации графов // Дискретный анализ и исследование операций. — 2011. — Т. 18. — №1. — С. 41-60.

[21] Ильев В.П., Фридман Г.Ш. К задаче аппроксимации графами с фиксированным числом компонент // Докл. АН СССР. — 1982. Т. 264. — №3. — С. 533-538.

[22] Кельманов А.В., Пяткин А.В. КР-трудность некоторых евклидовых задач разбиения конечного множества точек // Журн. вычислит. математики и мат. физики. — 2018. — Т.58. — №5. — С. 852-856.

[23] Ковалев М.Я. Интервальные е-приближенные алгоритмы решения дискретных экстремальных задач // Дис. канд. физ.-мат. наук. — Минск, 1986. — 110 с.

[24] Колоколов А.А. Нижняя оценка числа итераций для одного класса алгоритмов отсечения // Управляемые системы. — Новосибирск, 1983.

— Вып. 23. — С. 64-69.

[25] Колоколов А.А. Методы дискретной оптимизации. Учебное пособие.

— Омск: ОмГУ, 1984. — 75 с.

[26] Колоколов А.А. Регулярные отсечения при решении задач целочисленной оптимизации // Управляемые системы. — Новосибирск, 1981. — Вып. 21. — С. 18-25.

[27] Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании // Сибирский журнал исследования операций. — Новосибирск, 1994. — Т. 1. — №2. — С. 18-39.

[28] Колоколов А.А., Девятерикова М.В. Анализ устойчивости некоторых алгоритмов дискретной оптимизации // Автоматика и телемеханика.

— 2004. — №3. — С. 48-54.

[29] Колоколов А.А., Заозерская Л.А. О среднем числе итераций некоторых алгоритмов для решения задачи об упаковке множества // Материалы XIV Байкальской международной школы-семинара "Методы оптимизации и их приложения". — Иркутск, 2008. — Т. 1. — С. 388-395.

[30] Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. — М.: Наука, 1975. — 360 с.

[31] Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. — М.: Наука, 1969. — 368 с.

[32] Корбут А.А., Финкельштейн Ю.Ю. Приближенные методы дискретного программирования // Изв. АН СССР. Техн. кибернет. — Минск, 1969. — №1. — С. 165-176.

[33] Э.Г.Коффман и др. Теория расписаний и вычислительные машины.

— М.: Наука, 1984. — 335 с.

[34] Кочетов Ю.А. Вычислительные возможности локального поиска в комбинаторной оптимизации // Журн. вычислит. математики и мат. физики. — 2008. — Т. 48. — №5. — C. 788-807.

[35] Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения. Сборник лекций молодежных и научных школ по дискретной математике и ее приложениям. — М: МГУ, 2001. — С. 87-117.

[36] Кристофидес Н. Теория графов. Алгоритмический подход. — М: Мир, 1978. — 420 с.

[37] Кук С.А. Сложность процедур вывода теорем // Киберн. сб. — Новая серия, 1975. — Вып. 12. — С. 5-15.

[38] Лазарев А. А., Кварацхелия А. Г. Свойства оптимальных расписаний задачи теории расписаний минимизации суммарного взвешенного момента окончания для одного прибора // Автоматика и телемеханика.

— 2010. — №10. — С. 80-89.

[39] Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. — М.: Мир, 1985. — 512 с.

[40] Подчасова Т.П., Португал В.М., Татаров В.А., Шкурба В.В. Эвристические методы календарного планирования. — Киев: Техника, 1980. — 140 с.

[41] Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. — М.: Мир, 1989. — 478 с.

[42] Рейногольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. Пер.с англ. — М.: Мир, 1980. — 476 с.

[43] Севастьянов С.Е. Геометрические методы и эффективные алгоритмы в теории расписаний : Дис. док. физ.-мат. наук. — Новосибирск, 2000.

— 280 с.

[44] Сервах В.В. Алгоритм решения задачи календарного планирования с единичными длительностями работ // В кн. Дискретная оптимизация и анализ сложных систем, ВЦСО АН СССР. — Новосибирск, 1989. — С. 99-107.

[45] Сервах В.В. Календарное планирование с работами единичной длительности // Материалы межреспубликанского семинара по дискретной оптимизации. — Киев, 1990. — С. 66.

[46] Сервах В.В. Эффективные алгоритмы для некоторых задач календарного планирования // В кн. Методы решения и анализа задач дис-

кретной оптимизации. Сб.научных трудов под ред. А.А. Колоколова.

— Омск: ОмГУ, 1992. — С. 94-106.

[47] Симанчев Р.Ю. О неравенствах, порождающих фасеты комбинаторных многогранников // Дискретный анализ и исследование операций.

— 2017. — Т. 24. — №4. — С. 95-110.

[48] Симанчев Р.Ю. О ранговых неравенствах, порождающих фасеты многогранника связных k-факторов // Дискретный анализ и исследование операций. — Новосибирск, ИМ СО РАН, 1996. — Т. 3. — №3. — С.84-110.

[49] Симанчев Р.Ю. Сравнение вполне регулярных отсечений и алгоритмов // Методы решения и анализа задач дискретной оптимизации. — Омск: ИИТПМ СО РАН, 1992. — С. 107-123.

[50] Симанчев Р.Ю. О смежности вершин многогранника связных k-факторов // Труды ИММ УрО РАН. — 2018. — Т. 24. — №2. — С. 235-242.

[51] Симанчев Р.Ю. Комбинаторная структура и смежность вершин политопа b-факторов // Известия вузов. Математика. — 2014. — №6. — С. 56-69.

[52] Симанчев Р.Ю. Комбинаторные условия фасетности опорных неравенств // Вестник Омского университета. — 1997. — №3. — С. 11-13.

[53] Симанчев Р.Ю. Линейные симметрии многогранника паросочетаний и автоморфизмы графа // Вестник Омского университета. — 1996. — №1. — С. 18-20.

[54] Симанчев Р.Ю. Выпуклые многогранники и фасетные неравенства. Учебно-методическое пособие. — ОмГУ, 1999. — 39 с.

[55] Симанчев Р.Ю. Смежность вершин многогранника k-факторов // Математические структуры и моделирование. — 1998. — Вып. 2. — С. 39-50.

[56] Симанчев Р.Ю. Структура нецелочисленных вершин релаксации многогранника k-факторов // Математические структуры и моделирование. — 1998. — Вып. 1. — С. 20-26.

[57] Симанчев Р.Ю. О вполне регулярных отсечениях для задач целочисленной оптимизации // Управляемые системы. - Новосибирск, ИМ СО АН СССР. — 1990. — С. 61-71.

[58] Симанчев Р.Ю., Соловьева П.В. bH-базисы для одного класса фасет многогранника разбиения на клики // Математические структуры и моделирование. — 2018. — Т. 48. — №4. — С. 27-34.

[59] Симанчев Р.Ю., Уразова И.В. Класс t-дольных неравенств для многогранника расписаний обслуживания требований параллельными приборами // DATA, MODELING AND SECURITY: DMS, 2017. URL: http://ceur-ws.org/Vol-1965/paper8.pdf

[60] Симанчев Р.Ю., Уразова И.В. Применение дихотомии для решения задачи обслуживания единичных требований параллельными приборами // Вестник Омского университета. — 2011. — №4. — С. 26-30.

[61] Симанчев Р.Ю., Уразова И.В. Задачи обслуживания единичных требований параллельными приборами (полиэдральный подход). — LAP LAMBERT Academic Publishing, 2012. — 104 с.

[62] Симанчев Р.Ю., Уразова И.В. Класс опорных неравенств для многогранника расписаний обслуживания единичных требований параллельными процессорами // Труды XIV Байкальской международной школы-семинара "Методы оптимизации и их приложения". — 2008. — Т. 1. — С. 530-536.

[63] Симанчев Р.Ю., Уразова И.В. Многогранник расписаний обслуживания идентичных требований параллельными приборами // Дискретный анализ и исследование операций. — 2011. — Т. 18. — №11. — С. 85-97.

[64] Симанчев Р.Ю., Уразова И.В. О задаче упаковки вершин ациклического орграфа в полосу фиксированной ширины // Доклады Одесского семинара по дискретной математике (ДОСДМ). — 2010. — №9. — С. 56-59.

[65] Симанчев Р.Ю., Уразова И.В. Оценки числа целочисленных вершин, смежных с дробной в симметричной задаче коммивояжера // Пятая азиатская международная школа-семинар "Проблемы оптимизации сложных систем". — Новосибирск, 2009. — С. 210-214.

[66] Симанчев Р.Ю., Уразова И.В. Целочисленная модель задачи минимизации общего времени обслуживания параллельными приборами единичных требований с предшествованиями // Автоматика и телемеханика. — 2010. — №10. — С. 100-106.

[67] Симанчев Р.Ю., Уразова И.В. О гранях многогранника задачи аппроксимации графов // Дискретный анализ и исследование операций. — 2015. — Т. 22. — №2. — С. 86-101.

[68] Симанчев Р.Ю., Уразова И.В., Кочетов Ю.А. Метод ветвей и отсечений для задачи разбиения на клики // Дискретный анализ и исследование операций. — 2019. — Т. 26. — №3. — С. 60-87.

[69] Симанчев Р.Ю., Шерешик Н.Ю. Целочисленные модели обслуживания требований одним прибором с прерываниями // Дискретный анализ и исследование операций. — 2014. — Т. 21. — №4. — С. 89-101.

[70] Симанчев Р.Ю., Шерешик Н.Ю. Схема дихотомии для поиска минимального директивного срока в задаче обслуживания различных требований одним прибором // Вестник Омского университета. — 2013. — №2. — С. 48-50.

[71] Сотсков Ю.Н. Оптимальное обслуживание двух требований при регулярном критерии // Автоматизация процессов проектирования. — Минск:ИТК АН БССР, 1985. — С. 52-62.

[72] Схрейвер А. Теория линейного и целочисленного программирования. — М.: Мир, 1991. — Т. 2. — 342 с.

[73] Танаев В.С., Гордон В.С., Шафранский В.В. Теория расписаний. Одностадийные системы. — М.: Наука, 1987. — 384 с.

[74] Танаев В.С., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. — М.: Наука, 1989. — 328 с.

[75] Танаев В.С., Шкурба В.В. Введение в теорию расписаний. — М.: Наука, 1975. — 256 с.

[76] Уразова И.В. Класс правильных неравенств для задачи упаковки вершин ациклического орграфа в полосу заданной ширины // Вестник Омского университета. — 2011. — Т. 60. — №2. — С. 48-52.

[77] Уразова И.В. Результаты вычислительного эксперимента для одной задачи теории расписаний //IV Всероссийская конференция "Проблемы оптимизации и экономические приложения". — Омск, 2009. — С. 169.

[78] Уразова И.В. Релаксации Лагранжа и Ь-структура многогранника задачи об упаковке // Труды XII Байкальской международной школы-семинара "Методы оптимизации и их приложения". — Иркутск: ИСЭМ СО РАН, 2005. — Т. 1. — С. 589-594.

[79] Финкельштейн Ю.Ю. Теоретическая оценка максимального числа итераций для полностью целочисленного алгоритма Гомори // Проблемы кибернетики. — М.: Наука, 1973. — Вып. 26. — С. 315-326.

[80] Фридман Г.Ш. Одна задача аппроксимации графов // Управляемые системы. — 1971. — Вып. 8. — С. 73-75.

[81] Харари Ф. Теория графов. — М.: Мир, 1973. — 300 с.

[82] Хачай М. Ю., Незнахина Е. Д. Разрешимость обобщенной задачи коммивояжера в классе квази- и псевдопирамидальных маршрутов // Тр. ИММ УрО РАН. — 2017. — Т. 23. — №3. — С. 280-291.

[83] Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании // ДАН СССР. — 1979. — Т. 244. — С. 1093-1096.

[84] Ху Т. Целочисленное программирование и потоки в сетях. — М.: Мир, 1974. — 520 с.

[85] Червак Ю. Ю. Поиск лексиграфически максимальной дискретно определенной точки выпуклого множества // Математические методы решения экономических задач. — М.: Наука, 1979. — Вып. 8. — С. 69-75.

[86] Червяков О.В. Аффинные симметрии многогранника системы независимости с единичным сдвигом // Дискретный анализ и исследование операций. Серия 1. — 1999. — Т. 6. — №2. — С. 82-96.

[87] Шевченко В.Н. Выпуклые многогранные конусы, системы сравнений и правильные отсечения в целочисленном программировании // Комбинаторно-алгебраические методы в прикладной математике. — Горький: Изд-во Горьк. ун-та, 1979. — С. 109-119.

[88] Шевченко В.Н. Задача составления оптимального расписания работы на п станках // Проблемы кибернетики. — М.: Наука, 1967. — Вып. 18. — С. 129-146.

[89] Шевченко В.Н. Качественные вопросы целочисленного программирования. — М.: Физматлит, 1995. — 190 с.

[90] Шевченко В.Н. Линейное программирование и теория линейных неравенств. — Горький: Изд-во Горьк. ун-та, 1977.

[91] Шевченко В.Н. Построение правильных отсечений в целочисленном линейном программировании // Тр. 5-й Зимней школы-симпозиума по мат. программированию и смежным вопросам. — Москва, 1973. — Вып. 2. — С. 266-272.

[92] Шерешик Н. Ю. Релаксации многогранника оптимальных расписаний обслуживания требований одним прибором с прерываниями // Дис-

кретный анализ и исследование операций. — 2015. — Т. 22. — №6. — С. 78-90.

[93] Шкурба В.В. Задача трех станков. — М:Наука, 1976. — 96 с.

[94] Ailon N., Charikar M., Newman A. Aggregating inconsistent information: Ranking and clustering //J. ACM. — 2008. — Vol. 55. — №5. — P. 1-27.

[95] Alekseeva E., Kochetov Yu., Plyasunov A. Complexity of local search for the p-median problem // European Journal of Operational Research. — 2008. — №191. — Р. 736-752.

[96] Applegate D. L., Bixby R. E., Chvatal V., Cook W. J., Espinoza D. G., Goycoolea M., Helsgaun K. Certification of an optimal TSP tour through 85,900 cities // Operations Research Letters. — 2009. — Vol. 37. — P. 11-15.

[97] Araoz J., Cunningham W.H., Edmonds J., Green-Krotki J. Reductions to 1-matching polyhedra // Networks. — 1983. — Vol. 13. — P. 455-473.

[98] Baev I.D., Meleis W.M., Eichenberger A. Lower bounds on Precedence-Constrained Scheduling for Parallel Processors // IEEE, 2000.

[99] Balas E. On the convex hull of the union of certain polyhedra // Oper. Res. Let. — 1988. — №7. — P. 279-283.

[100] Balas E. On the facial structure of sheduling polyhedra // Mathematical Programming Study. — 1985. — №24. — P. 179-218.

[101] Balas E. The asymmetric assignment problem and some new facets of the travelling salesman polytope on directed graph // SIAM Journal on Discrete Math. — 1989. — №3. — P. 425-451.

[102] Balas E., Fischelti M. A lifting procedure for the asymmetric travelling salesman polytope and a large new class of facets // Math. Prog. — 1995. — №68. — P. 241-265.

[103] Bansal N., Blum A., Chawla S. Correlation clustering // Machine Learning. - 2004. - Vol. 56. - P. 89-113.

[104] Baroum S.M. and Patterson J.H. An Exact Solution Procedure for Maximizing the Net Present Value of Cash Flows in a Network // Jan Weglarz (Eds.). Project Scheduling: Recent Models, Algorithms and Applications. — Kluwer Academic Publishers, 1999. — P.107-133.

[105] Ben-Dor A., Shamir R., Yakhimi Z. Clustering gene expression patterns //J. Comput. Biol. — 1999. — Vol. 6. — № 3-4. — P. 281-297.

[106] BlaZewicz J., Lenstra J.K., Rinnoy Kan A.H.G. Scheduling subject to resource constraints: Classfication and complexity // Discrete Applied Mathematics. — 1983. — Vol. 5. — №1. — P. 11-24.

[107] Bolotashvili G., Girlich E., Kovalev M. New Facets of the Linear Ordering Polytope. Preprint Nr. 15. Otto-von-Guericke-Universitat Magdeburg. Fakult. Mathematik, 1995.

[108] Bolotashvily G., Kovalev M., Girlich E. New facets of the Linear Ordering Polytope // SIAM Journal on Discrete Mathematics. — 1999. — Vol. 12. — №3.

[109] Bocker S., Briesemeister S., Klau G.W. Exact algorithms for cluster editing: evaluation and experiments. Algorithmica. — 2011. — №60. — P. 316-334.

[110] Bouma W. Harmen, Goldengorin B. A Polytime Algorithm Based on a Primal LP Model for Scheduling Problem 1|pmtn;pi = 2;ri\Yp^iCi // Recent Advances in Applied Mathematics. Proceedings of the American Conference on Applied Mathematics (AMERICAN-MATH'10). — Harvard University, Cambridge, USA, 2010. — P. 415-420.

[111] Brimberg J., Janicijevic S., Mladenovic N., Urosevic D. Solving the clique partitioning problem as a maximally diverse grouping problem // Optim. Lett. — 2017. — №11. — P. 1123-1135.

[112] Brucker P. Scheduling algorithms. Springer-Verlag Berlin Heidelberg, 1998.

[113] Brucker P., Knust S. Complexity Results for Scheduling Problems. -URL: www//mathematik.uni-osnabrueck.de/research/OR/class.

[114] Brucker P., Drexl A., Mohring R., Neumann K. and Pesch E. Resource-constrained project scheduling: Notation, classification, models, and methods // European Journal of Operational Research. — 1999. — Vol. 112. — P. 3-41.

[115] Brucker P., Knust S. Complex Scheduling. Springer, 2006.

[116] Brusco M.J., Kohn H.F. Clustering qualitative data based on binary equivalence relations: neighborhood search heuristics for the clique partitioning problem // Psychometrika. — 2009. — №74. — P. 685-703.

[117] Cdnovas L., Landete M., Margin A. On the facets of the simple plant location packing polytope // Discrete Applied Mathematics. — 2002. — Vol. 124. — №1-3. — P. 27-53.

[118] Charikar M., Guruswami V., Wirth A. Clustering with qualitative information //J. Comput. Syst. Sci. — 2005. — Vol. 71. — № 3. — P. 360-383.

[119] Cho D.C., Johnson E.L., Padberg M., Rao M.R. On the uncapacitated plant location problem I: valid inequalities and facets // Mathematics of Operations Research. — 1983. — Vol. 8. — P. 579-589.

[120] Cho D.C., Padberg M., Rao M.R. On the uncapacitated plant location problem II: facets and lifting theorems // Mathematics of Operations Research. — 1983. — Vol. 8. — P. 590-612.

[121] Chopra S., Rinaldi G. The graphical asymmetric travelling salesman polyhedron: Symmetric inequalities // SIAM Journal on Discrete Mathematics. — 1996. — Vol. 9. — №4. — P. 602-624.

[122] Chvatal V. On certain polytopes assotiated with graph // Jornal of Combinatorial Theory (B). - 1975. - №18. - P. 138-154.

[123] Coffman E.G., Jr, Graham R.L. Optimal scheduling of two processor systems // Acfa Informat. - 1972. - №1. - P. 200-213.

[124] Conway R.W., Maxwell W.L. and Miller L.W. Theory of Sheduling. Addison-Wesley, 1967.

[125] Crowder H., Jonson E.L. and Padberg M.W. Solving large-scale zero-one linear programming problems // Oper. Res. - 1983. - №31. - P. 803-834.

[126] Diakova Z., Kochetov Yu. A double VNS heuristic for the facility location and pricing problem. Electronic Notes in Discrete Mathematics. - 2012.

- № 39. - P. 29-34.

[127] Edmonds J. Maximum Matching and a Polyhedron With O,1-Vertices // Journal jf Research of the National Bureau of Standards. Section B. -1965. - Vol. 69. - P. 125-130.

[128] Edmonds J., Giles R. A min-max relation for submodular functions on graphs// in: Studies in Integer Programming (Proceedings of the Workshop on Integer Programming, Bonn, 1975; P.L. Hammer, E.L. Johnson, B.H. Korte, G.L. Nemhauser, eds.). - 1977. - P. 185-204.

[129] Fortunato S. Community detection in graphs. Physics Reports. - 2010.

- Vol. 486. - № 3. - P. 75-174.

[130] Fujn M., T. Kasami, K. Ninimiya. Optimal sequencing of two equivalent processors // SIAM J. Appl. Math. - 1969. - №17. - P. 784-789.

[131] Garey M.R., Johnson D.S. Strong NP-completeness results: Motivation, examples, and implications // Journal of the ACM. - 1978. - Vol. 25. -P. 499-508.

[132] Gerards A.M.H. Matching // in: Network Models [Handbooks in Operations Research and Management Science. Elsevier, Amsterdam. -1995. - Vol. 7. - P. 135-224.

[133] Giotis I., Guruswami V. Correlation clustering with a fixed number of clusters // Theory of Computing. - 2006. - Vol. 2. - № 1. - P. 249-266.

[134] Gomory R.E. An algorithm for integer solution to linear program // Recent Advances in Math. Prog. (R.L.Graves and P.Wolfe, eds.) — McGraw-Hill, New York. - 1963. - P. 269-302.

[135] Gomory R.E. Integer faces of polyhedron // Proc. Nat. Acad. Sci. USA, 1967. - Vol. 57. - №1. - P. 16-18.

[136] Gomory R.E. Outline of an algorithm for integer solution to linear program // Bull. Amer. Math. Soc. - 1958. - Vol.64. - №5. - P. 275-278.

[137] Gomory R.E. Some polyhedra related to combinatorial problems //J. Linear Algebra and Its Applications. - 1969. - Vol. 2. - №4. - P. 451-558.

[138] Gordon V.S., Potts C.N., Strusevich V.A., Whitehead J.D. Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation // Journal of Scheduling. - 2008. - Vol. 11. - №5. - P. 357-370.

[139] Grotschel M., Holland O. Solution of large-scale symmetric travelling salesman problems // Math. Programming. - 1991. - №51. - P. 141-202.

[140] Grotschel M., Holland O. Solution of large-scale symmetric travelling salesman problems // Math. Programming. Issue 2. - 1991. - Vol. 51. -P. 141-202.

[141] Grotschel M., Junger M. and Reinelt G. Facets of the linear ordering polytope // Math. Programming. - 1985. - №33. - P. 43-60.

[142] Grotschel M., Junger M., Reinelt G. A cutting plane algorithm for the linear ordering problem // Oper. Res. - 1984. - Vol. 32. - P. 1195-1220.

[143] Grotschel M., Padberg M. W. On the symmetric travelling salesman problem I: inequalities; II: lifting theorems and facets // Math. Programming. - 1979. - Vol. 16. - №2. - P. 265-302.

[144] Grotschel M., Padberg M.W. Polyhedral computations. The Travelling Salesman Problem. Ed. by E.L. Lawler etc. — John Wiley and Sons Ltd,

1985.

[145] Grotschel M., Pulleyblank W.R. Clique tree inequalities and the symmetric travelling salesman problem // Mathematics of Oper. Res. —

1986. — Vol. 11. — №4. — P. 537-569.

[146] Grotschel M., Wakabayashi Y. A cutting plane algorithm for a clustering problem // Mathematical Programming (Series B). — 1989. — №45 — P. 59-96.

[147] Grotschel M., Wakabayashi Y. Facets of the clique partitioning polytope // Mathematical Programming. — 1990. — №47. — P. 367-387.

[148] Grotschel M., Wakabayashi Y. Composition of facets of the clique partitioning polytope. In: R. Bodendiek and R. Henn (Eds.) Topics in Combinatorics and Graph Theory. Physica-Verlag, Heidelberg. — 1990. — P. 271-284.

[149] Hammer P., Johnson E., Peled U. Facets of regular 0-1-polytopes // Math. Prog. — 1975. — №8. - P. 179-206.

[150] Harary F. On the notion of balance of a signed graph // Michigan Mathematical Journal. — 1955. — Vol. 2. — P. 143-146.

[151] Ham I., Hitomi K., and Yoshida T. Group Technology: Applications to Production Management. Kluwer, Dordrecht. — 1988.

[152] Hausmann D. Adjacency on Polytopes in Combinatorial Optimization. Oelschlager, Cambridge, MA, 1979.

[153] Hoffman A.J., Kruskal J.B. Integral boundary points of convex polyhedra // Linear Inequalities and Related Systems. Princeton Univ.Press. — 1956. — P. 223-246

[154] Hu T.C. Parallel sequencing and assembly line problems // Operation Research. — 1961. — №9. — P. 841-848.

[155] Iellamo S., Alekseeva E., Chen L., Coupechoux M., Kochetov Yu. Competitive location in cognitive radio networks, 4OR. — 2015. — Vol. 13. — № 1. — P. 81-110.

[156] Jeroslow R. Cutting-plane theory: algebraic method // Discrete Math.

— 1978. — Vol. 23. — №2. — P. 121-150.

[157] Krivanek M., Moravek J. NP-hard problems in hierarchical-tree clustering // Acta informatica. — 1986. — Vol. 23. — P. 311-323.

[158] Karp R.M., Papadimitriu C.H. On linear characterizations of combinatorial optimization problems // SIAM Journal on Computing. — 1982. — Vol. 11. — P. 620-632.

[159] Kolish R., Padman R. An Integrated Survey of Project Sheduling. — 1997.

[160] Kolish R., Sprecher A. PSPLIB - A project scheduling problem librory // Manuscripte aus den Instituten fur Betriebswirtschaftshehre. — Kiel, Germany, 1996. — №396.

[161] Kononov A., Sevastianov S. and Tchernykh I. When difference in machine loads leads to efficient scheduling in open shops // Annals of Oper. Res.

— 1999. — Vol. 92. — P. 211-239.

[162] Kovalyov M. Improving the complexities of approximation algorithm for optimization problems. // Operations Research Letters. — 1995. — Vol. 17. — P.85-87.

[163] Lawner E.L., Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B. Sequencing and scheduling: Algorithms and complexity. Handbook in Operations Research and Management Science (Graves S.C., Rinnooy Kan A.H.G., Zipkin P., Eds.) NorthHolland. — 1993. — Vol. 4.

[164] Lenstra J.K., Rinnooy Kan. Complexity of scheduling under precedence constraints // Oper. Res. — 1978. — №26. — P. 22-35.

[165] Marcotorchino, F., Michaud, P. Heuristic approach to the similarity aggregation problem // Methods Oper. Res. — 1981. — №43. — P. 395-404.

[166] Mladenovic N., Brimberg J., Hansen P., Moreno-Perez J. A. The p-median problem: A survey of metaheuristic approaches // Eur. J. Oper. Res. — 2007. — Vol. 179. — № 3. — P. 927-939.

[167] Mokotoff E. An exact algorithm for the identical parallel machine scheduling problem // Europ. J. of Oper. Res. — 2004. — Vol. 152. — P. 758-769.

[168] Nemhauser G.L., Savelsbergh M.W. A cutting plane algorithm of single machine scheduling problem with release times // Combinatorial Optimization: New Frontiers in the Theory and Practice. NATO ASI Series F: Computer and System Science. Springer, Berlin. — 1992. — Vol. 82. — P. 63-84.

[169] Nemhauser G.L., Trotter L. Properties of vertex packing and independence system polyhedra // Math. Programming. — 1993. — №6. — P. 48-61.

[170] Oosten M., Rutten J.H.G.C., Spieksma F.C.R. The clique partitioning problem: facets and patching facets. Networks. — 2001. — T. 38. — №4. — P. 209-226.

[171] Padberg M.W. and Rinaldi G. Facet Identification for the Symmetric Traveling Salesman Polytope // Mathematical Programming. — 1990. — Vol. 47. — P. 219-257.

[172] Papadimitriou C.H. The adjacency relation on the traveling salesman polytope is NP-complete // Math. Programming. — 1978. — Vol. 14. — №1. — P. 312-324.

[173] Pulleyblank W.R. Facet generating techniques. Thomas J. Watson Research Center, IBM Corporation P.O. Box218. Yorktown Heights, New York, 1993.

[174] Pulleyblank W.R. Polyhedral combinatorics. North-Holland, 1989. -Vol. 1.

[175] Queyranne M. Structure of simple scheduling polyhedron // Mathematical Programming. - 1993. - №58. - P. 263-285.

[176] Queyranne M., Wang Y. A cutting plane procedure for precedence-constraned single machine scheduling. Working paper. Faculty of Commerce. University of British Columbia. Vancouver. Canada, 1991.

[177] Queyranne M., Wang Y. Single-machine scheduling polyhedra with precedence constraints // Mathematics of Oper. Res. - 1991. - №16. -P. 1-20.

[178] Rao M.R. Adjacency of the traveling salesman tours and 0-1 vertices // SIAM J. Appl. Math. - 1976. - T. 30. - №2. - P. 191-198.

[179] Schrijver A. Combinatorial optimization. - Springer-Verlag Berlin Heidelberg, 2003. - Vol. A,B,C.

[180] Schulz A.S. Polytopes and Scheduling. - Berling, 1996.

[181] Schulz A.S., Philips C.A., Shmoys D.B., Stein C., Wein J. Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem // Journal of Combinatorial Optimization. - 1998. - №1. - P. 413-426.

[182] Schulz A.S., Queyranne M. Polyhedral Approaches to Machine Scheduling. - Berlin, 1994.

[183] Shamir R., Sharan R., Tsur D. Cluster graph modification problems // Discrete Applied Mathematics. - 2004. - Vol. 144. - №1-2. - P. 173-182.

[184] Simanchev R.Yu. , Urazova I.V. Separation problem for 2-partition inequalities // 23rd International Symposium on Mathematical Programming (ISMP) The World Congress of the Mathematical Optimization Society (MOS) Bordeaux, July 1-6. - Bordeaux, 2018.

[185] Simanchev R.Yu. The Support inequalities and facets of combinatorial polytops // Intern. conf. "Optimal Discrete Structures and Algorithms".

- Rostock, 1997. - P. 62.

[186] Simanchev R.Yu., Urazova I.V. Cutting Planes Algorithm for the Connected k-factor Problem Using the Facet Inequalities // VIII International Conference "Optimization and Applications" (OPTIMA-2015). - Petrovac, Montenegro, October 2-7, 2017. - URL: http://ceur-ws.org/Vol-1987/paper74.pdf

[187] Simanchev R.Yu., Urazova I.V. Separation Problem for k-parashutes // Proc. DOOR 2016, Vladivostok, Russia, September 19-23, 2016. CEUR-WS. - 2016. - Vol. 1623. - P. 109-114. - URL: http://ceur-ws.org/Vol-1623/paperco16.pdf

[188] Simanchev R.Yu., Urazova I.V. On the Facets of Combinatorial Polytopes // In: Kochetov, Yu. et all (eds.) DOOR-2016. LNCS. - Springer, Heidelberg, 2016. - Vol. 9869. - P. 233-243.

[189] Stoer M., Wagner F. A simple min-cut algorithm // Journal of the ACM.

- 1997. - Vol. 44. - №4. - P. 585-591.

[190] Wakabayashi Y. Aggregation of Binary Relations: Algorithmic and Polyhedral Investigations, Ph.D. Thesis Universitat Augsburg, West Germany, 1986.

[191] Zahn C. T. Approximating symmetric relations by equivalence relations // J. of the Society for Industrial and Applied Mathematics. - 1964. -Vol. 12. - № 4. - P. 840-847.

[192] Zuylen A., Williamson D.P. Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems // Mathematics of Operations Research. - 2009. - Vol. 34. - № 3. - P. 594-620.