0-1 Рюкзак с ограничениями на разбиение

Question

У меня есть проблема, что на поверхности выглядит как ранец 0-1. У меня есть набор возможных «кандидатов», которые можно выбрать (или нет), у каждого кандидата есть «вес» (стоимость) и потенциальная «ценность». Если бы это была целая проблема, я бы использовал подход DP и покончил с этим. Но вот Curveball: существуют «ограничения на разбиение» на возможных кандидатов, которые могут быть в конечном решении.

Я имею в виду, что пространство кандидатов разбивается на классы дискретной эквивалентности. По моей конкретной проблеме около 300 кандидатов и 12 возможных классов эквивалентности. Существуют «правила ведения бизнеса», которые говорят, что я могу только сказать 3 кандидата из класса C1 и 6 кандидатов из С2 и т. Д.

Это ограничение предполагает подход типа графа-поиска с использованием технологий с использованием ветвей и границ другая форма обрезки, однако я несколько тупик относительно того, как начать, так как я только знаком с решением DP с 0-1 рюкзаком. Какие методы/подходы могут быть подходящими для этой проблемы? Я также думал о возможностях использования библиотеки программирования ограничений, но не уверен, сможет ли она найти решение?

Answer 1

Вы можете попробовать Integer Linear Programming solver, где есть двоичная переменная для выбора каждого кандидата. Ограничения легко выражаются как линейные неравенства. С 300 переменными решателю не должно быть трудно решить проблему.

Самый простой способ, вероятно, состоит в том, чтобы написать вашу проблему в текстовом формате, таком как CPLEX LP format, а затем использовать решатель, такой как Coin CBC или GLPK.