Многогранники на алгебраических структурах в целочисленном линейном программировании тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ

ГЛАВА I. МНОГОГРАННИКИ НА АЛГЕБРАИЧЕСКИХ СТРУКТУРАХ

§1. Многогранники на частичной алгебре

§2. Грани многогранников Гомори на циклической группе . • . •.

§3. Субаддитивные функции

ГЛАВА 2. СПЕЦИАЛЬНЫЕ КОМБИНАТОРНЫЕ МНОГОГРАННИКИ

§4. Достаточное условие разрешимости задачи целочисленного линейного программирования

§5. Многогранник путей, соединяющих две вершины графа

§6. Многогранники метрических матриц

Задача целочисленного линейного программирования (ЦЛП) я тая ,21 С; х. , j-<1 4 «/ А и** 9

J=1 V / * '

ХУ ^ ^ »целые, /7,

- одна из основных задач исследования операций. Она имеет большое практическое значение, так как является универсальной формой постановки многих оптимизационных задач дискретной математики. Вследствие своей общности задача ЩЩ содержит все трудности, присущие отдельным задачам комбинаторной оптимизации. Если для задачи линейного программирования Л.Г.Хачияном [5?] доказано, что она полиномиально разрешима, то задача ЦЛП является представителем класса ЫР -полных проблем [166, 16?, ? ] . Надежды на построение единого эффективного алгоритма решения любой задачи ЦЛП в настоящее время сохранились лишь у тех, кто допускает, что можно опровергнуть гипотезу РФЫР .

Задача ЦЛП является объектом изучения уже более тридцати лет. Методы решения, разработанные к середине шестидесятых годов, можно разделить на две основные группы: методы отсечений и методы ветвей и границ [2.4, . В последующий период число методов и алгоритмов целочисленного линейного программирования резко возросло [2 2, 23, Ц09 5Ъ} 5€} 59 р . Новые методы решения разработаны Ю.И.Журавлевым [ * В.А.Емеличевым

З-И, 15] , В.С.Михалевичем [ ЗВ? 35], И.В.Сергиенко [4*]. Результаты белорусских математиков занимают достойное место в исследованиях по дискретной оптимизации - см. обзорную статью Д.А.Супруненко, В.А.Емеличева и В.С.Танаева Современное состояние развития вычислительных методов и программ решения задач ЦДЛ охарактеризовано в [ 2 3? 1?0] .

Во второй половине шестидесятых годов усилился интерес к изучению алгебраической структуры множеств решений дискретных оптимизационных задач. К этому времени относится появление нового общего подхода к задачам ЦДЛ, получившего название теоретико-группового. Начало ему положила работа Р.Гомори [13^]. Теоретико-групповой подход позволил объяснить природу отсечений в более раннем, но до сих пор популярном, циклическом алгоритме отсечений [133] и стал источником новых идей в теории целочисленного линейного программирования.

В 1968 г. Д.А.Супруненко предложил новый метод исследования и решения задач комбинаторной оптимизации, основанный на постановке их в виде задачи минимизации линейной формы на симметрической группе [4?]. Этот метод получил дальнейшее развитие как в его собственных исследованиях , так и в многочисленных работах его школы [напр., 3,36, 3?9 43 . Полученные теоретические результаты находят практическое применение для решения реальных задач.

В.А.Емеличев и его ученики всесторонне исследовали строение многогранников решений транспортных задач [ ] . Алгебраический подход характерен для исследований различных комбинаторных задач, проводимых В.К.Леонтьевым [ ZB-ЗP]. Изучению целочисленных многогранников посвящены работы В.А.Трубина С-^}, В.Н.Шевченко [ 3, - €6 ] , В.П.Гришухина [ 6 ] . Интенсивные исследования в этой области ведут зарубежные математики, среди которых особое место занимают Дж.Эдмондс, М.Грётшель, Л.Ловас, Е.Джонсон.

Хорошо известно Г 2 ? / ] , что для любой задачи ЦЛП с ограничениями равенствами в принципе существуют неравенства множество решений которых образует выпуклую оболочку решений исходной задачи. Для некоторых задач комбинаторной оптимизации эти неравенства удалось найти в явном виде, см. ¿9? 144]

Это позволило разработать на основе метода эллипсоидов Н.З.Шора [69] и фундаментального результата Л.Г.Хачияна [£"?] полиномиальные алгоритмы решения таких задач , даже несмотря на то, что число неравенств экспоненциально зависит от длины входа каждой такой задачи [168]. В общем случае проблема поиска неравенств, определяющих область допустимых решений задачи ЦЛП остается сложной, а возможно, и практически неразрешимой. Однако вполне реально пытаться описать многогранник, по возможности более близкий к многограннику задачи ЦЛП [ -/44].

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

ЦЛП 1136,

5% ] . Переход к задаче на группе подробнее описан в § 2. Там же говорится о проблеме поиска граней многогранника решений групповой задачи.

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

ЦЛП [134]. В работах [19, Ю, 33, 54, 58, 63, 1Ю, 111, 113, 114-120, 130> 13В, 150, 1?5, построено множество других алгоритмов решения групповой задачи. В [58, 176, /83] приведены отличные от условия Гомори достаточные условия решения задачи ЦЛП, но все они далеки от необходимых [ 93, 14 0]. Некоторые аспекты связи задачи ЦЯП и групповой задачи рассмотрены в [ 86-83, 96, 103 129, 148] . Различные алгоритмы решения задачи ЦЛП посредством решения задачи на группе можно найти в работах 15,11,91-103, 111, 121, 126,1И, 153, /?5, Щ 182-190]. В 131,34,118, 119; 122, 169,172,1811 разработаны алгоритмы для задач специального вида.

