Методы уменьшения размерности задачи бинарного программирования тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Ахмедов, Фирудун Беюкага оглы

• Ахмедов, Фирудун Беюкага оглы
• кандидат физико-математических наук
• 1985

Оглавление диссертации кандидат физико-математических наук Ахмедов, Фирудун Беюкага оглы

ВВЕДЕНИЕ

ГЛАВА I. МЕТОД ПОСЛЕДОВАТЕЛЬНОГО УМЕНЬШЕНИЯ РАЗМЕШОСТИ

ЗАДАЧИ БИНАРНОГО ПРОГРАММИРОВАНИЯ

§ I.I. Обзор некоторых подходов к уменьшению размерности задачи ЦЛП.

§ 1.2. Уменьшение количества переменных и ограничений в задаче бинарного программирования

§ 1.3. Описание алгоритма последовательного уменьшения размерности задачи бинарной оптимизации

§1.4. О вычислительной реализации алгоритма ПУРЗ

§ 1.5. Некоторые результаты вычислительных экспериментов

ГЛАВА П. МЕТОДЫ ПОСТРОЕНИЯ НИЖНЕЙ ОЦЕНКИ ОПТИМАЛЬНОГО ЗНАЧЕНИЯ ЦЕЛЕВОЙ ФУНКЦИИ ЗАДАЧИ БИНАРНОГО ПРОГРАММИРОВАНИЯ

§2.1. Методы приближенного решения и методы, ориентированные на построение допустимого решения

§2.2. Методы типа последовательного назначения для приближенного решения задачи бинарного программирования с неотрицательными коэффициентами

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

§ 2.4. Обобщение методов типа последовательного назначения для приближенного решения некоторых классов задач ЦДЛ.

§ 2.5. Пакет прикладных программ РАНЕЦ-I для приближенного решения задачи бинарного программирования с неотрицательными коэффициентами

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

ГЛАВА Ш. ШЭД ПОСТРОЕНИЯ ВЕРХНЕЙ ОЦЕНКИ ОПТИМАЛЬНОГО ЗНАЧЕНИЯ ЦЕЛЕВОЙ ФУНКЦИИ ЗАДАЧИ БИНАРНОГО ПРОГРАММИРОВАНИЯ

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

§ 3.2. Метод обхода вершин многогранника ограничений задачи бинарной оптимизации

§ 3.3. Вычислительные аспекты алгоритма ОБХОД

§ 3.4. Результаты вычислительных экспериментов

Введение диссертации (часть автореферата) на тему «Методы уменьшения размерности задачи бинарного программирования»

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

Одним из быстроразвивающихся разделов математического программирования является дискретное программирование, задачи которого выражаются в виде отыскания экстремума некоторой функции на некотором дискретном множестве. К задачам дискретной оптимизации сводятся многие оптимизационные задачи, имеющие важное народнохозяйственное значение. Это - задачи планирования работ, организации производства, размещения и реконструкции предприятий и др. [43, 54, 83,86,89] . За последние годы в связи с интенсивным развитием АСУ, теории и технологии вычислительных сетей в терминах дискретного программирования сформулированы многие задачи, возникающие при проектировании АСУ, вычислительных сетей и систем ЭВМ, а также при обработке данных в вычислительных центрах и системах [95,71,84] .

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

Постоянное внимание многих исследователей к задаче бинарного программирования не случайно, так как она имеет важное методологическое и практическое значение:

- к ней сводится всякая линейная задача дискретной оптимизации, множество допустимых решений которой ограничено [54,49] ;

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

- обычно не возникают трудности при распространении предложенного для ее решения метода на общую задачу ЦДЛ.

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

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

Максимизировать f" (X) = 2-С.Х:, (I)

И, ** ^ при оттятшянист* п - У п. v- ^ Р : = / yyj (2)

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

Сложность решения задач ЦЛП неоднократно была подтверждена как теоретически, так и экспериментально [52,891. В частности, исследование задачи ЦЛП с позиций сильно развивающейся в последние годы теории сложности вычислений: показало, что эта задача принадлежит к классу NP - полных задач [36,129].

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

Как видно, трудность решения задач ЦЛП основана не столько на некачественности методов и малой производительности современных ЭВМ, сколько в принципиальной сложности самих задач.

Экспоненциальная оценка трудоемкости методов решения задачи ЦЛП, являясь оценкой по наихудшему случаю, ни в коей мере не означает, что всякое применение этих методов к решению конкретных задач ЦЛП будет требовать очень большие вычислительные затраты. Имеется немало сообщений об удачном применении мощных пакетов программ к решению задач с сотнями и даже тысячами целочисленных переменных [106, 51]. Интересно отметить, что исправно служащий в течение долгого времени исследователям и практикам и считающийся достаточно эффективным симплекс - метод решения задачи линейного программирования (ЛП) тоже имеет экспоненциальную оценку трудоемкости.

Исторически первым методом решения задачи ЦЛП является метод отсечения, геометрически прозрачная идея которого впервые была предложена Данцигом f107] и вкратце заключается в следующем: предлагается вначале пренебречь условием целочисленности переменных и вместо задачи ЦЛП (I) - (4) решить задачу ЛП (I) - (3). Если решение задачи ЛП не является целочисленным, то к системе ограничений (2) - (3) добавляется новое ограничение, которому полученное решение задачи ЛП не удовлетворяет, а любое допустимое (целочисленное) решение задачи (I) - (4) заведомо удовлетворяет.

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

