Методы и алгоритмы решения задач дискретной оптимизации при построении АСУ широкого назначения тема диссертации и автореферата по ВАК РФ 05.13.06, кандидат наук Си Ту Тант Син

• Си Ту Тант Син
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Си Ту Тант Син

Введение

Глава 1. Применение задач дискретной оптимизации в АСУ

1.1 Двухэтапная задача раскроя двумерного материала

1.1.1 Нарезание нужного количество кусков из минимального количества листов

1.1.2 Оптимальное использование одного листа

1.2 Задачи оптимального выбора

1.3 Выводы по главе

Глава 2. Оценка сложности решения задачи о сумме

подмножеств

2.1 Постановка задачи

2.2 Верхняя оценка сложности

2.3 Нижняя оценка сложности наихудшего случая

2.4 Выводы по главе

Глава 3. Последовательные и параллельные варианты метода динамического программирования для задачи о

сумме подмножеств

3.1 Последовательные варианты метода динамического программирования

3.2 Экспериментальное исследование

3.3 Выводы по главе

Глава 4. Исследование эффективности различных вариантов метода динамического программирования для задачи

о ранце

4.1 Табличный вариант метода динамического программирования решения задачи о ранце

4.2 Вариант метода динамического программирования со списком

Стр.

4.3 Ускорение метода динамического программирования с помощью нижних и верхних границ

4.4 Экспериментальное сравнение эффективности различных алгоритмов

4.5 Выводы по главе

Глава 5. Решение задачи об оптимальной упаковке

5.1 Постановка задачи

5.2 Последовательный алгоритм решения

5.3 Параллельный алгоритм

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

5.5 Выводы по главе

Заключение

Список сокращений и условных обозначений

Список литературы

Список рисунков

Список таблиц

Приложение А. Программные коды

Приложение Б. Акт внедрения

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

Введение

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

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

Известно, что большинство комбинаторных задач являются КР-трудны-ми. К этому классу относятся и рассматриваемые в работе задачи дискретной оптимизации. Снижению вычислительной сложности алгоритмов решения таких задач для возможности их практического использования посвящено большое число исследований. Существенный вклад в развитие этого направления внесли работы А.А. Корбута, Ю.Ю. Финкельштейна, И.Х. Сигала, В.П. Гришу-

хина, А.А. Лазарева, Е.Р. Гафарова , В.Н. Шевченко, Н.Ю. Золотых, Д.И. Когана, В.И. Мунермана, Р.М. Колпакова, М.А. Посыпкина, V. Chvatal, D. Pisinger, S.Martello, P. Toth, E. Balas и др.

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

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

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

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

Для достижения поставленной цели были решены следующие основные задачи.

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

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

3. Разработаны и программно реализованы последовательные и параллельные методы решения задачи о ранце.

4. Разработаны и программно реализованы последовательные и параллельные методы решения задачи об оптимальной упаковке.

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

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

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

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

Научная новизна:

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

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

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

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

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

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

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

Разработанные в диссертационной работе методы решения задач дискретной оптимизации используются в АО «Завод «КОМПОНЕНТ» для оптимизации раскроя заготовок печатных плат (акт внедрения прилагается).

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

Внедрение результатов. Разработанные в диссертационной работе методы решения задач дискретной оптимизации используются в АО «Завод «КОМПОНЕНТ» для оптимизации раскроя заготовок печатных плат (акт внедрения прилагается).

Результаты, выносимые на защиту.

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

2. Способы реализации метода динамического программирования для задачи о сумме подмножеств:

- основанный на одномерном векторе (Уее^гЭР),

- учитывающий реальное число различных значений суммы элементов (8шаг1ЭР).

Экспериментальные результаты, позволившие установить, что более эффективным является параллельный вариант, основанный на одномерном векторе (РагУее^гЭР).

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

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

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

1. Микроэлектроника и информатика - 2010. 17-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. МИ-ЭТ, 2010.

2. Микроэлектроника и информатика - 2012. 19-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. МИ-ЭТ, 2012.

3. VII Международная научно-практическая конференция «Современные информационные технологии и ИТ-образование». МГУ, 2012.

4. XVI Международная телекоммуникационная конференция молодых ученых и студентов «МОЛОДЕЖЬ И НАУКА». НИЯУ МИФИ, 2013.

5. Микроэлектроника и информатика - 2013. 20-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. МИ-ЭТ, 2013.

6. VIII Международная научно-практическая конференция «Современные информационные технологии и ИТ-образование». МГУ, 2013.

7. Микроэлектроника и информатика - 2014. 21-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. МИ-ЭТ, 2014.

8. МЭС-2014. Проблемы разработки перспективных микро- и наноэлек-тронных систем - 2014. Москва, ИППМ РАН, 2014.

9. 2016 IEEE NW Russia Young Researchers in Electrical and Electronic Engineering Conference (EIConRusNW). МИЭТ, 2016.

10. Микроэлектроника и информатика - 2016. 23-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. МИ-ЭТ, 2016.

11. UKSim2016. 18th International Conference on Modelling and Simulation, Cambridge University (Emmanuel College), UK, 2016.

12. NUMTA2016. Numerical Computations: Theory and Algorithms, The 2nd International Conference and Summer School. Pizzo Calabro, Calabria, Italy, 2016.

13. 18th Mediterranean Electrotechnical Conference (MELECON 2016), Limassol, Cyprus, 2016

Публикации. По материалам диссертации опубликовано 5 тезисов докладов и 11 статей, в том числе 3 в журналах, входящих в перечень ВАК, 5 работы включены в базу Scopus.