Применение теоретико-группового подхода к задачам ЦЛП показало, что примерно в 70% случаев решение задачи на группе дает оптимальное решение целочисленной задачи [128, 14о] , но заранее трудно сказать, попадет ли конкретная задача ЦЛП в число этих 70%. Групповая задача является МР -полной [103], ее сложность зависит от порядка 0 получаемой группы & . Порядок группы равен определителю некоторой подматрицы максимального ранга матрицы ограничений и практически неограничен. В £142] отмечается, что при > 10000 решение групповой задачи становится трудной проблемой. По этим причинам, хотя чистый теоретико-групповой метод решения задач ЦЛП и дает для многих задач эффективные алгоритмы, в целом его результат оказывается непредсказуемым.

Больший оптимизм вселяют попытки применения теоретико-группового подхода в различных комбинациях с другими методами. Наиболее перспективным представляется использование групповых задач при вычислении оценок для метода ветвей и границ. Такие алгоритмы разработаны в [10%, 11*, 118, 1/9,12 141, 1*6, /¿4, /?г]л

Обнадеживают успехи применения теоретико-группового подхода для построения отсечений и даже граней многогранников некоторых задач. В 1980 г. Краудер, Джонсон и Падберг ["/16] докладывали о решении практических 0,1-задач с числом переменных от 300 до 2750. Отсечения определяли грани многогранников. В связи с поиском граней 0,1-многогранников необходимо отметить работу которая послужила толчком для многих других работ. Ее основные идеи близки к идеям теоретико-группового подхода. Хорошие результаты для решения булевых задач ЦЛП дало многолетнее сотрудничество Гуинард и Шпильберга, см. [447] .

Основные достижения последнего десятилетия в теории целочисленного линейного программирования в значительной мере связаны с осознанием той роли, которую играют субаддитивные функции при описании целочисленных многогранников. Пусть на некотором множестве $ определена алгебраическая операция- Ф , и 5 замкнуто относительно этой операции. Функция : $ —> Я называется субаддитивной относительно операции 4- , если для всех элементов * V 6 Д выполняется

7 * 2. соотношение

Одним из основных результатов Гомори является субаддитивная характеризация неравенств, определяющих грани группового многогранника. Она заключается в том, что коэффициенты неравенств являются значениями некоторой субаддитивной функции на группе б- , Сам факт субаддитивной характеризации граней был доказан Гомори в [?3ё]9 но то, что именно субаддитивность является основным свойством функций, определяющих грани, стало ясно из его совместной работы с Джонсоном [43 7], Введение субадаптивности в целочисленное линейное программирование следует считать важнейшим достижением теоретико-группового подхода.

Другим фактором, обусловившим дальнейшее развитие теории ЦЯП, явились результаты Фалкерсона [ 11Ъ- US'] о блокирующих и антиблокирующих многогранниках и их развитие в [ 789 809 109у 1S9t 16Zy 1%о] . Они обобщают понятие геометрической двойственности между гранями и вершинами ограниченных выпуклых многогранников [146] и теорию полярных множеств в выпуклом анализе Г*2]. Хороший обзор состояния исследований в этой области дан в [33].

Дж.Эдмондс первый заметил, что результаты Гомори о групповых многогранниках являются частным проявлением общих результатов о выпуклых многогранниках, а свойство субаддитивности их граней не имеет никакого отношения к понятию группы ("subadditivity ha8 nothing to do with the groups" - см. X. Араоз в диссертации, написанной под руководством Эдмондса и Джонсона, предложил способ построения многогранного множества на конечной абелевой полугруппе и доказал, что для его граней остается в силе свойство субаддитивной характеризации. Он обнаружил, что в виде оптимизационной задачи на этом многограннике можно сформулировать две широко известные задачи ЦЯП: о покрытии и о разбиении множеств г?«]. Оригинальные работы Араоза опубликованы большей частью в недоступных изданиях, но с его основными результатами можно ознакомиться по более поздним работам [1б1981] .

Используя субаддитивные функции на множестве всех вещественных чисел, Джонсон [lS49 458] и другие авторы [30 -$1)10Ь -1&6; 14 Z> 1ВЪ ] распространили теоретико-групповой подход на задачи смешанного ЦЛП. Это позволило Джерослоу обобщить построенную теорию на задачи на бесконечной полугруппе в вещественном пространстве [ 1S1 - 4S4 ] . Если обобщение Араоза направлено на рассмотрение задач о разбиении и о покрытии множеств, то елью Джерослоу было построение теории субаддитивных отсечений уш произвольной задачи ЦЛП.

Приведенные результаты позволяют говорить о том, что в семи-^сятые годы на базе теоретико-группового подхода был построен 5олее общий - суб аддитивный подход к задачам ЦЛП. Еще одним, не 1енее важным основанием для такого утверждения может служить по-;троение теории субаддитивной двойственности задач ЦЛП. Соответствующие результаты непосредственно связаны с уже приведенными I содержатся в тех же работах, а также в [ 101} 1109 111 15 6 у *607 1^1 > 12>$1 . Более точные формулировки основных теорем даются 5 § 3 . В {1112 предложен прямодвойственный (в смысле субадци-?ивной двойственности) алгоритм решения задач ЦЛП. Следует отме-?ить также работы С.С.Лебедева и О.К.Шейнмана [ 25 - Z 7 ] , юсвященные теории субадцитивной двойственности.

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

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

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

Первая глава диссертации содержит три параграфа.

В § I вводится и изучается множество на частичной алгебре, которое обобщает понятие многогранника на группе, полугруппе и аддитивной системе. Если алгебра конечна, то данное множество оказывается многогранным и для его граней выполняется свойство субаддитивной характеризации. Это означает, что неравенство определяет грань многогранного множества на частичной алгебре тогда и только тогда, когда оно является минимальным и крайним среди всех субаддитивных относительно операций алгебры неравенств (теорема I).

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

1) структура может иметь любое конечное число алгебраических операций,

2) в качестве операций структуры допускаются алгебраические операции любой конечной арности,

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

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

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

