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

• Федорин, Андрей Николаевич
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Федорин, Андрей Николаевич

ВВЕДЕНИЕ.

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

1.1. Классическая задача о ранце и алгоритмы поиска точного решения.

1.2. Многомерная задача о ранце.

1.3. Алгоритмы синтеза Парето-оптимальных решений для многокритериальной задачи о ранце на основе принципа динамического программирования.

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

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

2.1. Концепция оператора, строящего представительную совокупность. Понятие консервативного оператора.

2.2. Алгоритм синтеза совокупностей эффективных оценок, удовлетворяющих пороговым ограничениям.'.

2.3. Синтез ^-разреженных совокупностей эффективных оценок.

2.4. Алгоритмы построения совокупностей эффективных оценок получаемых применениями типовых схем компромисса при варьируемых параметрах этих схем.

2.4.1. Метод последовательных уступок.

2.4.2. Линейная свертка критериев.

2.4.3. Метод главного критерия.

2.4.4. Метод идеальной точки.

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

ГЛАВА 3. ПОДХОДЫ К УСКОРЕНИЮ СЧЕТА ПРИ ПОИСКЕ РЕШЕНИЙ МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ О РАНЦЕ.

3.1. б- эффективные оценки. Синтез совокупностей б- эффективных оценок методом ветвей и границ.

3.2. Применение эволюционно-генетических алгоритмов для получения эвристических решений.

3.3. Комбинированные алгоритмы решения задач о ранце.

3.4. Некоторые вопросы эффективности программной реализации сложных вычислительных алгоритмов.

ГЛАВА 4. НЕКОТОРЫЕ МОДИФИКАЦИИ ЗАДАЧИ О РАНЦЕ И МЕТОДЫ ИХ РЕШЕНИЯ.

4.1. Задача о ранце с аддитивным и точечным критериями.

4.1.1. Математическая постановка задачи и алгоритмы ее точного решения.

4.1.2. Эволюционно-генетический алгоритм решения задачи.

4.2. Задачи с несколькими ранцами.

4.2.1. Математические постановки задач с несколькими ранцами и алгоритмы их точного решения.

4.3.2. Эволюционно-генетические алгоритмы решения задач.

ГЛАВА 5. ОБ ОДНОЙ ЗАДАЧЕ ВЫБОРА ОГРАНИЧЕННОГО ПРЕДСТАВИТЕЛЬНОГО ПОДМНОЖЕСТВА ОБЪЕКТОВ.

5.1. Математическая модель задачи и ее интерпретация. Алгоритм поиска точного решения.

5.2. Эвристические алгоритмы поиска решения.

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

Классическая задача о ранце (КЗР) относится к числу широко известных задач дискретной оптимизации. Данная задача впервые была сформулирована Д. Данцигом в работе [120] и с тех пор активно исследуется. Популярность КЗР вызвана большим количеством ее приложений, поскольку многие из реально возникающих задач описываются в рамках данной модели. Основные сферы применения находятся в областях планирования и управления производственными и транспортными системами. В частности, отметим формулируемые в рамках КЗР задачи объемного планирования.

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

1950 гг. - Постановка КЗР; алгоритм решения, использующий принцип динамического программирования (R. Bellman, G. Dantzig- [16, 17,25, 120]).

1960 гг. — Первый алгоритм решения КЗР, основанный на методе ветвей и границ; совершенствование алгоритмов использующих принцип динамического программирования (G. Dantzig, А.Н. Land и A.G. Doig, P. Gilmore, R. Gomory, P.J. Kolesar- [25, 120, 141]).

1970 гг. — Исследование вычислительной сложности КЗР, доказательство ее NP-трудности, выделение частных полиномиально разрешимых подклассов. Разработка нескольких приближенных методов решения КЗР, имеющих полиномиальные оценки вычислительной сложности. Применение двойственности для повышения эффективности метода ветвей и границ. Изложенные результаты описаны в работах О.Г. Алексеева, В.А. Емеличева, Ю.Ю. Финкельштейна, М. Garey и D. Johnson, O.Ibarra и С. Kim, С. Ра-padimitriou и К. Steiglitz, S. Sahni - [1,24,29,46,47,67, 92-95, 135, 154].