Структура и объём диссертационной работы. Диссертация состоит из введения, пяти глав, заключения и двух приложений. Полный объём диссертации составляет 139 страниц, включая 4 рисунка и 8 таблиц. Список литературы содержит 52 наименования.

Глава 1. Применение задач дискретной оптимизации в АСУ

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

Другой типичной задачей, возникающей при управлении производственными процессами, является проблема оптимального выбора при наличии списка возможных вариантов. Каждая альтернатива характеризуется затратами и предполагаемым эффектом при ее выборе. Требуется найти оптимальный список выбранных вариантов, обеспечивающий максимальный суммарный эффект при условии соблюдения ограничения на затраты. Если обозначить через Wi, i = 1,п затраты на каждую альтернативу, а через pi, i = 1,п — эффект от их возможного применения, то получаем классическую постановку задачи о ранце:

п

У^ XiWi ^ max ,

i=1

п

^ ^ %iPi ^ С,

i=1

Xi G {0,1}, i G 1,n.

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

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

1.1 Двухэтапная задача раскроя двумерного материала

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

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

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

тике ограничены двухэтапным разрезанием по шаблону. Так как куски полученные в результате двухступенчатой процедуры резания могут иметь большие размеры, чем требуемые куски, избыточный материал необходимо удалить на этапе конечной обработки называемой обрезкой. Иллюстрации двухэтапной процедуры разрезания приведены на рис. 1.1 (с обрезкой) и на рис. 1.2 (без обрезки). В работе Морабито и Гарсиа [1] можно найти подробный пример двухступенчатой гильотинной резки используемой в целлюлозно-бумажной промышленности.

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

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

Есть много опубликованных трудов по двумерным алгоритмам резания, регулярно появляющихся в самых разных научных публикациях. Последние исследования были проведены Лоди, Мартелло и Моначи [2], Лоди, Мартелло и Виго [3]. Вычислительные сравнения современных методов были выполнены Альваресом-Вальдесом, Парадоне и Тамаритом [4]. В этом разделе мы лишь приводим некоторые случаи возникновения проблемы задачи о ранце в контексте данного исследования. Следует отметить, что двумерные геометрические задачи упаковки тесно связаны, а по сути, часто эквивалентны двумерным задачам резания. Однако, такие функции, как разрезы гильотины и запрещенные вращения, не переносятся на состав упаковки.

1.1.1 Нарезание нужного количество кусков из минимального

количества листов

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

гильотининными разрезами из минимального количества больших листов размером Ь х W без поворотов. Следует отметить, что многие методы используют двухэтапные шаблоны, чтобы упростить процесс резания. Последние публикации по проблеме двухэтапного подхода принадлежат Лоди, Мартелло и Виго [5], Капраре, Лоди и Моначи [6]. Расширение уровня-ориентированного подхода в эвристике для трехмерной упаковки одного контейнера дано Писингером [7].

Рисунок 1.1 — Первая полоса длиной 11 заполненная решением ограничением

задачи о ранце емкостью с = W — /ш1.

Двухэтапное разрезание непосредственно приводит к следующей базовой стратегии, описанной в [5]. После определения типа куска с максимальной длиной 1тах = /1, разрезается первая полоса длиной 1тах. Для определения других типов кусков, которые нужно нарезать из этой полосы, были предложены различные эвристические идеи, основанные на одномерной задаче об упаковке, но

лучший выбор представлен решением ограниченной задачи о ранце. Каждый тип куска ] приводит к весу п)^ в соответствующем задаче ограниченного ранца (ВКР) с прибылью pj = ^п)^ и весом п)^. Ограничение количества копий типов кусков в (ВКР) задается числом оставшихся типов кусков, подлежащих обрезке (bj в начале). Емкость, соответствующая доступной ширине полосы, задается выражением W — п)\. Иллюстрация полосы, упакованной используя такой подход, приведена на рисунке 1.1. Поскольку полученные примеры (ВКР) имеют умеренные размеры, даже оптимальные вычисления могут быть выполнены для этих подзадач в разумные сроки.

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

Просто расположив построенные полосы в произвольном порядке, мы получим решение связанной двумерной задачи упаковки полос, где вместо конечных листов задана бесконечная полоса ширины W. В этом варианте задачи общая длина, необходимая для удовлетворения общего количества, должна быть сведена к минимуму. Это проявляется, в частности, при резке стальных рулонов и рулонов бумаги (см., например, Феррейра, Невес и Кастро [8], Валерио де Карвалью и Гимараэс Родригес [9]).

Эту эвристику легко адаптировать к решению проблемы, когда разрешено вращение кусков. В этом случае длина новой полосы задается шах{ш1п{/^}\] = 1,...п} по всем остальным типам кусков. Для достижения плотного заполнения кусков в (ВКР) решении для остатка части полосы, остальные типы кусков ориентируются своей более длинной стороной параллельно длине полосы, если эта сторона не превышает длины полосы. В противном случае, их более короткая сторона, которая по определению не может превышать длину полосы, будет ориентирована параллельно длине полосы.

1.1.2 Оптимальное использование одного листа

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

Алгоритмы динамического программирования для задачи двухступенчатой резки были представлены Гилмором и Гомором [10-12]. Более поздние работы по этой теме включают работы Валерио де Карвалью и Гимараэса Родри-га [13], Файарда и Зисимопулоса [14], Хифи и Зисимопулоса [15] и Хифи [16]. Точный алгоритм для случая без гильотины, который включает в себя решение стандартной задачи о ранце в качестве подпрограммы, был предложен Хаджи-константину и Кристофидесом [17].