Впервые идею Данцига удалось удовлетворительно реализовать Гомори [116]. Ему принадлежат алгоритмы полностью и частично целочисленного линейного программирования, подробное изложение которых можно найти в [54,110,91,134]. Эти, ставшие уже классическими, алгоритмы дали начало целому ряду работ, в которых рассматривались различные способы построения отсечений[146,97,147,ИЗ, 103,92,112] и делались попытки их сравнения [ЗЗ].

Вычислительная практика (в основном, только по методам Гомори) показала невысокую эффективность методов отсечения [54].

Несмотря на это, алгоритмы отсечений могут быть успешно использованы, если их применять не как метод точного решения, а как вспомогательный аппарат для анализа задачи. Они также могут быть использованы в схемах различных методов решения задачи ЦЛП для увеличения эффективности этих методов и получения новых гибридных методов [88,119,27,138,106] . Такая методология применения отсечений систематически используется и в настоящей работе.

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

Одним из первых наиболее общих методов комбинаторного типа, примененного для решения задачи ЦЛП,был метод динамического программирования [22] . Метод может быть применен к задаче ЦЛП с небольшим числом ограничений. Наиболее хорошо разработаны и исследованы различные схемы применения метода динамического программирования к задаче о ранце [23,110] (задаче бинарного программирования только с одним ограничением вида (2)).

Метод динамического программирования для решения задач дискретной оптимизации является частным случаем более универсального и гибкого метода последовательного анализа вариантов, предложенного В.С.Михалевичем, Н.З.Шором [641 и развитого в последующих работах [ 65,66,68,69 ] . В основе схемы последовательного анализа вариантов лежит теоретико-множественный подход к задаче поиска решений. Алгоритмы, реализующие эту схему, используют различные идеи перебора и анализа вариантов, позволяющие отсеивать множества неоптимальных решений задачи без их полного просмотра. Многие исследования по методу последовательного анализа вариантов нашли широкое применение и развитие в созданной в Институте кибернетики АН УССР программной системе ДИСПРО для решения задач дискретного программирования [ 67].

Мощным средством решения широкого круга задач дискретной оптимизации является метод построения последовательности планов, разработанный и развитый Емеличевым В.А. и его учениками[40, 41,43,73]. Сущность этого метода состоит в замене исходной задачи более простой, вспомогательной задачей, для которой удается находить не только оптимальное решение, но и следующие за ним решения в порядке ухудшения новой целевой функции. Последовательное построение таких решений продолжается до выполнения критерия оптимальности. Важной особенностью метода построения последовательности планов является то, что схема метода позволяет в ходе процесса оценивать оптимум целевой функции исходной задачи с двух сторон, одновременно генерируя приближенное решение.

Из комбинаторных методов, предназначенных для решения специальных задач целочисленного программирования, следует выделить оригинальный метод последовательных расчетов [93], который предназначен для нахождения максимума функции -f(oJ), определенной на всех подмножествах заданного конечного множества Л . При этом предполагается, что функция удовлетворяет следующему аналогу условия выпуклости. Для любого ojh , 6. Л

На основе метода последовательных расчетов разработан ап-проксимационно-комбинаторный метод [90], успешно применяющийся для решения ряда прикладных задач.

На сегодняшний день по всеобщему признанию наиболее мощным и перспективным методом решения задач дискретной оптимизации является метод ветвей и границ. Первой публикацией по данному методу была работа [123] в I960 г., в которой предлагалась схема метода ветвей и границ применительно к задаче ЦЛП. Однако значительный интерес специалистов этот метод вызвал лишь после появления известной работы Литла, Мурти и др. [124^, где детально описывалось применение метода ветвей и границ к задаче о коммивояжере, а также сообщалось о машинной реализации и успешном решении, задач с количеством до 40 городов.

Под методом ветвей и границ обычно понимается метод последовательного разбиения множества допустимых решений на подмножества, имеющий древовидную структуру поиска решения и использующий в процессе поиска результаты решения оценочных (релаксиро-ванных) задач на подмножествах. Детальное описание формальной схемы метода ветвей и границ содержится, например, в [52,54,110, III] . Эта схема содержит четыре основных элемента:

1. Выбор подзадачи для ветвления.

2. Выбор способа ветвления. , | 3. Выбор метода построения оценочных подзадач.

4. Выбор метода решения оценочных подзадач.

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

Эффективность алгоритма существенным образом зависит от способа реализации указанных выше основных элементов (см.,например, [52]).

Высокая вычислительная эффективность метода ветвей и границ подтверждена многочисленными эксперементами и решением большого количества прикладных задач. Почти все наиболее мощные коммерческие пакеты программ по решению задачи ЦДЛ (ЛП АСУ, М1Р/370,АРЕХ Ш и 1У и др.) реализованы на базе метода ветвей и границ.

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

При проверке вычислительной эффективности новых точных и приближенных методов, при сравнении различных методов между собой становится необходимым иметь возможность сгенерировать серии случайных задач ЦЛЛ, исходные данные которых в случае необходимости можно было бы получать повторно. К сожалению, публикации о формировании тестовых задач немногочисленны. При проведении вычислительных эксперементов, результаты которых изложены в работе, для генерации тестовых задач в основном использовались генераторы тестовых задач из [77] и формулы вычисления случайных коэффициентов ЦЛП из [17]. Отметим интересную работу [104] , где изложены предварительные результаты попытки создать генератор тестовых задач бинарного программирования с заданными значениями параметров, определяющих, по мнению авторов, сложность решения этих задач.

В [20] предложен новый подход к проблеме построения тестовых задач дискретного программирования, основанный на использовании аппарата функции Лагранжа. Основная идея этого подхода заключается в сле,пующем. Если заданы коэффициенты ограничений -и целевой функции - с^, то каждому неотрицательному вектор - множителю Лагранжа соответствует функция Лагранжа. Максимум последней функции по прямым неизвестным при условии ихцелочисленности определяет некоторый вектор X* который является оптимальным решением задачи (I) - (4), если правые части положить равными Z, Xj, Эта задача и принимается за тестовую.

Опыт решения больших прикладных задач ЦЛП показывает наличие многих избыточностей в формулировке этих задач, которые не всегда могут быть замечены постановщиком задачи - как правило не являющегося специалистом по математическому программированию. Поэтому не удивительно, что успехи, достигнутые при применении коммерческих программ для решения прикладных задач, обычно связаны с предварительным анализом задач и видоизменением модели (с возможным участием пользователя)[106,109,128,131] . Многие из приемов предварительного анализа довольно прозрачны, вычислительно не трудоемки и обычно не требуют вычисления различных оценок с применением аппарата ЛП.' С другой стороны имеет смысл применить различные критерии для уменьшения размерности задачи с вычислением . оценок и привлечением аппарата ЛП. (Одна такая схема уменьшения размерности задачи бинарного программирования описана и исследуется в гл.1 настоящей работы). Такой вторичный анализ требует больших вычислительных усилий, чем предварительный анализ, но дает лучшие результаты по сокращению размерности задачи.

С учетом всего вышеизложенного, по нашему мнению, в настояг щее время наиболее перспективным можно считать следующую общую схему системы решения задачи ЦЛП:

Этап I

Этап 2

Препроцессирование задачи (Предварительный анализ и видоизменение модели)

Вторичный анализ (Применение более сильных критериев для уменьшения размерности задачи)

В связи с этим целью исследования в настоящей диссертационной работе является:

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

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

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

- реализовать все основные предложенные алгоритмы в виде комплексов программ и провести вычислительные эксперименты.

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

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

В § I.I дан краткий обзор основных способов уменьшения размерности задачи ЦДЛ и ЛП. При этом методы, применимые к задачам ЦЛП разделяются на две группы: I) относительно простые способы предварительного анализа и переформулирования задачи (видоизменение модели), не требующие вычисления различных оценок с применением ЛП и 2) методы уменьшения размерности задачи более сложного характера, использующие значения оценок, вычисленных с помощью аппарата ЛП.

