Получение следующих лучших решений после Оптимал

Question

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

    self.solver = pywraplp.Solver(
                'FD',
                pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING
            )
        self.objective = self.solver.Objective()
        self.objective.SetMaximization()
self.solver.solve()

Я пропустил код для определения переменных, но мой вопрос: выполнение этого кода даст мне оптимальный состав.Есть ли способ найти 2-е, 3-е и т. Д. Лучшее решение?

Answer 1

В задаче, похожей на рюкзак, легко получить следующее наилучшее решение в итерационной процедуре.

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

По сути, это сокращение, которое исключает первое оптимальное решение из решения.пространство.Таким образом, другое решение будет получено путем решения задачи после добавления дополнительного ограничения.

Answer 2

С CBC нет. CPLEX, Gurobi поддерживают сохранение большего количества решений, но это доступно в OR-Tools только для Gurobi с помощью метода NextSolution ().

Если ваша модель является чисто интегральной, вы можете взглянуть на решатель CP-SAT.

Хитрость в том, что если вы не исследуете все решения, второе лучшее решение в лучшем случае эвристическое.