难以理解如何将现实世界的问题表达给 opensolver 或 minizinc 以进行工人分配

Question

我要开始说我对 Minizinc 和约束编程都不精通，我看过 excel 我能理解的 youtube 上的“求解器”教程，但我不明白我是怎么做到的可以将我的问题转化为 excel 可求解的解决方案，也不是 Minizinc 就此而言。

为了解释这个问题，我有一个我认为是多级背包问题，但可能是错误的。以下是我认为的限制条件

There are 25 "admin" who supervise over 200 "staff".
Each admin has a unique workload allocation.
Each admin also has to moderate staff 
    that is both equal to or greater than their supervisorial allocation 
    and has the ability to rate their moderation preference
Admin cannot supervise and moderate the same staff member.
Every staff member has to have both a supervisor and a moderator.

为了解决这个问题，我将其表示为 table

table view of data sample set

a# = 管理员
s# = 员工
b = 主管
v# = 审核偏好（越低 = 越好）

以附例可见

admin1 是 staff1、13[= 的主管 54=]，和 17 他们自愿 moderate staff2, 20, 10 , 和 23 的顺序（偏好）。

忽略以上所有内容，这是我对问题的细分您可以将问题简化如下

每行的版主数量等于或大于主管，

并且每个专栏都有一个独特的主管和主持人（在可能的优先级被考虑在内的情况下，较低 = 更好）。

我希望我已经尝试足够好地解释这个问题并且我的分析不是太复杂，任何关于我如何解决这个问题以便它可以扩展到更大的数据集的指示将不胜感激。

谢谢。

Answer 1

您可以在 MiniZinc 中尝试以下 MIP 模型，求解器设置为 OsiCbc。

int: n = 10;
int: m = 24;
set of int: ADMIN = 1..n;
set of int: STAFF = 1..m;

array[ADMIN,STAFF] of var 0..1: supervise;
array[ADMIN,STAFF] of var 0..1: moderate;

array[ADMIN, STAFF] of int: moderateValue = [|
0,4,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,3,0,0,1,0|
3,2,0,0,0,0,0,0,4,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0|
0,0,1,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,0,3,0,0,0,2|
0,0,0,1,0,0,0,0,0,0,3,2,0,0,0,0,0,4,0,0,0,0,0,0|
0,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,3,0,0,0,0,2,0,1|
0,0,0,0,2,4,0,0,0,0,0,0,0,0,3,1,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,2,3,0,0,0,0,0,0|
0,2,0,0,0,0,0,4,0,0,0,0,3,1,0,0,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,3,0,0,0,0,4,0,0,2,1,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,3,2,1|];

% admin member cannot both supervise and moderate staff member
constraint forall(a in ADMIN, s in STAFF)
    (supervise[a,s] + moderate[a,s] <= 1);

% each staff member is supervised by exactly one admin member
constraint forall(s in STAFF)
    (sum(col(supervise, s)) = 1);

% each staff member is moderated by exactly one admin member
constraint forall(s in STAFF)
    (sum(col(moderate, s)) = 1);

% each admin member cannot supervise more staff members than moderated
constraint forall(a in ADMIN)
    (sum(row(supervise, a)) <= sum(row(moderate, a)));

var int: obj = sum(a in ADMIN, s in STAFF)(moderateValue[a,s]*moderate[a,s]);

solve maximize obj;

output ["obj = \(obj)\n"] ++ ["assignment = \n"] ++ [show2d(array2d(ADMIN, STAFF, [if supervise[a,s] = 1 then 1 elseif moderate[a,s] = 1 then 2 else 0 endif | a in ADMIN, s in STAFF]))];

我不确定我是否理解您的所有要求，但希望该模型可以作为基础。每个 admin 成员都可以在此处将 4、3、2 和 1 的审核值设置为 staff 成员。然后 objective 最大化指定节制的总和。在输出中 1 表示管理员成员监督工作人员，2 表示管理员成员审核工作人员，否则显示 0。模型中的数据基于提供的示例。

编辑：要使 supervise 预定义，请更改以下内容：

%array[ADMIN,STAFF] of var 0..1: supervise;

array[ADMIN, STAFF] of int: supervise = [|
1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0|
0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0|
0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0,0|
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0|
0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0|
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1|
0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0|];

难以理解如何将现实世界的问题表达给 opensolver 或 minizinc 以进行工人分配

Having trouble understanding how to express real world problem to opensolver or minizinc for worker allocation

excel

solver

knapsack-problem

constraint-programming

minizinc