Правило Каннингема

В математической оптимизации правило Каннингема (также известное как недавно рассматриваемое правило или правило циклического перебора ) представляет собой алгоритмическое усовершенствование симплексного метода оптимизации линейной .

Это правило было предложено в 1979 году У.Х. Каннингемом, чтобы победить деформированные конструкции гиперкуба Кли, Минти и др. (см., например, кубик Кли–Минти ). ^{[ 1 ]}

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

показали Недавно Дэвид Эвис и Оливер Фридман , что существует семейство линейных программ, в которых симплексный алгоритм, оснащенный правилом Каннингема, требует экспоненциального времени. ^{[ 2 ]}

Примечания

^ Каннингем, Вашингтон (1979). «Теоретические свойства сетевого симплексного метода». Математика исследования операций . 4 (2): 196–208. дои : 10.1287/moor.4.2.196 .
^ Авис, Дэвид; Фридманн, Оливер (2017). «Экспоненциальная нижняя граница правила Каннингема». Математическое программирование . 161 (1–2): 271–305. arXiv : 1305.3944 . дои : 10.1007/s10107-016-1008-4 . S2CID 2986216 .

[1] Каннингем, Вашингтон (1979). «Теоретические свойства сетевого симплексного метода». Математика исследования операций . 4 (2): 196–208. дои : 10.1287/moor.4.2.196 .

[2] Авис, Дэвид; Фридманн, Оливер (2017). «Экспоненциальная нижняя граница правила Каннингема». Математическое программирование . 161 (1–2): 271–305. arXiv : 1305.3944 . дои : 10.1007/s10107-016-1008-4 . S2CID 2986216 .

[ 1 ]

[ 2 ]