Второй параграф посвящен известной задаче поиска граней многогранника Гомори на конечной циклической группе £ порядка Предлагается новая форма представления неравенств, определяющих грани, - их коэффициенты должны быть целыми числами, взаимно простыми в совокупности. Такое представление дает возможность доказать ряд свойств граней. Свойства формулируются в виде теоретико-числовых соотношений между коэффициентами граней и не имеют аналогов в работах других авторов. Основной результат такого рода содержится в утверждении теоремы 3 : для любых I и ] % ^ 19 ] - i , коэффициенты 5Г. и 1Г. грани 2И ЕГ Ь. ^ многогранника с J к к на группе & удовлетворяют сравнению ¿^WJ =у-9Г (»их* , где (Л - делитель числа 0 . Доказанные свойства использовались автором при построении граней. В конце параграфа строятся новые грани групповых многогранников.

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

Вторую главу диссертации составляют параграфы 4-6.

Один из способов построения группы при теоретико-групповом подходе к задачам ЦЛП использует приведение матрицы ограничений задачи к нормальной форме Смита В § 4 нормальная форма Смита матрицы ограничений задачи применяется для получения достаточного условия разрешимости задачи ЦЛП. Известно, что разрешимость задачи ЦЛП - такая же сложная проблема, как и ее решение. Проверка предлагаемого достаточного условия сводится к решению серии задач линейного программирования и легко производится, если матрица ограничений задачи близка к квадратной или сильно вытянута.

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

В последнем параграфе диссертации рассматриваются многогранные множества матриц специального вида, которые названы метрическими. Это симметричные квадратные матрицы порядка П , диагональные элементы которых равны нулю, а недиагональные элементы удовлетворяют неравенству треугольника. Множество метрических матриц с неограниченными сверху элементами образует конус М и в ( 2 ) ~ мерйом пространстве. Задача поиска образующих этого конуса хорошо известна. Она возникает, в частности, в теории потоков в сетях при решении вопроса о разрешимости потоковых задач [ 2.1 - 3 4 ]. Некоторые крайние лучи найдены в работах

3*, И, 83, М].

В § 6 показывается, что конус метрических матриц является конусом субаддитивных функций на алгебре с одной частичной операцией. Такой взгляд на метрические матрицы позволяет применить теорему 4 о связи многогранников на частичной алгебре с конусом функций, субадцитивных относительно ее операций. Результатом применения является теорема 8, утверждающая, что каждой нетривиальной грани любого многогранника путей, соединяющих две вершины полного VI -вершинного графа, соответствует крайний луч конуса метрических матриц /Л и .

Далее в § 6 впервые устанавливается необходимое условие для того, чтобы метрическая матрица определяла крайний луч конуса

М • если метрическая матрица крайняя в конусе /Л и , то ее порождающий граф двусвязен (теорема 9).

С помощью порождающих графов строятся два новых больших семейства крайних лучей конуса метрических матриц (теоремы 10 и II). Из существования одного из этих семейств следует, что число крайних лучей конуса /ЛЪп не меньше числа неизоморфных связных графов на /I вершинах.

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

Все построения в диссертации проводятся в конечномерных векторных пространствах вида Я * над полем вещественных чисел Я . В соответствии с терминологией [42] под многогранным множеством в Я* понимается пересечение конечного числа замкнутых полупространств. Для краткости изложения в тех случаях, когда это не может вызвать недоразумений, термин "многогранник" используется для обозначения не только ограниченных, но и неограниченных многогранных множеств, а слово "грань" означает грань максимальной размерности многогранного множества, см. 41,60]. Такие алгебраические понятия, как группа, полугруппа и алгебра, предполагаются известными, см. [ /, .

Результаты диссертации опубликованы в работах £ 71 -76] и докладывались на У Конференции математиков Белоруссии (г.Гродно, 1980), на научных семинарах в Щ АН СССР, в ЦЭМИ АН СССР и на минском городском семинаре "Математическая кибернетика" в Институте математики АН БССР.

Автор выражает глубокую признательность своему научному руководителю академику АН БССР Д.А.Супруненко за введение в новую область исследований, ценные рекомендации и плодотворные советы, повседневное внимание и поддержку в трудные моменты работы над диссертацией.

1. Ван дер Варден. Алгебра. - М.: Наука, 1976, 648 с.

2. Веселов С.И. О числе крайних точек главного многогранника задачи групповой минимизации. Кибернетика, 1981, № 6, с. 137.

3. Веселов С.И., Шевченко В.Н. О гранях и крайних точках задач дискретного программирования. В сб.: Комбинаторно-алгебраические методы в прикладной математике. Горький: Изд-во ГГУ, 1981, с. 39-49.

4. Виноградов И.М. Основы теории чисел. М.: Наука, 1981, 176с.

5. Грицак В.В. О групповом методе решения задачи линейного целочисленного программирования. В сб.: Вычислительные аспекты в пакетах программ и опыт решения оптимизационных задач. Киев: ИК АН УССР, 1981, с. 76-81.

6. Гришухин В.П. Субмодулярные задачи и алгоритмы их решения. -Изв. АН СССР. Техн. киберн., 1983, № I, с. 188-193.

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