В § 1.2 сформулированы два основных критерия, применяемые для установления оптимальных значений части переменных и устранения избыточных ограничений, в следующих обозначениях. Пусть х*=(х*,.\»х£)- оптимальное решение задачи (I)-(4) ( о(-= i, j»l,K>) И f*= PCX") ; , F - нижняя оценка Г , причем 3 х , f = F С х) и

X - допустимое решение;

F ( Х-. = ) - верхняя оценка оптимума задачи, полученной из ис1 ходной добавлением условия = 9 где ос=0 или 1; { X = ( X, ,., Хи/) 1 gL(x) 4 , \ {-к}, 4,

Критерий I. Если

F(x.=oO < £ , С*) то Х*= 1-оС , где о1-0 или 1, je j \}%t.} . Критерий 2. Если

Угьож окСх) < ? хел*

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

В §1.3 приведено пошаговое описание основного алгоритма уменьшения размерности задачи бинарного программирования (алгоритм ПУРЗ). Предложены некоторые уточнения процесса проверки условия (*) при использовании аппарата ЛП для вычисления FCx^oC). а

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

Детальному описанию схемы вычислительной реализации всех основных процедурных частей алгоритма ПУРЗ посвящен следующий §1.4.

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

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

Результаты вычислительных экспериментов, проведенных с алгорит-юм ПУРЗ, изложены в § 1.5.

Эффективность алгоритма ПУРЗ в значительной степени зависит т качества периодически вычисляемых верхних и нижних оценок -f = и £ , от их близости к своим, соответственно, нижним верхним пределам. Вопросам вычисления эффективных нижних и верх-их оценок посвящены, соответственно, главы 2 и 3.

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

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

В § 2.2 с единой точки зрения описаны общие алгоритмы метода последовательного назначения единиц (алгоритм ПОСНВД) и двойственного двухэтапного метода последовательного назначения нулей (алгоритм ПОСНУЛ), имеющих эвристический характер и предназначенных для построения приближенного решения задачи бинарного программирования с неотрицательными коэффициентами- многомерной задачи о ранце. Оценена трудоемкость этих алгоритмов, выявлены некоторые их свойства. Предложен новый алгоритм - П0СНУЛ1 - последовательного назначения нулей, вычислена его трудоемкость. Сравнены трудоемкости алгоритмов ПОСНВД и ПОСНУЛ (на примере конкретных их вариантов) в зависимости от количества единиц в построенных приближенных решениях.

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

В § 2.4 алгоритмы ПОСНВД и ПОСНУЛ обобщены на случай многомерной задачи о ранце с ограниченными переменными и на случай задачи с ограничениями группового выбора. Также описаны способы обобщения и применения к этим задачам тех подходов, которые были рассмотрены в § 2.3.

Три конкретные реализации алгоритма ПОСНВД и алгоритм П0СНУЛ1: а также два метода улучшения допустимого решения реализованы в составе ППП РАНЕЦ-I для приближенного решения многомерной задачи о ранце. О назначении и структуре этого пакета сообщается в § 2.5.

Результаты обширного вычислительного эксперемента, проведенного, в основном, с использованием ППП РАНЕЦ-I, нашли свое отражение в § 2.6.

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

