0

对于解决此问题的任何帮助，我将不胜感激。在这个双层分配问题 (BAP) 中，我们有 n 个起点和 n 个终点，领导者必须选择 k 个起点和 k 个终点，这样才能解决追随者的典型（最小化）分配问题（AP）（大小为 k ) 被最大化。那是：

最大化（大小为 k 的 AP 的解决方案）[领导者的目标函数 (OF)]

st 1.Leader选择k个起点和k个目的地

  1. 大小为 k = minimum(sum(cij * xij) i= 1…k) 的 AP 的解（对于 k 个选定的起点和终点）[Follower's OF]

  2. 英石。典型的 AP 约束。（xij 布尔值等）

我已经成功地实现了两个目标函数对齐的情况下的代码（例如两个最小化），因为我可以通过编写一次目标函数来做到这一点，因为它对于领导者和追随者来说是完全相同的。当我尝试解决上述公式时，我的问题出现了，其中我们有一个最大化的领导者和一个最小化的追随者。下面是适用于领导者和追随者都最小化的情况的代码。

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[origins][destin]=[[5, 5, 7],
           [10, 3, 6],
           [4 ,4, 5]
 ];

dvar int x[k_origins] in origins;
dvar int y[k_destin] in destin;
dvar boolean z[k_origins][k_destin];
dvar int k_costs[k_origins][k_destin];

dexpr float totalcost = sum(i in k_origins, j in k_destin)
    k_costs[i][j] * z[i][j];

//The problem is right here, where I should maximize the leader's objective 
//function = solution of the minimization assignment problem of size k
minimize totalcost ;

subject to
{
//Cannot choose one origin/destination twice  
allDifferent(x);
allDifferent(y);

//Values must be ordered, so the indexes are respected in the next ct
forall(i in 1..k - 1) x[i]<= x[i+1];
forall(j in 1..k - 1) y[j]<= y[j+1]; 

//Definition of the follower's matrix of costs 
forall(i in k_origins, j in k_destin) k_costs[i][j] == costs[x[i]][y[j]];
 
//Typical AP Constraints applied to the follower 
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;
};

对于 Leader 的最大化问题和 Follower 的最小化问题（我无法实现），输出解决方案将是：选择行（起点）1 和 2 以及列（目的地）1 和 3，以及解决方案值 11（所选行和列的 AP）。欢迎任何帮助解决这个问题:)

非常感谢！

如果需要，这里有作业问题的描述：https ://en.wikipedia.org/wiki/Assignment_problem

4

0 回答 0