8. Демиденко В.М. Специальные случаи задачи о бродячем торговце с симметрической матрицей. ДАН БССР, 1980, т. 24, № 2, с. 105-108.

9. Емеличев В.А. К задачам дискретной оптимизации. ДАН СССР,1970, т. 192, №5, с. 1002-1003.

10. Емеличев В.А. К теории дискретной оптимизации. ДАН СССР,1971, т. 198, № 2, с. 273-276.

11. Емеличев В.А. Дискретная оптимизация. Последовательностные схемы решения. I. Кибернетика, 1971, № 6, с. 109-121.

12. Емеличев В.А. Дискретная оптимизация. Последовательностные схемы решения. II. Кибернетика, 1972, № 2, с. 92-103.

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

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

15. Емеличев В.А., Комлик В.И. Метод построения последовательности планов для решения задач дискретной оптимизации. -М.: Наука, 1981, 208 с.

16. Журавлев Ю.И. Локальные алгоритмы вычисления информации. I.-Кибернетика, 1965, № I, с. 12-19.

17. Журавлев Ю.И. Локальные алгоритмы вычисления информации. II.-Кибернетика, 1966, № 2, с. I-II.

18. Журавлев Ю.И. Алгебры над множествами некорректных (эвристических) алгоритмов. ДАН СССР, 1977, т. 235, № 4, с.761-763.

19. Ивлев В.И. Программа, реализующая асимптотический алгоритм.-Экономика и мат. методы, 1961, т. 17, № 2, с. 388-389.

20. Карзанов A.B. Справочная для выборки максимального элемента и ее приложения. В сб.: Исследования по дискретной оптимизации. М.: Наука, 1976, с. 348-359.

21. Карзанов A.B. Комбинаторные способы решения разрезных задач о мультипотоках. В сб.: Комбинаторные методы в потоковых задачах. Сб. трудов. М.: ВНИИСИ, 1979, вып. 3, с. 6-70.

22. Ковалев М.М. Дискретная оптимизация. Минск: Изд-во БГУ, 1977, 192 с.

23. Корбут A.A., Финкелыптейн Ю.Ю. Дискретное программирование. -М.: Наука, 1969, 368 с.

24. Лебедев С.С. Обобщенный метод пометок целочисленного линейного программирования. Экономика и мат. методы, 1984,т. 20, вып. 4, с. 704-718.

25. Лебедев С.С., Шейнман O.K. Двойственность в целочисленном программировании. Экономика и мат. методы, 1961, т. 27, вып. 3, с. 593-608.

26. Лебедев С.С., Шейнман O.K. Двойственный подход в целочисленном программировании. Изв. АН СССР. Техн. киберн., 1983,I, с. 181-187.

27. Леонтьев В.К. Алгебраическая структура некоторых задач дискретного программирования. В сб.: Пробл. кибернетики, вып. 26, М.: Наука, 1973, с. 279-290.

28. Леонтьев В.К. Дискретные экстремальные задачи. В сб.: Итоги науки и техники. Теор. вероятн. Матем. стат. Теор. киберн. М.: ВИНИТИ АН СССР, 1979, т. 16, с. 39-101.

29. Леонтьев В.К. О соотношениях длин траекторий в комбинаторных задачах выбора. ДАН СССР, 1981, т. 258, № 5, с. 1049-1052.

30. Литвак Б.Г. Об одном классе задач целочисленного программирования, решаемых модифицированным асимптотическим алгоритмом. В сб.: Мат. методы решения экономич. задач, 1980,9, М.: Наука, с. I07-II5.

31. Литвак Б.Г., Найвельт A.B. О решении задачи целочисленного линейного программирования с использованием теоретико-группового метода. Труды 6-ой Зимней школы по мат. программированию и смежн. вопросам, Дрогобыч,1973.-М.: 1975, с.158-166.

32. Литвак Б.Г., Найвельт A.B. Опорные групповые элементы в алгоритме групповой минимизации. В сб.: Исследования по дискретной оптимизации. М.: Наука, 1976, с. I4I-I55.

33. Ломоносов М.В. 0 системе потоков в сети. Проблемы передачи информации, 1978, т. 14, № 4, с. 60-73.

34. Мальцев А.И. Алгебраические системы. М.:Наука, 1970, 392 с.

35. Метельский H.H. Об экстремальных значениях линейной формы на некоторых множествах подстановок. Изв. АН БССР. Сер. физ.-мат. наук, 1972, № 5, с. 5-10.

36. Метельский H.H., Демиденко В.М. О квадратичной задаче выбора.-Изв. АН БССР. Сер. физ.-мат. наук, 1975, № 5, с. 25-29.

37. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. I. Кибернетика, 1965, № I, с. 45-66.

38. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. II. Последовательные правила для опытов с детерминированными исходами. Кибернетика, 1965, № 2, с. 85-89.

39. Михалевич B.C., Сергиенко И.В., Лебедева Т.Т. и др. Пакет прикладных программ ДИСПРО, предназначенный для решения задач дискретного программирования. Кибернетика, 1961, № 3, с.1.7-137.

40. Палернов Б.А. Реализуемость многопродуктовых потоков. В сб.: Исследования по дискретной оптимизации. - М.: Наука, 1976,с. 230-261.

41. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973, 472 с.

42. Сарванов В.И. О многогранниках, связанных с оптимизацией на подстановках. Ин-т мат. АН БССР, Препринт, 1977, № 7, 14 с.

43. Сарванов В.И. К оптимизации на подстановках. Изв. АН БССР. Сер. физ.-мат. наук, 1979, № 4, с. 9-II.