В § 3.1 приведен обзор некоторых результатов, имеющихся в целочисленном линейном программировании, которые могут быть использованы для получения верхних оценок оптимума, в т.ч. лучших, чем решение релаксированной задачи. В конце раздела сформулированы два новых результата, один из которых связан с уменьшением коэффициентов линейного неравенства с переменными 0 и I (что приводит к усилению этого неравенства), а второй - с вычислением верхних оценок оптимума, строго лучших, чем оптимум непрерывной релаксации, посредством решения некоторого конечного числа задач ЛП.

В первой части § 3.2 пояснена идея метода обхода вершин многогранника ограничений (МО) задачи бинарного программирования,заключающейся в целенаправленном просмотре части вершин МО, начиная с вершины Xм , двигаясь по вершинам в направлении убывания -Р(х) и останавливаясь при достижении первой же целочисленной вершины -оптимального решения X . Далее описан основной алгоритм метода -алгоритм ОБХОД и доказана теорема о правильности алгоритма и конечности поиска. Как основное приложение изложено получение верхней оценки оптимума с применением аппарата алгоритма ОБХОД. Рассмотрены другие возможные применения этого алгоритма.

Решению всех задач, связанных с вычислительной реализацией отдельных шагов алгоритма ОБХОД, посвящен § 3.3. Здесь в виде отдельных детальных алгоритмов изложены основные процедуры алгоритма ОБХОД.

Результаты вычислительного эксперимента с алгоритмом ОБХОД приводятся в § 3.4. Вычисления проводились по генерируемым тестовым задачам как по решению задач, так и по вычислению верхних оценок оптимума.

В заключении кратко изложены основные результаты исследования.

В приложения к работе включены: описание языка изложения алгоритмов, систематически используемого в работе; описание комплексов программ, реализующих алгоритмы ПУРЗ и ОБХОД; акты и справки о внедрении и использовании программ.

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

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

Описанные в диссертации алгоритмы и составленные на их основе программы нашли разнообразные приложения.

1. Программа решения задачи квадратичного программирования (КП) практической версией метода Била, которая входит составной частью в комплекс программ для решения задачи бинарного программирования с применением эквивалентных гиперсфер(§ 2.1), принята в ГосШ СССР (Программа № П003856).

2. Пакет прикладных программ РАНЕЦ-1 (§ 2.5), предназначенный для приближенного решения многомерной задачи о ранце принят в ГосШ1 (Программа № 007833).

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

- В РИВЦ Минздрава Азерб.ССР для решения задачи "Расчет индивидуализированной инфузионной терапии" в АСУ Центром реанимации в Республиканской клинической больнице;

- На Бакинском заводе бытовых кондиционеров для решения различных оптимизационных задач;

- В КИВЦ ВПО "Каспморнефтегазпром" для решения задач: "Определение максимального отбора нефти с месторождения и распределения дебитов скважин с учетом обводненности продукции при заданной суммарной закачке воды" и "Определение минимальной закачки воды и распределение дебитов по нагнетательным эксплуатационным скважинам при заданном планируемом объеме добычи нефти";

- В тресте Геокчаймелиоводстрой для оптимального выбора перечня строительных работ на очередной плановый период при наличии ограниченных материальных и трудовых ресурсов. Годовой экономический эффект от внедрения составил 27 тыс.рублей.

Применение результатов подтверждено соответствующими актами и справками.

Основное содержание диссертационной работы освещено в работах [3,5,6,7,8,9,10,11,12,19] .

Результаты, нашедшие отражение в диссертации, докладывались на конференции молодых ученых Института кибернетики АН Азерб.ССР (Баку, 1979г.), на У1 и УП Всесоюзных симпозиумах по системам программного обеспечения решения задач оптимального планирования (Пу-щино, 1980г.; Нарва-Йыэссу, 1982г.), на Всесоюзной школе-семинаре по математическим методам оптимизации и их приложениям в больших экономических и технических системах (Баку, 1980г.), на У совместных расширенных заседаниях научно-исследовательских семинаров Южного научного центра АН УССР и Кишиневского ГУ по дискретной математике, графам, гиперграфам и алгебраическим системам (Одесса, 1981г), на I Республиканской конференции молодых ученых по прикладной математике и кибернетике (Баку, 1981г.), на 1У Республиканской конференции молодых ученых по математике и механике (Баку, 1982г.),а также в течение ряда лет на различных семинарах в Институте кибернетики АН Азерб.ССР.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Ахмедов, Фирудун Беюкага оглы

ЗАКЛЮЧЕНИЕ

В диссертационной работе получены следующие основные результаты:

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

2. Все подалгоритмы алгоритма ПУРЗ доведены до машинных программ. Комплекс этих программ оформлен в соответствии с общей схемой и является реализацией алгоритма ПУРЗ.

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

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

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

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

6. Разработана и обоснована серия алгоритмов построения и улучшения приближенного решения для двух классов задач ЦЛП: многомерной задачи о ранце с ограниченными переменными и многомерной задаче о ранце с ограничениями группового выбора. Все эти алгоритмы являются обобщениями упомянутых выше соответствующих алгоритмов, разработанных для многомерной задачи о ранце с булевыми переменными.

7. Разработан пакет прикладных программ РАНЕЦ-I для приближенного решения многомерной задачи о ранце. В пакет включены как известные, так и предложенные в настоящей работе методы построения и улучшения приближенных решений. Модульный принцип пакета, а также наличие в нем двух генераторов тестовых задач позволяет использовать его также для изучения эффективности новых методов приближенного решения типа последовательного назначения. Проведен обширный вычислительный эксперимент с использованием ППП РАНЕЦ-I, а также некоторых других программ, разработанных автором. Эксперимент показал высокую эффективность предложенных методов приближенного решения.

