Search code examples
constraint-programmingminizinc

MiniZinc: Obtain a super set of array of sets


I am working on a constraint programming problem but stuck at a specific step and need suggestions.

My data has a bunch of orders with each order having some SKUs. I want to group these orders in different batches and then count unique SKUs in a batch/group. For e.g.

Order 1 - SKUs 1, 2, 3 
Order 2 - SKUs 2, 5 
Order 3 - SKUs 1, 3, 7
Order 4 - SKUs 3, 4, 6

Now, if I group Orders 1 & 4 in Batch 1 while Orders 2 & 3 in Batch 2 then following will be unique SKU count in each batch:

Batch 1 - SKUs 1, 2, 3, 4, 6 = 5 SKUs
Batch 2 - SKUs 1, 2, 3, 5, 7 = 5 SKUs

My code is as below

include "globals.mzn"; 

int: N_Orders = 14; % Number of orders
set of int: ORDERS = 1..N_Orders;
set of int: skuids = {1,2,3,4,5}; % Distinct sku ids across all orders
array[ORDERS] of set of skuids: oskuids = [{1,2,3},{1,3},{4},{4,5},{1},{1,4},{3,4},{5},{1,4,5},{1,2,3},{1,3},{4,5},{1},{1,4}]; % Distinct SKU ids in each order

% Orders per batch
ORDERS: x = 2; 

% Batches needed
int: N_Batches = 7;


% Define array that contains batch for each order
array[ORDERS] of var 1..N_Batches: obatch;
constraint global_cardinality(obatch, [i | i in (1..N_Batches-1)], [x | i in 1..(N_Batches-1)]); % Total orders in batch set to 'x'

% Distinct skus in each batch
array[1..N_Batches] of var int: skus_in_batch;
constraint forall(i in 1..N_Batches)(
             skus_in_batch[i] = card(array_union(o in ORDERS where obatch[o] = i)(oskuids[o]))
           );

solve satisfy;

On running this code, I get following error:

MiniZinc: type error: no function or predicate with this signature found: `array_union(array[int] of var opt set of int)'

How can I modify code to give me the required result?


Solution

  • Here is the answer I received from the architects of MiniZinc on another forum and realized that this method can be used at many other similar situations where we receive error due to unsupported option types -

    The expression

    skus_in_batch[i] = card(array_union(o in ORDERS where   
                       obatch[o] = i)(oskuids[o]));
    

    Is effectively equivalent to

    skus_in_batch[i] = card(array_union([ if obatch[o] = i then oskuids[o] else top endif | o in ORDERS]]);
    

    and hence fails since array_union is not able to handle the array of optional sets that are created. You can simple rewrite it to below to avoid option types.

    skus_in_batch[i] = card(array_union([ if obatch[o] = i then oskuids[o] else {} endif | o in ORDERS]]);
    
    or equivalently
    
    skus_in_batch[i] = card(array_union(o in ORDERS)
                       (if obatch[o] = i then oskuids[o] else {} endif));