1980 гг. - Выделение новых полиномиально разрешимых подклассов КЗР; доказательство ряда важных свойств; введение понятий «ядро» и «расширяющееся ядро» и построение приближенных схем решения, основанных на этих понятиях. Разработка комбинированных подходов к решению КЗР, сочетающих применение комбинаторных методов (динамическое программирование или метод ветвей и границ) с приближенными и эвристическими алгоритмами. Полученные результаты отражены в публикациях В.А. Емеличева, И.В. Сергиенко, И.Х. Сигала, Е. Balas, T.Hu, S. Martello, D. Pisinger, P. Toth, E. Zemel - [79, 80,98, 108, 147].

1990 гг. - Применение эвристических алгоритмов, нейронных сетей, параллельных алгоритмов, эволюционно-генетического подхода к решению ранцевых задач. Достигнутые результаты изложены А.А. Корбут, И. X. Сигалом, S. Khuri, W. Loots, Z. Michaleviwicz, M. Ohlsson, С. Peterson, D. Pisinger, T.H.C. Smith - [27, 82, 137, 138, 146, 148,150-153].

2000 гг. - Новые оценки трудоемкости метода ветвей и границ; параллельные реализации методов ветвей и границ и динамического программирования; комбинированный параллельный алгоритм решения КЗР. Описанные результаты получены P.M. Колпаковым, М.А. Посыпкиным, И.Х Сигалом [35-38, 74-76].

Начиная с 60-70-х гг. XX века стали рассматриваться различные модификации КЗР. В частности, была изучена КЗР с дробимыми предметами (решающий алгоритм разработан Д. Данцигом [25, 120]) и КЗР в многомерной постановке (см., например [47]). Последняя математическая модель, в отличие от КЗР, позволяет учитывать для каждого из предметов несколько ограничивающих его факторов. Присутствие такой возможности позволяет описать в рамках многомерной КЗР множество прикладных задач, которые было невозможно адекватно выразить в рамках математической постановки КЗР. К примеру, в задачах объемного планирования, когда трудоемкость производственных задач оценивается по видам или группам работ. Таким образом, оценивая трудоемкость вектором, получаем многомерную КЗР. Фонд рабочего времени и ресурсов также представлен вектором.

Одновременно с этим, исследуется КЗР, где требование булевозначности переменных заменено требованием принадлежности их некоторому множеству неотрицательных целых чисел в ограниченном.диапазоне. Вообще говоря, некоторые авторы (см. например [98, 102]) под КЗР понимают задачу с неотрицательными целочисленными переменными. Также встречаются постановки КЗР с нелинейными критериями, в частности Д.И. Батищев и Д.И. Коган в своей работе [7] рассматривают задачу о ранце с се-парабельным критерием.

Последнее десятилетие значительное внимание уделяется ранцевым задачам в многокритериальных постановках. Данное обстоятельство вызвано стремлением более адекватно описать возникающие на практике ситуации. Зачастую многие реальные задачи оценивают принимаемое решение по нескольким показателям, а критерии, по которым оценивается решение, не всегда выражаются аддитивными функциями. Можно утверждать, что все задачи, реально возникающие в экономических системах по сути своей многокритериальны. Это объективно связано с тем, что в каждой экономической системе имеется ряд участников, каждый из которых по-своему оценивает качество принимаемых решений. Кроме того, некоторые участники могут оценивать принимаемые решения по нескольким показателям. Задачей о ранце в многокритериальной постановке занимаются Д.И. Батищев, В.А. Емеличев, А.П. Иванова, Д.И. Коган, М.В. Лейкин, И.И. Меламед, И.Х. Сигал, J.R. Figueira, М.Н. Karwan, K.Klamroth, J. Teghem, L. Thiele, E.L. Ulungu, B. Villarreal, M. Wiecek, E. Zitzler и др. Основные результаты, полученные данными учеными, представлены в работах [6, 8-12, 14, 15, 30-32, 40, 41, 43, 5159,64,65, 83, 84, 125,139, 160-162,166-168].

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