44. Сарванов В.И. 0 сложности минизации линейной формы на множестве циклических подстановок. ДАН СССР, 1980, т. 253, № 3, с. 533-535.

45. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наукова думка, 1981, 288 с.

46. Супруненко Д.А. О значениях линейной формы на множестве подстановок. Кибернетика, 1968, № 2, с. 59-63.

47. Супруненко Д.А. К задаче о бродячем торговце. Кибернетика, 1975, № 5, с. I2I-I24.

48. Супруненко Д.А. О минимуме величины , т) на множестве циклов. Минск, Ин-т матем. АН БССР, Препринт, 1976,14 (14), II с.

49. Супруненко Д.А., Емеличев В.А., Танаев B.C. О работах белорусских математиков в области дискретной оптимизации. -Изв. АН СССР. Техн. киберн., 1982, № 6, с. 25-45.

50. Супруненко Д.А., Метельский Н.Н. Задача о назначениях и минимизация суммы линейных форм на симметрической группе. -Кибернетика, 1973, № 3, с. 64-68.

51. Таккер А.У. Двойственные системы однородных линейных соотношений. В сб.: Линейные неравенства и смежные вопросы,под ред. Г.У.Куна и А.У.Таккера, М.: ИЛ, 1959, с. I27-I4I.

52. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. -М.: Наука, 1975, 256с.

53. Тришин В.Н. Модифицированный алгоритм групповой минимизации с использованием опорных элементов. Ж. вычисл. матем. и мат. физики, 1983, т. 22, № 3, с. 593-598.

54. Трубин В.А. О методе решения задач целочисленного линейного программирования специального вида.-ДАН СССР, 1969, т. 189, № 5, с. 952-954.

55. Уздемир А.П. Динамические целочисленные задачи экономического планирования: Автореф. дис. на соиск. учен. степ, д-ра физ.-мат. наук. М., 1981, 42 с.

56. Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании. ДАН СССР, 1979, т. 244, № 5, с. 1093-1096.

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

58. Червак Ю.Ю. Методы лексикографической оптимизации и их применение: Автореф. дис. на соиск. учен. степ, д-ра физ.-мат. наук. Киев, 1981, 24 с.

59. Черников С.Н. Линейные неравенства. М.: Наука, 1968, 488 с.

60. Шевченко В.Н. О пересечении выпуклого многогранного конуса с целочисленной решеткой. Изв. высш. учебн. заведений. Радиофизика, 1970, т. 13, № 8, с. 1264-1266.

61. Шевченко В.Н. О двойственном описании конуса, целочисленно-порожденного конечным множеством векторов. Мат. заметки, 1973, т. 14, № 4, с. 523-526.

62. Шевченко В.Н. О решении элементарной задачи целочисленного линейного программирования. В сб.: Управляемые системы, Новосибирск, 1975, вып. 14, с. 69.

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

64. Шевченко В.Н. О числе крайних точек в целочисленном программировании. Кибернетика, 1981, № 2, с. 133-134.

65. Шевченко В.Н. Алгебраический подход в целочисленном программировании. Кибернетика, 1984, № 4, с. 36-41.

66. Шейнман O.K. Двойственность в некоторых дискретных задачах минимизации. Успехи мат. наук, 1978, т. 33, № 2, с. 211.

67. Шейнман O.K. Двойственность и субаддитивные функции в целочисленном программировании. Экономика и мат. методы, 1980, т. 16, вып. 4, с. 808-810.

68. Шор Н.З. О скорости сходимости метода обобщенного градиентного спуска с растяжением пространства. Кибернетика, 1970, № 2, с. 80-85.

69. Эрдеш П., Спенсер Дж. Вероятностные методы в комбинаторике.-М.: Мир, 1976, 131 с.

70. Метельский Н.Н., Шлык В.А. Об условиях разрешимости задачи целочисленного линейного программирования. Изв. АН БССР. Сер. физ.-мат. наук, 1977, № 5, с. 16-19.

71. Шлык В.А. О гранях главных многогранников Гомори. Изв. АН БССР. Сер. физ.-мат. наук, 1978, № 2, с. 5-И.

72. Шлык В.А. Одно свойство граней главных многогранников Гомори циклических групп. Изв. АН БССР. Сер. физ.-мат. наук, 1980, № 2, с. 45-48.

73. Шлык В.А. О многогранниках метрических матриц. Изв.АН БССР. Сер. физ.-мат. наук, 1984, № 5, с. 12-17.

74. Шлык В.А. Субаддитивная характеризация граней многогранных множеств на частичной алгебре. ДАН БССР, 1984, т. 28, № И, с. 980-983.

75. Шлык В.А. О гранях многогранных множеств на частичной алгебре. Изв. АН БССР. Сер. физ.-мат. наук, 1984, № 6, с. НО. (Рукопись депонирована в ВИНИТИ 18.05.84, рег.№ 3213-84 Дёп.)

76. Шлык В.А. Многогранник путей, соединяющих две вершины графа.-Изв. АН БССР. Сер. физ.-мат. наук , 1985.

77. Araoz J. Blocking and anti-blocking extensions. Oper. Res. Verfahren, 1978, v. 32, p. 5-18.

78. Araoz J. Packing problems in semigroup programming. Report N 82220 - OR, Inst, fur Okonom. und Oper. Res., Bonn, 1982, 28 S.

79. Araoz J., Edmonds J., Griffin V. Polarities given by systems of bilinear inequalities. Math. Oper. Res., 1983, v. 8,N 1, p. 34-41.

80. Araoz J., Johnson E.L. Polyhedra of additive system problems. Methods of Oper. Res., 1981, v. 40, p. 211-214.

