MiniZinc：简化几乎全为零的参数数组

Question

我正在研究一个关于时间表的模型，我有一个关于约束的问题。 这是模型（我删除了问题中所有不需要的部分）。

include "globals.mzn";

enum weektime = {M1,M2,M3,M4,M5,M6,T1,T2,T3,T4,T5,T6,W1,W2,W3,W4,W5,W6,TH1,TH2,TH3,TH4,TH5,TH6,F1,F2,F3,F4,F5,F6,S1,S2,S3,S4};

enum allsubjects = {BIO, CHA, CHI, CHO, CMAT, DES, DIR, DIS, EFI, ELE, EMM, FIS, GCA, GEE, GEO, GEP, IGI, INF, ING, IPM, ITA, LBIO, LCHA, LCHI, LCHO, LDES, LDIS, LELE, LFIS, LGCA, LGEE, LGEP, LIGI, LINF, LIPM, LLTE, LPCI, LSA, LSIS, LSTA, LTCH, LTE, LTEL, LTLC, LTMA, LTMM, LTOP, LTPS, LTTI, MAT, PCI, REL, ROB, SCI, SIS, STA, STO, TCH, TEL, TLC, TMA, TMM, TOP, TPS, TTI, n};

int: nc = 4;
set of int: class = 1..nc;

array[class, weektime] of allsubjects: subjects;
subjects = 
[| EFI, EFI, LIGI, LBIO, LBIO, n, MAT, MAT, BIO, ITA, IGI, n, ING, REL, ITA, LCHO, LCHO, IGI, LCHA, LCHA, CHO, IGI, MAT, ING, ING, BIO, ITA, ITA, CHA, MAT, ITA, ITA, LIGI, LIGI
| DIS, DIS, LCHI, MAT, SCI, ITA, MAT, ITA, ITA, SCI, DIR, n, ITA, LDIS, MAT, CHI, LSTA, LSTA, CHI, ING, DIR, LFIS, EFI, EFI, STA, ITA, ING, FIS, MAT, n, REL, ING, ITA, FIS
| REL, MAT, SIS, ITA, TPS, ING, ITA, ITA, INF, MAT, ING, n, ROB, ROB, ING, MAT, ITA, n, ITA, INF, LTPS, LTPS, MAT, TEL, LSIS, LSIS, ITA, LINF, LINF, LINF, LTEL, LTEL, EFI, EFI
| TMA, LTE, REL, MAT, LTTI, LTTI, MAT, TTI, TTI, ITA, LELE, n, ITA, MAT, LTTI, ING, LELE, LELE, ITA, EFI, EFI, LTMA, TTI, n, LTMA, LTMA, ITA, ITA, LLTE, LLTE, ITA, ING, LTE, LTE
|];

array[1..nc] of set of allsubjects: subjclass;
subjclass = [{ITA, ING}, {CHI, SCI, DIS, DIR}, {ITA, ING, MAT}, {ITA, ING, LELE}];

array[class, weektime] of var 0..1: tbl;

array[class, allsubjects] of 0..3: LB;
 
constraint forall (i in class, k in subjclass[i]) (sum([tbl[i,j] | j in weektime where subjects[i,j] == k]) >= LB[i,k]);

正如我编写约束一样，我需要定义参数数组

LB

，例如在单独的数据文件中。然而，如您所见，该数组有 4 行 66 列，其中大部分为零。

LB = 
[|0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,2,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,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,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,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,0,0,0,0,0,0,0,0,0,0,0,0,1,0,2,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,2,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,0,0,0,0,0,0,1,0,2,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,0,0,0,0,0,0,0,0,0,0,0,0,0,0
 |];

我花了很长时间来插入参数数组

LB

，实际上我使用的是一组其他模拟约束，更容易编写，但是这些解决方案要求模型中有数据，这是不可取的用于泛化和重用。

% class 1
constraint sum([tbl[1,j] | j in weektime where subjects[1,j] == ITA]) >= 2;
constraint sum([tbl[1,j] | j in weektime where subjects[1,j] == ING]) >= 1;

% class 2
constraint sum([tbl[2,j] | j in weektime where subjects[2,j] == DIS]) >= 1;

% class 3
constraint sum([tbl[3,j] | j in weektime where subjects[3,j] == ITA]) >= 2;
constraint sum([tbl[3,j] | j in weektime where subjects[3,j] == ING]) >= 1;
constraint sum([tbl[3,j] | j in weektime where subjects[3,j] == MAT]) >= 2;

% class 4
constraint sum([tbl[4,j] | j in weektime where subjects[4,j] == ITA]) >= 2;
constraint sum([tbl[4,j] | j in weektime where subjects[4,j] == ING]) >= 1;
constraint sum([tbl[4,j] | j in weektime where subjects[4,j] == LELE]) = 1;

所以问题是是否有办法以更简单的形式在参数数组中拥有相同的数据

LB 

，例如这样：

subjclass = [{ITA, ING}, {CHI, SCI, DIS, DIR}, {ITA, ING, MAT}, {ITA, ING, LELE}];
LB = [       {2,   1},   {0,   0,   1,   0},   {2,   1,   2},   {2,   1,   1}];

也许我需要改变模型的结构，但我找不到正确的方法。

Answer 1

最新版本的 MiniZinc 现在支持记录和元组。在这种情况下，这些数据类型可以允许您以稀疏格式提供相同的数据。

您可以将

LB

的声明更改为

array[int] of record(class: cl, all subjects: subj, 1..3: bound): LB;

它下面的约束就变成了

constraint forall (i in index_set(LB)) (
  sum([tbl[LB[i].cl,j] | j in weektime where subjects[LB[i].cl,j] == LB[i].subj]) >= LB[i].bound
);

对模型进行这些更改后，数据可以提供为：

LB = [
  (cl: 1, subj: ITA, bound: 2),
  (cl: 1, subj: ING, bound: 1),
  ...
  (cl: 4, subj: LELE, bound: 1),
];

并且只需列出

LB

中的非零情况。