时间戳

首页 > 解决方案 > 使用 Minizinc 在表中选择匹配的原料

constraint-programming - 使用 Minizinc 在表中选择匹配的原料

问题描述

我有一个包含 4 个功能（名称、价值、成本、人员）的项目表。我想在 Minizinc 中描述一个模型，它选择总价值最大化但总预算为 255 的项目，我可以在 20 个之间选择近 9 个项目。

我写了一个数据文件：data.dzn

%       name       value    cost  people
data = [
      | PRJ0,      6000,    35,    5
      | PRJ1,      4000,    34,    3
      | PRJ2,      1000,    26,    4
      ...
      | PRJ20,     1200,    18,    2    
      |];


PRJ = {PRJ0,...,PRJ20};
FEATURE = {name, value, budget, personnel};
max_budget = 225;
max_prj=9;

所以我的限制是：

choose_project <= 9 /\ budget<=255 s.t solve maximize tot_value;

如何在表中的原始项目中选择非任意数量的决策变量（1 到 9）？到目前为止，这是我的代码：invest.mzn

include "data.dzn";
int: max_budget;  %255
int: max_prj;     %9
enum FEATURE;
enum PRJ;
array[PRJ,FEATURE] of int: data;
constraint ...
...
solve maximize tot_value;

标签： constraint-programmingminizinc

解决方案

您可以声明一个布尔变量数组，例如selected_projects，用于对是否PRJ_k选择项目进行编码。

然后你可以简单地计算这个数组中有多少项目同时被选中。

例子：

enum FEATURE = {name, value, budget, personnel};
enum PRJ = { PRJ0, PRJ1 };

array[PRJ,FEATURE] of int: data =
     [| PRJ0,      6000,    35,    5
      | PRJ1,      4000,    34,    3
      |];

array[PRJ] of var bool: selected_projects;

var int: tot_value;

% The total number of selected projects must be in [1, 9]
constraint let {
        var int: tot_selected = sum(prj in PRJ) ( selected_projects[prj] )
    } in
        1 <= tot_selected /\ tot_selected <= 9;

constraint tot_value = sum(prj in PRJ) ( selected_projects[prj] * data[prj, value] );

% ...
% encoding of budget and personnel constraints
% ...

solve maximize tot_value;

推荐阅读