algorithm - 解决具有额外约束的分区的正确算法是什么?
问题描述
这是我的问题的摘要:
我有一组问题需要分配给一组人。每个问题只应分配给一个人,所有问题都应分配(分区)。每个问题都有一个值(连续变量)和一个成本(不同人的成本不同,每一对人问题都有自己的成本)。
目标是找到一个将问题分配给人们的分区,以便对于每个人来说,所有分配问题的最大成本低于某个阈值,并且所有分区的总值大致相同(或者更好的是人们之间的总值之间的差异最小化)。
谁能指出我正确的方向?我知道有贪心算法来解决多路分区问题,但我不知道如何修改它们以处理分配给一个人的所有问题的最大成本应该低于某个阈值的额外约束。
是否可以使用像 minizinc 这样的约束建模语言来解决?
任何帮助将不胜感激
解决方案
根据您的描述,我不确定您有分区问题,而是分配问题,因为您正试图为每个问题分配一个人。
下面我与您分享一个基本的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 和示例数据文件解决此问题模型,例如:
示例问题.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;
我希望这有助于全面阐述您的问题。
推荐阅读
- alm - 如何使用 REST API 和 JSON 在 ALM 中的单个请求中创建多个测试运行
- python - numpy数组的逻辑索引
- reactjs - 在使用 Jest 测试的 React 类上导入 css 文件
- iis - 如何在不使用浏览器的情况下在 IIS 上运行后端代码?
- r - 如何在 R 中为 geom_point() 圆着色
- kotlin - 多线程版本的协程
- git - 远程分支如何是本地的?(git-p4)
- vscode-settings - VSCode中的python解释器版本不一致
- python - 赠品结束时的时间戳
- reactjs - 在使用 react ref 调用子组件之前调用子方法