lemon-project-template-glpk

annotate deps/glpk/examples/hashi.mod @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
rev   line source
alpar@9 1 /* A solver for the Japanese number-puzzle Hashiwokakero
alpar@9 2 * (http://en.wikipedia.org/wiki/Hashiwokakero)
alpar@9 3 *
alpar@9 4 * Sebastian Nowozin <nowozin@gmail.com>, 13th January 2009
alpar@9 5 */
alpar@9 6
alpar@9 7 param n := 25;
alpar@9 8 set rows := 1..n;
alpar@9 9 set cols := 1..n;
alpar@9 10 param givens{rows, cols}, integer, >= 0, <= 8, default 0;
alpar@9 11
alpar@9 12 /* Set of vertices as (row,col) coordinates */
alpar@9 13 set V := { (i,j) in { rows, cols }: givens[i,j] != 0 };
alpar@9 14
alpar@9 15 /* Set of feasible horizontal edges from (i,j) to (k,l) rightwards */
alpar@9 16 set Eh := { (i,j,k,l) in { V, V }:
alpar@9 17 i = k and j < l and # Same row and left to right
alpar@9 18 card({ (s,t) in V: s = i and t > j and t < l }) = 0 # No vertex inbetween
alpar@9 19 };
alpar@9 20
alpar@9 21 /* Set of feasible vertical edges from (i,j) to (k,l) downwards */
alpar@9 22 set Ev := { (i,j,k,l) in { V, V }:
alpar@9 23 j = l and i < k and # Same column and top to bottom
alpar@9 24 card({ (s,t) in V: t = j and s > i and s < k }) = 0 # No vertex inbetween
alpar@9 25 };
alpar@9 26
alpar@9 27 set E := Eh union Ev;
alpar@9 28
alpar@9 29 /* Indicators: use edge once/twice */
alpar@9 30 var xe1{E}, binary;
alpar@9 31 var xe2{E}, binary;
alpar@9 32
alpar@9 33 /* Constraint: Do not use edge or do use once or do use twice */
alpar@9 34 s.t. edge_sel{(i,j,k,l) in E}:
alpar@9 35 xe1[i,j,k,l] + xe2[i,j,k,l] <= 1;
alpar@9 36
alpar@9 37 /* Constraint: There must be as many edges used as the node value */
alpar@9 38 s.t. satisfy_vertex_demand{(s,t) in V}:
alpar@9 39 sum{(i,j,k,l) in E: (i = s and j = t) or (k = s and l = t)}
alpar@9 40 (xe1[i,j,k,l] + 2.0*xe2[i,j,k,l]) = givens[s,t];
alpar@9 41
alpar@9 42 /* Constraint: No crossings */
alpar@9 43 s.t. no_crossing1{(i,j,k,l) in Eh, (s,t,u,v) in Ev:
alpar@9 44 s < i and u > i and j < t and l > t}:
alpar@9 45 xe1[i,j,k,l] + xe1[s,t,u,v] <= 1;
alpar@9 46 s.t. no_crossing2{(i,j,k,l) in Eh, (s,t,u,v) in Ev:
alpar@9 47 s < i and u > i and j < t and l > t}:
alpar@9 48 xe1[i,j,k,l] + xe2[s,t,u,v] <= 1;
alpar@9 49 s.t. no_crossing3{(i,j,k,l) in Eh, (s,t,u,v) in Ev:
alpar@9 50 s < i and u > i and j < t and l > t}:
alpar@9 51 xe2[i,j,k,l] + xe1[s,t,u,v] <= 1;
alpar@9 52 s.t. no_crossing4{(i,j,k,l) in Eh, (s,t,u,v) in Ev:
alpar@9 53 s < i and u > i and j < t and l > t}:
alpar@9 54 xe2[i,j,k,l] + xe2[s,t,u,v] <= 1;
alpar@9 55
alpar@9 56
alpar@9 57 /* Model connectivity by auxiliary network flow problem:
alpar@9 58 * One vertex becomes a target node and all other vertices send a unit flow
alpar@9 59 * to it. The edge selection variables xe1/xe2 are VUB constraints and
alpar@9 60 * therefore xe1/xe2 select the feasible graph for the max-flow problems.
alpar@9 61 */
alpar@9 62 set node_target := { (s,t) in V:
alpar@9 63 card({ (i,j) in V: i < s or (i = s and j < t) }) = 0};
alpar@9 64 set node_sources := { (s,t) in V: (s,t) not in node_target };
alpar@9 65
alpar@9 66 var flow_forward{ E }, >= 0;
alpar@9 67 var flow_backward{ E }, >= 0;
alpar@9 68 s.t. flow_conservation{ (s,t) in node_target, (p,q) in V }:
alpar@9 69 /* All incoming flows */
alpar@9 70 - sum{(i,j,k,l) in E: k = p and l = q} flow_forward[i,j,k,l]
alpar@9 71 - sum{(i,j,k,l) in E: i = p and j = q} flow_backward[i,j,k,l]
alpar@9 72 /* All outgoing flows */
alpar@9 73 + sum{(i,j,k,l) in E: k = p and l = q} flow_backward[i,j,k,l]
alpar@9 74 + sum{(i,j,k,l) in E: i = p and j = q} flow_forward[i,j,k,l]
alpar@9 75 = 0 + (if (p = s and q = t) then card(node_sources) else -1);
alpar@9 76
alpar@9 77 /* Variable-Upper-Bound (VUB) constraints: xe1/xe2 bound the flows.
alpar@9 78 */
alpar@9 79 s.t. connectivity_vub1{(i,j,k,l) in E}:
alpar@9 80 flow_forward[i,j,k,l] <= card(node_sources)*(xe1[i,j,k,l] + xe2[i,j,k,l]);
alpar@9 81 s.t. connectivity_vub2{(i,j,k,l) in E}:
alpar@9 82 flow_backward[i,j,k,l] <= card(node_sources)*(xe1[i,j,k,l] + xe2[i,j,k,l]);
alpar@9 83
alpar@9 84 /* A feasible solution is enough
alpar@9 85 */
alpar@9 86 minimize cost: 0;
alpar@9 87
alpar@9 88 solve;
alpar@9 89
alpar@9 90 /* Output solution graphically */
alpar@9 91 printf "\nSolution:\n";
alpar@9 92 for { row in rows } {
alpar@9 93 for { col in cols } {
alpar@9 94 /* First print this cell information: givens or space */
alpar@9 95 printf{0..0: givens[row,col] != 0} "%d", givens[row,col];
alpar@9 96 printf{0..0: givens[row,col] = 0 and
alpar@9 97 card({(i,j,k,l) in Eh: i = row and col >= j and col < l and
alpar@9 98 xe1[i,j,k,l] = 1}) = 1} "-";
alpar@9 99 printf{0..0: givens[row,col] = 0 and
alpar@9 100 card({(i,j,k,l) in Eh: i = row and col >= j and col < l and
alpar@9 101 xe2[i,j,k,l] = 1}) = 1} "=";
alpar@9 102 printf{0..0: givens[row,col] = 0
alpar@9 103 and card({(i,j,k,l) in Ev: j = col and row >= i and row < k and
alpar@9 104 xe1[i,j,k,l] = 1}) = 1} "|";
alpar@9 105 printf{0..0: givens[row,col] = 0
alpar@9 106 and card({(i,j,k,l) in Ev: j = col and row >= i and row < k and
alpar@9 107 xe2[i,j,k,l] = 1}) = 1} '"';
alpar@9 108 printf{0..0: givens[row,col] = 0
alpar@9 109 and card({(i,j,k,l) in Eh: i = row and col >= j and col < l and
alpar@9 110 (xe1[i,j,k,l] = 1 or xe2[i,j,k,l] = 1)}) = 0
alpar@9 111 and card({(i,j,k,l) in Ev: j = col and row >= i and row < k and
alpar@9 112 (xe1[i,j,k,l] = 1 or xe2[i,j,k,l] = 1)}) = 0} " ";
alpar@9 113
alpar@9 114 /* Now print any edges */
alpar@9 115 printf{(i,j,k,l) in Eh: i = row and col >= j and col < l and xe1[i,j,k,l] = 1} "-";
alpar@9 116 printf{(i,j,k,l) in Eh: i = row and col >= j and col < l and xe2[i,j,k,l] = 1} "=";
alpar@9 117
alpar@9 118 printf{(i,j,k,l) in Eh: i = row and col >= j and col < l and
alpar@9 119 xe1[i,j,k,l] = 0 and xe2[i,j,k,l] = 0} " ";
alpar@9 120 printf{0..0: card({(i,j,k,l) in Eh: i = row and col >= j and col < l}) = 0} " ";
alpar@9 121 }
alpar@9 122 printf "\n";
alpar@9 123 for { col in cols } {
alpar@9 124 printf{(i,j,k,l) in Ev: j = col and row >= i and row < k and xe1[i,j,k,l] = 1} "|";
alpar@9 125 printf{(i,j,k,l) in Ev: j = col and row >= i and row < k and xe2[i,j,k,l] = 1} '"';
alpar@9 126 printf{(i,j,k,l) in Ev: j = col and row >= i and row < k and
alpar@9 127 xe1[i,j,k,l] = 0 and xe2[i,j,k,l] = 0} " ";
alpar@9 128 /* No vertical edges: skip also a field */
alpar@9 129 printf{0..0: card({(i,j,k,l) in Ev: j = col and row >= i and row < k}) = 0} " ";
alpar@9 130 printf " ";
alpar@9 131 }
alpar@9 132 printf "\n";
alpar@9 133 }
alpar@9 134
alpar@9 135 data;
alpar@9 136
alpar@9 137 /* This is a difficult 25x25 Hashiwokakero.
alpar@9 138 */
alpar@9 139 param givens : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
alpar@9 140 25 :=
alpar@9 141 1 2 . 2 . 2 . . 2 . 2 . . 2 . . . . 2 . 2 . 2 . 2 .
alpar@9 142 2 . 1 . . . . 2 . . . 4 . . 5 . 2 . . 1 . 2 . 2 . 1
alpar@9 143 3 2 . . 5 . 4 . . 3 . . . . . 1 . . 4 . 5 . 1 . 1 .
alpar@9 144 4 . . . . . . . . . . . 1 . 3 . . 1 . . . . . . . .
alpar@9 145 5 2 . . 6 . 6 . . 8 . 5 . 2 . . 3 . 5 . 7 . . 2 . .
alpar@9 146 6 . 1 . . . . . . . . . 1 . . 2 . . . . . 1 . . . 3
alpar@9 147 7 2 . . . . 5 . . 6 . 4 . . 2 . . . 2 . 5 . 4 . 2 .
alpar@9 148 8 . 2 . 2 . . . . . . . . . . . 3 . . 3 . . . 1 . 2
alpar@9 149 9 . . . . . . . . . . 4 . 2 . 2 . . 1 . . . 3 . 1 .
alpar@9 150 10 2 . 3 . . 6 . . 2 . . . . . . . . . . 3 . . . . .
alpar@9 151 11 . . . . 1 . . 2 . . 5 . . 1 . 4 . 3 . . . . 2 . 4
alpar@9 152 12 . . 2 . . 1 . . . . . . 5 . 4 . . . . 4 . 3 . . .
alpar@9 153 13 2 . . . 3 . 1 . . . . . . . . 3 . . 5 . 5 . . 2 .
alpar@9 154 14 . . . . . 2 . 5 . . 7 . 5 . 3 . 1 . . 1 . . 1 . 4
alpar@9 155 15 2 . 5 . 3 . . . . 1 . 2 . 1 . . . . 2 . 4 . . 2 .
alpar@9 156 16 . . . . . 1 . . . . . . . . . . 2 . . 2 . 1 . . 3
alpar@9 157 17 2 . 6 . 6 . . 2 . . 2 . 2 . 5 . . . . . 2 . . . .
alpar@9 158 18 . . . . . 1 . . . 3 . . . . . 1 . . 1 . . 4 . 3 .
alpar@9 159 19 . . 4 . 5 . . 2 . . . 2 . . 6 . 6 . . 3 . . . . 3
alpar@9 160 20 2 . . . . . . . . . 2 . . 1 . . . . . . 1 . . 1 .
alpar@9 161 21 . . 3 . . 3 . 5 . 5 . . 4 . 6 . 7 . . 4 . 6 . . 4
alpar@9 162 22 2 . . . 3 . 5 . 2 . 1 . . . . . . . . . . . . . .
alpar@9 163 23 . . . . . . . . . 1 . . . . . . 3 . 2 . . 5 . . 5
alpar@9 164 24 2 . 3 . 3 . 5 . 4 . 3 . 3 . 4 . . 2 . 2 . . . 1 .
alpar@9 165 25 . 1 . 2 . 2 . . . 2 . 2 . . . 2 . . . . 2 . 2 . 2
alpar@9 166 ;
alpar@9 167
alpar@9 168 end;