8. Получен новый результат, связанный с уменьшением коэффициентов линейного неравенства с переменными 0 и I. Предложен один способ вычисления верхних оценок оптимума, строго лучших, чем оптимум непрерывной релаксации, посредством решения некоторого конечного числа задач ЛП.

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

9. Программа решения задачи квадратичного программирования практической версией метода Била, являющаяся составной частью комплекса программ для решения задачи бинарного программирования с применением эквивалентных гиперсфер (§ 2.1), а также ППП РАНЕЦ-1 (§ 2.5) приняты в Государственный фонд алгоритмов и программ СССР (№№ П003856, П007833). Программы, составленные автором на основе разработанных в диссертации алгоритмов точного и приближенного решения задачи ЦЛП внедрены в некоторых организациях и используются в течении нескольких лет для решения различных практических оптимизационных задач, что подтверждено соответствующими актами и справками.

Список литературы диссертационного исследования кандидат физико-математических наук Ахмедов, Фирудун Беюкага оглы, 1985 год

1. Алиев А.А. Новый подход к решению задачи целочисленного программирования.- Изв.АН Азерб.ССР, сер.физ.-техн. и мат.наук, 1930, № 1. с.140-146.

2. Алиев А.А. Алгоритм приближенного решения задачи булева программирования.- Изв.АН Азерб.ССР, сер.физ.-техн. и мат.наук,1982,2, C.III-II6.

3. Алиев А.А., Ахмедов Ф.Б. Пакет прикладных программ "РАНЕЦ-I", для приближенного решения многомерной задачи о ранце.-В кн.: Системы программного обеспечения решения задач оптимального планирования. УП Всесоюзный симпозиум. М.: ЦЭМИ АН СССР, 1932, с.57.

4. Артеменко В.И. Геометрический подход к поиску начальных приближений задачи целочисленного линейного программирования.-В кн.: Структура и организация пакетов программ.- Киев: 1973, с.50-62.-(Препринт/АН УССР. Ин-т кибернетики).

5. Ахмедов Ф.Б. Комбинированный метод решения задачи булева программирования.- Труды молодых ученых Института кибернетики АН Азерб.ССР.- Баку: 1978.- Деп.ВИНИТИ № 3121-79, с.25-28.

6. Ахмедов Ф.Б. Нахождение локального минимума квадратичной функции при линейных ограничениях практической версией метода Била.- Инф.бюлл.ГосФАП СССР "Алгоритмы и программы", П003856, 1979, № 6, с.23.

7. Ахмедов Ф.Б. Метод последовательного назначения нулей для приближенного решения многомерной задачи о ранце.- В кн.: Системы программного обеспечения решения задач оптимального планирования. У1 Всесоюзный симпозиум.-М.: ЦЭМИ АН СССР,1980, с.16-17.

8. Ахмедов Ф.Б. Применение отсечений для уменьшения размерности задачи булева программирования.- В кн.: Математические ме•годы оптимизации их приложения в больших экономических и технических системах,- М.: ЦЭМИ АН СССР, 1930, с.30-32.

9. Ахмедов Ф.Б. Об одном применении эквивалентных гиперсфер к решению задачи булева программирования.- В кн.: Математическая кибернетика и прикладная математика, вып.5, Баку: Элм,1981,с.З-7.

10. Ахмедов Ф.Б. Обход вершин многогранника ограничений задачи бинарного программирования.- В кн.: Материалы I республиканской конференции молодых ученых по прикладной математике и кибернетике.- Баку: Элм, 1932, с.14.

11. Ахмедов Ф.Б. Обход вершин многогранника ограничений в задаче бинарного программирования.- Изв.АН Азерб.ССР,сер.физ.-техн. и мат.наук, 1933, № 2, с.118-123.

12. Ахо А., Хопкрофт Дж., Ульман Дк. Построение и анализ вычислительных алгоритмов.- М.: Мир, 1979,- 536с.

13. Ашманов С.А. Линейное программирование.- М.: Наука, 1931.- 340с.

14. Бабаев Дж.А. Метод гиперсфер для решения задач дискретного программирования.- ДАН СССР,1975, т.221, №5, с.1009-1013.

15. Бабаев Дж.А. Метод гиперсфер для решения задач булева программирования.- ЖВМ и МФ, 1976, 16, № 6, с.1414-1426.

16. Бабаев Дж.А., Мамедов К.Ш., Мехтиев М.Г. Методы построения субоптимальных решений многомерной задачи о ранце.- ЖВМ и МФ, 1973, 18, № б, с.1443-1453.

17. Бабаев Дж.А., Велиев Г.П., Мамедов К.Ш. Априорное определение оптимальных значений неизвестных в задачах дискретногопрограммирования.- IBM и МФ, 1979, 19, № 2, с.519-523.

18. Бабаев Дж.А., Ахмедов Ф.Б., Алиев А.А. Пакет прикладных программ "РАНЩ-1" для приближенного решения многомерной задачи о ранце.- Инф.бюлл.ГосФАП СССР "Алгоритмы и программы", П007833, 1985, № I, с.50.

19. Бабаев Р.Д. Построение тестовых задач целочисленного программирования с бинарными неизвестными.- ЖВМ и МФ, 1935, № I,с.152-156.

20. Беленький В.З., Волконский В.А., Иванков С.А. и др. Итеративные методы в теории игр и программировании.-М.: Наука,1974,-239с.

21. Беллман Р. Динамическое программирование.- М.: Изд-во иностр.лит., I960.- 400с.

22. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования.- М.: Наука, 1965.- 455с.

