Блог

Я был бы очень признателен за некоторую помощь в следующем.

Имея 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

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;
};
 

работает нормально