modelingminizinc

MiniZinc: simplify a parameter array almost full of zero

I'm working on a model about timetables, and i have a question about a constraint. Here is the model (i deleted all the not necessary part for the 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]);

Just as i wrote the constraint, i need to define the parameter array LB, for example in a separate data file. However the array is 4 rows and 66 columns, most of which are zero, as you can see.

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
 |];

I take a very long time to insert the parameter array LB, and actually i'm using instead a set of other analogue constraints, more easy to write, but these solution request to have data in the model, which is not desiderable for generalization and reuse.

% 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;

So the question is if there is a way to have the same data in the parameter array LB in a more simple form, for example something like this:

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}];

Maybe i need to change the structure of the model, but i cannot find the right way.

Solution

  • The latest versions of MiniZinc now have support for Records and Tuples. These data types could in this case allow you to provide the same data in a sparse format.

    You could change the declaration of LB to be

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

    And the constraint underneath it then becomes

    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
);

    With these changes to the model, the data can then be provided as:

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

    And only the non-zero cases in LB have to be listed.