Известны два регулярных метода решения задач о ранце (в том числе многомерных многокритериальных) - принцип динамического программирования [5, 10, 16, 17, 40, 59, 139, 161] и схема ветвей и границ [43, 47, 82, 141, 160, 162]. Каждый из них допускает несколько реализаций и обладает своими достоинствами и недостатками; вместе с тем, оба они достаточно гибки и универсальны.

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

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

Второй подход базируется на принятии концепции эффективной оценки и Паре-то-оптимального решения [73, 110]. В данном случае, технология решения многокритериальной задачи заключается в построение для нее полной совокупности эффективных оценок с одновременным обеспечением возможности восстановления по любой эффективной оценке Парето-оптимального решения ее порождающего. Данная совокупность позволяет ЛПР составить полное представление о задаче и выбрать любое целесообразное для него решение. С другой стороны, полная совокупность может быть достаточно велика, а ее синтез, как правило, требует больших вычислительных затрат.

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

В жизни, при предъявлении полной совокупности эффективных оценок, ЛПР, как правило, выбирает некоторую его часть, используя собственные дополнительные соображения. Аналогичная идея используется в динамическом программировании при синтезе представительных совокупностей эффективных оценок. Реализована данная идея через концепцию оператора выбора; результативность данного оператора возможна только при условии его консервативности (см. например, [10,40]).

Альтернативный подход решения задач дискретной многокритериальной оптимизации основывается на использовании приближенных алгоритмов решения задачи, основным критерием эффективности которых, служит точность и полнота полученных решений. В настоящее время все большую популярность приобретают эволюционно-генетические алгоритмы (ЭГА) - алгоритмы случайного поиска, имитирующие в своей работе процесс эволюции популяции особей [13,23, 127, 129]. Также, в данный момент, вызывают большой интерес алгоритмы муравьиных колоний [2, 104, 122, 123].

Широкими возможностями по ускорению поиска точного решения задач дискретной оптимизации обладает комбинированный подход. Основная идея данного подхода заключается в комбинировании эвристических и точных алгоритмов решения — эвристические алгоритмы служат для достаточно быстрой генерации предварительных (приближенно-оптимальных) решений; полученные таким образом решения используются для ускорения счета процедур поиска точного решения. Наиболее удачной видится комбинирование эвристических алгоритмов с методом ветвей и границ.

Отдельное направление исследований формируют вопросы эффективной реализации вычислительных алгоритмов на ЭВМ. Конечной стадией разработки любого алгоритма является его программная реализация с целью применения в автоматизированных системах принятия решений. Вычислительная среда (аппаратная архитектура, операционная система, компилятор и т.д.) обладает своими особенностями, что не может не повлиять на работу алгоритма. Так же сюда можно отнести современные технологии параллельной реализации вычислительных алгоритмов на многопроцессорных системах (см., например [19]).

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

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

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

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

В разделе 1.1 приводятся математическая постановка классической задачи о ранце и алгоритмы ее решения, основанные на принципе динамического программирования и на схеме ветвей и границ. В раздел 1.2 излагаются модификации описанных выше алгоритмов в применении к многомерной задаче о ранце. В разделе 1.3 вводится многокритериальная задача о ранце; дан обзор основных подходов к решению задач дискретной многокритериальной оптимизации; приводится описание схем решения многокритериальной задачи о ранце, основанных на многокритериальном аналоге принципа динамического программирования. В разделе 1.4 излагаются общая схема адаптации метода ветвей и границ для решения многокритериальных задач дискретной оптимизации и конкретизация данной схемы в применении к многокритериальной задаче о ранце. Вопросы вычислительной сложности рассматриваются по мере описания алгоритмов. 7