81. Araoz J., Johnson E.L. Some results on polyhedra of semigroup problems. SIAM J. Alg. Discr. Methods, 1981, v. 2, N 3. P. 244-258.

82. Avis D. On the extreme rays of the metric cone. Canad. J. Math., 1980, v. 32, N1, p. 126-144.

83. Avis D. Extremal metrics induced by graphs. Annals of Discrete Math., 1980, v. 8, p. 217-220.

84. Avis D. Hypermetric spaces and the Hamming cone. Canad. J. Math., 1981, v. 33, H 4, p. 795-802.

85. Bachem A. Approximation ganzzahliger Polyeder durch Corner Polyeder. Z-t angew. Math, und Mech., 1976, Bd. 56, N 3, S. 332-333.

86. Bachem A. Reduction and decomposition of integer programs over cones. Annals of Discrete Math., 1977, v. 1, p. 1-11.

87. Bachem A. The theorem of Minkowski for polyhedral monoids and aggregated linear Diophantine systems. in: Optimization and operations research. Lect. Notes Econom. Math. Systems, Berlin, Springer, 1978, v. 157, p. 1-13.

88. Bachem A., Grotschel M. Hew aspects of polyhedral theory. -in: Modern Applied Math., ed. by B.Korte, North-Holl. Publ. Co., 1982, p. 51-106.

89. Bachem A., Johnson E.L., Schräder R. A characterization of minimal valid inequalities for mixed integer programs. -Oper. Res. Letters, 1982, v.1, N2, p, 63-66.

90. Bachem A., Schräder R. A duality theorem and minimal inequalities in mixed integer programming. Z-t angew. Math, und Mech., 1979, Bd.59, S. 88-89.

91. Bachem A., Schräder R. Minimal inequalities and subadditive duality. SIAM J. Control Optimiz., 1980, v.18, H 4, p. 437443.

92. Balas E. A note on the group theoretic approach to integer programming and the 0-1 case. Oper. Res., 1973» v.21, N 1, p. 321-322.

93. Balas E., Zemel E. Critical cutsets of graphs and canonical facets of set-packing polytopes. Math. Oper. Res., 1977» v.2, N 1, p. 15-19.

94. Balinski M.L., Spielberg K. Methods for Integer Programmings Algebraic, Combinatorial, and Enumerative. in: Progress in Oper. Res., v#3, ed. by J.S.Aronofsky, Wiley & Sons, 1969, p. 195-292.

95. Bell D.E. Intersections of corner polyhedra. IIASA Research Memorandum RM-74-14, Laxenburg, Austria, 1974, 17 p.

96. Bell D.E. Constructive group relaxations for integer programs.-SIAM J. Applied Math., 1976, v.30, p. 708-719.

97. Bell D.E. A simple algorithm for integer programs using group constraints. Oper. Res. Quart., 1977» v.28, IT 2, p. 453-458.

98. Bell D.E. Efficient group cuts for integer programs. Mathem. Program., 1979. v.17, p. 176-183.

99. Bell D.E., Fisher M.L. Improved integer programming bounds using intersections of corner polyhedra. Mathem. Program., 1975, v.8, N 3» P. W-368.

100. Bell D.E., Shapiro J.P. A finitely convergent duality theory for zero-one integer programming. IIASA Research Memorandum RM-75-33, Laxenburg, Austria, 1975, 27 p.

101. Bell D.E., Shapiro J.P. A convergent duality theory for integer programming. Oper. Res., 1977, v.25, N 3, P. 419-434.

102. Bertolazzi P., Leporelli C., Lucertini M. Alternative group relaxation of integer programming problems. Lect. Notes Control Inf. Sci., 1980, v. 23, P. 154-159.

103. Blair C.E. Minimal inequalities for mixed integer programs. -Discrete Math., 1978, v.24, N 2, p. 147-151.

104. Blair C.E., Jeroslow R.G. The value function of a mixed integer program: I. Discrete Math., 1977, v.19, N 2, p. 121-138.

105. Blair C.E., Jeroslow R.G. The value function of a mixed integer program: II. Discrete Math., 1979, v.25, N 1, p. 7-19.

106. Blair C.E., Jeroslow R.G. The value function of an integer program. Mathem. Program., 1982, v.23, N 3, P. 237-273.

107. Bradley G.H., Wahi P.N. An algorithm for integer linear programming: a combined algebraic and enumeration approach. -Oper. Res., 1973, v.21, N 1, p. 45-60.

108. Burdet C.A. Elements of a theory in non-convex programming. -Nav. Res. Log. Quart., 1977, v.24, N 1, p. 47-66.

109. Burdet C.A., Johnson E.L. A subadditive approach to the group problem of integer programming. Mathem. Program. Study 2, 1974, p. 51-71.

110. Bürdet C.A., Johnson E.L. A subadditive approach to solve linear integer programs. Annals of Discrete Math., 1977» v.1, p. 117-143.

111. Cambini A. Application of the method of dynamic programming to an optimization problem over a finite abelian group. -An. Pisos Univ. di Pisa, Dipt, di Ricerca Operativa e Sci-enze Statistiche, 1976, 26 p.

112. Chen D.S., Zionts S. Comparison of some algorithms for solving the group theoretic integer programming problems. -Oper. Res., 1977, v.24, p. 1120-1128.

113. Chvatal V. Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math., 1973, v.4, p. 303-337.

114. Crowder H.D., Johnson E.L. Use of cyclic group methods in branch and bound. in: Mathematical Programming, ed, by T.C. Hu and S.M. Robinson, Academic Press, New York, 1973, p. 213-226.