23. Бузыцкий П.Л., Фрейман Г.А. Аналитические методы в целочисленном программировании.- М.: 1930.- 53с.- (Препринт/АН СССР. ЦЭМИ).

24. Бузыцкий П.Л., Фрейман Г.А. 0 применении аналитических методов в комбинаторных задачах.- Изв.АН СССР. Техническая кибернетика, 1980, № 2, с.41-48.

25. Бурова Н.К., Станевичене Л.И., Станевичюс А.-И.А., Шкляр П.Э. Система линейного программирования ЛП/БЭСМ-6.- Сообщ.по программному обеспечению ЭВМ.- М.: ВЦ АН СССР, 1981, 126с.

26. Бушный А.Г. Один метод решения задач линейного целочисленного программирования.- Кибернетика, 1931, № 5, с.78-81.

27. Быков В.Н. 0 повышении эффективности методов локальной оптимизации для некоторых классов задач целочисленного программирования.- ДАН УССР, 1978, № I, с.60-62.

28. Быков В.Н., Сергиенко И.В. Один метод приближенного решения задач дискретного программирования.- Кибернетика, 1978, № 3, с.75-80.

29. Быков В.Н., Сергиенко И.В. Один метод поиска допустимого решения в задачах целочисленного программирования.- В кн.: Структура и организация пакетов программ.- Киев: 1978, с.26-33 (Препринт/АН УССР Ин-т кибернетики).

30. Велиев Г.П. Метод построения приближенного решения многомерной задачи о ранце, допускающий оценку отклонения от оптимума.-Изв.АН Азерб.ССР, сер.физ.-техн. и мат.наук,1980, № 2, с.122-126.

31. Велиев Г.П., Мамедов К.Ш. Метод решения задачи о ранце.-ЖВМ и МФ, 1981, № 3, с.605-611.

32. Вотяков А.А. Целочисленное программирование, сравнение отсечений.- Экономика и мат.методы, 1972, 8, вып.1, е.107-116.

33. Габасов Р., Кириллова Ф.М., Тятюшкин А.И. Конструктивные методы оптимизации. 4.1: Линейные задачи.- Минск: Университетское, 1984.- 214с.

34. Гене Г.В., Левнер Е.В. Дискретные оптимизационные задачи и эффективные приближенные алгоритмы. Обзор.- Изв.АН СССР. Техническая кибернетика, 1979, № 6, с.84-92.

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

36. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов.- М.: Мир, 1981.- 368с.

37. Данциг Дж. Линейное программирование, его обобщения и применения.- М.: Прогресс, 1966.- 600с.

38. Емеличев В.А. Вогнутое программирование с сепарабельной функцией цели при линейных ограничениях.- Изв.АН БССР, сер.физ.-мат.наук, 1969, № 6, с.25-28.

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

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

41. Емеличев В.А., Пирьянович В.А. Об одном методе построения субоптимального плана задачи целочисленного линейного программирования.- В кн.: Вопросы мат.обеспечения в автоматизированных системах.- Минск: 1979, с.4-9.

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

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

44. Журавлев Ю.И., Финкельштейн Ю.Ю. Локальные алгоритмы для задач линейного целочисленного программирования.- В кн.: Проблемы кибернетики.- М.: Наука, 1965, вып.14, с.289-295.

45. Журавлев Ю.И. Об алгоритмическом подходе к решению задач распознавания и классификации.- В кн.: Проблемы кибернетики.- М.: Наука, 1978, вып.33, с.5-68.

46. Иослович И.В., Макаренков Ю.М. 0 методах сокращения размерности задач линейного программирования.- Экономика и мат.методы, 1975, II, № з, с.516-524.

47. Казакова М.Ф. Метод типа ветвей и границ для обобщенной задачи о ранце.- Экономика и мат.методы, 1971, 7, вып.5,с.737-741.

48. Ковалев М.М. Дискретная оптимизация (целочисленное программирование).- Минск: Изд.БГУ им.В.И.Ленина, 1977.- 192с.

49. Ковалев М.М., Пирьянович В.А. Локально-стохастические алгоритмы в дискретной оптимизации.- Кибернетика, 1981, № 6,с.100-104

50. Корбут А.А., Сигал И.Х., Финкельштейн В.Ю. Метод ветвей и границ,- Math» Operationsforsch. Statist. Ser. Optimization, 1977, 8, N2, с.255-280,

51. Корбут А.А., Сигал И.Х., Финкельштейн Ю.Ю. Об эффективности комбинаторных методов в дискретном программировании.- В кн.: Современное состояние теории исследования операций.- М.: 1979,с.283-310.

52. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование.- М.: Наука, 1969.- 363с.

53. Корбут А.А., Финкелыптейн Ю.Ю. Приближенные методы дискретного программирования.- Изв.АН СССР. Техническая кибернетика,1983, № I, с.165-177.

54. Коробкин А.Д., Михайленко Ю.М. Методы нейтрализации пассивных компонент в задачах целочисленного программирования.- В кн.: Применение ЭВМ в оптимальном планировании и управлении. НГУ, Новосибирск, 1976, с.3-10.

55. Курош А.Г. Курс высшей алгебры.- 335с.

56. Лебедев С.С. Целочисленное программирование и множители Лагранжа.- Экономика и мат.методы, 1974, т.Х, вып.З, с.592-610.

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

58. Левнер Е.В., Гене Г.В. Дискретные оптимизационные задачи и эффективные приближенные алгоритмы.- М.: 1978.- 55с. (Препринт/АН СССР. ЦЭМИ).

59. Мамедов К.Ш. Эвристические методы и система последовательного улучшения решений в дискретных задачах принятия решений.

