Динамический CSP с Cplex

Question

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

Пример:

Задачи назначаются разным ресурсам.Ресурс 1 имеет задачи A, B & C, Ресурс 2 имеет задачи D, E & F.

Когда я добавляю Ресурс 3, я хочу, чтобы новое назначение было примерно таким:

R1 = A & B
R2 = D & E
R3 = C & F

Но Cplex, вероятно, вернет что-то вроде:

R1: F & E
R2: A & B 
R3: C & D

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

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

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

Спасибо

Answer 1

Класс этих проблем более широко упоминается как проблема присвоения в Операционном исследовании.

Очень просто, мы назначаем задачи ресурсам при определенных ограничениях. Целевая функция (цель) сводит к минимуму стоимость таких назначений. Один набор ограничений гарантирует, что каждому заданию назначается ресурс.

Вы, конечно, можете использовать CPLEX (или любой LP-решатель), чтобы получить решение. В частности, проблемы с назначением «проще» в том, что вам даже не нужно вызывать Simplex . Метод, известный как Венгерский метод , даст оптимальное решение.

В частности, в вашем случае, поскольку вы хотите сохранить большую часть существующего решения, вы можете назначить затраты или веса, чтобы стимулировать определенные назначения. Например, в вашей задаче, если вы сделаете стоимость присвоения A & B на R1 очень низкой, окончательное решение будет иметь такое значение, если только нет настоятельная необходимость изменить это назначение.

Вот одна ссылка для Задачи о назначении .

Также посмотрите Венгерский метод в Википедии , в котором есть очень доступный раздел под названием Объяснение непрофессионала . Как только вы это сделаете, вы также можете прочитать анализ чувствительности в CPLEX, где вы используете так называемый «теплый старт» для использования ранее сгенерированных решений.