Search code examples
minizinc

Few minizinc questions on constraints

A little bit of background. I'm trying to make a model for clustering a Design Structure Matrix(DSM). I made a draft model and have a couple of questions. Most of them are not directly related to DSM per se.

include "globals.mzn";

int: dsmSize = 7;
int: maxClusterSize = 7;
int: maxClusters = 4;
int: powcc = 2;

enum dsmElements = {A, B, C, D, E, F,G};

array[dsmElements, dsmElements] of int: dsm  = 
[|1,1,0,0,1,1,0 
 |0,1,0,1,0,0,1
 |0,1,1,1,0,0,1
 |0,1,1,1,1,0,1
 |0,0,0,1,1,1,0
 |1,0,0,0,1,1,0
 |0,1,1,1,0,0,1|];
 
array[1..maxClusters] of var set of dsmElements: clusters;
array[1..maxClusters] of var int: clusterCard;

constraint forall(i in 1..maxClusters)(
  clusterCard[i] = pow(card(clusters[i]), powcc)
);



% #1
% constraint forall(i, j in clusters where i != j)(card(i intersect j) == 0);

% #2
constraint forall(i, j in 1..maxClusters where i != j)(
  card(clusters[i] intersect clusters[j]) == 0
);

% #3
% constraint all_different([i | i in clusters]);

constraint (clusters[1] union clusters[2] union clusters[3] union clusters[4]) = dsmElements;

var int: intraCost = sum(i in 1..maxClusters, j, k in clusters[i] where k != j)(
  (dsm[j,k] + dsm[k,j]) * clusterCard[i]
) ;                      
                       
var int: extraCost =   sum(el in dsmElements, 
                           c in clusters where card(c intersect {el}) = 0, 
                           k,j in c)(
                              (dsm[j,k] + dsm[k,j]) * pow(card(dsmElements), powcc)
);



var int: TCC = trace("\(intraCost), \(extraCost)\n", intraCost+extraCost);


solve maximize TCC;

Question 1

I was under the impression, that constraints #1 and #2 are the same. However, seems like they are not. The question here is why? What is the difference?

Question 2

How can I replace constraint #2 with all_different? Does it make sense?

Question 3

Why the trace("\(intraCost), \(extraCost)\n", intraCost+extraCost); shows nothing in the output? The output I see using gecode is:

Running dsm.mzn
intraCost, extraCost
clusters = array1d(1..4, [{A, B, C, D, E, F, G}, {}, {}, {}]);
clusterCard = array1d(1..4, [49, 0, 0, 0]);
----------
<sipped to save space>
----------
clusters = array1d(1..4, [{B, C, D, G}, {A, E, F}, {}, {}]);
clusterCard = array1d(1..4, [16, 9, 0, 0]);
----------
==========
Finished in 5s 419msec

Question 4

The expression constraint (clusters[1] union clusters[2] union clusters[3] union clusters[4]) = dsmElements;, here I wanted to say that the union of all clusters should match the set of all nodes. Unfortunately, I did not find a way to make this big union more dynamic, so for now I just manually provide all clusters. Is there a way to make this expression return union of all sets from the array of sets?

Question 5

Basically, if I understand it correctly, for example from here, the Intra-cluster cost is the sum of all interactions within a cluster multiplied by the size of the cluster in some power, basically the cardinality of the set of nodes, that represents the cluster.

enter image description here

The Extra-cluster cost is a sum of interactions between some random element that does not belong to a cluster and all elements of that cluster multiplied by the cardinality of the whole space of nodes to some power.

enter image description here

The main question here is are the intraCost and extraCost I the model correct (they seem to be but still), and is there a better way to express these sums?

Thanks!

Solution

  • (Perhaps you would get more answers if you separate this into multiple questions.)

    Question 3: Here's an answer on the trace question:

    When running the model, the trace actually shows this:

    intraCost, extraCost

    which is not what you expect, of course. Trace is in effect when creating the model, but at that stage there is no value of these two decision values and MiniZinc shows only the variable names. They got some values to show after the (first) solution is reached, and can then be shown in the output section.

    trace is mostly used to see what's happening in loops where one can trace the (fixed) loop variables etc.

    If you trace an array of decision variables then they will be represented in a different fashion, the array x will be shown as X_INTRODUCED_0_ etc.

    And you can also use trace for domain reflection, e.g. using lb and ub to get the lower/upper value of the domain of a variable ("safe approximation of the bounds" as the documentation states it: https://www.minizinc.org/doc-2.5.5/en/predicates.html?highlight=ub_array). Here's an example which shows the domain of the intraCost variable:

    constraint
  trace("intraCost: \(lb(intraCost))..\(ub(intraCost))\n")
;

    which shows

    intraCost: -infinity..infinity

    You can read a little more about trace here https://www.minizinc.org/doc-2.5.5/en/efficient.html?highlight=trace .

    Update Answer to question 1, 2 and 4.

    The constraint #1 and #2 means the same thing, i.e. that the elements in clusters should be disjoint. The #1 constraint is a little different in that it loops over decision variables while the #2 constraint use plain indices. One can guess that #2 is faster since #1 use the where i != j which must be translated to some extra constraints. (And using i < j instead should be a little faster.)

    The all_different constraint states about the same and depending on the underlying solver it might be faster if it's translated to an efficient algorithm in the solver.

    In the model there is also the following constraint which states that all elements must be used:

    constraint (clusters[1] union clusters[2] union clusters[3] union clusters[4]) = dsmElements;

    Apart from efficiency, all these constraints above can be replaced with one single constraint: partition_set which ensure that all elements in dsmElements must be used in clusters.

    constraint partition_set(clusters,dsmElements);

    It might be faster to also combine with the all_different constraint, but that has to be tested.