Специально заказанный набор - Special ordered set
В дискретная оптимизация, а специальный заказанный набор (SOS) заказанный набор переменных, используемых как дополнительный способ задания условий целочисленности в модели оптимизации. Наборы для специального заказа - это в основном устройство или инструмент, используемый в ветвь и переплет методы ветвления по наборам переменных, а не по отдельным переменным, как в обычных смешанных целочисленное программирование. Зная, что переменная является частью набор и что это заказал дает алгоритму ветвей и границ более интеллектуальный способ решения проблемы оптимизации, помогая ускорить процедуру поиска. Члены специального упорядоченного набора по отдельности могут быть непрерывными или дискретными переменными в любой комбинации. Однако даже когда все члены сами по себе непрерывны, модель, содержащая один или несколько специальных упорядоченных наборов, становится проблемой дискретной оптимизации, требующей смешанное целое число оптимизатор для ее решения.
«Единственное» преимущество использования специальных упорядоченных наборов по сравнению с использованием только ограничений состоит в том, что процедура поиска в целом будет заметно быстрее.[1]
Согласно J.A. Томлин,[2] Наборы специального порядка предоставляют мощные средства моделирования невыпуклых функций и дискретных требований, хотя существует тенденция думать о них только в терминах программирования с множественным выбором «ноль-один».
Контекст приложений
- Программирование с множественным выбором
- Глобальная оптимизация с непрерывными разделяемыми функциями.
История
Идея возникла в статье Биля «Две транспортные проблемы» (1963).[3] где он представил модель оценки предложений, этот термин был впервые явно введен Билом и Томлином (1970).[4] Набор специального порядка был впервые реализован в системе математического программирования Scicon UMPIRE.[5]
Наборы специального заказа были важной и повторяющейся темой в работах Мартина Била.[6] и их ценность была признана до такой степени, что почти все производственные системы математического программирования (MPS) реализуют ту или иную версию или подмножество SOS.
Типы SOS
Есть два вида специальных упорядоченных наборов:
- Специальные заказанные наборы типа 1 (SOS1 или S1): представляют собой набор переменных, не более один из которых могут принимать ненулевое значение, а все остальные равны 0. Чаще всего они применяются, когда набор переменных на самом деле является переменными 0-1: другими словами, мы должны выбрать не более одной из набора возможных. Они могут возникнуть, например, когда мы решаем, какой размер фабрики строить, когда у нас есть набор вариантов, возможно, малый, средний, большой или вообще не фабрика, и если мы решаем построить фабрику, мы должны выбрать один и только один размер.
- Специальные заказанные наборы типа 2 (SOS2 или S2): упорядоченный набор неотрицательных переменных, из которых не более два может быть ненулевым, и если два отличны от нуля, они должны быть последовательными в своем порядке. Специальные упорядоченные наборы типа 2 обычно используются для моделирования нелинейных функций переменной в линейной модели. Они являются естественным продолжением концепций Разделимое программирование, но при встраивании в код Branch and Bound позволяет находить действительно глобальные оптимумы, а не только локальные.
Дальнейший пример
Заметки
- ^ Кристель Гере, Кристиан Принс, Марк Сево, "Приложения оптимизации с Xpress-MP", Editions Eyrolles, Париж, Франция (2000), ISBN 0-9543503-0-8, стр. 39-42 Ссылка на PDF
- ^ J.A. Томлин, «Специальные заказанные комплекты и приложение для планирования операций по поставке газа», Ketron Management Science, Inc., Маунтин-Вью, Калифорния 94040-1266, США
- ^ E.M.L. Бил, «Две транспортные проблемы», в: G.Kreweras и G.Morlat, ред., «Proceedings of the Third International Conference on Operational Research» (Dunod, Paris and English Universities Press, London, 1963) 780-788
- ^ E.M.L. Бил и Дж. Томлин, "Специальные средства в общей системе математического программирования для невыпуклых задач с использованием упорядоченных наборов переменных", в: Дж. Лоуренс, изд., "Труды Пятой Международной конференции по операционным исследованиям" (Tavistock Publications, Лондон, 1970 г.) ) 447-454
- ^ J.J.H. Форрест, Дж. П. Херст и Дж. А. Томлин, "Практическое решение больших задач смешанного целочисленного программирования с помощью UMPIRE", Management Sci. 20 (1974) 736-773
- ^ M.J.D. Пауэлл, "Биографические мемуары Эвелин Мартин Лэнсдаун Бил, FRS", Биографические мемуары членов Королевского общества 33 (1987)
использованная литература
- Понятие специальных упорядоченных множеств было введено Э. М. Л. Билом и Дж. А. Томлином. Специальные возможности в системе общего математического программирования для невыпуклых задач, использующих упорядоченные наборы переменных. В Дж. Лоуренсе, редакторе, Operational Research 69, стр. 447–454. Издательство Тависток, Лондон, 1970.
- Э. М. Л. Бил и Дж. Дж. Х. Форрест. Глобальная оптимизация с использованием специальных упорядоченных наборов. Математическое программирование, 10 (1): 52–69, 1976.
- «Комплекты специального заказа и приложение для планирования операций по поставке газа», J.A. Томлин, Ketron Management Science, Inc., Маунтин-Вью, CA 94040-1266, США
- Кристель Гере, Кристиан Принс, Марк Севаус, «Приложения оптимизации с Xpress-MP», Editions Eyrolles, Париж, Франция (2000), ISBN 0-9543503-0-8, стр. 39-42