60. В кн.: Проектирование и оптимизация элементов, устройств и системлетательных аппаратов с использованием ЭВМ.- Харьков, 1977,с.388-393.

61. Мамедов К.Ш. Двусторонняя оценка оптимального значения целевой функции в задачах бинарного программирования.- В кн.: Вопросы математической кибернетики и прикладной математики.- Баку, Элм, 1973, с.17-22.

62. Михайленко Ю.М., Коробкин А.Д. О редукции задач целочисленного программирования в алгоритмах ветвей и границ.- В кн.: Применение ЭВМ в оптимальном планировании и управлении. Вып.2 -Новосибирск: 1977, с.3-16.

63. Михалевич B.C., Шор Н.З. Численные решения многовариантных задач по методу последовательного анализа вариантов.- В кн.: Научно-методические материалы экономико-математического семинара, М.: ЛЭММ АН СССР, 1962, вып.1, сЛ5-42.

64. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. 1,П Кибернетика, 1965, № I, с.3-7; № 2, с.5-10.

65. Михалевич B.C., Сергиенко И.В., Шор Н.З. Исследование методов решения оптимизационных задач и их приложения.- Кибернетика, 1931, № 4, с.39-113.

66. Михалевич B.C., Сергиенко И.В., Шор Н.З. и др. Пакет прикладных программ ДИСПРО, предназначенный для решения задач дискретного программирования.-Кибернетика, 1931, № 3, с.117-137.

67. Михалевич B.C., Волкович В.Л. Вычислительные методы исследования и проектирования сложных систем.- М.: Наука, 1982.-286с.

68. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации.- М.: Наука, 1983,- 208с.

69. Муртаф Б. Современное линейное программирование.- М.: Мир, 1984.- 224с.

70. Никитин А.И., Нуриев У.Г. К задаче распределения резервирующих файлов в узлах сети.- В кн.: Тезисы докладов Всесоюзнойконференции "Программное обеспечение вычислительных сетей и систем реального времени", Киев, 1981.- с.117-118.

71. Нуриев У.Г. Гибридный метод решения многомерной задачи о ранце.- Киев: Ж АН УССР, 1933.- 23с.(Препринт/АН УССР, Ин-т кибернетики; № 83-43).

72. Павлечко В.А. Решение задачи целочисленного линейного программирования с булевыми переменными методом построения последовательности планов.- В кн.: Математическое обеспечение ЭВМ "Минск-32" -Минск: 1973, вып.8, с.99-103.

73. Пакет прикладных программ "Линейное программирование в АСУ" (ППП ЛП АСУ) на базе ОС ЕС.- Калинин, Центрпрограммсистем, 1977.

74. Пирьянович В.А. Локально-стохастические алгоритмы решения задач целочисленного линейного программирования.- Редколлегия журн."Известия АН БССР", сер.физ.-матем.наук, № 4, 1977, Деп. в ВИНИТИ № 1090-77 от 22.03.1977.

75. Пирьянович В.А. Машинные эксперименты по решению задач целочисленного линейного программирования с помощью локально-сто-хатических алгоритмов ЖВМ и МФ, 1979, 19, № I, с.79-87.

76. Пирьянович В.А. Генераторы тестовых задач целочисленного линейного программирования.- Редколлегия журн."Известия БГУ им. В.И.Ленина", cep.I, 1979, Деп.в ВИНИТИ № 1662-73 от 23.05.1978.

77. Программное обеспечение ЭВМ. Вып.43. Пакет научных программ. руководство для программиста. Адаптивная оптимизация. (Алгоритмы и программы). Под ред.Габасова Р., Кирилловой Ф.М.,Сенько А.А. Минск, 1933.- 239с.

78. Растригин Л.А. Статистические методы поиска.- М.: Наука, 1968.- 376с.

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

80. Романовский И.В. Алгоритмы решения экстремальных задач.-М.: Наука, 1977.- 352с.

81. Романовский И.В., Станевичюс А.-И.А. Программное обеспечение симплекс метода для задач большой размерности.- В кн.: Современное состояние теории исследования операций. М.: Наука, 1979,с.451-464.

82. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации.- Киев: Наукова думка, 1985.- 384с.

83. Сергиенко И.В., Парасюк И.Н., Тукалевская Н.И. Автоматизированные системы обработки данных.- Киев: Наукова думка, 1978.-256с.

84. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных задач оптимизации.- Киев: Наукова думка, 1930.- 273с.

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

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

87. Финкелыптейн Ю.Ю. Метод отсечения и ветвления для решения задач целочисленного линейного программирования.- Известия АН СССР, Техн.кибернетика, 1971, № 4, с.34-38.

88. Финкелыптейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования.- М.: Наука, 1976.- 264с.

89. Хачатуров В.Р. Аппроксимационно-комбинаторный метод и некоторые его приложения.- ЖВМ и МФ, 1974, 14, № 6, с.1464-1484.

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

91. Червак Ю.Ю. Об одном усиленном варианте алгоритма Гомори.-Экономика и мат.методы, 1977, 13, вып.2, с.391-394.

92. Черенин В.П. Решение некоторых комбинаторных задач оптимального планирования методом последовательных расчетов.- В кн.: Материалы конф. по опыту и перспективам применения мат.методови ЭВМ.- Новосибирск: СО АН СССР, 1962, с.41-54.

93. Юдин Д.Б., Голыптейн Е.Г. Линейное программирование. Теория, методы и проложения.- М.: Наука, 1969.- 424с.

94. Юдин Д.Б., Горяшко А.П., Немировский А.С. Математические методы оптимизации устройств и алгоритмов АСУ.- М.: Радио и связь, 1982.- 288с.