Большой лист имеет размерность Ь х W. Существует п различных типов кусков, каждый из которых имеет размер ^ х п)^, который может быть произведен в неограниченных числах. Части имеют ассоциированную прибыль pj, отражающую цены на некоторые куски. Если мы поставим pj = ^п)^, то целью является использование максимальной площади прямоугольного листа. Для формулировки задачи целочисленного программирования требуется верхняя граница к для числа вертикальных полос. Тривиальное ограничение может быть задано как к = I ~г~ I. Длины этих вертикальных полос могут быть представлены переменными у{ для % = 1,...,к. Мы используем переменную решения х^, чтобы представить, что элемент у вырезан х^ раз из полосы %. Кроме того, пусть т^ обозначает максимальное количество кусков типа у, которые можно вырезать из листа. Пример двухступенчатого шаблона резания приведен на рисунке 1.2.

Рисунок 1.2 — Шаблон двухэтапной резки.

Модель целочисленного программирования теперь становится в виде

к п

х = тахгтгхе^^ х^,

г=1 3=\

п

зиЬ^есЬ Хц ^ W, г = 1,...,к,

к

^Уг < Ь,

1=1

Ьх%2 ^ У^ = 1,...,k, ] = ly..,n,

^^ 2 X ^ ^ ^ X , % — 1 , ^ — 1

хгз е {0,...,т3}, г = 1,...,к,] = 1,...,п, х'%3 е {0,1}, % = 1,...,к,з = 1,...,n, уг е{1,...,L}, % = 1,...,к.

1.1)

1.2)

1.3)

1.4)

1.5)

Здесь ограничения (1.2) говорят о том, что никакая полоска не может превышать ширину листа, ограничение (1.3) гарантирует, что сумма длин полос должна быть в пределах длины листа, в то время как ограничения (1.4) требуют, чтобы каждый элемент j выбранный для полосы i должен иметь длину lj, не превышающую длину yi полосы. Ограничение (1.5) гарантирует, что если Xij > 0, то x'rij = 1.

Без ограничения общности можно предположить, что у1 ^ у2 ^ ... ^ у к, так как мы можем разрезать полосы в любом порядке.

Проблема может быть решена за две итерации. Во-первых, для каждой длины полосы yi = 1,...,L находим максимальную получаемую сумму прибыли в полосе шириной W, решая следующую задачу, определенную для множества типов позиций с длиной lj ^ уi.

Pi = maximize}^ ■=1 pj Xij,

subject to ^^WjXij ^ W, (1.6)

j=1

Xij E {0,...,mj}, j E {1,...,n} with lj ^ yi.

Далее, установив := yi для i = 1,...,L, мы определяем наиболее выгодную комбинацию полос, которая заполняет длину листа L.

Еп -■=1 Pi Xi,

п

■subject to ^^ \xi ^ L, (1.7)

i=i

хг Е {0,...,Ь}, г = 1,...,Ь.

Теперь решение (1.7) является оптимальным решением (1.1).

Гилмор и Гомори заметили, что указанные выше проблемы могут быть решены с оптимальностью в псевдо полиномиальное время, решая только две задачи о неограниченном ранце. Идея заключается в том, чтобы упорядочить куски по возрастающей длине ^ и решить задачу (1.6) посредством динамического программирования. Таким образом учитываются все возможные длины

полос = ^ (нет смысла вырезать полосу длиной, не равной длине куска). Для (1 = 0,...^ и ] = 1,...,п пусть х3(<£) будет определяться как

х3 (д) := тах<

I Хк Хк ^ е = 1>...Л \.

К к=\ к=1 )

(1.8)

Мы можем найти все вышеперечисленные решения за время ). Бла-

годаря упорядочению кусков х3 ^) будет оптимальным решением (1.6). Задача (1.7) распознается как неограниченная задача о ранце (ИКР) и, следовательно, может быть решена за время О(пЬ) используя ту же рекурсию, так как мы имеем только п различные значения р^.

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

Если размер Ь х W доступного листа можно выбрать произвольно, мы можем использовать один и тот же алгоритм несколько раз, так как алгоритм динамического программирования решает (1.6) для всех ширины листа W, и, следовательно, должна тестироваться только заданная длина В (1.7).

1.2 Задачи оптимального выбора

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

Список литературы диссертационного исследования кандидат наук Си Ту Тант Син, 2018 год

Список литературы

1. Morabito R., Garcia V. The cutting stock problem in a hardboard industry: a case study. — Computers and Operations Research, 25, 1998. — 469-485 pp.

2. A. Lodi S. Martello, Monaci M. Two-dimensional packing problems: a survey.

— European Journal of Operational Research, 141, 2002. — 241-252 pp.

3. A. Lodi S. Martello, Vigo D. Recent advances on two-dimensional bin packing problems, 123. — Discrete Applied Mathematics, 2002. — 379-396 pp.

4. R. Alvarez-Valdes A. Parajon, Tamarit J.M. A computational study of heuristic algorithms for two-dimensional cutting stock problems. — In Proceeding of 4th Meta-heuristics International Conference (MIC 2001), 2001. — 7-11 pp.

5. A. Lodi S. Martello, Vigo D. Approximation algorithms for two-dimensional oriented bin packing problem. — European Journal of Operational Research, 112, 1999. — 158-166 pp.

6. A. Caprara A. Lodi, Monaci M. An approximation scheme for the two-stage, two-dimensional bin packing problem. — In Integer Programming and Combinatorial Optimization, 9th IPCO Conference, volume 2337 of Lecture Notes in Computer Science, Springer, 2002. — 320-334 pp.

7. Pisiger D. Heuristics for the container loading problem. — European Journal of Operational Research, 141, 2002. — 381-392 pp.

8. J. Soeiro Ferreira M.A. Neves, Castro P.F. A two-phase roll cutting problem.

