Оптимізація на загальній множині перестановок зі знаком
A general signed permutation set is introduced. Approaches to optimization on it that are based on its mapping into the Euclidean space are considered. In the scope of the study, properties of the Euclidean combinatorial set and its convex hull - the general signed permutohedron are derived. They in...
Gespeichert in:
| Datum: | 2017 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2017
|
| Schlagworte: | |
| Online Zugang: | https://journal.iasa.kpi.ua/article/view/103892 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Institution
System research and information technologies| _version_ | 1867334280907063296 |
|---|---|
| author | Pichugina, Oksana S. |
| author_facet | Pichugina, Oksana S. |
| author_institution_txt_mv | [
{
"author": "Oksana S. Pichugina",
"institution": "Кафедра прикладной математики Харьковского национального университета радиоэлектроники, Харьков"
}
] |
| author_sort | Pichugina, Oksana S. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2018-04-04T16:37:16Z |
| description | A general signed permutation set is introduced. Approaches to optimization on it that are based on its mapping into the Euclidean space are considered. In the scope of the study, properties of the Euclidean combinatorial set and its convex hull - the general signed permutohedron are derived. They include set’s cardinality, an irreducible H-representation of the polyhedron, its dimension, the vertex and adjacency vertex criteria, and the number of combinatorially nonisomorphic polyhedra of a fixed dimension. The behavior of some classes of functions over the general signed permutation set is investigated. Functional-analytical representations of this set are constructed including polyhedral-superspherical and strict superspherical. Explicit solutions of a linear problem and a projection problem over the general signed permutation set are presented. The research allows applying continuous methods to optimization on the discrete set and obtaining both exact and approximate solutions with accuracy estimates. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2017.4.07 |
| first_indexed | 2025-07-17T10:21:02Z |
| format | Article |
| fulltext |
О.С. Пичугина, 2017
74 ISSN 1681–6048 System Research & Information Technologies, 2017, № 4
УДК 519.85
DOI: 10.20535/SRIT.2308-8893.2017.4.07
ОПТИМИЗАЦИЯ НА ОБЩЕМ МНОЖЕСТВЕ
ПЕРЕСТАНОВОК СО ЗНАКОМ
О.С. ПИЧУГИНА
Аннотация. Введено общее множество перестановок со знаком и рассмотрены
подходы к оптимизации на нем, основанные на погружении в арифметическое
евклидово пространство. В рамках исследования изучены свойства этого евк-
лидового комбинаторного множества и его выпуклой оболочки (общего мно-
гогранника перестановок со знаком), такие как мощность множества, несводи-
мое H-представление многогранника, его размерность, критерии и смежности
вершин, а также количество комбинаторно неэквивалентных многогранников
фиксированной размерности. Исследованы особенности поведения нескольких
классов функций на общем множестве перестановок со знаком. Построен ряд
функционально-аналитических представлений этого множества, включая по-
лиэдрально-суперсферическое и строгое суперсферическое. Приведены явные
решения линейной задачи и задачи проектирования на множество перестано-
вок со знаком. Проведенное исследование позволяет применять непрерывные
методы к оптимизации на дискретном множестве и получать как точные, так и
приближенные решения оптимизационных задач с оценкой точности.
Ключевые слова: комбинаторная оптимизация, полиэдрально-сферическое
множество, перестановки со знаком, общее множество перестановок, бинарное
множество, суперсфера, полиэдрально-поверхностный метод, метод условного
градиента.
ВВЕДЕНИЕ
Задачи дискретной оптимизации на векторах евклидового пространства час-
то возникают в практических и теоретических предметных областях. Так,
среди приложений задачи оптимизации на 0–1-векторах (безусловной буле-
вой задачи) теория графов, экономика, финансы, менеджмент, логистика,
машинное обучение, компьютерная архитектура, задачи размещения, упа-
ковка и раскрой [1, 2]. Оптимизационные задачи на векторах перестановок
применяются в таких областях, как упаковка и раскрой, задачи балансиров-
ки, дизайн микросхем, загрузка суден, оснащение самолетов, геометриче-
ский дизайн, задачи размещения, логистика и т.п. [2–4]. По сравнению
с задачами оптимизации, моделируемыми и решаемыми в метрических про-
странствах, возможность погружения комбинаторного множества в арифме-
тическое евклидово пространство дает множество преимуществ, таких как
возможность учета геометрических особенностей допустимой области, на-
личие нормы, скалярного произведения и т.п. Дискретные множества, по-
зволяющие такое погружение, называют евклидовыми комбинаторными
множествами [5], а научное направление по исследованию свойств погру-
жений и применении их в оптимизационных методах — евклидовой комби-
наторной оптимизацией [3, 4]. В этом направлении исследуются как
свойства евклидовых комбинаторных множеств и их выпуклых оболочек,
так и особенности поведения функций на этих множествах. Свойства мно-
Оптимизация на общем множестве перестановок со знаком
Системні дослідження та інформаційні технології, 2017, № 4 75
жеств, как правило, ложатся в основу комбинаторных оптимизационных
методов типа ветвей и границ, отсечений и т.п. [6] Свойства же функций
обычно составляют основу непрерывных подходов к решению дискретных
задач. Это могут быть релаксационные методы, методы, использующие пе-
реформулировки, и др. [7]
Предлагаемый нами подход к решению задач евклидовой комбинатор-
ной оптимизации состоит в комплексном исследовании свойств допустимых
областей и функций с последующей разработкой методов оптимизации на
их основе [2, 8–11].
Работа посвящена исследованию нового евклидова комбинаторного
множества — общего множества перестановок со знаком — и поведения
некоторых классов функций. Это позволит расширить область применения
оптимизационных методов, приведенных в работах [2–4,8–13], на новый,
достаточно широкий класс задач оптимизации, включающий, в частности,
безусловные булевые задачи.
ПОСТАНОВКА ЗАДАЧИ
Рассмотрим задачу дискретной оптимизации
min)( xf , (1)
)(GEx nk
, (2)
где )(GEnk
— комбинаторное множество n -векторов, сформированных из
мультимножества G ;
:},...,{}g,...,g{ 1
11
kn
k
n
n eeG
, ,0e ; ,0 ;,0
1
1111 nnJieeJigg
k
i
ikkiinii
(3)
и бинарного множества n
nB }1,1{' следующим образом:
} , ,)( :{)( niiiJii
n
nk JiyxzzzRzGE
n
, (4)
')( ),()( nJiinkJii ByyGExx
nn
, (5)
где )(GEnk — общее евклидово комбинаторное множество перестановок
[4, 14] из формулы (3), т.е. множество упорядоченных n -выборок из G , рас-
сматриваемое как множество векторов евклидового арифметического про-
странства, },...,1{ nJn .
Помимо мультимножества (3) используем представление мультимно-
жества G при помощи основы ( )S G , т.е. множества его элементов, упорядо-
ченных по возрастанию, а также первичной спецификации [G] — вектора
кратностей элементов основы [4]: ),...,(=[G] },,...,{)( 11 kk nneeGS .
Множество )(GEnk
назовем общим евклидовым комбинаторным мно-
жеством перестановок со знаком или просто общим множеством переста-
новок со знаком. Как видно из (4), (5), )(GEnk
представляет собой отра-
О.С. Пичугина
ISSN 1681–6048 System Research & Information Technologies, 2017, № 4 76
жение общего множества перестановок )(GEnk , индуцированного неот-
рицательным мультимножеством G , относительно всех координатных
плоскостей. По аналогии с классификацией множеств класса )(GEnk [4]
введем в рассмотрение такие подклассы )(GEnk
:
а) если kn , т.е. G — неотрицательное множество, будем использо-
вать сокращенное обозначение )(GEn
и называть его множеством пере-
становок со знаком из G ;
б) если к тому же nJG , для такого множества будем использовать
сокращенную запись
nE и называть его просто множеством перестановок
со знаком. Отметим, что
nE представляет собой погружение в евклидово
арифметическое пространство группы перестановок со знаком [15], образо-
ванной из группы перестановок первых n натуральных чисел.
Поскольку при исследовании множества )(GEnk всегда можно предпо-
лагать, что 0G , т.е. мультимножество (3) выполнено, то множество
)(GEnk
представляет собой обобщение как общего перестановочного мно-
жества, так и множества
nE . Еще два известные комбинаторные множества,
входящие в класс (4), — это множество размещений с повторениями с цен-
тром симметрии в начале координат: })({}),({ 1112
n
n
nnn
eEeeE (сюда же от-
носится nB и соответствует 11 e ), а также множество
)},0,...,0(),...,0,...,0,{()( 111 eeeCEn (6)
вершин гипероктаэдра [15]
} :{)( conv)( 1111 exRxeCEeCP n
nn , (7)
образующееся при },0{ 1
1 eG n , частным случаем которого являются
)1(nn CPCP — единичный гипероктаэдр и множество его вершин
)1(nn CECE .
Введем в рассмотрение выпуклую оболочку множества (4)
)( conv)( GEG nknk
,
и назовем общим многогранником перестановок со знаком. В частности,
)( conv)( GEG nn
будем называть многогранниками перестановок со
знаком из G , а nn E conv — просто многогранником перестановок со
знаком.
По способу построения )(GEnk
видно, что это множество будет насле-
довать свойства обоих множеств )(GEnk и nB , а также их выпуклых оболо-
чек
nnnknk BBPGEG conv ),( conv)(
Оптимизация на общем множестве перестановок со знаком
Системні дослідження та інформаційні технології, 2017, № 4 77
общего перестановочного многогранника и гиперкуба соответственно. Эти
два класса комбинаторных множеств и многогранников достаточно хорошо
изучены в работах [3–5, 14, 16]. Отметим лишь два из них, которые исполь-
зуем в )(GEnk
— это нейтральность по отношению к знакам и порядку сле-
дования координат элементов. Также свойства )(Gnk
должны объединить
воедино свойства гиперкуба и гипероктаэдра. Как известно [15], эти два
многогранника являются двойственными, в частности количество вершин
nBP и соответственно гиперграней nCP , равно n2 , т.е. экспоненциально
зависит от n . В свою очередь, число вершин nCP , следовательно и количе-
ство гиперграней nBP , зависят от n полиномиально:
n
nnn CPBBP 2 facesvert ; (8)
nBPCECP nnn 2 facesvert . (9)
Данная работа посвящена исследованию свойств задачи (1), (2) с целью
адаптации комбинаторных и непрерывных подходов, приведенных в рабо-
тах [2–4, 8–13], к ее решению. Под исследованием свойств задачи оптими-
зации подразумеваем комплексное исследование алгебро-топологических
свойств допустимой области
)(GEE nk
(10)
и свойств функций на данной области, в частности формирование аналити-
ческих функциональных представлений E . Далее будет обозначено как вы-
явленные особенности задачи (1), (2), применимы к ее решению.
1. АЛГЕБРО-ТОПОЛОГИЧЕСКИЕ СВОЙСТВА )( ),( GGE nknk
Исследуем свойства общих множества и многогранника перестановок со зна-
ком. В качестве иллюстрации справедливости результатов будут использо-
ваны nB , nCE и 0> ),( GGEnk
, а также соответствующие многогранники.
Главным фактором, на наш взгляд, отличия характеристик множеств
класса (10) и многогранников
)(GP nk
(11)
является кратность нулевого элемента в мультимножестве G , поэтому да-
лее вместо (3) будем использовать обозначение
ki
k
i
i
nnn JinnnneeG
,0 ,0 ,0e , :},…,,{0= 01
0
k1
k10 .
Мощность множества E . В первую очередь рассмотрим мощность
)(GEnk
.
Теорема 1. Мощность множества (10) исчисляется по формуле
00 2
!
)!(
C=)(
1
0 nn
k
i
i
n
nnk
n
nn
GE
. (12)
О.С. Пичугина
ISSN 1681–6048 System Research & Information Technologies, 2017, № 4 78
Доказательство. Введем в рассмотрение общее множество перестано-
вок из :G
0.> если),(
;0= если),(
)(
01,
0
nGE
nGE
RGEE
kn
nkn
nk (13)
Выделим три этапа в формировании )(GEnk
, обозначив количество
способов их осуществить 321 ,, NNN соответственно:
На первом этапе фиксируются позиции нулевых элементов
)(GEx nk
, что возможно сделать 0=1
n
nCN способами.
На втором этапе оставшиеся 0nn положительные элементы
}e,…,e{ k1
k1
nn переставляются и это осуществимо
k
i
in
nn
N
1
0
2
!
!)(
= способами.
Наконец, на третьем этапе осуществляется отражение каждого эле-
мента x образованного множества (13) относительно 0nn координатных
плоскостей, соответствующих ненулевым координатам x , в результате чего
каждой точке Ex будет отвечать 02 nn точек E . В целом множество E
увеличится в 023
nnN раз.
По правилу умножения общее количество способов образования эле-
ментов E — 321 NNNN , откуда следует формула (12).
Пример 1. Формула (12) справедлива для упомянутых частных случаев
)(GEnk
— nn CEB , . Поскольку
})1,0({ 1
2
n
nn EСE , (14)
подстановка 10 nn в формулу (12) дает в точности (9): nСE
nn
n 22C 11 . Для nB учтем, что
})1({ n
nn EB , (15)
т.е. 00 n . В данном случае формула (12) обращается в nn
nn n
n
B 22
!
!
C0
и отвечает выражению (8).
Рассмотрим еще один частный случай 0G , когда мощность )(GEnk
также легко найти. В формуле (13) это соответствует
)(GEE nk . (16)
В данном случае
!...!
!
1 knn
n
E , а поскольку 00 n , то при отражениях
относительно всех координатных осей формируется n2 взаимно непересе-
кающихся образов E , т.е.
Оптимизация на общем множестве перестановок со знаком
Системні дослідження та інформаційні технології, 2017, № 4 79
!...!
!
22
1 k
nn
nn
n
EE . (17)
Такое же выражение дает формула (12).
Наконец, в качестве последнего примера рассмотрим частный случай
(10) — множество перестановок со знаком )(GEn
из 0G . Для него за
счет отсутствия кратных элементов G величина (17) принимает максималь-
ное возможное значение !2)( nGE n
n .
Отсюда видно, что ]!2,2[)( nnGE n
nk , причем предельные случаи со-
ответствуют максимальной кратности нулевого элемента ( 10 nn ) и ми-
нимальной кратности нулевого ( 00 n ) и некратным ненулевым элементам.
В данном классе есть множества с количеством элементов, зависящим от
размерности пространства как полиномиально, так и экспоненциально, при-
чем в первую группу попадает единственное множество (6), мощность кото-
рого линейно зависит от n.
H-представление многогранника P . Учитывая структуру E , его
симметрию относительно начала координат и способ построения, удается
решить не только задачу построения системы ограничений многогранника
)(GEnk
, иначе говоря H-представления, но и сформировать несводимое та-
кое представление.
Для того чтобы сформулировать теорему о несводимом H-представлении
многогранника )(Gnk
, воспользуемся таким представлением общего мно-
гогранника размещений [4], а также тем фактом, что )(Gnk
представим
объединением n2 многогранников, комбинаторно эквивалентных некото-
рому многограннику размещений.
Напомним, что общим евклидовым комбинаторным множеством
n -размещений )(GEn
k из мультимножества
11 , ,)(= :}{
JiggGSkgG iiJii , (18)
называется результат погружения в nR множества упорядоченных n -выбо-
рок из мультимножества G , где n , а его выпуклая оболочка )(Gn
k —
это общий многогранник n -размещений, индуцируемый G [4].
Теорема 2 (несводимая система )(Gn
k ) [11]. Несводимое
H-представление многогранника )(Gn
k имеет вид:
n
j
j
j
j Jgx
,
||
1
, 1,,2 1 nnn k ; (19)
||
1
1
j
j
j
j gx , nJ , 1,,2 1 nnnk . (20)
О.С. Пичугина
ISSN 1681–6048 System Research & Information Technologies, 2017, № 4 80
Теорема 3 (несводимая система )(Gnk
). Многогранник (11) задается
несводимой системой неравенств:
1
1
j
jn
j
j gx , nJ , 1,,2 0 nnnnI k . (21)
Доказательство. Сформируем мультимножество (18), дополнив G ну-
лями так, чтобы кратность нулевого элемента достигла n :
},...,,0{},...,,0{}0{ 1
0
0
11
kn
k
nn
nnn
nnn eeggGG
. (22)
Рассмотрим вспомогательное множество 'E — общее множество
n -размещений из G . Его параметры — 02 nnG , 1)( kGS , со-
ответственно )(' 1, GEE n
k .
Запишем систему ограничений многогранника
)(' 1, GP n
k . (23)
По построению одной из его вершин будет начало координат. Адап-
тируя (19) и (20) к (22), (23), получаем несводимую систему ограниче-
ний 'P :
;0x (24)
1
1
j
jn
j
j gx , nJ , 1,,2 0 nnnnI k . (25)
Действительно, учитывая (22), ограничения подсистемы (20) приобре-
тают вид
1
1
j
jn
j
j gx . Согласно теореме 2 избыточными являются:
а) неравенства (19) союзов n,2 , в результате чего остается только союз
(24); б) неравенства (20) союзов kn,2 и 1,,2 nnnk
1,,2 0 nnnnk . Итак, (24), (25) — несводимая линейная система мно-
гогранника 'P .
Перейдем к многограннику P . Подобно множеству n
nk RGE
)( он
образуется из многогранника nRP его отражением относительно всех
координатных плоскостей, в результате чего подсистема (25) преобразуется
в модульное ограничение (21), а (24) исчезает. При этом система (21) по-
прежнему не содержит ни одного избыточного ограничения, поскольку
в противном случае за счет симметрии это бы означало наличие избыточных
ограничений в системе (25).
Теорема доказана.
Пример 2. Продемонстрируем результат теоремы 3 на примере тех же
множеств, что и в примере 1. Для nB множество I в системе (21) имеет вид:
nnnnnnnnI ,21,0,21,,2 01 , соответственно (21) приоб-
Оптимизация на общем множестве перестановок со знаком
Системні дослідження та інформаційні технології, 2017, № 4 81
ретает форму 1j nx , j J , а задает гиперкуб со стороной 2 — это в точ-
ности nBP .
Для nCE множество I упрощается до 1,,2 01 nnnnI , а система
(21) приобретает вид 1
1
n
j
jx , что соответствует (7) и задает многогранник
nPE .Третье множество — ),(GEnk
0>G . В данном случае имеем
kk nnnnI ,21,0,2 . Соответственно набор гиперграней многогран-
ника определяется кратностью элемента ke . Так, если 1kn , то I и
система (21) приобретает вид:
1
1
j
jn
j
j gx , nJ ; 1,11,11,2 nnnn . (26)
В частности )(Gn
задается несводимой системой (26). Если же ke —
кратный, т.е. 1kn , несводимая система )(Gn
:
1
1
j
jn
j
j gx , nJ , nnk ,1}1{ .
Размерность P .
Лемма 1. Многогранник )(Gnk
полномерный, т.е.
nGnk )( dim . (27)
Доказательство. Рассмотрим гиперкуб 2
n n na ,a , где
1
1 n
i
i
a g
n
.
По условию (3) он не вырожден в точку, следовательно является полномер-
ным, как и любой другой гиперкуб. Поскольку }),({)( 2
nnn
n aaG ,
многогранник )(Gnk
также полномерный и условие (27) выполнено.
Сферическая расположенность E . Сферически расположенным на-
зываем произвольное множество, вписанное в сферу [8]: )(aSE r , где
)(aSr — гиперсфера радиуса r с центром в точке nRa .
Лемма 2. Множество )(GEnk
— сферически расположенное:
2/1
1
2= ),()(
n
i
irnk grSGE 0 , (28)
при этом описанная сфера — единственная (здесь точка 0 — начало коор-
динат).
Доказательство. Каждая точка )(GEnk
имеет координаты, модули ко-
торых образуют мультимножество G , т.е.
Rm
n
i
m
i
n
i
m
i gx
11
. (29)
О.С. Пичугина
ISSN 1681–6048 System Research & Information Technologies, 2017, № 4 82
В частности, при 2m имеем:
n
i
i
n
i
i gx
1
2
1
2 , (30)
т.е. точки E равноудалены от начала координат на расстояние r , заданное
формулой (28), т.е. E лежит на )0(rS , следовательно является сферически
расположенным. Эта описанная вокруг E сфера единственна вследствие
леммы 1, поскольку )(Gnk
— полномерный.
Е-полиэдрально-сферическое множество. Конечное множество назы-
вается полиэдрально-сферическим [8], если оно образуется в результате пе-
ресечения некоторых гиперсферы S и многогранника P :
SPE . (31)
Полиэдрально-сферическим представлением множества E называется
система его ограничений, включающая H-представление многогранника P
и уравнение гиперсферы S [10]. Такое представление E неизбыточно, если
в нем участвует несводимое H-представление многогранника P [10].
Для множества (10) условие (31) очевидно выполнено, при этом S за-
дается (30), а P — многогранник (11). При этом, поскольку теоремой 3 ус-
танавливается несводимое H-представление многогранника P , справедлива
следующая лемма.
Лемма 3. Множество )(GEnk
— полиэдрально-сферическое и его не-
избыточное полиэдрально-сферическое представление задается системой
ограничений (21) и (31).
Критерий вершины P . Из условия E и (31) следует, что
PE vert , т.е. некоторые вершины P могут лежать вне сферы S . Однако в
случае, если P представляет собой выпуклую оболочку конечного сфериче-
ски расположенного множества, будет, очевидно, выполнено и обратное
включение PE vert . Соответственно
EPE convvert vert . (32)
Множества вида (32) называются вершинно расположенными [9, 12].
Это довольно широкий класс комбинаторных множеств, в частности, вер-
шинно расположенными являются nB , )(GEnk , )(,1 GEn
kn , )(2 GEn
и другие
комбинаторные множества [11]. Для таких множеств критерием вершины
является условие принадлежности этому множеству. Установить вершин-
ную расположенность, как правило, достаточно сложно [4, 16]. Однако для
полиэдрально-сферических множеств эта задача легко разрешима, посколь-
ку сфера является множеством крайних точек соответствующего шара, т.е.
ни одна из точек сферы не может быть выражена выпуклой линейной ком-
бинацией других точек сферы. Это же справедливо и для любого подмноже-
ства точек на сфере, в частности, для произвольного полиэдрально-
Оптимизация на общем множестве перестановок со знаком
Системні дослідження та інформаційні технології, 2017, № 4 83
сферического множества E . Таким образом E является множеством край-
них точек своей выпуклой оболочки, представляющим собой многогранник,
т.е. множеством его вершин.
Таким образом, для )(GEnk
в силу леммы 3 справедливо следующее
утверждение.
Лемма 4 (критерий вершины )(Gnk
). Множество )(GEnk
является
вершинно расположенным, т.е. ).(vert )( GGE nknk
Критерий смежности вершин P . Прежде чем перейти к исследова-
нию вопроса о смежности вершин )(Gnk
, выделим два случая в соответст-
вии с множеством (13):
Случай 1, когда все элементы G положительны, т.е. 0=0n и выполне-
но условие (16). Соответственно основа G имеет вид:
kJiieGS }{)( . (33)
Случай 2, когда среди элементов G есть нулевые, соответственно
0>0n , т.е.
)(,1 GEE kn
; (34)
}{ ,0e где ,}{},...,,0{)( 0
01 0
kkJiik JJeeeGS
k
. (35)
Будем рассматривать их последовательно и сформулируем критерий
смежности вершин в зависимости от рассматриваемого случая. Одновре-
менно установим и степень регулярности d вершины )(Gnk
, т.е. количе-
ство вершин, смежных с ней.
Теорема 4 (критерий смежности вершин )(Gnk
и степень их регу-
лярности). Если выполнено (16), )(GEx nk
смежные к ней вершины
)(Gnk
образуются из x заменой максимум двух переменных: заменой в x
двух координат ji xx , , абсолютные значения которых являются последова-
тельными элементами основы G , значениями ijji xxxx sgn ,sgn (спо-
соб 1) либо сменой на противоположный знак координаты x , равной по мо-
дулю 1e (способ 2).
При выполнении (34) смежные к )(GEx nk
вершины )(Gnk
отлича-
ются от x не более чем двумя координатами и формируются из нее либо
способом 1, либо транспозицией нулевой координаты и координаты с абсо-
лютным значением 1e с последующей сменой знака ненулевой координаты
на противоположный (способ 3).
В случае 1 степень регулярности произвольной вершины )(Gnk
зада-
ется формулой
1
1
11
k
i
iinnnd ; (36)
О.С. Пичугина
ISSN 1681–6048 System Research & Information Technologies, 2017, № 4 84
в случае 2:
1
1
1102
k
i
iinnnnd . (37)
Доказательство. Сначала сформируем множество смежных вершин многогран-
ника Gnk
для точек ,E затем распространим результат на все множество )(GEnk
.
Введем обозначение для множества смежных вершин некоторого многогран-
ника и их числа среди точек vertM :
xyMyxNM :, ,
)()( ,, xNxd MM . Так, например, )(, xN PE , )(, xd PE соответствует искомым
множеству и степени вершины )(Gnk
, )(
,
xN
PE включает только смежные вер-
шины P среди точек E и т. п.
Введем также в рассмотрение многогранник E convP , представ-
ляющий собой общий перестановочный многогранник.
Случай 1. Рассмотрим произвольную точку Ex . Во множестве )(, xN PE
выделим две части:
)()()(
,\,, xNxNxN
PEEPEPE . (38)
Первая часть — это множество вершин многогранника P , смежных с
x — )()(
,,
xNxN
PEPE , вторая — оставшиеся смежные вершины. В
соответствии с критерием смежности вершин общего перестановочного
многогранника [16], )(
,
xN
PE будет включать перестановки, образованные
из x транспозицией последовательных элементов основы )(GS вида (33),
т.е. 1 ii ee -транспозицией )( 1 kJi . Их количество определяется по
формуле [4]
1
1
1,
)(
k
i
iiPE
nnxd . (39)
Для формирования )(
,\
xN
PEE воспользуемся критерием вершины
общего многогранника размещений [4], учитывая тот факт, что x является
не только вершиной 'P , но и многогранника 'P вида (23). В )(',' xN PE выде-
лим также две части:
)()()(
','\,',' xNxNxN
PEEPEPE , (40)
последняя из которых содержит точки, образованные из x заменой наи-
меньшей координаты 1e - нулем. Количество таких смежных вершин будет
равно кратности 1e : 1','\
)( nxd
PEE
. Продлив ребра )(],,[
,'\
xNyyx
PEE
симметрично точке y , из x будет сформировано 1n точек E путем смены
знака одной координаты 1e . Это и будет искомое множество )(
,\
xN
PEE .
Оптимизация на общем множестве перестановок со знаком
Системні дослідження та інформаційні технології, 2017, № 4 85
Соответственно
1,\
)( nxd
PEE
. (41)
Объединяя эти результаты, получаем, что в случае 1: Ex множе-
ство )(, xN PE образуется из x транспозицией соседних элементов основы
G либо заменой знака минимальной координаты на противоположный.
Из выражения (40) следует:
)()()(
','\,',' xdxdxd
PEEPEPE . (42)
Соответственно подстановка (39), (41) приводит к тому, что степень ре-
гулярности вершины x равна
1
1
11, )(
k
i
iiPE nnnxd . Это также справедли-
во для оставшихся точек ,E т.е. в этом случае формула (36) верна.
Пусть теперь x — произвольная точка E . Помимо абсолютных значе-
ний координат x при построении )(, xN PE будут учитываться и знаки коор-
динат x . Для x и смежных с ней вершин эти знаки будут совпадать, за ис-
ключением максимум одной координаты, равной по модулю 1e .
Итак в случае 1, учитывая симметрию E , для вершины x многогран-
ника P критерий смежности выглядит следующим образом: Ex множе-
ство )(, xN PE включает точки, образованные из x одним из двух способов:
a) способом 1 , т.е. заменой в x двух координат jixx ji ,, , абсолютные
значения которых являются последовательными элементами основы G вида
(33), значениями ijji xxxx sgn ,sgn соответственно; б) способом 2, т.е.
сменой знака координаты, равной по модулю 1e , на противоположный. При
этом степень регулярности произвольной вершины P определяется по фор-
муле (36).
Случай 2. Снова рассмотрим точку Ex . Множество смежных к ней
вершин также представим в виде (38) . Однако в отличие от случая 1 в силу
(34) формула (39) преобразуется к виду
1
0
1,
)(
k
i
iiPE
nnxd . (43)
Что касается )(
,\
xN
PEE , то поскольку минимальная координата x
равна нулю, )(
',
xNy
PE ребра ],[ yx вырождаются в точку x , от кото-
рой расходятся ребра как в область nR , так и в области
} ,0 ,0 :{,
0 ijxxRxR jj
nin , }0 :{ in
x xJiIi . (44)
Количество таких ребер xIi , идущих в inR ,
0 , будет 1n и будут обра-
зовываться из x 10 e -транспозицией ji xx , -координат, где xIj , с по-
следующей сменой знака ix на противоположный. Поскольку, в соответ-
О.С. Пичугина
ISSN 1681–6048 System Research & Information Technologies, 2017, № 4 86
ствии с кратностью нулевого элемента количество областей вида (44) — 0n ,
общее количество образованный вершин в смежных к nR областях:
10,\
)( nnxd
PEE
. (45)
Подставляя (43), (45) в формулу (42), получаем 10, )( nnxd PE
1
0
1
k
i
iinn , т.е. Ex верна формула (37). Вследствие симметрии E и P
формула (37) будет верна для всех точек E , при этом в случае 2 Ex
критерий смежности вершин многогранника P излагается следующим об-
разом: множество )(, xN PE включает точки, образованные из x одним из
двух способов: a) заменой в x двух координат jixx ji ,, , абсолютные зна-
чения которых являются последовательными элементами основы G вида
(35), значениями ijji xxxx sgn ,sgn соответственно, т.е. при помощи спо-
соба 1; б) способом 3, т.е. транспозицией нулевой координаты и координа-
ты, равной по модулю 1e , с последующей сменой знака ненулевой коорди-
наты на противоположный: 1 ,0 :, exxxx jiji ; новые значения этих
координат 0 ,)(sgn 1 jji xexx . Степень регулярности вершин P опре-
деляется по формуле (37).
Теорема доказана.
Пример 3. Проиллюстрируем теорему 3 на примере тех же множеств,
что и в примерах 1, 2.
Множества '
nB и )( ),( GEGE nnk
для 0G соответствуют случаю 1.
В частности, для nBP , учитывая (15), }1{ nG , следовательно формула (36)
обращается в nnd 1 . Поскольку E вырождено в точку, смежных вер-
шин, образованных перестановкой координат, не будет и все смежные вер-
шины будут формироваться только способом 2, соответствующим смене
знака одной координаты на противоположный. Для )(GEn
формула (36)
преобразуется в nd
n
i
1
1
11 , а критерий смежности остается без измене-
ний. Как и ожидалось, многогранники )( , GBP nn
— простые, т.е. степень
регулярности их вершин совпадает с размерностью многогранников.
Наконец, множество nCE соответствует случаю 2. Учитывая (14),
в данном случае }1,0{ 1 nG , в соответствии с формулой (37) имеем:
)1(22 10 nnnd .
Так, например, для 3n 4)13(2 d и в соответствии с критерием
смежности вершин, например, для вершины )0,0,1(x половина смежных
вершин — )0,1,0(1 x , )0,1,0(2 x будет сформирована способом 1, ос-
тавшаяся половина — )0,1,0(3 x , )1,0,0(4 x — способом 3 из предыду-
щих двух точек.
Оптимизация на общем множестве перестановок со знаком
Системні дослідження та інформаційні технології, 2017, № 4 87
Полученные результаты подтверждают известные свойства ,nBP nCP ,
в частности, что вершины гиперкуба имеют n смежных, а для вершины ги-
пероктаэдра все оставшиеся вершины — смежные с нею, за исключением
диаметрально противоположной.
Число комбинаторно неэквивалентных многогранников )(Gnk
.
Прежде чем перейти к исследованию вопроса о комбинаторной эквивалентно-
сти многогранников класса )(Gnk
, приведем некоторые определения [16].
Графом H многогранника , )( HH , называется граф, образо-
ванный вершинами и ребрами : )edges,vert (),( HH EVH .
Графы ),( HH EVH и ),( HH EVH изоморфны, если существует
биекция между HH VV , : HH VV
такая, что произвольные две вершины
графа H — смежные тогда и только тогда, когда соответствующие две
вершины графа H — смежные:
212122112121 ,,:)(),( :, vvVvvvvvvvvVvv HH .
Многогранники называются комбинаторно эквивалентными, если их
графы изоморфны.
Введем обозначение nM для числа комбинаторно неэквивалентных
многогранников )(Gnk
размерности n . Произведем предварительную
оценку числа nM . Так, из системы неравенств (24) видно, что число гипер-
граней P определяется комбинациями чисел knn ,0 . Учитывая, что
000 , , ZnZnnnn kk , получаем
2
1 nnn CMM . (46)
Точное значение nM определим, учитывая то, что количество смежных
вершин x и множество смежных вершин определяются первичной специ-
фикацией G .
Итак, докажем следующую теорему.
Теорема 5 (число комбинаторно неэквивалентных общих многогран-
ников перестановок со знаком). Для фиксированного n число nM комбина-
торно неэквивалентных многогранников )(Gnk
:
12 n
nM . (47)
Доказательство. Случаи 1, 2 рассмотрим по отдельности, обозначив
соответствующие числа комбинаторно неэквивалентных многогранников
размерности n — 21 , nn MM .
Начнем со случая 1: число различных векторов первичных специфика-
ций вида ),...,(=][ 1 knnG , удовлетворяющих nn
k
i
i
1
, nk , равно числу
композиций числа n , следовательно 11 2 n
nM .
О.С. Пичугина
ISSN 1681–6048 System Research & Information Technologies, 2017, № 4 88
Для случая 2:
),...,,(=][ 10 knnnG , (48)
nn
k
i
i
0
, 1,0 kn . Поскольку каждой композиции длины 1k ставится
в соответствие первичная спецификация (48), все компоненты которой не-
нулевые, условие 10 n будет выполнено всегда. Для определения 2
nM из
числа композиций числа n достаточно отнять единицу, поскольку в случае
)(=][ nG не выполняется 1k . Итак, 12 12 n
nM . Учитывая, что
21
nnn MMM , окончательно имеем формулу (47).
Теорема доказана.
Пример 4. Для 3n оценка (46) 62
4
'
33 CMM близка к точному
значению (47) — 7123
3 M . Для иллюстрации теоремы 4 в таблице
приведены различные 3-мультимножества, соответствующие семи возмож-
ным векторам первичной спецификации, а также кратности минимального и
максимального элементов и степени вершин многогранников. Как видно,
первые 4 мультимножества соответствуют случаю 1, остальные 3 — слу-
чаю 2. Как было отмечено, первым признаком комбинаторной неэквива-
лентности является различие комбинаций knn ,0 . Нетрудно видеть, что эти
параметры совпадают только у пары 31,GG , т.е. в точности 6'
3 M комби-
наций knn ,0 выявлено. Смотрим второй признак — степень регулярности
вершин: для 1G 3d , в то время, как для 3G .4d Таким образом, даже
вот такой беглый анализ показывает, что все многогранники )(3 ik G ,
7Ji — не комбинаторно эквивалентны.
Многогранники )(3 ik G
Мультимножество g1 g 2 g 3 n0 nk r
G1 1 2 3 0 1 3
G 2 1 2 2 0 2 3
G 3 1 1 2 0 1 4
G 4 1 1 1 0 3 3
G 5 0 1 2 1 1 3
G 6 0 1 1 1 2 4
G7 0 0 1 2 1 4
Все семь трехмерных многогранников данного класса показаны на
рис. 1–7. Видно, что некоторые из них формируются из гиперкуба отсече-
ниями его вершин, остальные — вершин и ребер, в результате чего образу-
ются вершины со степенью регулярности 3 и 4. Простыми многогранниками
в данном семействе являются, помимо упомянутых '
33 , B , еще два —
)( 232 G , )( 53 G .
Оптимизация на общем множестве перестановок со знаком
Системні дослідження та інформаційні технології, 2017, № 4 89
Пример 5. Для 4n формула (46) дает оценку 102
5
'
4 CM числа
некомбинаторно эквивалентных многогранников среди общих многогран-
ников перестановок со знаком размерности 4, в то время, как точное их ко-
личество согласно (47), в полтора раза больше: 15124
4 M .
2. СВОЙСТВА ФУНКЦИЙ НА )( ),( GGE nknk
Свойства линейных и некоторых нелинейных функций на множестве E ви-
да (10) и многограннике P вида (11) рассматривались в разделе 1. Так
H-представление ,P приведенное в теореме 3, описывает поведение линей-
ных функций как на ,P так и на E . В то же время это линейное аналитиче-
ское (или функциональное в терминах [9–11]) представление E в компакт-
ной форме (21) также демонстрирует поведение на E и P нелинейных
функций, представляющих собой суммы модулей некоторых координат и
показывает пределы изменения их значений.
Уравнение (30) также указывает, что квадратичная функция
n
i
ixxh
1
2)(
принимает постоянное значение на E , а (29) демонстрирует выполнение
этого же свойства для целого семейства функций
Рис. 1. 313 )(G Рис. 2. )( 232 G
Рис. 3. )( 332 G Рис. 4. 3431 )( BPG
Рис. 5. )( 332 G Рис. 6. )( 632 G Рис. 7. 3732 )( CPG
О.С. Пичугина
ISSN 1681–6048 System Research & Information Technologies, 2017, № 4 90
0
1
,)(
Rmxxh
n
i
m
im . (49)
Поверхность
n
i
m
im
n
m xxhRxS
1
)(: задает в пространстве так
называемую суперсферу [17]. В этих обозначениях (29) представляется
в виде
0 , RmSE m , (50)
и свидетельствует о том, что E вписано не только в сферу, но и лежит на
целом семействе (50) суперсфер. В зависимости от параметра деформации
2
m
суперсферы могут быть как выпуклые ( 1m ), так и невыпуклые
( )1,0(m ); как гладкие при ),2[ m , так и негладкие в противном случае.
Значениям ,1m соответствуют кусочно-линейные поверхности гиперок-
таэдра
n
i
in gCP
1
и гиперкуба }),({conv}),({ 22
n
k
n
k
nn
k
n
k
n
ggEgg . Соот-
ветственно можем судить о поведении целого класса функций (49) на E .
Отметим также, что при ),2[ m функция )(xhm сильно выпуклая,
при mm ),2,1[ — строго выпуклая.
Справедливо следующее обобщение представления (21), (30).
Лемма 5. ),1( m множество )(GEnk
задается несводимым функ-
циональным представлением (21),
n
i
m
i
n
i
m
i gx
11
. (51)
Представление (21), (51) — гладкое при ),2[ m и принимает фор-
му (21),
n
i
m
i
n
i
m
i gx
11
22/ )( . (52)
Как видно, найдено множество полиномиальных функциональных
представлений множества E , включающих систему ограничений P , число
которых неполиномиально. Возникает вопрос, существуют ли функцио-
нальные представления E с меньшим числом компонент. Ответ на этот во-
прос положительный и основан на следующей теореме.
Теорема 6 [18]. Система полиномиальных уравнений
, ,
11
n
n
i
j
i
n
i
j
i Jjgx
(53)
является функциональным представлением общего множества перестано-
вок, индуцированного мультимножеством },...,{ 1 nggG .
Аналитические представления в виде систем уравнений, таких как (53),
называем строгими функциональными представлениями множеств. Геомет-
Оптимизация на общем множестве перестановок со знаком
Системні дослідження та інформаційні технології, 2017, № 4 91
рически они представляют множество как пересечение некоторых поверх-
ностей.
На основании теоремы 6 сформируем строгое представление E , при-
меняя ее к мультимножеству (3).
Лемма 6. Система уравнений
n
n
i
j
i
n
i
j
i Jjgx
,
11
(54)
задает строгое функциональное представление общего множества переста-
новок со знаком из мультимножества вида (3).
Доказательство. В данном случае система (53) задает общее множест-
во перестановок E вида (13). Поскольку E образуется отражениями E
относительно всевозможных координатных плоскостей, в пересечении су-
персфер (54) образуется E и только оно.
Еще одно представление E легко получить из теоремы 6, применяя ее
к E и осуществляя затем замену переменных niiii Jiggxx , , 22 .
Лемма 7. Система полиномиальных уравнений
, ,
1
2
1
2
n
n
i
j
i
n
i
j
i Jjgx
(55)
является строгим функциональным представлением множества )(GEnk
, ин-
дуцированного мультимножеством (3).
Преимуществом представления (55) по сравнению с (54) является глад-
кость, отсутствие модулей в записи и тот факт, что она включает сильно вы-
пуклые функции.
Важным свойством общего множества перестановок является тот факт,
что произвольная перестановка координат его элементов не выводит за пре-
делы этого множества, вследствие чего все симметричные функции прини-
мают постоянное значение на )(GEnk . Нетрудно заметить, что это свойство
сохраняется при переходе от )(GEnk к )(GEnk
. Кроме этого, смена знаков
произвольного количества переменных элементов )(GEnk
приводит к фор-
мированию точки этого же множества. Итак, имеем следующее утвержде-
ние.
Лемма 8. Произвольная функция
RGEf nk )(: такая, что: а) )(xf —
симметричная; б) )(xf не изменяет значения при замене знаков произволь-
ного числа координат, принимает на )(GEnk
постоянное значение )(GA ,
определяемое элементами G : )()(
)(
GAxf
GEnk
.
Замечание 1. Из леммы 8 следует, что nJj
)(1
))1((ln
GE
n
i
j
i
nk
x
n
i
j
i
GE
g
nk 1)(
))1((ln , или, например,
n
i
j
i
GE
n
i
j
i gx
nk 1)(1
sinsin .
О.С. Пичугина
ISSN 1681–6048 System Research & Information Technologies, 2017, № 4 92
Однако вопрос, задает ли семейство ,))1((ln))1((ln
1)(1
n
i
j
i
GE
n
i
j
i gx
nk
nJj или n
n
i
j
i
GE
n
i
j
i Jjgx
nk
,sinsin
1)(1
множество )(GEnk
, требует
отдельного изучения. Если он решен положительно, т.е. когда решена зада-
ча построения функционального представления множества, возникают но-
вые задачи — о неизбыточности функциональных представлений, об опти-
мальном выборе такого представления при решении задачи (1), (2). Так
например, представление (53), как правило, неизбыточное представление
)(GEnk . В то же время, в работе [10] установлено, что оно избыточное,
поскольку для некоторых G , например, })1,0({ 1
2
n
nE полностью определя-
ется двумя последовательными компонентами (53). Переходя к представле-
ниям рассматриваемого множества )(GEnk
, можно сказать, что как (54), так
и (55) — в отдельных случаях сводимы, поскольку })1,0({ 1
2
n
nE будет со-
ответствовать 1})1,0({ 1
2 n
n
n CEE , определяемое любыми двумя компо-
нентами этих представлений [10]. То же касается множества '
2 })1({ n
n
n BE
[8, 10].
Отметим еще одну особенность E — простоту решения линейной за-
дачи и, как следствие, проектирования на E .
Итак, множество E называется хорошо описанным (a well described set)
[19], если линейная задача )( cE,LP : xx T
E
Elin c argmin, эффективно разрешима.
Структура )(GEnk
позволяет легко записать решение этой задачи.
Лемма 9. Если ,=}{ :)( nJjjJjj Jii
nn 1 ,
1
nii Jjcc
jj
, то
nji
GElin
i Jjgx
j
nk
j
,)c(sgn
)(,
. (56)
Как видно, решение ))(( c,GELP nk
сводится к простому упорядочива-
нию коэффициентов целевой функции и присваиванию (56), т.е. )(GEnk
—
хорошо описанное.
Теорема 7 [2]. Если E — хорошо описанное полиэдрально-сферическое
множество, то задача поиска проекции произвольной nRy на E эффек-
тивно разрешима и сводится к ),( yaELP , где a — центр описанной во-
круг E сферы.
Применяя теорему 7 к (10) и учитывая формулу (28), получаем
yx E
P Pr , (57)
т.е. решение задачи ),(),( yELPyELP 0 — это решение задачи
xT
E
c maxarg . Адаптируем лемму 9 к этому случаю.
Оптимизация на общем множестве перестановок со знаком
Системні дослідження та інформаційні технології, 2017, № 4 93
Лемма 10. Решение задачи (57) на )(GEnk
для произвольной nRy
nji
P
i Jjgyx
jj
,)(sgn ,
где 1 , ,= }{:)(
1
niinJjjJjj JjyyJii
jjnn
.
Наконец, последнее свойство, которое приводим, — это возможность
упрощенной проверки произвольной точки nRx на принадлежность
)(Gnk
. Оно основано на лемме 9 и свойствах функций
j
jx , nJ на
этом многограннике.
Лемма 11. Точка )(Gx nk
тогда и только, когда она удовлетворяет
системе ограничений:
j
j
jn
j
j
in gx
j
1'
1'
1'
1'
, }1,,2{\ 0 nnnnJj kn .
3. ПОДХОДЫ К РЕШЕНИЮ ЗАДАЧИ (1), (2)
Решение задачи поиска функционального представления дискретного мно-
жества E позволяет эквивалентно переформулировать (1), (2) в виде непре-
рывной задачи (1) с дополнительными ограничениями
ki Jixf ,0)( ; (58)
kki JJif \ ,0 ' , (59)
где ' ,0)( ki Jixf — компоненты функционального представления E . В
частности, строгие суперсферические представления (54) и (55) позволяют
свести к классической задаче (1), (58) на условный экстремум.
Вершинная расположенность E позволяет свести исходную задачу к
оптимизации выпуклой функции, а именно к задаче
min)( xF , (60)
)(xF — выпуклая на выпуклом компакте EK , (61)
при ограничениях (58), (59). Эквивалентность задач (58)–(61) и исходной
обеспечивается тем, что ),()( xfxF
E
т.е. )(xF — выпуклое продолжение
)(xF с E на K [9, 12]. При этом )(xF часто может быть найдена с помо-
щью компонент строгих представлений E в форме )()( xfxF
),(
1
xfi
k
i
i
ki JiR , [2, 9, 10].
Суперсферические представления E позволяют также применять к (1),
(2) метод множителей Лагранжа, штрафные методы и их комбинации [20].
При этом выпуклость )(xF позволяет давать и уточнять нижние оценки,
О.С. Пичугина
ISSN 1681–6048 System Research & Information Technologies, 2017, № 4 94
а проектирование на множество E в ходе всего итерационного процесса —
получать и последовательно уточнять верхние оценки.
Использование в качестве ограничений (58), (59) полиэдрально-
суперсферических представлений (21), (52) позволяет комбинировать раз-
личные релаксации исходной задач, в том числе и выпуклые, — полиэдраль-
ную — min)(
P
xF , суперсферическую min)(
mS
xF и супершаровую
min)(
mC
xF , где mS — строго выпуклая суперсфера, mm SC conv . Таким
образом, к (1), (2) применимы точные и приближенные (с оценкой точности)
полиэдрально-поверхностные методы [2].
Способ задания E через )(GEnk , nB позволяет легко генерировать
его элементы и предложить различные эвристические подходы к решению
(1), (2), в том числе генетические алгоритмы [21]. Для последних полезным
является простота проектирования на E точек, образованных в результате
скрещивания. Критерий смежности вершин P позволяет использовать схе-
мы спуска [22] и комбинировать с случайным поиском в метаэвристиках.
Оценку точности результата и здесь при желании можно получить c помо-
щью полиэдральной или супершаровой релаксаций.
В заключение несколько слов об упомянутых выпуклых релаксациях.
Несводимая система P позволяет точно определить, полиномиальным или
неполиномиальным числом ограничений задается многогранник. В послед-
нем случае оперирование всей системой многогранника невозможно при
решении реальных задач, поэтому для решения полиэдральной релаксации
используются специальные приемы типа метода последовательного подсое-
динения ограничений [4], основанные на применении леммы 11 и позво-
ляющие использовать незначительную часть ограничений P . В то же время
тот факт, что E хорошо описанное, позволяет эффективно решать полиэд-
ральную релаксацию модифицированным методом условного градиента [2].
ВЫВОДЫ
Проведено исследование свойств общих множества и многогранника пере-
становок со знаком, в частности установлены: мощность множества )(GEnk
и порядок несводимого H-представления многогранника )(Gnk
, размер-
ность, критерии вершин и смежности вершин )(Gnk
, а также количество
комбинаторно неэквивалентных многогранников фиксированной размерно-
сти. Представлена иллюстрация многогранников )(3 Gk
всевозможных
форм. Для множества )(GEnk
приведен ряд функциональных представле-
ний, включая полиэдрально-суперсферическое и строгое суперсферическое,
а также приведены явные решения линейной задачи и задачи проектирова-
ния на это множество. Перечислены оптимизационные методы, примени-
мость которых стала возможной в результате исследованных свойств
)(GEnk
и )(Gnk
.
Оптимизация на общем множестве перестановок со знаком
Системні дослідження та інформаційні технології, 2017, № 4 95
ЛИТЕРАТУРА
1. Kochenberger G. The unconstrained binary quadratic programming problem: a sur-
vey / G. Kochenberger, J.-K. Hao, F. Glover etc // Journal of Combinatorial Op-
timization. — 2014. — N 1. — P. 58-81. DOI: 10.1007/s10878-014-9734-0.
2. Pichuginа O. Convex extensions and continuous functional representations in opti-
mization, with their applications / O. Pichuginа, S. Yakovlev // J. Coupled Syst.
Multiscale Dyn. — 2016. — Vol. 4(2) . — P. 129–152. DOI:
10.1166/jcsmd.2016.1103
3. Стоян Ю.Г. Математические модели и оптимизационные методы геометриче-
ского проектирования / Ю.Г. Стоян, С.В. Яковлев. — К. : Наук. думка,
1986. — 268 с.
4. Стоян Ю.Г. Теорія і методи евклідової комбінаторної оптимізації / Ю.Г. Стоян,
О. О. Ємець. — К. : Ін-т системн. дослідж. освіти, 1993. — 188 с.
5. Стоян Ю.Г. Некоторые свойства специальных комбинаторных множеств (Пре-
принт АН УССР/Институт проблем машиностр.; 85) / Ю.Г. Стоян. — Харь-
ков, 1980. — 22 с.
6. Taha H. A. Integer Programming: Theory, Applications, and Computations. Edited
by J. William Schmidt / H.A. Taha. — New York: Academic Press, 2014. — 392 p.
7. Sherali H.D. A reformulation-linearization technique for solving discrete and con-
tinuous nonconvex problems / H.D. Sherali, W.P. Adams, P.M. Pardalos
(eds.).— Dordrecht: Kluwer Academic Publishers, 1999. — 518 p. DOI:
10.1007/978-1-4757-4388-3.
8. Pichuginа O. Continuous Approaches to the Unconstrained Binary Quadratic Prob-
lems / O. Pichuginа, S. Yakovlev // Mathematical and Computational Ap-
proaches in Advancing Modern Science and Engineering, Edited J. Bélair et al.
— Springer, Switzerland. — 2016. — P. 689–700. DOI: 10.1007/978-3-319-
30379-6_62.
9. Pichugina O.S. Continuous Representations and Functional Extensions in Combina-
torial Optimization / O.S. Pichugina, S.V. Yakovlev // Cybernetics and Systems
Analysis. — 2016. — Vol. 52, N 6. — P. 921–930. DOI: 10.1007/s10559-016-
9894-2.
10. Pichugina O. Continuous Representation Techniques in Combinatorial Optimization
/ O. Pichugina, S. Yakovlev // IOSR Journal of Mathematics. — 2017. —
Vol. 13, N 2, Ver.V. — P. 12–25. DOI: 10.9790/5728-1302051225.
11. Pichugina O. Optimization on Polyhedral-Spherical Sets: Theory and Applications /
O. Pichugina, S. Yakovlev // In 2017 IEEE First Ukraine Conference on Electri-
cal and Computer Engeneering (UKRCON) . — 2017. — P. 1167–1174. DOI:
10.1109/UKRCOM.2017.8100436.
12. Яковлев С.В. Теория выпуклых продолжений функций на вершинах выпуклых
многогранников / С. В. Яковлев // Журн. вычисл. матем. и матем. физ. —
1994. — 34, № 7. — С. 1112–1119.
13. Яковлев С.В. О некоторых классах задач оптимизации на комбинаторных мно-
жествах размещений / С.В. Яковлев, И.В. Гребенник // Изв. вузов. Сер. Мат.
— 1991. — №11. — С. 26 – 30.
14. Postnikov A. Permutohedra, associahedra, and beyond / A. Postnikov // IMRN: In-
ternational Mathematics Research Notices. — 2009. — N 6. — P. 1026-1106.
DOI: 10.1093/imrn/rnn153.
15. Weisstein E.W. CRC Concise Encyclopedia of Mathematics, Second Edition /
E.W. Weisstein. — Boca Raton: CRC Press, 2002. — 3242 p.
16. Емеличев В.А. Многогранники, графы, оптимизация (комбинаторная теория
многогранников) / В.А. Емеличев, М.М. Ковалев, М.К. Кравцов. — М.:
Наука. Гл. ред. физико-мат. лит-ры, 1981. — 344 с.
О.С. Пичугина
ISSN 1681–6048 System Research & Information Technologies, 2017, № 4 96
17. Onaka S. Superspheres: intermediate shapes between spheres and polyhedra /
S. Onaka // Symmetry. — 2012. — Vol.4, N 3. — P. 336–343. DOI:
10.3390/sym4030336.
18. Пичугина О.С. Функционально-аналитические представления общего
перестановочного множества / О.С. Пичугина, С.В. Яковлев // Eastern-
European Journal of Enterprise Technologie. — 2016. — № 1 — С. 101–126.
DOI: 10.15587/1729-4061.2016.58550.
19. Berstein Y. Parametric nonlinear discrete optimization over well-described sets and
matroid intersections / Y. Berstein, J. Lee, S. Onn, R. Weismantel // Mathemati-
cal Programming. — 2010. — Vol. 124, N 1/2 — P. 233–253. DOI:
10.1007/s10107-010-0358-6.
20. Bertsekas D.P. Nonlinear Programming, 2nd edn. / D.P. Bertsekas. — Belmont:
Athena Scienific, 1999. — 708 p.
21. Гуляницький Л.Ф. Прикладні методи комбінаторної оптимізації : навчальний
посібник / Л.Ф. Гуляницький, О.Ю. Мулеса. — К: Видавничо-поліграф.
центр "Київський університет", 2016. — 142 с.
22. Sergienko I.V. Methods of optimization and systems analysis for problems of
transcomputational complexity / I.V. Sergienko. — New York: Springer,
2012. — 226 p. DOI: 10.1007/978-1-4614-4211-0.
Поступила 16.06.2017
|
| id | journaliasakpiua-article-103892 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:21:02Z |
| publishDate | 2017 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/6a/43811fab132cfc0376637e13dcc1796a.pdf |
| spelling | journaliasakpiua-article-1038922018-04-04T16:37:16Z Optimization over the general signed permutation set of permutations Оптимизация на общем множестве перестановок со знаком Оптимізація на загальній множині перестановок зі знаком Pichugina, Oksana S. combinatorial optimization the polyhedral-spherical set signed permutations the general permutation set the binary set a supersphere the polyhedral-surface method the conditional gradient method комбинаторная оптимизация полиэдрально-сферическое множество перестановки со знаком общее множество перестановок бинарное множество суперсфера полиэдрально-поверхностный метод метод условного градиента комбінаторна оптимізація многогранно-сферична множина перестановки зі знаком загальна множина перестановок бінарна множина суперсфера многогранно-поверхневий метод метод умовного градієнта A general signed permutation set is introduced. Approaches to optimization on it that are based on its mapping into the Euclidean space are considered. In the scope of the study, properties of the Euclidean combinatorial set and its convex hull - the general signed permutohedron are derived. They include set’s cardinality, an irreducible H-representation of the polyhedron, its dimension, the vertex and adjacency vertex criteria, and the number of combinatorially nonisomorphic polyhedra of a fixed dimension. The behavior of some classes of functions over the general signed permutation set is investigated. Functional-analytical representations of this set are constructed including polyhedral-superspherical and strict superspherical. Explicit solutions of a linear problem and a projection problem over the general signed permutation set are presented. The research allows applying continuous methods to optimization on the discrete set and obtaining both exact and approximate solutions with accuracy estimates. Введено общее множество перестановок со знаком и рассмотрены подходы к оптимизации на нем, основанные на погружении в арифметическое евклидово пространство. В рамках исследования изучены свойства этого евклидового комбинаторного множества и его выпуклой оболочки (общего многогранника перестановок со знаком), такие как мощность множества, несводимое H-представление многогранника, его размерность, критерии и смежности вершин, а также количество комбинаторно неэквивалентных многогранников фиксированной размерности. Исследованы особенности поведения нескольких классов функций на общем множестве перестановок со знаком. Построен ряд функционально-аналитических представлений этого множества, включая полиэдрально-суперсферическое и строгое суперсферическое. Приведены явные решения линейной задачи и задачи проектирования на множество перестановок со знаком. Проведенное исследование позволяет применять непрерывные методы к оптимизации на дискретном множестве и получать как точные, так и приближенные решения оптимизационных задач с оценкой точности. Уведено загальну множину перестановок зі знаком і розглянуто підходи до оптимізації на ній, що ґрунтуються на зануренні в арифметичний евклідів простір. У межах дослідження вивчено властивості евклідової комбінаторної множини та її опуклої оболонки (загального багатогранника перестановок зі знаком), такі як потужність множини, незвідне H-подання багатогранника, його вимірність, критерії вершин та суміжності вершин, а також кількість комбінаторно нееквівалентних багатогранників фіксованої вимірності. Досліджено особливості поведінки кількох класів функцій на загальній множині перестановок зі знаком. Побудовано ряд функціонально-аналітичних подань цієї множини, у тому числі поліедрально-суперсферичне і строге суперсферичне. Наведено явні розв’язки лінійної задачі та задачі проектування на множину перестановок зі знаком. Проведене дослідження дозволяє застосовувати неперервні методи до оптимізації на дискретній множині й отримувати як точні, так і наближені розв’язки оптимізаційних задач з оцінкою точності. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2017-12-15 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/103892 10.20535/SRIT.2308-8893.2017.4.07 System research and information technologies; No. 4 (2017); 74-96 Системные исследования и информационные технологии; № 4 (2017); 74-96 Системні дослідження та інформаційні технології; № 4 (2017); 74-96 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/103892/114234 Copyright (c) 2021 System research and information technologies |
| spellingShingle | комбінаторна оптимізація многогранно-сферична множина перестановки зі знаком загальна множина перестановок бінарна множина суперсфера многогранно-поверхневий метод метод умовного градієнта Pichugina, Oksana S. Оптимізація на загальній множині перестановок зі знаком |
| title | Оптимізація на загальній множині перестановок зі знаком |
| title_alt | Optimization over the general signed permutation set of permutations Оптимизация на общем множестве перестановок со знаком |
| title_full | Оптимізація на загальній множині перестановок зі знаком |
| title_fullStr | Оптимізація на загальній множині перестановок зі знаком |
| title_full_unstemmed | Оптимізація на загальній множині перестановок зі знаком |
| title_short | Оптимізація на загальній множині перестановок зі знаком |
| title_sort | оптимізація на загальній множині перестановок зі знаком |
| topic | комбінаторна оптимізація многогранно-сферична множина перестановки зі знаком загальна множина перестановок бінарна множина суперсфера многогранно-поверхневий метод метод умовного градієнта |
| topic_facet | combinatorial optimization the polyhedral-spherical set signed permutations the general permutation set the binary set a supersphere the polyhedral-surface method the conditional gradient method комбинаторная оптимизация полиэдрально-сферическое множество перестановки со знаком общее множество перестановок бинарное множество суперсфера полиэдрально-поверхностный метод метод условного градиента комбінаторна оптимізація многогранно-сферична множина перестановки зі знаком загальна множина перестановок бінарна множина суперсфера многогранно-поверхневий метод метод умовного градієнта |
| url | https://journal.iasa.kpi.ua/article/view/103892 |
| work_keys_str_mv | AT pichuginaoksanas optimizationoverthegeneralsignedpermutationsetofpermutations AT pichuginaoksanas optimizaciânaobŝemmnožestveperestanovoksoznakom AT pichuginaoksanas optimízacíânazagalʹníjmnožiníperestanovokzíznakom |