#arrays #optimization #multidimensional-array #dynamic-arrays
Вопрос:
Я был бы очень признателен за некоторую помощь в следующем.
Имея n источников и n пунктов назначения и соответствующую матрицу затрат n x n (целых чисел) в качестве входных данных, я должен выбрать k источников и k пунктов назначения (k У нас есть 3 переменные решения: выбранные источники, выбранные пункты назначения и, наконец, выбранные края (затраты, то есть решение проблемы назначения).
Я не могу определить условие, которое создает матрицу затрат k x k, основанную на выборе источников и пунктов назначения, поэтому она служит входными данными для задачи назначения. Я попробовал следующий код:
int n=...;
int k= ...;
range origins = 1..n;
range destin = 1..n;
range k_origins =1..k;
range k_destin = 1..k;
int costs[origins][destin]=...;
dvar boolean x[origins];
dvar boolean y[destin];
dvar boolean z[k_origins][k_destin];
///First I tried to create k x k costs matrix directly:
//dexpr int k_costs[k_origins][k_destin]= costs[i: x[i]==1][j: y[j]==1]; //ERROR: Syntax error: unexpected ":"
//Then I tried to extract first the indexes and then create the k x k matrix, but there is always an error:
//dexpr int array_origins[k_origins] = [i: x[i]==1| i in origins]; //ERROR: Boolean[{int}] type cannot be used for dexpr int[k_origins]
//dexpr {int} array_origins = {i| i in origins : x[i]==1}; //ERROR: {int} type cannot be used with decision expressions
dexpr int k_costs[i in k_origins][j in k_destin]= costs[i][j]* (x[i]==1)*(y[j]==1);
dexpr float totalcost = sum(i in k_origins, j in k_destin)
k_costs[i][j] * z[i][j];
minimize totalcost ;
subject to
{
sum(i in origins)x[i]==k;
sum(j in destin)y[j]==k;
forall(j in k_destin) sum(i in k_origins)z[i][j] == 1;
forall(i in k_origins) sum(j in k_destin)z[i][j] == 1;
};
Любая идея или совет приветствуются! Спасибо
*Краткое описание проблемы с назначением можно найти здесь https://en.wikipedia.org/wiki/Assignment_problem
Ответ №1:
In https://www.linkedin.com/pulse/how-opl-alex-fleischer/
Как использовать переменную принятия решения в качестве индекса с помощью CPLEX ?
range r=1..5;
float value[r]=[2,3,4.5,1,0];
dvar int i in 1..5;
maximize sum(k in r) value[k]*(k==i);
subject to
{
}
execute
{
writeln("i=",i);
}
или если с выражениями решения
range r=1..5;
float value[r]=[2,3,4.5,1,0];
dvar int i in 1..5;
dexpr float cost=sum(k in r) value[k]*(k==i);
minimize cost;
subject to
{
}
execute
{
writeln("i=",i);
}
В вашем примере вы могли бы использовать CPOptimizer:
using CP;
int n=3;
int k= 2;
range origins = 1..n;
range destin = 1..n;
range k_origins =1..k;
range k_destin = 1..k;
int costs[o in origins][d in destin]=ftoi(abs(o-d)) mod 2;
dvar boolean x[origins];
dvar boolean y[destin];
dvar boolean z[k_origins][k_destin];
///First I tried to create k x k costs matrix directly:
//dexpr int k_costs[k_origins][k_destin]= costs[i: x[i]==1][j: y[j]==1]; //ERROR: Syntax error: unexpected ":"
//Then I tried to extract first the indexes and then create the k x k matrix, but there is always an error:
//dexpr int array_origins[k_origins] = [i: x[i]==1| i in origins]; //ERROR: Boolean[{int}] type cannot be used for dexpr int[k_origins]
//dexpr {int} array_origins = {i| i in origins : x[i]==1}; //ERROR: {int} type cannot be used with decision expressions
dexpr int k_costs[i in k_origins][j in k_destin]= costs[i][j]* (x[i]==1)*(y[j]==1);
dexpr float totalcost = sum(i in k_origins, j in k_destin:i in origins amp;amp; j in destin)
k_costs[i][j] * z[i][j];
minimize totalcost ;
subject to
{
sum(i in origins)x[i]==k;
sum(j in destin)y[j]==k;
forall(j in k_destin) sum(i in k_origins)z[i][j] == 1;
forall(i in k_origins) sum(j in k_destin)z[i][j] == 1;
};
или если вы хотите остаться с MIP
int n=3;
int k= 2;
range origins = 1..n;
range destin = 1..n;
range k_origins =1..k;
range k_destin = 1..k;
int costs[o in origins][d in destin]=ftoi(abs(o-d)) mod 2;
dvar boolean x[origins];
dvar boolean y[destin];
dvar boolean z[k_origins][k_destin];
///First I tried to create k x k costs matrix directly:
//dexpr int k_costs[k_origins][k_destin]= costs[i: x[i]==1][j: y[j]==1]; //ERROR: Syntax error: unexpected ":"
//Then I tried to extract first the indexes and then create the k x k matrix, but there is always an error:
//dexpr int array_origins[k_origins] = [i: x[i]==1| i in origins]; //ERROR: Boolean[{int}] type cannot be used for dexpr int[k_origins]
//dexpr {int} array_origins = {i| i in origins : x[i]==1}; //ERROR: {int} type cannot be used with decision expressions
dexpr int k_costs[i in k_origins][j in k_destin]= costs[i][j]* ((x[i]==1) amp;amp;(y[j]==1));
dvar int k_coststimesz[i in k_origins][j in k_destin];
dexpr float totalcost = sum(i in k_origins, j in k_destin:i in origins amp;amp; j in destin)
k_coststimesz[i][j];
minimize totalcost ;
subject to
{
forall(i in k_origins, j in k_destin) (z[i][j]==0) => (k_coststimesz[i][j]==0);
forall(i in k_origins, j in k_destin) (z[i][j]==1) => (k_coststimesz[i][j]==k_costs[i][j]);
sum(i in origins)x[i]==k;
sum(j in destin)y[j]==k;
forall(j in k_destin) sum(i in k_origins)z[i][j] == 1;
forall(i in k_origins) sum(j in k_destin)z[i][j] == 1;
};
работает нормально
Комментарии:
1. Спасибо за ваш ответ, Алекс! Я применил ваше предложение, но теперь я получаю другую ошибку: CPLEX (по умолчанию) не может извлечь выражение k_costs[i][j] * z[i][j], а CPLEX (по умолчанию) не может извлечь выражение минимизировать общую стоимость. Не могли бы вы, пожалуйста, помочь мне правильно запустить его? Я только что добавил код в формате кода, чтобы его можно было скопировать и вставить. Я действительно ценю вашу помощь, я был зациклен на этой проблеме в течение нескольких недель. С наилучшими пожеланиями из Аргентины 🙂
2. Привет, Алекс, я очень благодарен тебе за помощь! Оба предложения хорошо работают с массивом int costs[o в источниках][d в предназначении]=ftoi(abs(o-d)) mod 2. Однако, когда я изменяю его значения на целые числа, такие как: int стоит[происхождение][судьба]=[[5,2,7], [10,3,2],[5,4,4]]; матрица k_costs принимает некоторые значения 0. Например, когда я запускаю код MIP с этой последней предложенной мной матрицей затрат, то k_costs = [[0,2],[0,0]], в то время как это должно быть [[2,7],[3,2]], тогда решение для точки доступа равно 4. Еще раз спасибо