Программная система, решающая бикритериальные задачи о ранце, прошла апробацию во ФГУП «ФНПЦ НИИИС им. Ю.Е. Седакова» при решении задач размещения компонентов интегральных схем, возникающих при проектировании больших интегральных схем на базовых матричных кристаллах с аналоговой частью (имеется акт об использовании).

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

В разделе 2.1 рассматриваются особенности построения представительных подмножеств эффективных оценок методами, реализующими принцип многокритериального динамического программирования. Вводится понятие оператора, строящего представительную совокупность, а также концепция консервативного оператора. Излагается ряд полученных ранее результатов о консервативности и не консервативности некоторых конкретных операторов выбора. Разделы 2.2 - 2.4 посвящены изложению методов синтеза представительных совокупностей эффективных оценок для многокритериальной многомерной задачи о ранце; указанные методы являются модификациями рассмотренного в разделе 1.4 алгоритма ветвей и границ. Уделяется внимание построению представительных совокупностей эффективных оценок в случае, когда это невозможно применением принципа многокритериального динамического программирования (оператор выбора является неконсервативным). Данный факт является несомненным преимуществом схемы ветвей и границ перед принципом динамического программирования.

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

В разделе 3.1 излагаются процедуры адаптации метода ветвей и границ для синтеза приближенных решений многокритериальной задачи о ранце с заданной точностью. Раздел 3.2 посвящен применению эволюционно-генетических алгоритмов для получения эвристических решений. Произведен обзор имеющихся технологий и подходов. Предложены собственные реализации эволюционно-генетических алгоритмов учитывающие специфику задачи и преодолевающие недостатки существующих подходов. Раздел 3.3 содержит описание комбинированных алгоритмов решения задач о ранце. Рассмотрены варианты комбинирования метода ветвей и границ и эволюционно-генетических алгоритмов для ускорения поиска точного решения задач о ранце; дана экспериментальная оценка ускорения от применения данного подхода. В разделе 3.4 рассматриваются некоторые вопросы эффективности программной реализации сложных вычислительных алгоритмов на ЭВМ.

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

В разделе 4.1 вводится математическая постановка задачи о ранце с аддитивным и точечным критериями. Излагаются решающие процедуры поиска точных решений, основанные как на принципе динамического программирования, так и на схеме ветвей и границ. В качестве эвристического алгоритма описывается конкретная реализация ЭГА. Рассматривается прикладная задача оптимальной загрузки судов, адекватно формализуемая в рамках построенной модели. Разработанные алгоритмы и реализованная на их основе программная система используются в ОАО «АЗИМУТ» для решения задач планирования транспортно-технологических процессов на внутреннем водном транспорте (имеется акт о внедрении).

Раздел 4.2 посвящен двум постановкам задачи с несколькими ранцами. Приводятся алгоритмы поиска точных решений. Предлагаемые решающие процедуры основаны на принципе многокритериального динамического программирования (его списковой реализации). Описывается возможность дополнительного использования верхних и нижних оценок для сокращения объема выполняемых вычислений. Рассматриваются основанные на ЭГА эвристические процедуры решения поставленных задач.

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

В разделе 5.1 приводится математическая постановка задачи и одна из ее интерпретация. Излагается адаптация ранее представленного алгоритма решения КЗР для поиска точного решения описанной задачи. Раздел 5.2 посвящен рассмотрению эвристических алгоритмов, реализующих второй подход к решению поставленной задачи. Предложенные алгоритмы основаны на сведении исходной задачи к специальным образом построенной многомерной задаче о ранце и ее решении ранее описанными методами. В качестве альтернативы излагается эволюционно-генетический алгоритм поиска решений. Каждый из представленных алгоритмов программно реализован и прошел тестирование на реальных задачах. В частности, результаты проведенных исследований нашли применение в ЗАО "Бизнес Аналитика", г. Москва. На данном основании имеется акт о внедрении научно-технической разработки.

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

Основные результаты, полученные в ходе работы над диссертацией, изложены в одиннадцати публикациях [42-45, 78, 86-91, 124], в том числе восемь из них в центральной печати [43, 45, 86-91], четыре в материалах и тезисах докладов на международных [44,78, 124] и российских конференциях [42].

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Федорин, Андрей Николаевич

