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

Знаете ли вы, есть ли способ изменить некоторые ограничения в уже решенной задаче оптимизации ограничений 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

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

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

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

Спасибо


java constraint-programming cplex
person Leandro    schedule 06.01.2012    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Класс этих проблем обычно называют проблемой назначения в исследовании операций.

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

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

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

Вот ссылка на проблему с назначением.

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

person Ram Narasimhan    schedule 15.01.2012
comment
Большое спасибо! Это было действительно полезно. Я провожу небольшое исследование, и когда закончу, поделюсь решением. - person Leandro; 16.01.2012