— European Journal of Operational Research, 44, 1990. — 185-196 pp.

9. de Carvalho J.M. Valerio, Rodrigues A.J Guimaraes. An LP-based approach to a two-stage cutting stock problem. — European Journal of Operational Research, 84, 1995. — 580-589 pp.

10. Gilmore P.C, Gomory R.E. A linear programming approach to the cutting stock problem. — Operations Research, 9, 1961. — 849-859 pp.

11. Gilmore P.C, Gomory R.E. A linear programming approach to the cutting stock problem, Part 2. — Operations Research, 11, 1963. — 863-888 pp.

12. Gilmore P.C, Gomory R.E. Multistage cutting stock problems of two and more dimensions. — Operations Research, 13, 1964. — 94-120 pp.

13. de Carvalho J.M. Valerio, Rodrigues. A.J Guimaraes. A computer based interactive approach to a two-stage cutting stock problem. — INFOR, 1994. — 243-252 pp.

14. Fayard D, Zissimopoulos V. An approximation algorithm for solving unconstrained two-dimensional knapsack problems. — Europeam Journal of Operational Research, 84, 1995. — 618-632 pp.

15. Hifi M, Zissimopoulos V. Constrained two-dimensional cutting: an improvement of Christofides and Whitlock's exact algorithm. — Journal of the Operational Research Society, 48, 1997. — 324-331 pp.

16. Hifi M. Exact algorithms for large-scale unconstrained two and three staged unconstrained cutting problems. — Conputational Optimization and Applications, 18, 2001. — 63-88 pp.

17. Hadjiconstantinou E., Christofides N. An exact algorithm for general, orthogonal, two-dimensional knapsack problems. — European Journal of Operational Research, 83, 1995. — 39-56 pp.

18. Lorie J.H., Savage L.J. Three problems in capital rationing. — The Journal of Business, 28, 1955. — 229-239 pp.

19. Everett H. Generalized Lagrange multiplier method for solving problems of optimum allocation of resources. — Operations Research, 11, 1963. — 399-417 pp.

20. Weingartner H.M., Ness D.N. Methods for the solution of the multidimensional 0/1 knapsack problem. — Operations Research, 15, 1967. — 83-103 pp.

21. Nemhauser G.L., Ullmann Z. Discrete dynamic programming and capital allocation. — Management Science, 15, 1969. — 494-505 pp.

22. Weingartner H.M. Capital budgeting of interrelated projects: survey and synthesis. — Management Science, 12, 1966. — 485-516 pp.

23. Beinsen L., Pferschy U. Economic scenarios involving problems of the knapsack family. — manuscript in preparation, Faculty of Economics, University of Graz.

24. Elton E.J., Gruber M.J. Modern Portfolio Theory and Investment Analysis. — J. Wiley, 5th edition, 1995.

25. M.M. Guntzer D. Jungnickel, Leclerc. M. Efficient algorithms for the clearing of interbank payments. — European Journal of Operational Research, 106, 1998.

— 212-219 pp.

26. Martello Silvano, Toth Paolo. Knapsack problems: algorithms and computer implementations. — John Wiley & Sons, Inc., 1990.

27. Kellerer Hans, Pferschy Ulrich, Pisinger David. Knapsack problems. 2004.

28. А.А. Лазарев. Графический подход к решению задач комбинаторной оптимизации. — АиТ, №4., 2007. — 13-23 с.

29. A. Lazarev A. Graphic approach to combinatorial optimization. — Automation and Remote Control. V. 68. No. 4., 2007. — 583-592 pp.

30. Сигал И.Х. Иванова А.П. Введение в прикладное дискретное программирование. — М.: ФИЗМАТЛИТ., 2007.

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

32. В.П. Гришухин. Эффективность метода ветвей и границ в задачах с булевыми переменными. — Исследования по дискретной оптимизации., 1976. — 203-130 с.

33. Колпаков Р.М. Посыпкин М.А. Асимптотическая оценка сложности метода ветвей и границ с ветвлением по дробной переменной для задачи о ранце.

— Дискретн. анализ и исслед. операций, №15. Т. 1., 2008. — 58-81 с.

34. Lazarev A. A. Werner F. A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems. — Comput. Math. Appl. V. 58. No 4., 2009. — 619-631 pp.

35. Колпаков Р.М. Посыпкин М.А. Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце. — Дискретная математика.Т. 22. №1., 2010. — 58-73 с.

36. Колпаков Р.М. Посыпкин М.А. Верхняя оценка числа ветвлений для задачи о сумме подмножеств. — Мат. вопросы кибернетики.вып. 18., 2013. — 213-226 с.

37. Lazarev Alexander, Werner Frank. A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems // Computers Mathematics with Applications. — 2009. — Vol. 58, no. 4. — Pp. 619-631.

38. Kolpakov Roman Maksimovich, Posypkin Mikhail Anatol'evich. Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem // Discrete Mathematics and Applications. — 2010. — Vol. 20, no. 1.

— Pp. 95-112.

39. Kolpakov RM, Posypkin MA, Sin Si Tu Tant. Complexity of solving the Subset Sum problem with the branch-and-bound method with domination and cardinality filtering // Automation and Remote Control. — 2017. — Vol. 78, no. 3.

— Pp. 463-474.

40. Gary Michael R, Johnson David S. Computers and Intractability: A Guide to the Theory of NP-completeness. — 1979.

41. El Baz Didier, Elkihel Moussa. Load balancing methods and parallel dynamic programming algorithm using dominance technique applied to the 0-1 knapsack problem // Journal of Parallel and Distributed Computing. — 2005. — Vol. 65, no. 1. — Pp. 74-84.

42. Tan Guangming, Sun Ninghui, Gao Guang R. A parallel dynamic programming algorithm on a multi-core architecture // Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures / ACM. — 2007. — Pp. 135-144.

43. Kolpakov Roman Maksimovich, Posypkin Mikhail Anatolevich, Sigal I Kh. On a lower bound on the computational complexity of a parallel implementation of the branch-and-bound method // Automation and Remote Control. — 2010. — Vol. 71, no. 10. — Pp. 2152-2161.

44. Kolpakov Roman, Posypkin Mikhail. The lower bound on complexity of parallel branch-and-bound algorithm for subset sum problem // AIP Conference Proceedings / AIP Publishing. — Vol. 1776. — 2016. — P. 050008.

45. Гаврилов С.В. А.Л. Глебов и А.Л. Стемпковский. Структурная оптимизация цифровых КМОП схем. — Информационные технологии и вычислительные системы, №4., 2002. — 40-47 с.

46. др. Лупин С. А. и. К вопросу оценки точности алгоритмов дискретной оптимизации. — Проблемы разработки перспективных микро-и наноэлектрон-ных систем-2012 (МЭС-2012)., 2012. — 553-556 с.

47. KellererH. PfershyU., PisingerD. Knapsack Problem. — Springer Verlag., 2004. — 546 pp.

48. Р. Беллман. Динамическое программирование. — Изд-во иностранной литературы., 1960.

49. А.П. Сигал И.Х. и Иванова. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы..

50. М.А. Колпаков Р.М. и Посыпкин. Асимптотическая оценка сложности метода ветвей и границ с ветвлением по дробной переменной для задачи о ранце. — Дискретн. анализ и исслед. опер, 15:1., 2008. — 58-81 с.

51. Adleman. L.M. On breaking generalized knapsack public Key cryptosystems. — In Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC)., 1983. — 402-412 pp.

52. Лазарев. А.А. Графический подход к решению задач комбинаторной оптимизации. — Автомат.ителемех, № 4., 2007. — 13-23 с.

Список рисунков

1.1 Первая полоса длиной 1\ заполненная решением ограничением

задачи о ранце емкостью с = W — ......................................13

1.2 Шаблон двухэтапной резки................................................16

4.1 Таблица метода динамического программирования......................54

4.2 Таблица метода динамического программирования со списком. ... 56

Список таблиц

1 Сравнение числа итераций алгоритмов Уе^огЭР и 8шаг1ЭР..........49

2 Время работы алгоритмов Уе^огЭР и РагУе^огЭР (мсек)..............50

3 Время работы алгоритмов 8шаг1ЭР и Раг8шаг1ЭР (мсек)..............50

4 Время работы алгоритмов ТаЬЭР и РагТаЬЭР (мсек)..................51

5 Время выполнения (секунд) ..............................................59

6 Число шагов метода..........................................................59

7 Время выполнения при различном числе виртуальных процессоров (секунд)......................................................................68

8 Число итераций алгоритма при различном числе виртуальных процессоров..................................................................69

Приложение А Программные коды

Листинг А.1 Генератор для случайных входных экземпляров на C++.

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <time.h> #include <string> #include <sstream> #include <sys/stat.h> 10 #include <chrono> #include <random> #include <vector> using namespace std; class Instances_generator {

int *p, *w, sum, min, capacity, C, alpha_size; FILE *a, *b, *c, *d, *e, *f, *g; vector<float> alpha; public :

Instances_generator(int number_of_items , int a_size); void Uncorrelated_data_instances(int number_of_items, int R.

int num_instances) ; void Weekly_correlated_instances(int number_of_items, int R.

int num_instances) ; void Strongly_correlated_instances(int number_of_items, int

R, int num_instances); void Inverse_strongly_correlated_instances(int number_of_items, int R, int num_instances); void Almost_strongly_correlated_instances(int number_of_items, int R, int num_instances); void Subset_sum_instances(int number_of_items, int R, int

num_instances) ; void Subset_sum_instances_hard(int number_of_items, int R,

int num_instances) ; void Uncorrelated_instances_with_similar_weights(int

number_of_items, int R, int num_instances); void printPair(FILE * f, int *p, int *w, int N, int C) ; string file_name(string method, int N, int R, int C, int num_instance);

35

40

45

50

55

60

Instances_generator::Instances_generator(int number_of_items, int a_size){ sum = 0; min = 0; capacity = 0; C = 0;

alpha_size = a_size;

mkdir("inputs" , 0777);

for(int i=0; i<alpha_size; i++){

float temp=float(i+1)/float(alpha_size+1); alpha.push_back (temp);

}

p = (int *) malloc(number_of_items * sizeof (int)); if (p == NULL) {

cerr << "Error : Your size is too much.\n"; exit (1) ;

}

w = (int *) malloc(number_of_items * sizeof (int)); if (w == NULL) {

cerr << "Error : Your size is too much.\n"; exit (1) ;

}

}

void Instances_generator::printPair(FILE* f, int *p, int *w, int N, int C) {

f printf ( f , " °/„d\t°/„d\n" , N, C); for (int i = 0; i < N; i++)

f printf (f , "°/d\t°/d\n" , p [i] , w [i] ) ;

}

string Instances_generator::file_name(string method, int N, int R, int C, int num_instance) { ostringstream os; os << "input s/"; os << method << " /" ;

os << method << "_" << N << "_" << R << "_"; if (num_instance < 10)os << "0" << "0" << num_instance; if (num_instance >= 10 && num_instance < 100)os << "0" <<

num_instance; if (num_instance >= 100)os << num_instance;

75

80

85

90

95

100

os << "_" << C; return os . str () ;

void Instances_generator::Uncorrelated_data_instances(int number_of_items, int R, int num_instances) { string M = "Uncorrelated_data_instances"; mkdir("inputs/Uncorrel ated_data_instances", 0777) ; // obtain a seed from the system clock:

unsigned seed = static_cast<int> ( std : :chrono : :system_clock

: : now () .time_since_epoch() . count () ) ; // seeds the random number engine, the

mers enne_twister_ engine std::mt19937 generator(seed); // set a distribution range (1 - R)

std: :uniform_int_distribution<int> distribution(1, R) ; for (int j = 0; j < num_instances * alpha_size; j++) { p[0] = distribution(generator); w[0] = distribution(generator); sum = sum + w [0] ; min = w [0] ;

for (int i = 1; i < number_of_items; i++) { p[i] = distribution(generator); w[i] = distribution(generator); s um = s um + w[ i ] ; if (min > w[i])min = w[i] ;

}

C = alpha[j / num_instances] * sum; if (C >= min)capacity = C; else {

capacity = min;

}

a = fopen(file_name(M, number_of_items , R, capacity, j -

1).c_str(), "w"); printPair(a, p, w, number_of_items, capacity); fclose(a); sum = 0; mi n = 0 ;

}

void Instances_generator::Weekly_correlated_instances(int number_of_items, int R, int num_instances) {

}

115

120

125

130

135

}

string M = "Weekly_correlated_instances";

mkdir("inputs/Weekly_correlated_instances", 0777);

unsigned seed = static_cast<int> ( std : :chrono: :system_clock

: :now() .time_since_epoch () .count ()) ; std::mt19937 generator(seed);

std::uniform_int_distribution<int> distribution1(1, R); for (int j = 0; j < num_instances * alpha_size; j++) { w[0] = distribution1(generator);

std: :uniform_int_distribution<int> distribution2(w [0] -(R

/ 10) , w [0] + (R / 10) ) ; p[0] = distribution2(generator); sum = sum + w [0] ; min = w [0] ;

for (int i = 1; i < number_of_items; i++) { w[i] = distribution1(generator);

std: :unif orm_ int _di s tribut ion<int> distribution2(w[i

]-(R / 10), w[i]+(R / 10)); p[i] = distribution2(generator); s um = s um + w[ i ] ; if (min > w[i])min = w[i] ;

}

C = alpha[j / num_instances] * sum; if (C >= min) capacity = C; else {

capacity = min;

}

b = fopen(file_name(M, number_of_items , R, capacity, j +

1).c_str(), "w"); printPair(b, p, w, number_of_items, capacity); fclose (b) ; sum = 0; mi n = 0 ;

void Instances_generator::Strongly_correlated_instances(int number_of_items, int R, int num_instances) { string M = "Strongly_correlated_instances"; mkdir("inputs/Strongly_correlated_instances", 0777) ; unsigned seed = static_cast<int> (std::chrono::system_clock

: :now() .time_since_epoch() .count ()) ; std::mt19937 generator(seed);

std::uniform_int_distribution<int> distribution(1, R);

}

150

155

160

165

170

175

for (int j = 0; j < num_instances * alpha_size; j++) { w[0] = distribution(generator); p [0] = w [0] + (R / 10) ; sum = sum + w [0] ; min = w [0] ;

for (int i = 1; i < number_of_items; i++) { w[i] = distribution(generator); p[i] = w[i] + (R / 10) ; s um = s um + w[ i ] ; if (min > w[i])min = w[i] ;

}

C = alpha[j / num_instances] * sum; if (C >= min)capacity = C; else {

capacity = min;

}

c = fopen(file_name(M , number_of_items , R, capacity,

1).c_str(), "w"); printPair(c, p, w, number_of_items, capacity); fclose(c) ; sum = 0; mi n = 0 ;

}

}

void Instances_generator::Inverse_strongly_correlated_instances( int number_of_items, int R, int num_instances) { string M = "Inverse_strongly_correlated_instances"; mkdir("inputs/Inverse_strongly_correlated_instances", 0777); unsigned seed = static_cast<int> ( std : :chrono: :system_clock

: :now() .time_since_epoch() .count ()) ; std::mt19937 generator(seed);

std: :uniform_int_distribution<int> distribution(1, R) ; for (int j = 0; j < num_instances * alpha_size; j++) { p[0] = distribution(generator); w [0] = p [0] + (R / 10) ; sum = sum + w [0] ; min = w [0] ;

for (int i = 1; i < number_of_items; i++) { p[i] = distribution(generator); w [i] = p [i] + (R / 10) ; s um = s um + w[ i ] ; if (min > w[i])min = w[i] ;

+

190

195

200

205

210

215

}

C = alpha[j / num_instances] * sum; if (C >= min) capacity = C; else {

capacity = min;

}

d = fopen(file_name(M , number_of_items , R, capacity

1).c_str(), " w") ; printPair(d, p, w, number_of_items, capacity); fclose (d) ; sum = 0; mi n = 0 ;

}

void Instances_generator::Almost_strongly_correlated_instances( int number_of_items, int R, int num_instances) { string M = "Almost_strongly_correlated_instances"; mkdir("inputs/Almost_strongly_correlated_instances" , 0777) ; unsigned seed = static_cast<int> ( std : :chrono: :system_clock

: : now () .time_since_epoch() . count () ) ; std::mt19937 generator(seed);

std::uniform_int_distribution<int> distribution1(1, R); for (int j = 0; j < num_instances * alpha_size; j++) { w[0] = distribution1(generator);

std: :uniform_int_distribution<int> distribution2(w [0] + (R

/ 10)-(R / 500), w[0] + (R / 10) + (R / 500)); p[0] = distribution2(generator); sum = sum + w [0] ; min = w [0] ;

for (int i = 1; i < number_of_items; i++) { w[i] = distribution1(generator);

std: :unif orm_ int _di s tribut ion<int> distribution2(w[i

] + (R / 10)-(R / 500), w[i]+(R / 10) + (R / 500)); p[i] = distribution2(generator); s um = s um + w[ i ] ; if (min > w[i])min = w[i] ;

}

C = alpha[j / num_instances] * sum; if (C >= min) capacity = C; else {

capacity = min;

}

+

}

230

235

240

245

250

e = fopen(file_name(M, number_of_items, R, capacity,

1).c_str(), " w") ; printPair(e, p, w, number_of_items, capacity); fclose (e) ; sum = 0; mi n = 0 ;

}

void Instances_generator : : Subset_sum_instances (int number_of_items , int R, int num_instances) { string M = " Subset_sum_instances " ; mkdir("inputs/Subset_sum_instances", 0777);

unsigned seed = static_cast<int> ( std : :chrono: :system_clock

: :now() .time_since_epoch () .count ()) ; std::mt19937 generator(seed);

std: :uniform_int_distribution<int> distribution(1, R) ; for (int j = 0; j < num_instances * alpha_size; j++) { p[0] = w[0] = distribution(generator); sum = sum + w [0] ; min = w [0] ;

for (int i = 1; i < number_of_items; i++) { p[i] = w[i] = distribution(generator); s um = s um + w[ i ] ; if (min > w[i])min = w[i] ;

}

C = alpha[j / num_instances] * sum; if (C >= min)capacity = C; else {

capacity = min;

}

f = fopen(file_name(M, number_of_items , R, capacity, j -

1).c_str(), "w"); printPair(f, p, w, number_of_items, capacity); fclose (f) ; sum = 0; mi n = 0 ;

+

}

}

}

void Instances_generator::Subset_sum_instances_hard(int number_of_items, int R, int num_instances) { string M = "Subset_sum_instances_hard";

265

270

275

280

285

290

}

mkdir("inputs/Subset_sum_instances_hard", 0777) ;

unsigned seed = static_cast<int> ( std : :chrono: :system_clock

: : now () .time_since_epoch() . count () ) ; std::mt19937 generator(seed);

std: :uniform_int_distribution<int> distribution(1, R) ; for (int j = 0; j < num_instances * alpha_size; j++) { p[0] = w[0] = 2 * distribution(generator); sum = sum + w [0] ; min = w [0] ;

for (int i = 1; i < number_of_items; i++) {

p[i] = w[i] = 2 * distribution(generator);

s um = s um + w[ i ] ;

if (min > w[i])min = w[i] ;

}

C = alpha[j / num_instances] * sum; if ( C >= min)

capacity = C; else {

capacity = min;

}

if(capacity % 2 == 0) capacity ++;

f = fopen(file_name(M, number_of_items , R, capacity, j -

1).c_str(), "w"); printPair(f, p, w, number_of_items, capacity); fclose (f) ; sum = 0; mi n = 0 ;

void Instances_generator::

Uncorrelated_instances_with_similar_weights(int number_of_items, int R, int num_instances) {

string M = "Uncorrelated_instances_with_similar_weights"; mkdir("inputs/Uncorrelated_instances_with_similar_weights", 0777) ;

unsigned seed = static_cast<int> (std::chrono::system_clock

: :now() .time_since_epoch() .count ()) ; std::mt19937 generator(seed);

std::uniform_int_distribution<int> distribution1 (1, 1000); std::uniform_int_distribution<int> distribution2(100000, 100100);

}

305

310

315

320

325

330

}

for (int j = 0; j < num_instances * alpha_size; j++) { p[0] = distribution1(generator); w[0] = distribution1(generator); sum = sum + w [0] ; min = w [0] ;

for (int i = 1; i < number_of_items; i++) { p[i] = distribution1(generator); w[i] = distribution1(generator); s um = s um + w[ i ] ; if (min > w[i])min = w[i] ;

}

C = alpha[j / num_instances] * sum; if (C >= min)capacity = C; else {

capacity = min;

}

g = fopen(file_name(M, number_of_items , R, capacity, j +

1).c_str(), "w"); printPair(g, p, w, number_of_items, capacity); f close(g) ; sum = 0; mi n = 0 ;

R, a_size ;

int main(int argc, char* argv []) { string method; struct stat st ;

int num_instances, number_of_items if (argc >= 2) {

method = argv [1] ; if (argc == 6) {

number_of_it ems = atoi(argv [2]) ; R = atoi(argv [3]) ; num_instances = atoi(argv [4]) ; a_size = atoi(argv [5]) ;

}

} else {

f printf (stderr , "Usage: \°/„s <method> <number of items> < range> <How many instances for each alpha value> <

Alpha size>\n---Methods---\nUC =

Uncorrelated_data_instances\nWC = Weekly_correlated_instances\nSC =

}

335

340

345

350

Strongly_correlated_instances\nISC = Inverse_strongly_correlated_instances\nASC = Almost_strongly_correlated_instances\nSS = Subset_sum_instances\nSSH = Subset_sum_instances_hard \nUCS = Uncorrelated_instances_with_similar_weights\n " , argv [0]) ; exit (-1) ;

}

Instances_generator IG(number_of_items, a_size);

if (method == "UC" || method == "ALL") {

if (stat("inputs/Uncorrelated_data_instances", &st) ==

0)system("rm -r inputs/Uncorrelated_data_instances"); IG.Uncorrelated_data_instances(number_of_items, R, num_instances) ;

} if

} if

} if

} if

