SCIP и филиал и цена

Если вы определяете свои переменные как непрерывные и просто добавляете цену, SCIP решит основную задачу оптимально (т. Е. Решит ограниченный мастер, добавит улучшающие столбцы, решит обновленный ограниченный мастер и т. Д., Пока больше не будет улучшающихся столбцов). найденный).

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

Однако следует отметить, что все правила ветвления в SCIP выполняют ветвление по переменным, то есть они принимают целочисленную переменную с дробным значением и разбивают ее домен; двоичная переменная будет зафиксирована на 0 и 1 в двух дочерних узлах. Обычно это плохая идея для филиалов и цен: во-первых, она довольно несбалансированная. У вас есть огромное количество переменных, из которых только немногие будут иметь значение 1 в конце, большинство будет равно 0. Следовательно, фиксирование переменной в 1 имеет большое значение, в то время как ее установка в 0 практически не влияет. Но что еще более важно, вам нужно принять во внимание решение о ветвлении в вашей проблеме ценообразования. Если вы зафиксировали переменную равной 0, вы должны удерживать оценщика от создания копии запрещенного столбца (что, вероятно, улучшит решение LP, поскольку оно было частью прежнего оптимального решения). Для этого вам, возможно, потребуется поискать 2-е (или более позднее k) -лучшее решение. Поскольку вы решаете проблемы ценообразования в виде MIP с помощью SCIP, вы можете просто добавить ограничение, запрещающее это решение (логическое или линейное для бинарных переменных или ограниченное (не линейное) для общих целочисленных переменных).

Я бы порекомендовал внедрить ваше собственное правило ветвления, которое учитывает, что вы выполняете ветвление и цену и ответвления таким образом, чтобы он был более сбалансированным и не наносил слишком большой ущерб вашей цене. Для примера, проверьте Райана&Приемлемое правило ветвления, которое является стандартом для бинарных задач с основной структурой разбиения множеств. Это правило реализовано в Binpacking, а также в примере Coloring, поставляемом со SCIP.

Пожалуйста, ознакомьтесь с разделом часто задаваемых вопросов по SCIP, где есть целый раздел о ветвлении и цене, который также охватывает тему ветвления (в частности, как решения о ветвлении могут храниться и реализовываться с помощью обработчика ограничений, что вам нужно сделать для Райана&Фостер ветвление): http://scip.zib.de/doc/html/FAQ.php

В списке рассылки SCIP также было много вопросов о цене и филиале.
http://listserv.zib.de/mailman/listinfo/scip/. Если вы хотите найти его, вы можете использовать Google и искать «site: listserv.zib.de scip search-string»

Наконец, я хотел бы рекомендовать взглянуть на проект GCG: http://www.or.rwth-aachen.de/gcg/
Это расширение SCIP для универсального решателя среза и цены, т. Е. Вам не нужно ничего реализовывать, вы просто вводите оригинальную формулировку своей модели, которая затем переформулируется с помощью декомпозиции Данцига-Вульфа и решается через филиал-по-цене. Вы можете предоставить структуру для переформулирования, проблемы ценообразования решаются в виде MIP (как вы это делаете), а также существуют различные правила ветвления. GCG также является частью пакета оптимизации SCIP и может быть легко встроен в пакет.