1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | language Essence 1.3 $ Problem Minimum Energy Broadcast $ $ Problem details available at http://www.csplib.org/Problems/prob048/ $ $ Essence model by Andrew Martin $ $ Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/ given numNodes : int (1..) given maxPower : int (1..) given initialNode : int (1..) letting dNodes be domain int (1..numNodes) letting dPower be domain int (0..maxPower) $ if a node has power link of 0 to another node, that link is not possible given linkCosts : matrix indexed by [dNodes, dNodes] of dPower $ if a node has power of 0 it is not broadcasting find nodeBroadcastPower : matrix indexed by [dNodes] of dPower $ AUX FIND VALUES, appear in solution but are not important - $ checking that these exist is much slower than 'find'ing values for them find directChildrenMatrix : matrix indexed by [dNodes] of set of dNodes find totalChildrenMatrix : matrix indexed by [dNodes] of set of dNodes $ minimising total power usage minimising ( sum i : dNodes . nodeBroadcastPower[i]) such that $ NODES DO NOT SHARE CHILDREN forAll i,j : dNodes . i=j \/ |directChildrenMatrix[i] intersect directChildrenMatrix[j]| = 0 , $ TOTAL CHILD NODES OF NODE initialNode MUST BE SIZE NUMNODES (THUS CONTAINING ALL NODES) |totalChildrenMatrix[initialNode]| = numNodes /\ forAll node : dNodes . $ EACH NODE IS A TOTAL CHILD OF ITSELF node in totalChildrenMatrix[node] /\ $ ENSURE NODES TOTAL EQUALS THE SUM OF ITS DIRECT CHILDRENS TOTALS + ITSELF $ (Each link must add a new node to the graph, not including cycles) ( sum i in directChildrenMatrix[node] . |totalChildrenMatrix[i]|) = |totalChildrenMatrix[node]| - 1 /\ $ NODE MUST HAVE TOTALCHILDREN CONTAIN A SUBSET WHICH IS THE TOTALCHILDREN OF EACH DIRECT CHILD forAll childNode in directChildrenMatrix[node] . totalChildrenMatrix[childNode] subsetEq totalChildrenMatrix[node] /\ $ LINK MUST BE ALLOWED linkCosts[node][childNode] != 0 /\ $ CONSTRAINT FOR PROBLEM SOLUTION nodeBroadcastPower[node] >= linkCosts[node][childNode] |