Есть ли хороший вариант для создания пользовательских правил ветвления в ветвлении и привязке для MILP в Python? - PullRequest
Новая
       51

Есть ли хороший вариант для создания пользовательских правил ветвления в ветвлении и привязке для MILP в Python?

2 голосов
/ 11 мая 2019

В основном, я хочу воссоздать концептуальные результаты из статьи «Обучение ветвлению в смешанном целочисленном программировании» Халила и др., В то же время избегая, если возможно:

1) Необходимость получения академической лицензии на CPLEX (которая использовалась в статье) или аналогичном серьезном коммерческом решении

2) Необходимость использования C на основе API. Это не является строгим требованием, но преимущество Python заключается в наличии хороших и очень доступных библиотек ML, что кажется большим преимуществом для этой конкретной цели

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

Так что, если у кого-то есть более глубокий опыт попыток настроить решатели Python для своих весьма специфических потребностей, я был бы признателен за совет.

1 Ответ

3 голосов
/ 11 мая 2019

Боюсь, что в какой-то момент вы наткнетесь на контрольно-пропускной пункт. Это действительно трудно сделать без работы на C / C ++ (imho).

Python-полосная

Я знаю только три проекта с некоторыми низкоуровневыми функциями (и все еще трудно сказать, соответствуют ли они вашим потребностям).

  • https://github.com/coin-or/python-mip
  • https://github.com/coin-or/CyLP
    • не так много развития в течение многих лет
      • весь разработчик python-3 был печален (см. Проблемы; pull-запрос не обрабатывался годами; это проблема с ресурсами: сопровождающие - хорошие люди!)
    • был разработан для исследования поворота
    • но также сказано: For example, you may .. define cut generators, branch-and-bound strategies
      • трудно понять, как добиться того, что вы ищете, кроме абстрактного LP-relax - исправить - решить
      • может быть трудно контролировать особенности (теплый старт или горячий старт)
      • сборка с открытым исходным кодом Cbc / Clp
  • https://github.com/SCIP-Interfaces/PySCIPOpt
    • базовые документы показывают более высокий уровень использования
    • но его внутренний код как минимум имеет записи для branchexeclp и co.
    • построение вокруг решателя с открытым исходным кодом SCIP
    • легче схватить решатель в академической среде, но ни в коем случае бесплатно (я не юрист и не буду пытаться найти правильные слова)
    • хотя бы один его разработчик активен в StackOverflow

Альтернатива: C ++

при попытке получить полный контроль; что может потребоваться при минимальной необходимости понимания базового решателя во всех его деталях, вы, вероятно, захотите использовать C / C ++ в Coin OSI . К сожалению, часть Cbc не поддерживается, но, в зависимости от конкретной задачи, вам может потребоваться, например, Clp .

Альтернатива: Юлия

Я не следил за последними событиями там, но язык действительно уделял большое внимание математической оптимизации (движимой большой группой людей), превосходящей питона даже в первые дни (imho!).

Но я не уверен, достаточно ли MathOptInterface для вашей задачи.

...