115. Crowder H.D., Johnson E.L., Padberg M. Solving 0-1 programming problems. in: IV Workshop on Combinatorial Optimization, Bonn, 1980. Report N 80159-OR, Inst, fur Ökonom, und Oper. Res., Bonn, 1980, p. 14-15.

116. Cuninghame-Green R.A. Integer programming by long division. -Discrete Appl. Math., 1981, v.3, p. 19-25.

117. Denardo E.V., Fox B.L. Shortest-route methods: 1. Reaching, pruning, and buckets. Oper. Res., 1979, v.27, N 1, p.161-186.

118. Denardo E.V., Pox B.L. Shortest-route methods: 2. Group knapsacks, expanded networks, and branch-and-bound. Oper. Res., 1979, v. 27, N 3, P. 548-566.

119. Fanelli S. An extension of Hu»s group minimization algorithm. -Calcolo, 1978, v.15, N 2, p. 197-210.

120. Fisher M.L., Shapiro J.P. Constructive duality in integer programming. SIAM J. Appl. Math., 1974. v.27, p. 31-52.

121. Frieze A.M. Shortest path algorithms for knapsack type problems. Mathem. Program., 1976, v.11, p. 150-157.

122. Fulkerson D.R. Blocking polyhedra. in: Graph Theory andits Applications, ed. by B.Harris, Academic Press, 1970, p. 93-112.

123. Fulkerson D.R. Blocking and anti-blocking pairs of polyhedra.-Mathem. Program., 1971, v.1, p. 168-194.

124. Fulkerson D.R. Anti-blocking polyhedra. J. Combinat. Theory, 1972, v.12, p. 50-71.

125. Gallo G., Simeone B. New cuts for integer programming via group optimization. Publ. Inst, applic. calcolo Mauro Pico-ne, 1975, ser. 3, N 105, P. 5-19.

126. Garfinkel R.S., Nemhauser G.L. Integer programming. Wiley & Sons, New York, 1972.

127. Garfinkel R.S., Nemhauser G.L. A survey of integer programming emphasizing computation and relations among models. -in: Mathematical Programming, ed. by T.C.Hu and S.M.Robinson, Academic Press, New York, 1973, P. 77-155.

128. Giulianelli S., Lucertini M. A decomposition technique in integer linear programming. Lect. Notes Comput. Sci., 1976, v.41, p. 87-97.

129. Glover F. Integer programming over a finite additive group. -SIAM J. Control, 1969, v.7, N2, p. 213-231.

130. Glover F. Faces of the Gomory polyhedron. in: Integer and Nonlinear Programming II, ed. by J.Abadie, North-Holl. Publ. Co., 1970, p. 367-379.

131. Glover F. Paces of the Gomory polyhedron for cyclic groups. -J. Math. Anal, and Appl., 1871, v.35, N 1, p. 195-208.

132. Gomory R.E. An algorithm for integer solutions to linear programs. in: Recent Advances in Mathematical Programming, ed. by R.L.Graves and P.Wolfe, McGraw-Hill, New York, 1962, p. 269-302.

133. Gomory R.E. On the relation between integer and non-integer solutions to linear programs. Proc. National Acad. Sei., 1965, v.53, N 2, p. 260-265.

134. Gomory R.E. Paces of an integer polyhedron. Proc. National Acad. Sei., 1967, v.57, N 1, p. 16-18.

135. Gomory R.E. Some polyhedra related to combinatorial problems.-Lin. Algebra and Its Appl., 1969, v.2, N 4, p. 451-558.

136. Gomory R.E., Johnson E.L. Some continuous functions related to corner polyhedra I, II. Mathem. Program., 1972, v.3,N 1, p. 23-85; N 3, P. 359-389.

137. Gondran M. Programmation linéaire en nombres entiers: optimisation dans un cone. Rev. franc, inform, et rech. oper., 1970, t.4, N R-2, p. 11-27.

138. Gordan P. Über die Auflosungen linearer Gleichungen mit reelen Coefficienten. Math. Ann., 1873, Bd.6, p. 23-28.

139. Gorry G.A., Northup W.D., Shapiro J.P. Computational experience with a group theoretic integer programming algorithm. -Mathem. Program., 1973, v.4, p. 171-192.

140. Gorry G.A., Shapiro J.P. An adaptive group theoretic algorithm for the integer programming problems. Manag. Sei., 1971, v.17, N 5, P. 285-306.

141. Gorry G.A., Shapiro J.F. , Wolsey L.A. Relaxation methods for pure and mixed integer programming problems. Manag. Sci., 1972, v.18, IT 5, P- 229-239.

142. Greenberg H. A dynamic programming solution to integer programs. J. Math. Anal., 1969, v.26, p. 454-439.

143. Grotschel M. Approaches to hard combinatorial problems. -in: Modern Applied Mathematics, ed. by B.Korte, ITorth-Holl. Publ. Co., 1982, p. 437-515.

144. Grotschel M., Lovasz L., Schrijver A. The, ellipsoid method and its consequences in combinatorial optimization. Combi-natorica, 1981, v.1, p. 169-197.

145. Grunbaum B. Convex Polytopes. Wiley & Sons, London, 1967.

146. Guinard M., Spielberg K. Logical reduction methods in zero-one programming. Minimal preferred variables. Oper. Res., 1981, v.29, И 1, p. 49-74.

147. Halfin S. Arbitrarily complex corner polyhedra are dense in Rn. SIAM J. Appl. Math., 1872, v.23, IT 2, p. 157-163.

148. Hammer P.L., Johnson E.L.,Peled U.N. The role of master polytopes in the unit cube. SIAM J. Appl. Math.,1977, v.32, IT 4, p. 711-716.

