解决具有额外约束的分区的正确算法是什么?

Question

这是我问题的摘要：

我有一组问题需要分配给一组人。每个问题只应分配给一个人，并且应分配所有问题(分区(。每个问题都有一个值(连续变量(和一个成本(不同的人的成本不同，每个对人的问题都有自己的成本(。

目标是找到一个将问题分配给人员的分区，以便对于每个人，所有分配问题的最大成本低于某个阈值，并且所有分区的总值大致相同(或者更好的是，人员之间的总值之间的差异最小化(。

谁能指出我正确的方向？我知道有贪婪的算法来解决多路分区问题，但我不知道如何修改它们以处理额外的约束，即分配给一个人的所有问题的最大成本应该低于某个阈值。

是否可以使用像 minizinc 这样的约束建模语言来解决？

任何帮助将不胜感激

Answer 1

从您的描述中，我不确定您是否有分区问题，而是分配问题，因为您正在尝试为每个问题分配一个人。

下面我与您分享一个基本的MiniZinc模型，该模型应该可以大致捕获您的问题;您可能需要进行一些调整以完全符合您的问题描述。

问题.mzn：

int: num_people;  % the number of people
set of int: PEOPLE = 1..num_people;
int: num_problems; % the number of problems
set of int: PROBLEMS = 1..num_problems;
array[PROBLEMS] of float: value;  % the value of each problem
array[PROBLEMS, PEOPLE] of float: cost; % the cost of each problem, for each person
float: threshold; % the threshold for the overall costs
% DECISION VARIABLE: assign to each problem a person
array[PROBLEMS] of var PEOPLE: personForProblem;

% the sum of the costs of the "problem-person" assignment must be smaller than a threshold 
constraint 
sum (problem in PROBLEMS) (cost[problem, personForProblem[problem]] )  
<= threshold;
% maximize the sum of the value of each "problem-person" assignment
solve maximize 
sum (problem in PROBLEMS) ( value[personForProblem[problem]]);

在此模型中，我首先定义您定义的所有参数：人数、num_people、问题数量、num_problems、每个问题的value以及每个问题的cost(因人而异(以及总体成本的threshold。

其次，我定义决策变量，personForProblem决策变量是一个整数变量数组，其中整数表示问题分配给的人。

第三，我发布了所有成本的总和必须小于threshold的约束。

最后，我声明问题的目标是最大化整体value。不确定这是否是您的目标，您尚未指定value的目的是什么，因此这是一个猜测。

如果将上面的文本保存到文件problem.mzn那么您可以使用MiniZinc和示例数据文件来解决此问题模型，例如：

sample-problem.dzn：

num_people = 4;
num_problems = 3;
value = [  3.0,  7.2, 1.2 ];
cost = array2d(PROBLEMS, PEOPLE, 
[ 
2.3, 6.2, 1.2, 4.2, % cost for the 4 people for problem-1
5.1, 3.2, 2.3, 7.8, % cost for the 4 people for problem-2
1.5, 1.7, 4.2, 1.2, % cost for the 4 people for problem-3
]);
threshold = 10.0;

我希望这有助于充分阐述您的问题。