Created
September 19, 2025 16:29
-
-
Save Lipen/58b71df7bcf499ab27651759069f37ab to your computer and use it in GitHub Desktop.
MiniZinc model for Jaccard similarity problem data generation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| int: n_objects = 9; | |
| int: n_sets = 6; | |
| int: min_set_size = 3; | |
| int: max_set_size = 4; | |
| set of int: OBJ = 1..n_objects; | |
| set of int: SET = 1..n_sets; | |
| array[SET, OBJ] of var bool: membership; | |
| array[SET] of var min_set_size..max_set_size: set_size; | |
| array[SET, SET] of var 0.0 .. 1.0: jaccard; | |
| array[OBJ] of var 0..n_objects: used_times; | |
| constraint forall(s in SET) ( | |
| set_size[s] = sum(o in OBJ)(bool2int(membership[s, o])) | |
| ); | |
| constraint forall(o in OBJ) ( | |
| used_times[o] = sum(s in SET)(bool2int(membership[s, o])) | |
| ); | |
| constraint forall(o in OBJ) ( | |
| used_times[o] >= 2 | |
| ); | |
| % Jaccard definition | |
| constraint forall(s1, s2 in SET where s1 < s2) ( | |
| jaccard[s1, s2] = let { | |
| var int: inter_size = sum(o in OBJ)(bool2int(membership[s1, o] /\ membership[s2, o])), | |
| var int: union_size = set_size[s1] + set_size[s2] - inter_size | |
| } in inter_size / union_size | |
| ); | |
| constraint forall(s1, s2 in SET where s1 < s2) ( | |
| jaccard[s1, s2] < 0.7 | |
| ); | |
| % Specific constraints for components and connections | |
| constraint jaccard[1,2] >= 0.25; | |
| constraint jaccard[2,3] >= 0.25; | |
| constraint jaccard[1,3] < 0.25; | |
| constraint jaccard[4,5] >= 0.5; | |
| constraint jaccard[4,5] < 1.0; | |
| constraint forall(s1 in 1..3, s2 in 4..n_sets) ( | |
| jaccard[s1, s2] < 0.25 | |
| ); | |
| constraint exists(s1 in 1..3, s2 in 4..n_sets) ( | |
| jaccard[s1, s2] > 0 | |
| ); | |
| constraint forall(s1 in 4..5, s2 in 6..n_sets) ( | |
| jaccard[s1, s2] < 0.25 | |
| ); | |
| constraint exists(s1 in 4..5, s2 in 6..n_sets) ( | |
| jaccard[s1, s2] > 0 | |
| ); | |
| % solve satisfy; | |
| % Maximize total similarity: | |
| solve maximize sum(s1, s2 in SET where s1 < s2)(jaccard[s1, s2]); | |
| output [show(set_size) ++ "\n"]; | |
| output [show(used_times) ++ "\n"]; | |
| output [ | |
| "Sets:\n" | |
| ] ++ [ | |
| "Set " ++ show(s) ++ ": {" ++ join(", ", [show(o) | o in OBJ where fix(membership[s, o])]) ++ "}\n" | s in SET | |
| ] ++ [ | |
| "\nJaccard similarities:\n" | |
| ] ++ [ | |
| "J(\(s1),\(s2)) = " ++ show_float(2, 2, fix(jaccard[s1, s2])) ++ "\n" | |
| | s1, s2 in SET where s1 < s2 | |
| ]; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment