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

На правах рукописи

Нгуен Минь Ханг

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

01.01.09 — Дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2009

003460140

Работа выполнена в Учреждении Российской академии наук Вычислительный центр им. А. А. Дородницына РАН.

Научный руководитель: Официальные оппоненты:

Ведущая организация:

кандидат физико-математических наук

A. И. Голиков

доктор физико-математических наук, профессор

B. И. Цурков,

кандидат физико-математических наук, М. А. Посыпкин

Учреждение Российской академии наук Институт системного анализа РАН

Защита состоится " Же/^а-лЯ 2009 в ч. _0(?мин. на заседании Диссертационного совета Д 002.017.02 при Учреждении Российской академии наук Вычислительный центр им. А. А. Дородницына РАН по адресу: 119991, г. Москва, ул. Вавилова, дом 40, тел: (499) 135-24-89.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан "^ " .Яи/лАЯ 2009.

Учёный секретарь Диссертационного совета доктор физико-математических наук (1 Рязанов В. В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

В 1975г. Дж. Холландом было показано, что поиск решения оптимизационной задачи можно представить в виде эволюции группы решений, что привело к развитию генетического алгоритма (ГА) как достаточно эффективной техники оптимизации, которая моделирует процесс естественной эволюции, открытый Ч. Дарвином. Тем не менее остается актуальной разработка генетических алгоритмов, учитывающих специфику конкретной оптимизационной задачи в максимальной степени. Примером таких задач являются важная с практической точки зрения задача раскроя материалов и задача покрытия множества системой его

подмножеств, к которой сводятся многие практические задачи.

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

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

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

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

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

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

4. Исследование задачи покрытия множества и разработка алгоритма ее решения на основе генетического алгоритма;

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

К методам исследования, примененным в данной работе, относятся: теория и численные методы оптимизации, линейная алгебра, параллельные методы программирования. Научная новизна:

1. Разработан новый эффективный метод решения двойственной задачи ЛП с большим числом переменных и небольшим числом

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

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

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

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

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

Практическая ценность работы состоит в том, что разработаны, исследованы и программно реализованы методы для решения больших задач оптимизации: линейного программирования, раскроя листовых материалов, задачи о покрытии множества и задачи оптимизации структуры атомного кластера. Разработанный алгоритм решения задачи одномерного раскроя листовых материалов различных типоразмеров внедрен и успешно используется в производственном процессе трубопрокатного завода VG PIPE (Вьетнам).

Результаты, выносимые на защиту, состоят в следующем:

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

• одномерного раскроя листовых материалов разных размеров;

• задачи о покрытии множества системой его подмножеств;

• глобальной оптимизации структуры атомных кластеров;

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

3. Получена оценка порогового значения параметра, начиная с которого метод находит проекцию заданной точки на множество решений двойственной задачи ЛП;

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

Апробация работы. Результаты работы докладывались и обсуждались на 13-й Всероссийской конференции "Математическое программирование и приложения"(Екатеринбург, Россия, 2007 г.), на 9-м Международном семинаре по компьютерным наукам и информационным технологиям С81Т'07 (Уфа, Россия, 2007 г.), на XIV Байкальской международной школе-семинаре (Иркутск, Байкал, Россия, 2008 г.), а так же на семинарах отдела прикладных проблем оптимизации ВЦ РАН (Москва, Россия, 2006-2008 гг.).

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

Объем и структура работы. Диссертация состоит из введения, трех глав, заключения и списка, литературы. Общий объем работы составляет 116 страниц и список литературы из 115 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность исследуемой проблемы, сформулирована цель и задачи диссертационной работы, перечислены полученные в диссертации новые результаты, их практическая ценность, представлены положения, выносимые на защиту и описана структура диссертации.

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

В §1.2 приведена модель задачи одномерного линейного раскроя материала, впервые предложенная Л.В. Канторовичем, в виде задачи целочисленного программирования с неявно заданной информацией о

столбцах матрицы раскроя А = (%■):

lDCSPG(m,L,l,b) = min ¿xj = min ЦхЦ, (1)

j=l

n

dijXj > bi, i = l,...,m, (2)

3 = 1

m

}Zhaij<L, j = l,...,n, (3)

i=i

Xj e Z+, j = 1,..., n. (4)

В этой задаче xj - целочисленные переменные, обозначающие интенсивность применения шаблона раскроя j в решении, п - количество шаблонов, L - ширина листа раскраиваемого материала, m - количество различных заготовок, раскраиваемых из исходного листового материала, Ii - ширина заготовки типа г, а есть требуемое количество заготовок этого типа, т.е. заказ на этот тип продукт.

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

Предположим, что aJ , j = 1,..., п, - все шаблоны раскроя и каждый элемент Xj вектора xJ = {х\...хп) показывает количество применений шаблона а?. Заметим, что п может быть очень большим. Таким образом, получим следующую модель:

lDMCSP(m, М, I, Ь, L) = min £ с^, (5)

3=1

TL

J2aijXj>bi, г = 1,..., m, (6)

3=1

т. M

< J2Lia(i+m)j, (7)

2=1 i—1 M

Y!a(i+m)i = 1) (8)

i=1

хещ, a,j£Z™', j = l,...,n, (9)

где m! = m + M, LT = (L\...Lm) - вектор ширины листов материала. Вектор аТ = (ai...am>) € Ъ™ представляет один шаблон раскроя, если выполнены ограничения (7)-(8). Элемент о<, г = 1 определяет,

сколько заготовок вида г будет раскроено. Элемент йк+т равен единице, если используется материал вида к, а остальные элементы аг+т,г € {1 ,...,М} \ /с, равны нулю. Если шаблон раскроя aJ использует материал вида к, то Cj = Cfc, где с^ - элемент вектора стоимости листов материалов.

Пусть xt - оптимальное решение задачи (5)-(9). Введем обозначения-.

• fi(fc), к = 1 ,...,М - множество всех шаблонов раскроя листа материала вида к, соответствующее решению х„ задачи (5)-(9);

• xt/Q,(k) - проекция xt на fi(fc);

• Ьк - вектор заготовок, полученный из (5)-(9) в соответствии с элементами х„/й(к).

Теорема 1.1. Если х* - оптимальное решение задачи 1 DMCSP(m, М, I, b, L) (5) — (9), то а;»/fl(fc) есть оптимальное решение задачи lDCSPG{m,Lk,l:bk) (1) - (4), к = 1,.. -,М.

На основе теоремы 1.1 можно представить задачу 1DMCSP в следующем виде:

м

lDMCSP(m, М, I, Ь, L) = min £ 1 DCSPG(m, Lk, l, bk)ck, (10)

fc=i

м

Zbk>b, (ii)

jt=i

bk £ Z™. (12)

м

Каждый набор векторов bk, удовлетворяющих = b, назовем

fc=i

разбиением вектора b.

Теорема 1.2. Оптимальное решение задачи (10) — (12) определено на множестве разбиений вектора Ь.

Теорема 1.2 позволяет ограничить пространство поиска решения задачи 1DMCSP внутри множества всех разбиений вектора заказа. Теоремы 1.1 и 1.2, а также новое представление задачи 1DMCSP в виде (10)-(12) наводят на идею разбиения задачи 1DMCSP на базисные задачи 1 DCSPa(m,Lk,l,bk) для последующего применения метода генерации столбцов. Оптимальные решения всех базисных задач будут собраны для получения допустимого решения задачи 1DMCSP. Поиск оптимального решения задачи 1 DMCSP проводится генетическим алгоритмом над пространством поиска, являющимся множеством всех разбиений вектора заказа Ъ.

Алгоритм GA-CG Шаг 0. Создать популяцию из Я особей Gq = {sio, ■••, s#o}. Инициализация начальной популяции легко проводится путем создания Н разбиений вектора Ь, каждое разбиение соответствует одной особи

популяции. Особи представлены следующим образом:

и

Sio = (blо,...,ь>0 е ъ™, = ь,i = 1,.., я

¿=1

Шаг 1. Решить задачу 1 DCSPcim, Lk,l,b^t), г = 1,..., Я, к = 1,..., М, где t - номер итерации (номер популяции), методом генерации столбцов. Рассчитать степени приспособленности /(s; () для каждой особи из Gt по формуле

f(Si t) = Т{-•

J2lDCSPG(m:Lk,l,b^t)ck к=1

Шаг 2. Выбрать родительские особи из Gt в зависимости от степени приспособленности для скрещивания. Пусть Si = и =

(bl,...,^1) - две произвольные особи. Тогда с помощью случайного числа к, 1 < к < rri, из этих особей производим два потомка:

^(bb-.bf), s'2 = (b\,..Jn b\[r}=b\[r}, 6|T[r] = ЬЦг], r = l,...,k, г = 1,...,M, Ш = Ш Ш = b[Ul j = к + 1,..., m, i = 1,..., M. Получить множество особей потомков G(.

Шаг 3. Воздействовать оператором мутации на GtUGt для получения Gt. Оператор мутации воздействует на особи s = (Ь1,...,ЬМ) для получения новой особи Si = (b\, ...jbi1) со случайно выбранной тройкой целых чисел (р, q, г), таких что 1 < р < М, 1 < q < М, 1 < г < т, следующим образом:

b\ = Ь1 при i^ipiiiyiq г = 1,..., М, Ш = Ш Щ\з) = b"\j] при j ± г и j = 1,..., то, 6f[r] = W[r] - 1, 6j[r] = 69[r] + 1, если V[r\ > 0, Ь?[г] = 6P[r], ЬЦг] = bq[r], если W[r) = 0.

Шаг 4. Совершить расчет, как на шаге 1, для особей из Gt-

Шаг 5. Вероятность отбора определяется пропорционально степени

приспособленности

Ps = Tl/fl?f(sy 03)

где s есть особь из рассматриваемой популяции G. Применить оператора отбора (13) над Gt для отбора Я особей с наибольшей приспособленностью, составляющих новую популяцию Gt+i-

Шаг 6. Если не выполнен критерий останова, то вернуться к шагу 2.

Иначе алгоритм останавливается и дает решение вместе с соответствующей матрицей раскроя.

Работа разработанного алгоритма продемонстрирована на ряде тестовых примеров. Алгоритм и его программная реализация внедрены и используются на трубопрокатном заводе VG PIPE (Вьетнам) более двух лет. С оборотом производства в 70000 тонн/год применение данного алгоритма позволило заводу сэкономить каждый год более 1000 тонн материалов.

В §1.3 предложен эвристический алгоритм решения задачи нахождения минимального покрытия с неоднородной стоимостью, постановка которой формально определена следующим образом. Пусть имеются конечное множество S = (ci, ог,...,сгт) и система его подмножеств Sj С S, j = 1,2, ...,п, такие что

\Js} = s.

j=1

Каждому из подмножеств Sj поставлен в соответствие вес (стоимость) Cj > 0, таким образом рассматривается задача о взвешенном покрытии. Требуется найти минимальный по числу подмножеств набор Sj, такой что каждый элемент множества S принадлежит хотя бы одному из подмножеств этого набора. Введем матрицу А = {а^)тхп следующим образом:

_ Г 1, если оч 6 Sj, lj ~ \ 0, если а, £ Sj.

Предполагается, что каждый элемент <Tj входит хотя бы в одно из подмножеств Sj . Введем булевы переменные Xj, j = 1,2, ...,п :

_ ( 1, если Sj входит в покрытие, 3 \ 0, если Sj не входит в покрытие.

Тогда задача о покрытии множества состоит в нахождении покрытия с минимальной стоимостью по следующей математической модели:

п

J2 CjXj —> min, (14)

i=i

п

aijXj > 1, г = 1,2,..., т, (15)

j=1

Х,е{0,1},^ = 1,2,..,п. (16)

Для решения задачи нахождения минимального покрытия (14)-(16) предлагается следующий генетический алгоритм:

Шаг 1. Создание начальной популяции из N случайных особей. Каждая особь к представлена n-мерным булевым вектором хк , у которого элемент хк принимает значение единицы, если подмножество Sj входит в покрытие, и принимает значение нуля, если иначе. Степень приспособленности Д особи хк рассчитывается следующим образом:

п

.7=1

Шаг 2. Выбрать две особи xFl и хРг из популяции методом пропорционального выбора (tournament selection method), используя вероятность выбора, определенную по формуле

1 /Л /.»N Рк = -л- ■ (17)

Е1Ш i

Шаг 3. Применить оператор кроссовер над особями xPl и хР2 для создания новой особи xch. Пусть fxPi и fxp2 есть степени приспособленности родительских особей xPl и хРг соответственно и определяются по (17), xch есть потомок, полученный в результате применения оператора кроссовера над xPl и хРг. Так как гены принимают только значения из набора {0,1}, обозначим через po(j) частоту появления значения нуля и через Pi(j) частоту появления значения единицы для j-ro гена в популяции. Тогда для всех j, 1 < j < п, мы определим x^h по следующему правилу:

1. Если xPl = Xj2, присвоим x^h = xPl = хР2.

2. Если xPl ф xf, то

а) при xPl = 0: присвоим xfh = xp\ если fxPl ■ p0(j) > fxp2 -pi(j), иначе присвоим x^h = хРг]

б) при xPl = 1: присвоим х?н = хР\ если fxFl ■ pi(j) > fxr2 -p0{j), иначе присвоим x^h — хР2.

Шаг 4. Воздействовать над xCh оператором мутации. Вместо использования классической постоянной частоты мутации применяется переменная частота мутации. Для каждого j-ro гена, 1 < j < п, рассчитываем соответствующую энтропию

Hj = -РоО") logpo(j) - pi(j') logpi(j),

где po{j) и pi(j) - определенные выше частоты появления значения 0 и 1 в j-м гене в популяции. Определим вероятность мутации j-ro гена, 1 < j < п,

по следующей формуле:

РтиЬаНоп^) ~ ~ ' •

Е 1 !Щ

Г=1

Оператор мутации будет применен над потомками, созданными оператором кроссовер. Гены, имеющие вероятность мутации больше 1/п, будут выбраны для мутации по следующему правилу замены битов:

1.Если ртишш{з) > = 1,рх{э) > роС?), то = 0.

2.ЕСЛИ Pmv.taticm.i3) > 1/п, = 0,р0(з) > РхЦ), ТО Х?Н = 1.

Шаг 5. Применить алгоритм восстановления допустимости решения на хС1г для получения допустимой и неизбыточной особи хск'. Если хС11 совпадает с какой-либо особью в популяции, то вернуться к шагу 2. Иначе перейти к следующему шагу.

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

Шаг 7. Повторить шаги 2-6 до того момента, когда больше не рождаются новые особи в популяции. Тогда решением задачи является особь с наименьшей степенью приспособленности в популяции.

Работоспособность разработанного алгоритма проверена на тестовых задачах библиотеки ОИ-НЬгагу, доступной в Интернете (http://people.brunel.ac.uk/ тав^Ь/]еЬ/т1о.Ы;т1). Результаты вычисления показывают, что для задач средних размеров (т = 200 — 400, п — 1000 — 4000), для которых известно оптимальное решение, алгоритм дает оптимальное решение в большей части экспериментов и среднее отклонение не превышает 1.12%. Для 8 из 20 задач больших размерностей классов Е-Н (т = 500 — 1000, п = 5000 — 10000) алгоритм дает лучшее решение, чем представленные в библиотеке ОИ-НЬгагу. Среднее время расчетов составляет от несколько секунд для первой группы задач и достигает несколько минут для второй группы.

Задача оптимизация структуры атомного кластера подробно рассмотрена в §1.4. Дан обзор некоторых точных и эвристических методов поиска глобального минимума. Представлен новый генетический алгоритм нахождения множества достаточно хороших конфигураций атомных кластеров с точки зрения минимальной потенциальной энергии. Шаг 1. Инициализация начальной популяции

Для получения возможных структур кластеров из N атомов используется известная оптимальная структура кластера меньшей размерности (Д^ — > 1 в качестве "зародыша". Остальные д атомов получаются

путем раздвоения случайно выбранного атома из (N — q) и разнесения их на расстояния rmjn. Так же производится проверка расстояния между всеми парами атомов r(i,j) в кластере на предмет удовлетворения условия r{hj) > i~min, где rmin есть минимальное межатомное расстояние для рассматриваемого вида атомного кластера. Если атомы удалены меньше, чем на такое расстояние, то кластер будет иметь высокую энергию и таким образом не будет иметь физического смысла. После получения начальных кластеров-особей, каждый из них обязательно подвергается процессу локальной оптимизации методом сопряженного градиента. Значения энергии этих локально оптимальных структур кластера будут использованы в качестве меры приспособленности особей. Шаг 2. Кроссовер (скрещивания)

Отбор пар родителей для скрещивания производится турнирным способом. Особи-родители делятся плоскостью, перпендикулярной случайной оси и проходящей через центр масс кластера, на две "половинки". Эти "половинки" затем обмениваются для получения двух потомков. Особи-потомки подвергаются локальной оптимизации. Шаг 3. Мутация

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

Отбор особей для перехода в следующее поколение происходит по принципу естественного отбора. Из всех особей текущей популяции, а также потомков и мутантов, отбираются лучшие Npop особи, которые составят новое поколение. Шаг 5. Критерии останова

Если количество поколений больше заданной величины MaxGen или отклонение средней энергии особей популяции меньше заданной малой величины toi, то алгоритм останавливается, иначе перейти к шагу 2.

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

формулой:

а потенциальная энергия Морса определена следующим образом:

{г) = [ер(1"г) - I]2 - 1.

Заметим, что в функции энергии Морса присутствует параметр р, с ростом которого увеличивается сложность поиска глобального экстремума, обычно рассматриваются р = 3,6,10,14.

Проведено сравнение работы предложенного алгоритма с алгоритмом монотонного случайного спуска по локальным минимумам (Monotonie Basin Hopping) для некоторых кластеров Ленарда-Джонса, которое показало эффективность предложенного алгоритма с точки зрения меньшего количества вызовов функции локальной оптимизации почти в 2 раза.

Параллельный вариант предложенного алгоритма был реализован на С++ с использованием MPI. Для кластеров Морса с Natom < 80 алгоритм показал возможность нахождения значений оптимумов, совпадающих с представленными в Кэмбриджской базе данных, за приемлемое время. Ниже в таблице представлены некоторые результаты работы алгоритма на комплексе MVS-6000 для некоторых кластеров Морса с Natom > 80- Размер популяции во всех задачах был установлен 30. Значение f*1 есть найденное значение потенциальной энергии Морса, Р - количество использованных процессоров, а время расчета - время работы алгоритма до нахождения ft1. Отметим, что значение оптимальной потенциальной энергии Морса при Natom > 80 пока неизвестно.

Natom Р jM Р время расчетов, мин.

85 3 -748.643598 20 5

85 6 -405.026458 20 12

85 10 -368.440724 50 16

85 14 -363.531055 50 164

90 3 -807.445287 40 5

90 6 -433.355380 40 11

90 10 -393.04228 80 24

90 14 -388.401652 80 178

95 3 -867.268837 80 6

95 6 -459.671925 80 14

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

Пусть задана прямая и двойственная задачи ЛП соответственно в следующем виде:

/» = min стх, X = {х е Rn : Ах = b, х> 0„}. (Р)

х€Х

/, = max bTu, U = {и е Rm : Ати < с}. (£)')

иеи

Здесь А £ Rmxn, с 6 Rn и b £ Rm заданы, х - вектор прямых переменных, au- двойственных, через Oj обозначен ¿-мерный нулевой вектор.

Предположим, что множество решений X, прямой задачи (Р) непусто, следовательно, множество решений U* двойственной задачи (D') также непусто.

Всюду ниже двойственную задачу (D') будем представлять в следующем эквивалентном виде:

ft = max bTu, W = {и е Rm, v е Rn : Ати + v = c, v> 0n}, (D)

ueU

где v - вектор неотрицательных дополнительных переменных. Через W, = [U* х У»] обозначим множество решений задачи (D).

Из множества решений W„ двойственной задачи (D) выделим решение w„ = [и*, г)»], ближайшее в евклидовой норме к некоторому заданному вектору й> = [й, й], т.е. найдем единственное решение w, = [й»,г)*] задачи строго выпуклого квадратичного программирования

W-Ü||2 + |HW||2)= min 1(||и-й||2 + ||г;-«||2), (18)

1 w=[u,v\eLW, l

W, = {и £ R™ ,v G Rl : ATu + v = c, bTu = /,}.

Здесь ft ~ оптимальное значение целевой функции исходной задачи ЛП.

Двойственная задача к (18) является задачей безусловной максимизации

max max {-сту - üT(ab - Ау) - ЩаЬ - Ау)||2 + а/, + УйЦ2 -¡/еЯ" aeR1

-\\\{Ъ~У)Л2}- (19)

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

1 = ти %,а,ш), (20)

где скаляр а фиксирован, а функция 5(у, а, и>) определена следующим образом:

5(1/, а, й) = -сту + йгАу - аЬ - Лу||2 - - у)+||2.

Без потери общности предположим, что первые I компонент вектора й» строго больше нуля. Тогда векторы г),, г), у и матрица Л представимы в виде

У! = [йГ.Л = УТ = [у'ТУ\ А = [А, I Л,],

где у{ > ОI, -0» = 0¿,<1 = п-1

Определим величину а, следующим образом:

а» = и^ М {а : аЬ - А4уа = й, - й - А^ -V1), уй > (21)

абД1 у,'€Й<'

Показано, что ограничения в (21) совместны, но целевая функция может быть не ограничена снизу. В этом случае полагается, что а» = 7, где 7-некоторое число. Если система уравнений в (21) однозначно разрешима относительно уа, то а* представима в виде

тах *——^-^—если а

гео- (22)

7 > —оо, если а = 0.

Здесь введено индексное множество ст = {7 + 1<г<п : > 0} и 7 — произвольное число.

Теорема 2.1 Пусть множество решений И7* исходной задачи ЛП непусто. Тогда при любом а > а», где а, вычисляется из (21), проекция гй* = [й»,г>„] заданной точки й = [й, й] определяется по формулам

щ = й + аЬ - Ау(а), V* = {У - у(а))+,

где у (а) - решение задачи безусловной оптимизации (20).

Если дополнительно матрица А^, соответствующая нулевым компонентам г)*, имеет полный ранг, то а„ определяется по формуле (22), а точное решение прямой задачи (Р) находится в результате решения задачи безусловной максимизации (20) по формуле

4 = -И<») + {¿¡АД^АЦй. - й - Мь{ - V1)). (23)

а

Теорема 2.1 позволяет заменить задачу (19), содержащую априори

неизвестное число /*, на задачу (20), в которой вместо этого

числа фигурирует полуинтервал [а», +со), что существенно проще с вычислительной точки зрения.

Отметим, что значение а», найденное из решения задачи линейного программирования (21) или формулы (22), может быть отрицательным. Это означает, что для двойственной задачи (Б) проекция точки ю на множество ее решений совпадает с проекцией этой точки на допустимое множество IV.

Следующая теорема утверждает, что если известна какая-нибудь точка ги* Е \У*, то можно получить решение прямой задачи (Р) после однократного решения задачи безусловной максимизации (20). Теорема 2.2 Пусть множество решений \У, задачи ЛП (В) непусто. Тогда для любых а>0иг& = и>»£ точное решение прямой задачи (Р) находится по формуле х„ = у(а)/а, где у{а) — решение задачи безусловной максимизации (20).

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

Щ+1 =щ + аЬ- Аук+и (24)

Щ+1 = {щ - ук+\)+, (25)

где произвольный параметр а > 0 фиксирован, а вектор ук+\ определяется из решения следующей задачи безусловной максимизации:

уш € агётах{-сту + и[Ау - 1||(а6 - Ау)||2 - Ь|(г/* - 2/)+||2}. (26)

У€ К" I I

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

Безусловная максимизация в (20) может выполняться любым методом, например методом сопряженного градиента. Но, как показал О. Мангасарьян, для безусловной оптимизации кусочно-квадратичной функции особенно эффективен обобщенный метод Ньютона.

Предлагаемый метод решения прямой и двойственной задач ЛП (метод ДП) сочетает итерационный процесс (24)-(25) и обобщенный метод Ньютона, примененный для решения задачи (26). Метод реализован в системе МАТЬАВ в виде программы БЬР в §2.2.

В конце расчетов вычислялись чебышевские нормы векторов невязок:

А1 = ]|Лх - 6||оо, Д2 = \стх — 6ти|, Д3 = ||(ЛТи + 1>-с)||оо.

Ниже в таблице приведены результаты численных расчетов по программе БЬР на компьютере Р-С2Б, 2.4 Й^.Д СЬ., щ = 0т, г)0 = 0„, уо = 1„, р~ плотность заполнения А ненулевыми элементами.

7П X п X р т, сек. I шаг а, Аь Аз, Аз,

10® х 100 х 0.01 3.8 2 10~5 1.4 х Ю"10 4.5 х Ю-7 1.8 х 10"10

106 х 500 х 0.01 18.6 2 2 х Ю-5 5.5 х Ю-10 4.3 х Ю-8 1.0 х 10"9

10е х 700 х 0.01 26.7 2 8 х 10~5 3.7 х Ю"10 1.1 х КГ7 2.0 х НГШ

106 х 1000 х 0.01 39.5 2 5 х 10~5 6.5 х 10"п 1.3 х 10"7 1.0 х ИГ11

106 х 2000 х 0.01 80.4 2 8 х 10~5 5.5 х 10"п 6.2 х 10~8 1.1 х 10"10

106 х 3000 х 0.01 244.1 4 5 х 10"5 5.6 х Ю-11 2.1 х 10~8 4.3 х 10"11

104х 500x 1 34.7 5 4.5 х Ю-4 1.1 х Ю"10 9.8 х 10"9 8.9 х КГ10

104 х 1000 х 1 210.7 7 0.2 5.5 х 10"12 3.0 х Ю"9 1.0 х Ю-7

3000 х 2000 х 1 241.1 10 0.1 6.2 х 10"п 2.4 х Ю-9 3.0 х Ю-10

5000 х 1000 х 1 96.2 10 0.01 5.5 х Ю-11 4.8 х КГ9 5.7 х 10"п

104 х 4000 х 0.01 67.7 3 0.01 2.9 х 10~12 7.2 х Ю-10" 4.9 х 10"12

(5.106) х 500 х 0.01 93.6 2 5 х 10~6 5.9 х Ю~10 1.6 х 10'7 4.7 х 10"п

(5.106) х 1000 х 0.01 198.0 3 5 х Ю-6 4.5 х Ю-10 6.1 х Ю-7 2.6 х 10"11

107 х 500 х 0.01 177.2 3 10~б 1.0 х КГ9 2.4 х Ю-7 4.6 х Ю"10

В третьей главе предлагаются, исследуются и экспериментально проверяются четыре параллельные схемы решения задач ЛП с помощью метода, предложенного Ю. Г. Евтушенко и А. И. Голиковым. Метод был подробно исследован и реализован в системе МАТЪАВ (программа ЕСМ) в диссертационной работе Н. Моллаверди. Численные эксперименты и сравнение программы ЕСМ с известными коммерческими и исследовательскими программами показали превосходство программы ЕСМ и возможность решать задачи ЛП с 50 миллионами переменных, но с небольшим числом ограничений (не более 4 тысяч). Актуальность параллельной реализации является очевидной для увеличения числа ограничений решаемых задач.

• В §3.1 описание реализации начинается с расчетных формул рассматриваемого итерационного метода

1. Задается начальное приближение х° и р°, р = р°.

2. Вычисляется функционал

8(р\(3,х°) = Ътрк-1-\\{х° + Атрк-рс)+\\2. (27)

Здесь э - номер внешней итерации, а к - номер внутренней итерации метода Ньютона для решения задачи безусловной максимизации

Рк+1 € ащтахреят {6Тр - + Атр - (Зс)+1|2}.

3. Вычисляется градиент функционала (27) по переменной р:

ЭЧ

(3* = —(рк,(3,хв) = Ь- А{ха + Атрк - Рс)+. (28)

4. Формируется обобщенная матрица Гессе функционала (27) по переменной р (здесь удобно использовать матрицу Гессе со знаком минус):

Нк = 51 + АОкАт. (29)

Диагональная матрица Ик 6 Мпхп задается равенствами

тк\ = / 1' если ^ + лТрк ~~ >

( Ы \ 0, если (:хк + Атрк - /Зс)< < 0. Таким образом, Нк € Мтхт.

5. Находится направление максимизации 6р как приближенное решение линейной системы

Нк5р = -вк. (30)

6. Находится рк+1 = рк — Тк5р.

7. Если достигнута сходимость внутренних итераций по к, то положим р =рк+Вычисляется по формуле

х"+1 = (а;5 + Атр — 0с)+, р° = р и повторяются шаги 2-6.

В §3.2 рассматриваются основные операции параллельного алгоритма. Параллельная реализация алгоритма 1-7 требует распараллеливания следующих основных операций:

• умножение матрицы на вектор: Ах и Аур;

• скалярное произведение вида хту, х, у £ Ет и ртд, р, ц € Кп;

• формирование обобщенной матрицы Гессе (29);

• умножение обобщенной матрицы Гессе на вектор;

Заметим, что все оставшиеся вычисления на этапах алгоритма 1-7 являются локальными. Например, метод сопряженных градиентов требует вычисления распределенных скалярных произведений и распределенного умножения матрицы на вектор. Остальные вычисления локальны и не требуют обменов. При вычислении функционала (27) необходимо распределенное умножение матрицы на вектор для вычисления вектора гк = (х* + Атрк — Рс)+ и для вычисления скалярного произведения Ьтрк. Для вычисления градиента (28) нужна дополнительная операция умножения матрицы на вектор.

В §3.3 последовательно приводятся описания четырех схем разбиения данных по процессорам для распараллеливания рассматриваемого

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

пр

Ах —— ^ ^ ¿=1

При этом умножение подматриц на подвекторы Xi производится независимо, и пр полученных векторов размерности m складываются друг с другом при помощи функции MPI_Allreduce из библиотеки MPI.

(

Л,

Л2

Л

А А,

А А;

А А,

А А,

Рис. 1. Столбцовая схема: разбиение матриц и векторов Матрицу Гессе Я можно представить в виде

пр

Н = ^Ни где Щ = Л.ДЛГ, ¿=1

где Д € - диагональные блоки матрицы Б. В столбцовой схеме

матрица Я не формируется. На каждом процессоре вычисляется локально матрица Я;. Для умножения матрицы на вектор

пр

#<7 = £я<д

!=1

каждое слагаемое вычисляется локально, и пр получившихся векторов суммируются при помощи функции МР1_А11гес1исе, так что результат суммирования оказывается доступен на всех процессорах.

Таким образом, метод сопряженных градиентов для решения линейной системы (30) не является параллельным и его вычислительные

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

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

Н! Р1 Л,

Ъ Р' А2

н, РI Л,

н, Р< А,

4 Я 4

л

ш &

м

Рис. 2. Строчная схема: разбиение матриц и векторов

Однако если хранить на каждом процессоре только соответствующую подматрицу, то при формировании обобщенной матрицы Гессе возникает необходимость обмена всех подматриц между процессорам, что означает большие коммуникационные затраты. Для избежания этих обменов на каждом процессоре матрица А хранится целиком, хотя каждый процессор i отвечает только за свою подматрицу .4* € Все векторы размерности

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

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

разбивается на прямоугольные блоки, как показано на рис.3.

Рис. 3. Клеточная схема: разбиение матриц и векторов

Для простоты изложения предположим, что полное число процессоров можно представить в виде пр = пг х пс, т.е. достаточно условно можно полагать, что процессоры расположены в узлах решетки размера пт х пс, при этом величина п делится нацело на пс, а тп делится нацело на пг. Таким образом, п = пс х Л^ и то = пг х Мг. Таким образом, матрица А состоит из подматриц Ац € КЛГгХЛГс. В этой схеме вектор х € Кп разбивается на пс подвекторов Х{, а вектор р £ Кт на пг подвекторов р^, причем подвектор лежит одновременно на пг процессорах, принадлежащих ^'-му столбцу "решетки" так же, как и все подматрицы А*у

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

Для решения задач ЛП с большим числом переменных (порядка несколько миллионов) и большим числом ограничений (порядка несколько сотен тысяч), где критичны размерности задачи, а следовательно, и объем требуемой памяти, предлагается новая схема, наиболее экономичная по использованию памяти. Матрицы разбиваются так же, как показано на рис.2. Однако в этой схеме на каждом процессоре хранится только одна строчная подматрица А,, а матрица Н в явном виде не хранится.

На каждой внешней итерации метода вычисляется только градиент, соответствующая подматрица Гессе Н{ не вычисляется. Далее на каждой внутренней итерации (метода сопряженных градиентов) каждый процессор вычисляет произведение своей подматрицы Гессе Щ на вектор pj путем последовательного вычисления двух произведений матрицы на векторов: ы = ВА]рг И Я, = Л; VI.

г

Для суммирования длинных разреженных векторов V} по всем процессорам был предложен специальный способ суммирования разреженных векторов. Это позволило в некоторой степени уменьшить

коммуникационные затраты.

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

Время работы строчной схемы т=5000. п=1000000. р=0.01

кол-во процессоров

Время работы столбцовой схемы тИОООО. п=1000000. р*0.01

■во процессоров

Время работы клеточной схемы шаЮООО, п=1000000. р=0.01

>-Т_101 -*--Т_1|П -*-Т_гёт] кол-во процессоров

Ускорение строчной схемы т=5000, п*1000000. Р«0.01

кол-во процессоров

Ускорение столбцовой схемы т=10000, п=1000000. ¿>=0.01

кол-во процессоров

Ускорение клеточной схемы тИОООО, пгЮООООО. рв0.01

10 20

40 50

1-ВО процессоров

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

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

т х п х р пр Ttot Ai д2 Дз

5 • 104 х 106 х 0.01 16 400.02 2.1- Ю-6 2.1- Ю-7 1.Ы1"

105 х 10в х 0.01 20 484.62 8.1 • 10~6 3.6 ■ 10~ь 5.6- 10~п

105 х 2 • 106 х 0.01 40 823.13 4.5 • 10~ь 4.2-10"' 7.2 • Ю-11

2 • 105 х 2 • 10ь х 0.01 80 2317.42 4.9 ■ 10~5 6.6-10~6 5.2- 10-ш

Из таблицы видно, что безматричная схема позволяет решать задачи ЛП с большим числом ограничений (т=200 тыс., п=2 млн., 80 процессоров, время решения 40 мин.).

Основное содержание диссертационной работы изложено в следующих публикациях:

1. Nguyen Minh Hang et al. A model combining genetic algorithm and simplex method for solving a production expense minimizing problem. // Journal of Computer Science and Cybernetics, No.22, Vol.4, Hanoi, 2006. P.319-324 (in Vietnamese).

2. Нгуен M.X. Применение генетического алгоритма для решения задачи планирования производства. // Тр. ХШ-й Всеросс. конф. "Математическое программирование и приложения", Екатеринбург, Россия, Март 2007. С. 132-133.

3. Nguyen М.Н. About one application о/ genetic algorithm in Production planning problem. // Proc. of the 9th Int. Workshop on Сотр. Sci. and Inf. Techn. Ufa, 2007 (Sept. 13-16). Vol.1. Pp. 225-229.

4. Нгуен M.X. Применение генетического алгоритма для решения одной задачи планирования производства. / / Динамика неоднородных систем. М.:Изд-во ЛКИ, 2007. Т. 29. Вып. 11. С.160-167.

5. Нгуен М.Х. Двухэтапный метод решения одной задачи раскроя материалов. // Тр. XIV Байкальской междунар. школы-семинара. "Приложение методов оптимизации". Т. 4. Иркутск-Северобайкальск, Россия. Июль 2008. С. 192-202.

6. Нгуен М.Х. Применение генетического алгоритма для задачи нахождения покрытия множества. // Динамика неоднородных систем. М.:Изд-во ЛКИ, 2008. Т. 33. Вып. 12. С.206-219.

Нгуен Минь Ханг Разработка и реализация численных методов решения оптимизационных задач большой размерности Подписано в печать 13.01.2009 Формат бумаги 60x84 1/16 Уч.-изд.лЛ. Усл.-печ. л. 1,5 Тираж 100 экз. Заказ 44 Отпечатано на ротапринтах в Вычислительном центре им. A.A. Дородницына Российской академии наук 119991, Москва, ул. Вавилова, 40

ВВЕДЕНИЕ

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

1.1. Генетический алгоритм как метод нахождения оптимальных решений.

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

1.2.1. Общее описание задачи одномерного раскроя материалов

1.2.2.Метод генерации столбцов.

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

1.2.4.Генетический алгоритм для решения задачи раскроя стальных листов.

1.2.5.Практические результаты применения алгоритма GA-CG для задачи раскроя.

1.3. Использования генетического алгоритма для решения задачи покрытия множества.

1.3.1.Постановка задачи о покрытии множества

1.3.2.Подход, основанный на генетическом алгоритме, для нахождения минимального покрытия.

1.3.3.Результаты использования ГА для решения задачи покрытия множества.

1.4. Оптимизация структуры атомного кластера с помощью генетического алгоритма.

1.4.1.Задача конфигурационной оптимизации атомного кластера

1.4.2.Обзор предложенных методов.

1.4.3.Генетический алгоритм оптимизации структуры атомного кластера.

1.4.4. Параллельная реализация.

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

2. МЕТОД НЬЮТОНА ДЛЯ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ БОЛЬШОЙ РАЗМЕРНОСТИ

2.1. Нахождение проекции точки на множество решений •двойственной задачи линейного программирования

2.2. Программная реализация и результаты вычислений метода Ньютона для решения двойственной задачи ЛП

3. ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ ОБОБЩЕННОГО МЕТОДА НЬЮТОНА ДЛЯ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ БОЛЬШОЙ РАЗМЕРНОСТИ

3.1. Параллельный итерационный алгоритм.

3.2. Основные операции параллельного алгоритма.

3.3. Схемы разбиения данных.

3.3.1.Столбцовая схема.

3.3.2.Строчная схема.

3.3.3.Клеточная схема.

3.3.4.Безматричная схема.

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

ВЫВОДЫ

Объект исследования и актуальность темы.

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

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

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

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

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

Нахождение глобального оптимума является общей проблемой для многих отраслей науки, техники и управления, а её решению, глобальной оптимизации, посвящен отдельный раздел прикладной математики [6]. Задачи нахождения глобального оптимума являются весьма сложными с вычислительной точки [7]. В настоящее время большинство методов поиска глобальных экстремумов относится к направленному перебору. Встречающиеся же прикладные: задачи глобальной оптимизации зачастую требуют поиска глобального минимума в пространстве достаточно большого числа переменных исследуемой функции. Примерами таких задач из области химии является поиск глобального минимума поверхности потенциальной энергии (ППЭ) ван-дер-ваальсовых комплексов [8] и предсказание третичной структуры белков [9]. '

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

В 1975г. Дж. Холландом было показано, что поиск решения оптимизационной задачи можно представить в виде эволюции группы решений [10]. Это позволило успешно моделировать процессы, происходящие в природе, для решения NP-полных задач. В последние годы разработчики методов и программ для решения сложных проектных и оптимизационных задач все чаще обращают внимание на эволюционные методы, среди которых алгоритм муравьиной колонии, алгоритм моделирования отжига и генетические алгоритмы.

Генетический алгоритм (ГА) представляет собой технику оптимизации, которая моделирует феномен естественной эволюции (впервые открытой Ч. Дарвином) [11]. При естественной эволюции выживают и дают самое многочисленное потомство особи, наиболее адаптированные к сложным условиям окружающей среды. Степень адаптации, в свою очередь, зависит от набора хромосом конкретной особи, полученного от родителей. Это основа выживания сильнейшего -не только процесс выживания, но и участие в формировании следующего поколения. В природе выживание является определяющей и основной функцией. Генетический алгоритм не пытается оптимизировать единственное начальное решение. Он работает с группой начальных решений, которые кодируются, подобно хромосомам. Отдельные гены хромосомы представляют собой уникальные переменные для изучаемой проблемы. На каждом шаге генетического алгоритма присутствует набор объектов - особей, обладающих "генетической информацией", или "хромосом". Для пар особей определяются правила скрещивания, согласно которым, при переходе на следующий шаг алгоритма, производится потомство на основе "генетической информации" родителей. Из этого потомства при помощи критерия приспособленности выбираются особи, которые войдут в следующее поколение. При отборе "здоровых" хромосом из популяции и использовании генетических операторов (таких как рекомбинирование и мутация) в популяции остаются только те хромосомы, которые лучше всех приспособлены к окружающей среде, т.е. наиболее полно отвечают задаче. Особи могут также подвергаться случайным мутациям, в результате которых наследственная информация подвергается изменениям.

Использовавшиеся для моделирования биологической эволюции генетические алгоритмы были обобщены для использования в глобальной оптимизации [12]. В этом случае - "генетическая информация" - это точка в пространстве аргументов, а "приспособленность" - значение целевой функции. Правила скрещивания и мутации выбираются в зависимости от строения множества, на котором определена целевая функция.

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

В связи с интенсификацией производства в настоящее время вопросы оптимизации планирования и управления производства на предприятиях очень актуальны. Перспективным направлением работ по повышению эффективности функционирования автоматизированных систем управления является разработка и реализация программных систем, позволяющих решать совокупность взаимосвязанных оптимизационных задач планирования производства. Построение оптимальных карт раскроя ресурсного материала является одной из самых трудоемких задач на заготовительной стадии производства. В то же время это одна из самых важных задач в ресурсосберегающих технологиях, поскольку напрямую ведет к экономии материала и снижению отходов. Начало теоретическим исследованиям в области методов рационального раскроя положили труды академика JL В. Канторовича [13, 14], в которых он показал возможность эффективного решения оптимизационных задач с помощью ЭВМ. В своих работ Канторовича JI. В. впервые представил задачу раскроя одинаковых листов материала в виде задачи целочисленного линейного программирования, в которой матрица ограничений задана неявно. Эта модель стала основой для многих методов решений. На протяжении последних 70 лет исследованиям в области раскроя и разработки новых алгоритмов укладки плоских заготовок было посвящено множество отечественных и зарубежных работ [15] - [53]. Однако задача раскроя на заводах, где в качестве исходных ресурсов используют материалы различных типоразмеров, порождает очень большую матрицу ограничений, а вместе с тем и огромное количество переменных, что часто не позволяет использовать классические оптимизационные методы. В работе [54] показано, что построение эвристических алгоритмов для решения задачи раскроя материалов различных размеров необходимо, так как точные подходы не пригодны в этом случае. Разработка нового метода решения конкретной практической задачи с учетом ее специфики позволит получить качественно лучшее решение и таким образом повысить эффективность производства.

Задача о покрытии множества (ЗПМ) системой его подмножеств [55]-[57] является математической моделью для многих важных приложений, таких как составление расписания [58], планирование сервиса, распознавание образов [59]-[61], прогнозирование, логический анализ данных, упрощение булевских выражений [57] и т.д. ЗПМ относится к классу NP-полных задач [5], поэтому построение алгоритма нахождения оптимального или приближенного решения является весьма сложной задачей. Однако структура представления реальной задачи предоставляет дополнительную информацию, позволяющую решать ЗПМ довольно больших размерностей (несколько сотен строк и несколько миллионов столбцов) с результатом, отличающимся от оптимального решения примерно на 1%, за приемлемое время счета [57]. Практические методы решения ЗПМ опираются на различные подходы и могут быть распределены по классам таким, как класс алгоритмов, основанных на теории линейного программирования, класс эвристических алгоритмов и класс алгоритмов ветвей и границ [62]. В данной работе будет приведено формальное представление задачи, а так же предложен алгоритм решения ЗПМ, основанный на принципах генетического алгоритма.

Исследования атомных и молекулярных кластеров - быстро развивающаяся область физики и химии [63]-[77]. Как видно из приведённых литературных данных, совершенствование теоретических и экспериментальных методов позволяет исследовать все более сложные системы со всё возрастающей точностью. Поверхности потенциальной энергии кластеров являются своеобразным местом встречи, где теоретические модели могут найти подтверждение со стороны экспериментальных подходов. В то же время, функции, описывающие ППЭ кластеров, в дополнение к большому числу аргументов (степеней свободы), обладают во многих случаях большим числом стационарных точек. Правильное нахождение геометрических конфигураций кластеров, отвечающих наиболее глубоким минимумам ППЭ, важно для правильного описания свойств этих частиц. В то же время, нахождение стационарных точек и, в частности, минимумов, на сложных гиперповерхностях представляет собой отдельную проблему, для решения которой существуют специализированные численные методы. ГА является успешным методом определения глобального минимума, но иногда с физической точки зрения структуры, соответствующие более высоким локальным минимумам, могут быть более важными, чем глобальный минимум. Наконец, стоит отметить, что биологически активные формы белков, возможно, не всегда соответствуют глобальным минимумам. Таким образом, возможность ГА наряду с поиском глобального минимума находить семейство локальных минимумов, близких к глобальному, является особенностью этого метода и имеет важную практическую ценность.

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

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

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

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

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

4. Исследование задачи покрытия множества и разработка алгоритма ее решения на основе генетического алгоритма;

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

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

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

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

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

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

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

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

Разработанный алгоритм решения задачи одномерного раскроя листовых материалов различных типоразмеров внедрен и успешно используется в производственном процессе трубопрокатного завода VG PIPE (Вьетнам).

Результаты, выносимые на защиту состоят в следующем:

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

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

3. Получена оценка порогового значения параметра, начиная с которого метод находит проекцию заданной точки на множество решений двойственной задачи ЛП;

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

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

1. На 13-й Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, Россия, 2007 г.);

2. На 9-м Международном семинаре по компьютерным наукам и информационным технологиям CSIT'07 (Уфа, Россия, 2007 г.);

3. На XIV Байкальской международной школе-семинаре (Иркутск, Байкал, Россия, 2008 г.);

4. На семинарах отдела прикладных проблем оптимизации ВЦ РАН (Москва, Россия, 2006-2008 гг.);

Основные результаты опубликованы в [78]-[83].

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

В 1.2 приведена модель задачи одномерного линейного раскроя материала, предложенная JI.B. Канторовичем в [13]. Из всех известных методов решения этой задачи выбран и описан метод генерации столбцов. Представлена так же модель для расширенной задачи раскроя с различными исходными материалами на примере раскроя листов стали на трубопрокатном заводе. Показано, что для расширенной задачи .значительно возрастает степень сложности из-за роста количества переменных, и таким образом, почти невозможно решить ее целиком с помощью известных алгоритмов. Доказано, что решение "большой" задачи определено на множестве разбиений вектора заказа. На основе доказанных теорем разработан новый алгоритм решения расширенной задачи на основе комбинирования генетического алгоритма с методом генерации столбцов. Работа предложенного алгоритма продемонстрирована на наборе тестовых примеров. Результаты практического внедрения алгоритма в производственный процесс трубопрокатного завода VG PIPE (Вьетнам) показали его эффективность с точки зрения сокращении объема отходов. Отход металла уменьшился почти в 2 раза.

В параграфе 1.3 предложен эвристический алгоритм решения задачи нахождения минимального покрытия с неоднородной стоимостью. Алгоритм основан на генетическом алгоритме с операторами кроссовер и мутации, моделирующими различные свойства естественной эволюции, такие как "доминантность", "чистокровность" и "биологическое разнообразие". Работоспособность разработанного алгоритма проверена на тестовых задачах библиотеки OR-library [84], доступной в Интернете. Результаты вычисления показывают, что алгоритм может дать оптимальное решение для задач средних размерностей и качественно лучшее решение для задач больших размерностей, чем полученное другими алгоритмами и опубликованное в библиотеке OR-library.

Задача оптимизация структуры атомного кластера подробно рассмотрена в параграфе 1.4. Дан обзор как точных, так и эвристических методов поиска минимумов поверхности потенциальной энергии. Представлен генетический алгоритм нахождения множества достаточно хороших конфигураций атомных кластеров с точки зрения минимальной потенциальной энергии без возможности доказательства оптимальности найденных решений. Предложенный алгоритм призван найти набор "хороших" структур атомного кластера за относительно малое время вычислений. Так же разработана схема параллельной реализации предложенного алгоритма, дающая возможность использования современных мощных вычислительных комплексов для нахождения оптимальных структур атомных кластеров больших размеров. Приведено сравнение работы предложенного алгоритма с алгоритмом монотонного случайного спуска по локальным минимумам (Mono-tonic Basin Hopping) для некоторых кластеров Ленарда-Джонса. Так же представлены результаты вычислений для кластеров Морса с количеством атомов 80 < Natom < 95, отсутствующие в Кембриджской базе данных [85] .

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

Показано, что повторная безусловная оптимизация этой функции, в которой вместо точки проектирования взято решение двойственной задачи, дает некоторое точное решение прямой задачи ЛП. То есть решения прямой и двойственной задач ЛП можно найти в результате двукратной безусловной оптимизации вспомогательной функции, размерность переменных которой равна числу ограничений задачи ЛП. Для безусловной оптимизации предлагается использовать обобщенный метод Ньютона. Так как вспомогательная функция является выпуклой квадратичной функцией, то для ее минимизации целесообразно применять обобщенный метод Ньютона, который, как показал О. Мангасарьян [86], сходится глобально за конечное число шагов. В параграфе 2.1 приведена программа DLP, которая реализует предложенный метод в системе MATLAB. Проведены численные эксперименты на случайно сгенерированных задач ЛП. Они показали высокую эффективность предложенного метода, возможность решать задачи ЛП с несколькими миллионами переменных и до 5 тысяч ограничений за приемлемой время. Сравнение раннее предложенного метода нахождения проекции на множество решений двойственной задачи [87] с предложенным в данной работе показало явное преимущество последнего. Это связано с тем, что в [87] вспомогательная функция оптимизируется на положительном ортанте и для применения обобщенного метода Ньютона требуется учесть условия неотрицательности переменных с помощью штрафной функции. Еще раз подчеркнем, что предлагаемая в работе вспомогательная функция оптимизируется на всем пространстве обобщенным методом Ньютона.

В третьей главе предлагаются, исследуются и экспериментально проверяются четыре параллельные схемы решения задач ЛП с помощью метода, предложенного в [88]. Метод из [88] подробно исследован в [87]. Численные эксперименты и сравнение программы

EGM, реализованной в MATLAB, с известными коммерческими и исследовательскими программами показали превосходство программы EGM [89] и возможность решать задачи ЛП с 50 миллионами переменных , но с небольшим числом ограничений (не более 4 тысяч). Параллельная реализация позволила увеличить число ограничений до 200 тысяч и решать задачи ЛП за существенно меньшее время.

выводы

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

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

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

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

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

6. Задача одномерного раскроя листовых материалов и разработанное программное обеспечение внедрены в практику производства трубопрокатного завода VG PIPE (Вьетнам) и дали значительную экономию металла.

1. Еремин И. И. Теория линейной оптимизации. Екатеринбург, УрО РАН, 1998.

2. Васильев Ф. П., Иваницкий А. Ю. Линейное программирование. М.: Факториал, 2003.

3. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. -СПб.:БХВ-Петербург, 2002. 608с.

4. Цурков В. И. Декомпозиция в задачах большой размерности. М.: Наука. 1981.

5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — Пер. с англ.— 1982.

6. Стронгин Р.Г., Сергеев Я.Д., Гришагин В.А. Введение в параллельную глобальную оптимизацию. -Н.Новгород: Изд-во ННГУ, 1998, 87стр.

7. Жиглявский А. А., Жилинкас А. Г. Методы поиска глобального экстремума. М.: Наука. Физматлит, 1991.

8. Maranas С. D., Floudas С. A. A global optimization approach for Lennard-Jones microclusters //J. Chem. Phys., v 97, pp. 7667-7678, 1992.

9. Kolinski A., Godzik A., Skolnick J. A general method for the prediction of the three dimensional structure and folding pathway of globular proteins: Application to designed helical proteins //J. Chem. Phys., v. 98, pp. 7420-7433, 1993.

10. Holland J. H. Adaptation in natural and artificial systems.- The University of Michigan Press,Ann Harbor,MI, 1975.

11. Гладков JI.A., Курейчик В.В., Курейчик В.М. Генетические алгоритмы / Под ред. В.М. Курейчика. — 2-е изд., испр. и доп.- М.: ФИЗМАТЛИТ, 2006. 320 с.

12. Goldberg D. Е. Genetic algorithms in search, optimization, and machine learning —MA.: Addison-Wesley, 1989.

13. Канторович Л.В. Математические методы в организации и планировании производства . — Л.: Изд-во ЛГУ, 1939 (воспроизведено в сб. "Применение математики в экономических исследованиях М., Соцэкгиз, 1959).

14. Канторович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов — Новосибирск: Наука, 1971. — 299 с.

15. Бронфельд Г.Б. Алгоритм решения задачи оптимального распределения плана производства / / Труды института. Автоматизация и механизация управления производством, Горький, НИИУавтопром. —1977 — вып.2—с.75-83.

16. Cheng, С.Н., Feiring, B.R., Cheng, Т.С.Е. The cutting stock problem- a survey. // International Journal of Production Economics.— 1994. vol.36.- P.291-305.

17. Gilmore P., Gomory R. A linear programming approach to the cutting stock problem.// Operations Research, 9, 1961: 849-859.

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

19. Brown A.R. Optimum packing and depletion: The computer in space and resource usage problems// New York, 1971.

20. Dantzig G. В., Wolfe P. Decomposition Principle for Linear programs. 11 Operations Research, 8, 1960 : 101-111.

21. Dyckhoff H., Kruse H.-J., Abel D., and Gal T. Trim loss and related problems // Omega, 13, 1985: 59-72.

22. Dyckhoff H. A typology of cutting and packing problems, f/ European Journal of Operational Research, 44(2), 1990: 145-159.

23. Dyckhoff H., Wascher G. Cutting and packing. // European Journal of Operational Research, 44(2), 1990.

24. Wascher G., Haubner H., Schumann H. An improved typology of cutting and packing problems.// European Journal of Operational Research, 183(3), 2007: 1109-1130.

25. Wang P.Y., Wascher G. Cutting and packing.)/ European Journal of Operational Research, 141(2), 2002.

26. Oliveira J. F., Wascher G. Cutting and Packing. // European Journal of Operational Research, 183, 2007: 1106-1108.

27. Marcotte O. The cutting stock problem and integer rounding // Math. Program., 33, No. 1, 1985. -p.82-92.

28. Shahin A. A., Salem О. M. Using genetic algorithms in solving the one-dimensional cutting stock problem in the construction industry. // Canadian Journal of Civil Engineering, Vol.31 (2), 2004. pp.321-332

29. Afshar A. et al. An Improved Linear Programming Model for One-Dimensional Cutting Stock Problem. // First International Conference on Construction In Developing Countries, Karachi, 2008.

30. Belov G. and Scheithauer G.A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths. // European Journal of Operational Research, 141, no. 2,Special issue on cutting and packing, 2002. -p. 274-294.

31. Belov G. and Scheithauer G-Л branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. // Technical report, Dresden University, 2003, URL: www.math.tu-dresden.de/?capad.

32. Belov G. and Scheithauer G. Setup and open stacks minimization in one-dimensional stock cutting // Technical report, Dresden University, 2003.

33. Sallaume S. et al. One Dimensional Cutting Stock Problem with Redevelopment of the Surplus Material. // EngOpt 2008, Rio de Janeiro, Brazil, 01 05 June 2008.

34. Wongprakornkul S. et al. Optimization Based Heuristic Approaches for Solving an Integrated One-dimensional Cutting Stock-Transportation Problem. I j Journal of Mathematics and Statistics 3 (3): 142-150, 2007.

35. Coffman E. G. , Garey M. R., and Johnson D. S. Approximation algorithms for bin packing: A survey. // In D. S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, Boston, 1997.

36. Falkenauer E. Tapping the full power of genetic algorithm through suitable representation and local optimization. // In J. Biethann and V. Nissen, editors, Evolutionary Algorithms in Management Applications. Springer-Verlag, Berlin, 1995.

37. Falkenauer E. A hybrid grouping genetic algorithm for bin packing. // Journal of Heuristics, 2:5-30, 1996.

38. Belov G. Problems, Models and Algorithms in One- and Two-Dimentional Cutting Dissertation. TU Dresden, 2004

39. Puchinger J. Combining Metaheuristics and Integer Programming for Solving Cutting and Packing Problem. Dissertation. Vienna University of Technology.

40. Scheithauer G. and Terno J. A Branch-and-Bound Algorithm for Solving One-Dimentional Cutting Sock Problems Exactly. // Applicationes Matematicae 23 (2), 1995. pp. 151-167

41. Alves С. M. M. Cutting and Packing: Problems, Models and Exact Algorithms. Dissertation. Universidade de Minho. 2005

42. Rietz J. and Dempe S. Large Gaps in One-dimentional Cutting Stock Problems. // Discrete Applied Mathematics, Vol.156 (10), 2008.

43. Moretti A. C. et al. Nonlinear Cutting Stock Problem Model to minimize the Number of different Patterns and Objects. // Computational & Applied Mathematics, Vol.27 (1), 2008. pp.61-78

44. Belov G. and Letchford A. N. A Node-Flow Model for ID Stock Cutting: Robust Branch-Cut-and-Price. 2005.

45. Foerster H., Wascher G. Pattern Reduction in One-Dimentional Cutting Stock Problems. // Int. Journal of Production Research, Vol.38(7), 2000. pp.1657-1676.

46. Wongprakornkul S. Round Down Technique for Solving an Integer Linear Programming. // KKU Science Journal vol.36, 2008. pp. 187-198

47. Скобцов Ю.А., Балабанов B.H. К вопросу о применении метаэвристик в решении задач рационального раскроя и упаковки // Вестник Хмельницкого национального университета. — 2008. — Т. 1, N 4. С. 205-217.

48. Подлазова А.В. Генетические алгоритмы на примерах решения задач раскроя // Проблемы управления, № 2. 2008. -сс.57-63.

49. Мухачева Э.А., Мухачева А.С., Валеева А.Ф. Картак В.М. Методы локального поиска оптимума в задачах ортогонального раскрояи упаковки: аналитический обзор и перспективы развития.// Информационные технологии, №5, 2004, приложение, -С. 2-17.

50. Мухачева Э. А. Рациональный раскрой промышленных материалов. Применение АСУ. М.: Машиностроение, 1984. - 176 с.

51. Мухачева А.С., Чиглинцев А.В. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя // Информационные технологии. 2001. - №3. - С. 27-31.

52. Hinterding R., Khan L. Genetic algorithms for cutting stock problems: with and without contiguity. J J Evo Workshops, 1994: 166-186.

53. Liang K., Yao X., Newton C., Hoffman D. A new evolutionary approach to cutting stock problems with and without contiguity. // Computers & Operations Research, 29, 2002: 1641-1659.

54. Holthaus O. Decomposition approaches for solving the integer onedimen-sional cutting stock problem with different types of standard lengths.// European Journal of Operational Research, 141, 2002. pp. 295-312.

55. Ceria S. et all. Set Covering Problem. //In Dell'Amico, F. Maffioli and S. Martello (eds.), Annotated Bibliographies in Combinatorial Optimization.: Wiley and Sons, 1997.- P.415-428.

56. Galinier P. and Heztz A. Solution techniques for the large set covering problem. //Discrete applied Mathematics.— 2007.— vol.155. Issue 3.

57. Caprara A., Fischetti M., Toth P. Algorithms for the set covering problem. //Working Paper, DEIS, University of Bologna — 1998.

58. Capara A. et all. Algorithms for Railway Crew Management. //Mathematical Programming.— 1997.—vol.79.— P.125-141.

59. Дюкова E. В. Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основныемодели. Учебное пособие для студентов математических факультетов педвузов. М.: Прометей, 2003. - 29 с.

60. Дюкова Б.В., Журавлёв Ю.И. Дискретный анализ признаковых описаний в задачах распознавания большой размерности. // Ж. вычисл. матем. и матем. физ. 2000. Т. 40. №8. С. 1264-1278.

61. Дюкова Е.В., Инякин А.С. Задача таксономии и тупиковые покрытия целочисленной матрицы. // Сообщения по прикладной математике. М.: ВЦ РАН, 2001. 28с.

62. Еремеев А. В., Заозерская J1. А., Колоколов А. А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования. ./ Сборник трудов Сибирской конференции по дискретному анализу и исследованию операций. 2000. С. 37-41.

63. Marka S., Cheney С. P., Wang W., Lupke G., Gilligan J., Yao Y., and Tolk N. H. Nonlinear energy-selective nanoscale modifications of materials and dynamics in metals and semiconductors // Tech. Phys., 1999 V 44, pp. 1069-1072.

64. Leary R. H. Global optimization on funneling landscapes // J. Global Optim., 18, 367-383, 2000.

65. Doye J.P.K., Wales D.J., Berry R.S. The effect of the range of the potential on the structure of clusters// J. Chem. Phys, 103, 4234-4249, 1995.

66. Doye J. P. K. and Wales D. J. Structural consequences of the range of the intera-tomic potential: A menagerie of clusters// J. Chem. Soc., Faraday Trans., 93, 4233-4244, 1997.

67. Doye J. P. K., Leary R. H. , Locatelli M., Schoen F. Global Optimization of Morse Clusters by Potential Energy Transformations// INFORMS Journal on Computing 16(4): 371-379, 2004.

68. Grosso A., Locatelli M., Schoen F. A population-based approach for hard global optimization problems based on dissimilarity measures// Mathematical Programming, Vol. 110, 373-404, 2007.

69. Евтушенко Ю.Г., Малкова В.У., Станевичюс А.А. Распараллеливание процесса поиска глобального экстремума// Автоматика и Телемеханика, 46-59, 2007.

70. Посыпкин М. А. Параллельный эвристический алгоритм глобальной оптимизации // Труды ИСА РАН, Т. 32, 2008 г., С. 117-130.

71. Wille L.T. Minimum-energy configurations of atomic clusters new results obtained by simulated annealing // Chem. Phys. Lett., v. 133, pp. 405-410, 1987.

72. Deaven D. M., Но К. M. Molecular-geometry optimization with a genetic algorithm// Phys. Rev. Lett., 75, pp. 288-291, 1995.

73. Deaven D. M., Tit N., Morris J. R., Но К. M. Structual optimization of Lennard-J ones clusters by a genetic algorithm// Chem. Phys. Lett. 1996, v 256, pp. 195-200.

74. Ona O., Bazterra V. E., Caputo M. C., Ferraro M. В., Fuentealba P. and Facelli J. C. Modified genetic algorithms to model atomic cluster structures: CuSi clusters// J. Mol. Struct. (THEOCHEM) 681, 149, 2004.

75. Wolf M. D., Landman U. Genetic algorithms for structural optimization //J. Phys. Chem. A, v. 102, pp. 6129-6137, 1998.

76. Johnston R. L. Evolving better nanoparticles: Genetic algorithms for optimising cluster geometries //(Dalton Perspective) Dalton Transactions, pp. 4193-4207, 2003.

77. Cheng L. et al.A connectivity table for cluster similarity checking inthe evolutionary optimization method, j I Chemical Physics Letters, 389, 2004. pp.309-314.

78. Nguyen Minh Hang et al. A model combining genetic algorithm and simplex method for solving a production expense minimizing problem. // Journal of Computer Science and Cybernetics, No22, Vol.4, Hanoi, 2006. P.319-324 (in Vietnamese).

79. Нгуен M.X. Применение генетического алгоритма для решения задачи планирования производства. // Труды XIII-й Всероссийской конференции "Математическое программирование и приложения", Екатеринбург, Россия, Март 2007. -с. 132-133.

80. Nguyen М.Н. About one application of genetic algorithm in Production planning problem. // Proc. of the 9th Int. Workshop on Сотр. Sci. and Inf. Techn., Ufa, 2007, (Sept. 13-16), Vol.1, pp. 225-229.

81. Нгуен M.X. Применение генетического алгоритма для решения одной задачи планирования производства. / / Динамика неоднородных систем. —М.: Издательство ЛКИ, 2007.— т. 29, вып. 11.—С.160-167.

82. Нгуен М.Х. Двухэтапный метод решения одной задачи раскроя материалов. // Труды XIV Байкальской международной школы-семинара, т. 4 "Приложение методов оптимизации", Иркутск-Северобайкальск, Россия, Июль 2008. —С. 192-202.

83. Нгуен М.Х. Применение генетического алгоритма для задачи нахождения покрытия множества. // Динамика неоднородных систем. —М.:Издательство ЛКИ, 2008 — т. 33, вып. 12 —С.206-219.

84. Beasley J.E. OR-Library: distributing test problems by electronic mail. //Journal of the Operational Research Society.— 1990.—vol.41.— P. 10691072.

85. The Cambridge Cluster Database. http: //www-wales. ch. cam. ас. uk/ CCD. html.

86. Mangasarian O.L. A Newton Method for Linear Programming. // Journal of Optimization Theory and Applications. 2004. V. 121. P. 1-18.

87. Моллаверди Н.И. Методы решения задач линейной оптимизации большой размерности. Диссертация на соискание ученой степени кандидата физико-математических наук. ВЦ РАН. 2005.

88. Голиков А.И., Евтушенко Ю.Г. Метод решения задач линейного программирования большой размерности // ДАН, т.397, N6, 2004. С. 727-732.

89. Evtushenko Yu. G., Golikov A. I., and N. Mollaverdi Augemented La-grangian method for large-scale linear programming problems, j/ Optimization Methods and Software, vol. 20, N4^5, 2005. -pp.515-524.

90. Unger R. The Genetic Algorithm Approach to Protein Structure Prediction Structure and Bonding, vol. 110, 2004. -pp. 153-175.

91. Feltl H. and Raidl R.G. An improved hybrid genetic algorithm for the generalized assignment problem j I Proceedings of the 2004 ACM symposium on Applied computing, 2004. -pp. 990-995.

92. Gunther R. Raidl The multiple container packing problem: A genetic algorithm approach with weighted codings // SIGAPP Appl. Comput. Rev., vol. 7 no.2, 1999. -pp. 22-31.

93. Mahmood A. A Hybrid Genetic Algorithm for Task Scheduling in MultiprocessorReal-Time Systems // Journal of Studies in Informatics and Control, vol.9, no.3, 2000.

94. Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации. // Дискретная математика и ее приложения. М.: Изд-во центра прикладных исследований при механико-математическм факультете МГУ, 2001. - С 84-117.

95. Blum С. and Roli A. Hybrid Metaheuristics: An Introduction.)I Studies in Computational Intelligence, Vol. 114, 2008.

96. Батищев Д. И. Генетические алгоритмы решения экстремальных задач// Учеб. пособие. Воронеж, гос. техн. ун-т; Нижегородский гос. ун-т. Воронеж.— 1995.

97. Iwanmra К., Okaday N., Deguchiz Y. Recent Advancements of a Genetic Algorithm to Solve the Set Covering Problem — 2004.

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

99. Lan G. and DePuy G.W. On the effectiveness of incorporating randomness and memory into a multi-start metaheuristic with application to the Set Covering Problem. // Computers and Industrial Engineering.— vol.51, Issue 3 — 2006.

100. Beasley J.E. and Jornsten K. Enhancing an algorithm for set covering problems. // European Journal of Operational Research. -1992.—No. 58.— R 293-300.

101. Jacobs L.W. and Brusco M.J. A simulated annealing-based heuristic for the set covering problem. // Working paper, Operations Management and1.fprmation Systems Department, Northern Illinois University, Dekalb, IL 60115, USA 1993.

102. Евтушенко Ю. Г. Численный метод поиска глобального экстремума (перебор на неравномерной сетке). Журнал вычислительной математики и математической физики, Т. 11, N 6, 1971. С. 1390-1403.

103. Евтушенко Ю.Г., Ратькин В.А. Метод половинных делений для глобальной оптимизации функции многих переменных // Техническая кибернетика, № 1, 119-127, 1987.

104. Kirkpatrick S., Gelatt С. D. and Vecchi М. P. Optimization by simulated annealing //Science, v.220. pp.617-680, 1983.

105. Schneider J., Morgenstern I., Singer J. M. Bouncing towards the optimum: Improving the results of Monte Carlo optimization algorithms // Phys.Rev. E, v.58, pp. 5085-5095, 1998.

106. Metropolis N., Rosenbluth A. W., Rothenbluth M. N., Teller A. H., Teller E. Equations of state calculations by fast computing machines // J. Chem. Phys., v.21, p. 1087, 1953.

107. Mangasarian O.L. A Finite Newton Method for Classification // Opti-mizat. Meth. and Software. 2002. V. 17. P. 913-930.

108. Голиков А.И., Евтушенко Ю.Г., Моллаверди H. Применение метода Ньютона к решению задач линейного программирования большойразмерности // Ж. вычисл. матем. и матем. физ. 2004. Т. 44. № 9. С. 1564-1573.

109. Голиков А.И., Евтушенко Ю.Г. Нахождение проекции заданной точки на множество решений задач линейного программирования. // Труды института математики и механики УрО РАН. Т. 14. № 2. 2008. С. 33-47.

110. Голиков А.И., Евтушенко Ю.Г. Отыскание нормальных решений в задачах линейного программирования // Ж. вычисл. матем. и матем. физ. 2000. Т. 40. №12. С. 1766-1786.

111. Kanzow С., Qi Н., Qi L. On the Minimum Norm Solution of Linear Programs. // Journal of Optimization Theory and Applications. 2003. V. 116. P.333-345.

112. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.

113. Попов Л.Д. Квадратичная аппроксимация штрафных функций при решении задач линейного программирования большой размерности //Ж. вычисл. матем. и матем. физ. 2007. Т. 47. № 2. С. 206-221.