95. Balas Е. An additive algorithm for solving linear programs with zero-one variables. Oper.Res,, 1965» 13» No.4,p.517-546.

96. Balas E. The intersection cut a new cutting plane for integer programming. - Oper.Res., 1971, 19, No.1, p.19-39.98*Balas E., Zemel E. An algorithm for large zero-one knapsack problems. Oper.Res., 1980, 28, No.5, p.1130-1154.

97. Beale C.M.L. Numerical methods. In "Nonlinear programming" (J.Abadie, ed.), North-Holland Publishing Co., Amsterdam, 1967, p.133-205.

98. Beged-Dov A.G. Lower and upper bounds for the number of lattice points in a simplex. SIAM J.Appl.Math., 1972, 22, No.1, p.106-108.

99. Bowman V.J., Nemhauser G.L. Deep cuts in Integer programming. Oper.Res., 1971, 8, No.1, p.89-111.

100. Bradley G.H., Hammer P.L., Wolsey L.A. Coefficient reduction for inequalities in 0-1 variables. Math.Progr., 1974, 7, p.263-282.

101. Glover F. Heuristic for Integer programming using surrogate constraints. Decision Sciences, 1977, 8, No.1, p.156-166.

102. Glover F. Some fresh, heuristic principles for integer programming. Management Science / Information Science Report Series. Report No.77-7.

103. Gomory R.E. Outline of an algorithm for integer solution to linear programs, Bull.Amer.Math.Soc., 1958, 64, N0.5,p. 275-278.117* Guignard M., Spielberg K. Logical reduction methods in zero-one programming. Oper.Res., 1981, 29, No.1, p.49-74.

104. Hillier F.S. Efficient heuristic procedures for integer linear programming with an interior. Oper.Res., 1969, 17,p.600-637.

105. Hofstedt K., Thamelt W. Uber einen algorithmus zur losung gemischt-ganzzahlier optimalprobleme. Math.Operationforschung ind Statist, 1971, 2, N0.3, p.199-212.

106. Ingargiola G.P., Korsh G.F. A reduction algorithm for zero-one single knapsack problems. Manag.Sci., 1973, 20, No.4, p.460-463.

107. Kianfar F. Stronger inequalities for 0,1 integer programming using knapsack functions. Oper.Res., 1971, 19,p.1373-1392.

108. Kianfar F. Stronger inequalities for 0,1 integer programming! computational refinements. Oper.Res., 1976, 24, N0.3, p.581-585.

109. Land A.H., Doig A.G. An automatic method of solving discrete programming problems. Econometrica, 1960, 28, N0.3,э. 497-520.

110. Little J., Murty K., Sweeney D., Karel 0. An algorithm for the traveling salesman problem. Oper.Res., 1963, 11» No.6, p.972-989.

111. Lou.lou R., Michaelid.es E. New greed-y-like heuristics for the multidimensional 0-1 knapsack problem.- Oper.Res., 1979, 27, No.6, p.1101-1114.

112. Martello S., Toth P. An upper bound for the zero-one knapsack problem and branch and bound algorithm. Eur.J.of Oper.Res., 1977, 1, p.169-175.

113. Martello S., Toth P. The 0-1 knapsack problem. -Comb.Optimiz.Lect.Summer Sch., Urbano, 1977.- Chichester e.a., 1979, p.237-279.

114. Oley L.A., Sjoquist R.J. Automatic reformulation of mixed and pure integer models to reduce solution time in APEX IV.- SIGMAP bulletin, No.32, April 1983, p.40-51.

115. Papadimitriou C.H. On the complexity of integer programming. J.Assos.Comput.Mach., 1981, 28, No.4, p.765-768.

116. Petersen C.C. Computational experience with variants of the Balas algorithm applied to the selection of R & D projects. Manag.Sci., 1967, 13, N0.9, p.736-750.

117. Powell S. Report of the session on current computer codes. In : Discrete optimization, II.(Ed. P.L.Hammer, E.L. Johnson, B.H.Korte). Annals of Discrete Mathematics, 5. -Amsterdam, North-Holland, 1979, p.279-283.

118. Toyoda Y. A simplified algorithm for obtaining approximate solutions in zero-one programming problems. Manag.Sci., 1975, 21, No.12, p.1417-1427.

119. Walukiewicz S. The size reduction of binary knapsack problem.- Bull.des L'academie Polonaise des Sciences, ser.des sciences techniques, 1975, XXIII, N0.5, p.41-46.

120. Walukiewicz S. An equivalent constraint using an objective function. Bull.des L'academie Polonaise des Sciences, ser.des sciences techniques, 1975, XXIII, N0.5, p.33-39.

121. Weingartner N.M., Ness D.N., Methods for the solution of the multi-dimensional 0-1 knapsack problem. Oper.Res., 1967, 15, No.1, p.83-103.

122. Williams H.P. Experiments in the formulation of integer programming problems. Math.Progr.Study, 1974, 2,p.180-197.

123. Williams H.P. A reduction procedure for linear and integer programming models. Lect.Notes Econ.and Math.Syst., 1983, 206, p.87-107.

124. Wyman p.P. Binary programming : A decision rule for selecting optimal vs.heuristic techniques. Oomp.J., 1973, 16, p.135-140.

125. Young R.D. A primal (all integer) integer programming algorithm. J.Res.Nat.Bur.Standarts, 1965, В 69, No.3,p.213-250.

126. Young R.D. Hypercylindrically deduced cuts in zeroone integer programming. Oper.Res., 1971, 19, No.1, p.1393-1405.