(method == "WC" || method == "ALL") { if (stat("inputs/Weekly_correlated_instances", &st) ==

0)system("rm -r inputs/Weekly_correlated_instances"); IG.Weekly_correlated_instances(number_of_items, R, num_instances) ;

(method == "SC" || method == "ALL") { if (stat("inputs/Strongly_correlated_instances", &st) == 0)system("rm -r inputs/Strongly_correlated_instances ") ;

IG.Strongly_correlated_instances(number_of_items, R, num_instances) ;

(method == "ISC" || method == "ALL") { if (stat("inputs/Inverse_strongly_correlated_instances", &st) == 0)system("rm -r inputs/ Inverse_strongly_correlated_instances"); IG.Inverse_strongly_correlated_instances(number_of_items , R, num_instances) ;

(method == "ASC" || method == "ALL") { if (stat("inputs/Almost_strongly_correlated_instances", &st) == 0)system("rm -r inputs/ Almost_strongly_correlated_instances"); IG.Almost_strongly_correlated_instances(number_of_items, R, num_instances) ;

} if

( me t ho d

"SS"

me t ho d

" ALL" ) {

365

370

} if

} if

}

if (stat("inputs/Subset_sum_instances", &st) == 0)system

("rm -r inputs/Subset_sum_instances") ; IG.Subset_sum_instances(number_of_items, R, num_instances) ;

(method == " SSH" || method == "ALL") { if (stat("inputs/Subset_sum_instances_hard", &st) == 0)

system("rm -r inputs/Subset_sum_instances_hard"); IG.Subset_sum_instances_hard(number_of_items, R, num_instances);

(method == "UCS" || method == "ALL") { if (stat("inputs/

Uncorrelated_instances_with_similar_weights" , &st) ==

0)system("rm -r inputs/ Uncorrelated_instances_with_similar_weights ") ; IG.Uncorrelated_instances_with_similar_weights( number_of_items , R, num_instances) ;

return 0;

Листинг А.2 Генератор для задачи о сумме подмножеств на C++.

}

10

15

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <string>

#include <sstream>

#include <sys/stat.h>

#include <chrono>

#include <random>

#include <math.h> using namespace std;

class Instances_generator_ss {

int *p, *w, capacity;

FILE *a, *b, *c, *d, *e; public:

Instances_generator_ss(int number_of_items);

void pthree_instances(int number_of_items, int num_instances ) ;

5

30

35

40

45

50

void psix_instances(int number_of_items, int num_instances); void evenodd_instances(int number_of_items, int

num_instances) ; void evenoddvar_instances(int number_of_items, int num_instances);

void avis_instances(int number_of_items, int num_instances); void somatoth_instances(int number_of_items, int

num_instances) ; void f2_instances(int number_of_items, int num_instances); void printPair(FILE * f, int *p, int *w, int N, int C) ; string file_name(string method, int N, int C, int num_instance);

Instances_generator_ss::Instances_generator_ss(int number_of_it ems) { mkdir("inputs_ss" , 0777);

p = (int *) malloc(number_of_items * sizeof (int)); if (p == NULL) {

cerr << "Error : Your size is too much.\n"; exit (1) ;

}

w = (int *) malloc(number_of_items * sizeof (int)); if (w == NULL) {

cerr << "Error : Your size is too much.\n"; exit (1) ;

}

}

void Instances_generator_ss::printPair(FILE* f, int *p, int *w int N, int C) { f printf (f , " °/„d\t°/„d\n" , N, C); for (int i = 0; i < N; i++)

f printf (f , "°/d\t°/d\n" , p [i] , w [i] ) ;

}

string Instances_generat or_ss::file_name(string method, int N, int C, int num_instance) { ostringstream os; os << "inputs_ss/" ; os << method << "/"; os << method << "_" << N << "_";

if (num_instance < 10)os << "0" << "0" << num_instance;

65

70

75

80

85

num_instance < 100)os << "0" <<

if (num_instance >= 10 <

num_instance; if (num_instance >= 100)os << num_instance; os << "_" << C; return os . str () ;

}

void Instances_generator_ss::pthree_instances(int number_of_items, int num_instances) { string M = "pthree_instances"; mkdir("inputs_ss/pthree_instances", 0777); // obtain a seed from the system clock:

unsigned seed = static_cast<int> ( std : :chrono : :system_clock

: : now () .time_since_epoch() . count () ) ; // seeds the random number engine, the

mers enne_twister_ engine std::mt19937 generator(seed); // set a distribution range (1 - 1000)

std::uniform_int_distribution<int> distribution(1, 1000); for (int j = 0; j < num_instances; j++) {

for (int i = 0; i < number_of_items; i++) { p[i] = w[i] = distribution(generator);

}

capacity = floor(number_of_items * (1000 / 4)); a = fopen(file_name(M, number_of_items, capacity

.c_str () , "w") ; printPair(a, p, w, number_of_items, capacity); fclose(a);

j + 1)

}

void Instances_generator_ss: :psix_instances(int number_of_items , int num_instances) { string M = "psix_instances" ; mkdir("inputs_ss/psix_instances", 0777);

unsigned seed = static_cast<int> (std::chrono::system_clock

: : now () .time_since_epoch() . count () ) ; std::mt19937 generator(seed);

std::uniform_int_distribution<int> distribution(1, 1000000); for (int j = 0; j < num_instances; j++) {

for (int i = 0; i < number_of_items; i++)

p[i] = w[i] = distribution(generator); capacity = floor(number_of_items * (1000000 / 4));

}

100

105

110

115

120