Специальный заказной набор
В дискретной оптимизации специальный упорядоченный набор ( SOS ) — это упорядоченный набор переменных, используемый как дополнительный способ задания условий целостности в модели оптимизации. Наборы специального порядка — это, по сути, устройство или инструмент, используемый в методах ветвей и границ для ветвления наборов переменных, а не отдельных переменных, как в обычном программировании смешанных целых чисел . Знание того, что переменная является частью множества и что она упорядочена, дает алгоритму ветвей и границ более разумный способ решения проблемы оптимизации, помогая ускорить процедуру поиска. Членами специального упорядоченного множества по отдельности могут быть непрерывные или дискретные переменные в любой комбинации. Однако даже если все члены сами по себе являются непрерывными, модель, содержащая один или несколько специальных упорядоченных наборов, становится проблемой дискретной оптимизации, требующей смешанного целочисленного для своего решения оптимизатора.
«Единственное» преимущество использования наборов специального порядка по сравнению с использованием только ограничений заключается в том, что процедура поиска обычно будет заметно быстрее. [ 1 ] По мнению Дж. А. Томлина, наборы специального порядка предоставляют мощные средства моделирования невыпуклых функций и дискретных требований, хотя существует тенденция думать о них только с точки зрения программирования с множественным выбором, ноль-единица. [ 2 ]
Контекст приложений
[ редактировать ]- Программирование с множественным выбором
- Глобальная оптимизация с непрерывными разделимыми функциями.
История
[ редактировать ]Истоком концепции послужила статья Била «Две транспортные проблемы» (1963). [ 3 ] где он представил модель оценки предложений. Однако этот термин впервые был явно введен Билом и Томлином (1970). [ 4 ] Набор специальных порядков был впервые реализован в системе математического программирования UMPIRE компании Scicon. [ 5 ]
Наборы специального заказа были важной и постоянной темой в работах Мартина Била, и их ценность была признана до такой степени, что почти все производственные системы математического программирования (MPS) реализовали ту или иную версию или подмножество SOS. [ 6 ]
Типы
[ редактировать ]Существует два вида наборов специального заказа:
- Специально упорядоченные наборы типа 1 (SOS1 или S1): представляют собой набор переменных, не более одной из которых может принимать ненулевое значение, а все остальные имеют значение 0. Чаще всего они применяются там, где набор переменных на самом деле равен 0. 1 переменная: другими словами, нам нужно выбрать не более одной из множества возможностей. Они могут возникнуть, например, когда мы решаем, какого размера фабрику строить, когда у нас есть набор вариантов, возможно, маленькая, средняя, большая фабрика или вообще отсутствие фабрики, и если мы решим построить фабрику, нам придется выбрать один и только один размер.
- Специальные упорядоченные наборы типа 2 (SOS2 или S2): упорядоченный набор неотрицательных переменных, из которых не более двух могут быть ненулевыми, а если два ненулевых, они должны быть последовательными в своем порядке. Специальные упорядоченные наборы типа 2 обычно используются для моделирования нелинейных функций переменной в линейной модели. Они являются естественным расширением концепций раздельного программирования , но при внедрении в код ветвей и границ позволяют находить действительно глобальные оптимумы, а не только локальные оптимумы.
Дальнейший пример
[ редактировать ]Примечания
[ редактировать ]- ^ Кристель Гере, Кристиан Принс, Марк Сево, «Применение оптимизации с помощью Xpress-MP», Editions Eyrolles, Париж, Франция (2000), ISBN 0-9543503-0-8 , стр. 39–42. Ссылка на PDF.
- ^ Дж. А. Томлин, «Наборы по специальному заказу и применение к планированию операций по поставке газа», Ketron Management Science, Inc., Маунтин-Вью, Калифорния 94040-1266, США
- ^ EML Beale, «Две транспортные проблемы», в: G.Kreweras и G.Morlat, ред., «Труды Третьей Международной конференции по операционным исследованиям» (Dunod, Paris и English Universities Press, Лондон, 1963) 780-788
- ^ Э.М.Л. Бил и Дж.А. Томлин, «Специальные возможности в общей системе математического программирования для невыпуклых задач с использованием упорядоченных наборов переменных», в: Дж. Лоуренс, изд., «Материалы пятой Международной конференции по операционным исследованиям» (Тависток) Публикации, Лондон, 1970) 447–454.
- ^ Дж. Дж. Х. Форрест, Дж. П. Х. Херст и Дж. А. Томлин, «Практическое решение больших задач смешанного целочисленного программирования с помощью UMPIRE», Management Sci. 20 (1974) 736-773
- ^ MJD Пауэлл, «Биографические мемуары Эвелин Мартин Лэнсдаун Бил, FRS», Биографические мемуары членов Королевского общества 33 (1987)
Ссылки
[ редактировать ]- Понятие специально упорядоченных наборов было введено Э.М.Л.Билом и Дж.А.Томлином. Специальные возможности общей системы математического программирования для решения невыпуклых задач с использованием упорядоченных наборов переменных. У Дж. Лоуренса, редактора, Operational Research 69, страницы 447–454. Издательство Тависток, Лондон, 1970.
- EML Бил и Джей Джей Форрест. Глобальная оптимизация с использованием специально упорядоченных наборов. Математическое программирование, 10 (1): 52–69, 1976.
- «Специальные комплекты и применение к планированию операций по поставке газа», Дж. А. Томлин, Ketron Management Science, Inc., Маунтин-Вью, Калифорния 94040-1266, США.
- Кристель Гере, Кристиан Принс, Марк Севаус, «Применение оптимизации с помощью Xpress-MP» , Editions Eyrolles, Париж, Франция (2000 г.), ISBN 0-9543503-0-8 , страницы 39–42.
 | |||||||||||||||
| |||||||||||||||