Основные результаты анализа кода и реализованные методы устранения "узких мест" приводятся в таблице 3.4.2.

ЗАКЛЮЧЕНИЕ

Сформулируем основные результаты диссертационной работы:

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

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

3. На основе анализа разнообразных концепций эволюционно-генетических алгоритмов (ЭГА) решения задач многокритериальной оптимизации и, в частности, многокритериальной задачи о ранце, реализованы собственные модели ЭГА, учитывающие специфику задачи и преодолевающие ряд недостатков существующих подходов.

4. Предложены варианты комбинирования метода ветвей и границ и ЭГА для ускорения поиска точных решений задач о ранце с несколькими критериями; даны экспериментальные оценки ускорения, обеспечиваемого реализацией этого подхода.

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Федорин, Андрей Николаевич, 2010 год

1. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. - М.: Наука, 1987.

2. Антамошкин А.Н., Кагиров P.P. Алгоритмы муравьиных колоний для многомерной задачи о рюкзаке // Системы управления и информационные технологии, 2007, №1.2(27), с. 214-218.

3. Архангельский А.Я. Программирование в C++Builder 4. 2-е изд., перераб. и до-полн. -М.: ЗАО «Издательство БИНОМ», 2000 г. - 1088 е.: ил.

4. Бабат Л.Г. Приближенное вычисление линейной функции на вершинах единичного п-мерного куба // в сб. «Исследования по дискретной оптимизации». М.: Наука, 1976, с. 156-169.

5. Батищев Д.И. Методы оптимального проектирования. М.: Радио и связь, 1984.

6. Батищев Д.И., Коган Д.И. Вычислительная сложность экстремальных задач переборного типа. Н.Новгород: Издательство Нижегородского университета, 1994.

7. Батищев Д.И., Коган Д.И. Многокритериальный выбор элементнотехнической базы для покрытия схем // в межвуз. сб. «Автоматизированное проектирование в электронике и приборостроении». Санкт-Петербург: изд-во СПбГЭТУ, 1994, с.26 - 32.

8. Батищев Д. И., Коган Д. И. Метод решения одного класса многокритериальных целочисленных задач сепарабельного программирования. Ассоциация математического программирования. Информационный бюллетень № 5, Екатеринбург, 1995, с. 36.

9. Батищев Д.И., Коган Д.И., Лейкин М.В. Многокритериальные задачи о ранце: эффективные оценки. // в межвуз. сб. «Высокие технологии в технике, медицине, образовании», изд-во Воронежского технического госуниверситета, 2001, с.4 -11.

10. Батищев Д.И., Коган Д.И., Лейкин М.В. Многокритериальные задачи о ранце: метод линейной свертки. // в межвуз. сб. «Прикладные задачи моделирования и оптимизации», изд-во Воронежского технического госуниверситета, 2001, с. 13-22.

11. Батищев Д.И., Коган Д.И., Лейкин М.В. Вопросы синтеза совокупностей эффективных оценок в многокритериальной задаче о ранце Н Математическое моделирование и оптимальное управление: Вестник Нижегородского университета, вып. 1 (25), 2002, с.211-223.

12. Батищев Д.И., Коган Д.И., Лейкин М.В. Алгоритмы синтеза решений для многокритериальной многомерной задачи о ранце // Информационные технологии, №1, 2004, с.18-27.

13. Батищев Д.И., Коган Д.И., Шеянов А.В. Модифицированная многокритериальная задача о ранце и алгоритм ее решения // в межвуз. сб. «Моделирование и оптимизация сложных систем» Волжская Гос.академия водного транспорта, вып. 273 (часть 2), 1998, с. 125-132.

14. Батищев Д.И., Неймарк Е.А., Старостин Н.В. Применение генетических алгоритмов к решению задач дискретной оптимизации: Учебное пособие.-Нижний Нов1415,16