149. Helgason R.V., Kennington J.L. A new storage reduction technique for the solution of the groupproblem. Nav. Res. Log. Quart., 1979, v.26, IT 4, p. 681-687.

150. Jeroslow R.G. Cutting-plane theory: Disjunctive methods. -Annals of Discrete Math., 1977, v.1, p. 293-330.

151. Jeroslow R.G. Cutting-plane theory: Algebraic methods. -Discrete Math., 1978, v.23, IT 2, p. 121-150.

152. Jeroslow R.G. Some basis theorems for integral monoids. -Math. Oper. Res., 1978, v.3, N 2, p. 145-154.

153. Jeroslow R.G. The theory of cutting planes. in: "Combinatorial Optimization. Lect. Summer Sch., Urbino, 1977", 1979, P. 21-79.

154. Jeroslow R.G. Minimal inequalities. Mathem. Program., 1979, v.17, p. 1-15.

155. Johnson E.L. Paces of mixed integer programming problems. -Symposia Mathematica, Vol. XIX, Academic Press, 1976, p. 289299.

156. Johnson E.L. Support functions, blocking pairs, and antiblocking pairs. Mathem. Program. Study 8, 1978, p. 167-196.

157. Johnson E.L. On the group problem and a subadditive approachto integer programming. Annals of Discrete Math., 1979, v.5, p. 97-112.

158. Johnson E.L. Integer programming. Facets, subadditivity, and duality for group and semi-group problems. Philadelphia: SIAM, 1980, 68 p.

159. Johnson E.L. On the generality of the subadditive characterization of faces. Mathem.Oper. Res., 1981, v.6, N 1, p. 101112.

160. Johnson E.L. Characterization of facets for multiple right-hand choice linear programs. Mathem. Program. Study 14, 1981, p. 112-142.

161. Johnson E.L., Suhl U.H. Experiments in integer programming. -Discrete Appl. Math., 1980, v.2, p. 39-55.

162. Kannan R., Bachem A. Polynomial algorithms for computing the Smith normal form of an integer matrix. SIAM J. Corn-put. , 1979, v.8, p. 499-507.

163. Kannan R., Monma C.L. On the computational complexity of integer programming problems. Lect. Notes Econom. Math. Systems, v.157, Springer, Berlin, 1978, p. 161-172.

164. Karp R.M. On the computational complexity of combinatorial problems. Networks, 1975, v.5, P. 44-68.

165. Karp R.M., Papadimitriou C.H. On linear characterizations of combinatorial optimization problems. SIAM J. Comput., 1982, v.11, N 4, p. 620-632.

166. Kennington J.I., Unger V.E. The group-theoretic structure in the fixed-charge transportation problem. Oper. Res., 1973, v.21, p. 1142-1153.

167. Land A., Powell S. Computer codes for problems of integer programming. Annals of Discrete Math., 1979, v.5, p. 221226.

168. Meyer R.R., Wage M.L. On the polyhedrality of the convex hull of the feasible set of an integer program. SIAM J. Control Optim., 1978, v.16, N 4, p. 682-687.

169. Salkin H.M. Integer programming. Addison-Wesley Publ. Co., Reading, Masa, 1975, 537 P.

170. Shapiro J.P. Dynamic programming algorithms for the integer programming problem I: The integer programming problem viewed as a knapsack type problem. - Oper. Res., 1968, v.16, N 1, p. 103-121.

171. Shapiro J.P. Group theoretic algorithms for the integer programming problem II: Extension to a general algorithm. -Oper. Res., 1968, v.16, IT 5, p. 928-947.

172. Simeone B. A conic algorithm for the group minimization problem. Cah. Centre Etud. Rech. Oper., 1979, T.21, p. 337-351.

173. Stiemke E. fiber positive Losungen homogener linearer Gleichungen. Math. Ann., 1915, Bd.76, p. 340-342.

174. Thiriez H. The set covering problem: a group theoretic approach. Rev. Franc. Inform. Rech. Oper., 1971, T.3, P. 83-104.

175. Tind J. Certain kinds of polar sets and their relation to mathematical programming. Mathem.Program.Study 12, 1980,p. 206-213.

176. Volpentesta A. Some remarks about homomorphisms and group minimization problems. Survey of mathematical programming, Budapest, 1980, p. 553-557.

177. Wolsey L.A. Extensions of the group theoretic approach in integer programming. Manag. Sci., 1971, v.18, N 1, p. 74-83.

178. Wolsey L.A. Group-theoretic results in mixed integer programming. Oper. Res., 1971, v.19, N 7, p. 1691-1697.

179. Wolsey L.A. Groups, bounds and cuts for integer programming problems. Rev. belg. statist, inform, rech. oper., 1973, t.13, N1, p. 38-43.

180. Wolsey L.A. A view of shortest route methods in integer programming. Cah. Centre Etud. Rech. Oper., 1974, t.16, N 4,P. 317-335.

181. Wolsey L.A. A number theoretic reformulation and decomposition methods for integer programming. Discrete Math., 1974, v.7, p. 393-403.

182. Wolsey L.A. Valid inequalities and superadditivity for 0-1 integer programs. Math. Oper. Res., 1977, v.2, N 1,p. 66-77.

183. Wolsey L.A. Cutting plane methods. in; Operations Research Support Methodology, ed. by A.G.Holzman, Hew York, p. 441466.

184. Wolsey L.A. Integer programming duality: price functions and sensitivity analysis. Mathem.Program., 1981, v.20, P. 173-195.

185. Yamamoto Y. A group theoretic dual problem without duality gaps for bounded integer programs. J. Oper. Res. Soc. Japan, 1980, v.23, IT 2, p. 146-155.