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

Question

这里是我的问题的总结:

我有一组问题需要分配给一组人。每个问题应该只分配给一个人，所有问题都应该分配(分区)。每个问题都有一个值(连续变量)和一个成本(成本因人而异，每一对人-问题都有自己的成本)。

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

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

是否可以使用像 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)、每个问题的成本(因人而异)以及总成本的阈值。

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

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

最后，我声明问题目标是最大化整体值(value)。不确定这是否是您的目标，您没有指定 value 的用途，所以这是一个猜测。

如果您将上面的文本保存到文件 problem.mzn 中，那么您可以使用带有示例数据文件的 MiniZinc 解决这个问题模型，例如:

示例问题.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;

我希望这有助于全面阐述您的问题。