Как найти возможные значения границ переменной в линейном программировании с Python? - PullRequest
Новая
       25

Как найти возможные значения границ переменной в линейном программировании с Python?

1 голос
/ 10 апреля 2020

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

Например, с переменными a, b и c и ограничения a>b, b>c и a+b+c=100, у нас есть:

a in [33.33-100] b in [0-50] c in [0-33.33]

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

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

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

1 Ответ

1 голос
/ 10 апреля 2020

Это очень распространенный топи c, обычно называемый сжатие границ , очень важный для:

  • stati c предварительное решение
  • итеративное использование в глобальной оптимизации

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

Gleixner, Ambros M., et al. "Three enhancements for optimization-based bound tightening." Journal of Global Optimization 67.4 (2017): 731-757. Например, начинается с:

Сжатие границ на основе оптимизации (OBBT) - одна из наиболее эффективных процедур сокращения вариабельных областей невыпуклых смешанно-целочисленных нелинейных программ (MINLP). В то же время это одна из самых дорогих процедур сжатия границ, так как она решает вспомогательные линейные программы (LP) - вдвое больше, чем множество переменных. Основная цель этой статьи - обсудить алгоритмы c методов для эффективной реализации OBBT.

Существуют альтернативы технологии не-LP (например, интервальная арифметика c), такие как обоснование ужесточения границ .

См. например:

  • Belotti, Pietro, et al. "Feasibility-based bounds tightening via fixed points." International Conference on Combinatorial Optimization and Applications. Springer, Berlin, Heidelberg, 2010.

Вы знаете некоторые ключевые слова для поиска сейчас. Может быть, это хорошее начало (но я его не читал):

  • Puranik, Yash, and Nikolaos V. Sahinidis. "Domain reduction techniques for global NLP and MINLP optimization." Constraints 22.3 (2017): 338-376.
...