lemon-project-template-glpk

annotate deps/glpk/examples/pbn/pbn.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 /* PBN, Paint-By-Numbers Puzzle */
alpar@9 2
alpar@9 3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
alpar@9 4
alpar@9 5 /* NOTE: See also the document "Solving Paint-By-Numbers Puzzles with
alpar@9 6 GLPK", which is included in the GLPK distribution. */
alpar@9 7
alpar@9 8 /* A paint-by-numbers puzzle consists of an m*n grid of pixels (the
alpar@9 9 canvas) together with m+n cluster-size sequences, one for each row
alpar@9 10 and column. The goal is to paint the canvas with a picture that
alpar@9 11 satisfies the following constraints:
alpar@9 12
alpar@9 13 1. Each pixel must be blank or white.
alpar@9 14
alpar@9 15 2. If a row or column has cluster-size sequence s1, s2, ..., sk,
alpar@9 16 then it must contain k clusters of black pixels - the first with
alpar@9 17 s1 black pixels, the second with s2 black pixels, and so on.
alpar@9 18
alpar@9 19 It should be noted that "first" means "leftmost" for rows and
alpar@9 20 "topmost" for columns, and that rows and columns need not begin or
alpar@9 21 end with black pixels.
alpar@9 22
alpar@9 23 Example:
alpar@9 24 1 1
alpar@9 25 1 1
alpar@9 26 2 1 1 1 1 1 2 3
alpar@9 27 3 2 1 2 1 2 3 4 8 9
alpar@9 28
alpar@9 29 3 6 # # # . # # # # # #
alpar@9 30 1 4 # . . . . . # # # #
alpar@9 31 1 1 3 . . # . # . . # # #
alpar@9 32 2 . . . . . . . . # #
alpar@9 33 3 3 . . # # # . . # # #
alpar@9 34 1 4 # . . . . . # # # #
alpar@9 35 2 5 # # . . . # # # # #
alpar@9 36 2 5 # # . . . # # # # #
alpar@9 37 1 1 . . . # . . . . . #
alpar@9 38 3 . . # # # . . . . .
alpar@9 39
alpar@9 40 (In Russia such puzzles are known as "Japanese crosswords".)
alpar@9 41
alpar@9 42 References:
alpar@9 43 Robert A. Bosch, "Painting by Numbers", 2000.
alpar@9 44 <http://www.oberlin.edu/~math/faculty/bosch/pbn-page.html> */
alpar@9 45
alpar@9 46 /*--------------------------------------------------------------------*/
alpar@9 47 /* Main part based on the formulation proposed by Robert Bosch. */
alpar@9 48
alpar@9 49 param m, integer, >= 1;
alpar@9 50 /* the number of rows */
alpar@9 51
alpar@9 52 param n, integer, >= 1;
alpar@9 53 /* the number of columns */
alpar@9 54
alpar@9 55 param row{i in 1..m, 1..n div 2}, integer, >= 0, default 0;
alpar@9 56 /* the cluster-size sequence for row i (raw data) */
alpar@9 57
alpar@9 58 param col{j in 1..n, 1..m div 2}, integer, >= 0, default 0;
alpar@9 59 /* the cluster-size sequence for column j (raw data) */
alpar@9 60
alpar@9 61 param kr{i in 1..m} := sum{t in 1..n div 2: row[i,t] > 0} 1;
alpar@9 62 /* the number of clusters in row i */
alpar@9 63
alpar@9 64 param kc{j in 1..n} := sum{t in 1..m div 2: col[j,t] > 0} 1;
alpar@9 65 /* the number of clusters in column j */
alpar@9 66
alpar@9 67 param sr{i in 1..m, t in 1..kr[i]} := row[i,t], integer, >= 1;
alpar@9 68 /* the cluster-size sequence for row i */
alpar@9 69
alpar@9 70 param sc{j in 1..n, t in 1..kc[j]} := col[j,t], integer, >= 1;
alpar@9 71 /* the cluster-size sequence for column j */
alpar@9 72
alpar@9 73 check{i in 1..m}: sum{t in 1..kr[i]} sr[i,t] <= n - (kr[i] - 1);
alpar@9 74 /* check that the sum of the cluster sizes in each row is valid */
alpar@9 75
alpar@9 76 check{j in 1..n}: sum{t in 1..kc[j]} sc[j,t] <= m - (kc[j] - 1);
alpar@9 77 /* check that the sum of the cluster sizes in each column is valid */
alpar@9 78
alpar@9 79 check: sum{i in 1..m, t in 1..kr[i]} sr[i,t] =
alpar@9 80 sum{j in 1..n, t in 1..kc[j]} sc[j,t];
alpar@9 81 /* check that the sum of the cluster sizes in all rows is equal to the
alpar@9 82 sum of the cluster sizes in all columns */
alpar@9 83
alpar@9 84 param er{i in 1..m, t in 1..kr[i]} :=
alpar@9 85 if t = 1 then 1 else er[i,t-1] + sr[i,t-1] + 1;
alpar@9 86 /* the smallest value of j such that row i's t-th cluster can be
alpar@9 87 placed in row i with its leftmost pixel occupying pixel j */
alpar@9 88
alpar@9 89 param lr{i in 1..m, t in 1..kr[i]} :=
alpar@9 90 if t = kr[i] then n + 1 - sr[i,t] else lr[i,t+1] - sr[i,t] - 1;
alpar@9 91 /* the largest value of j such that row i's t-th cluster can be
alpar@9 92 placed in row i with its leftmost pixel occupying pixel j */
alpar@9 93
alpar@9 94 param ec{j in 1..n, t in 1..kc[j]} :=
alpar@9 95 if t = 1 then 1 else ec[j,t-1] + sc[j,t-1] + 1;
alpar@9 96 /* the smallest value of i such that column j's t-th cluster can be
alpar@9 97 placed in column j with its topmost pixel occupying pixel i */
alpar@9 98
alpar@9 99 param lc{j in 1..n, t in 1..kc[j]} :=
alpar@9 100 if t = kc[j] then m + 1 - sc[j,t] else lc[j,t+1] - sc[j,t] - 1;
alpar@9 101 /* the largest value of i such that column j's t-th cluster can be
alpar@9 102 placed in column j with its topmost pixel occupying pixel i */
alpar@9 103
alpar@9 104 var z{i in 1..m, j in 1..n}, binary;
alpar@9 105 /* z[i,j] = 1, if row i's j-th pixel is painted black
alpar@9 106 z[i,j] = 0, if row i's j-th pixel is painted white */
alpar@9 107
alpar@9 108 var y{i in 1..m, t in 1..kr[i], j in er[i,t]..lr[i,t]}, binary;
alpar@9 109 /* y[i,t,j] = 1, if row i's t-th cluster is placed in row i with its
alpar@9 110 leftmost pixel occupying pixel j
alpar@9 111 y[i,t,j] = 0, if not */
alpar@9 112
alpar@9 113 var x{j in 1..n, t in 1..kc[j], i in ec[j,t]..lc[j,t]}, binary;
alpar@9 114 /* x[j,t,i] = 1, if column j's t-th cluster is placed in column j with
alpar@9 115 its topmost pixel occupying pixel i
alpar@9 116 x[j,t,i] = 0, if not */
alpar@9 117
alpar@9 118 s.t. fa{i in 1..m, t in 1..kr[i]}:
alpar@9 119 sum{j in er[i,t]..lr[i,t]} y[i,t,j] = 1;
alpar@9 120 /* row i's t-th cluster must appear in row i exactly once */
alpar@9 121
alpar@9 122 s.t. fb{i in 1..m, t in 1..kr[i]-1, j in er[i,t]..lr[i,t]}:
alpar@9 123 y[i,t,j] <= sum{jp in j+sr[i,t]+1..lr[i,t+1]} y[i,t+1,jp];
alpar@9 124 /* row i's (t+1)-th cluster must be placed to the right of its t-th
alpar@9 125 cluster */
alpar@9 126
alpar@9 127 s.t. fc{j in 1..n, t in 1..kc[j]}:
alpar@9 128 sum{i in ec[j,t]..lc[j,t]} x[j,t,i] = 1;
alpar@9 129 /* column j's t-th cluster must appear in column j exactly once */
alpar@9 130
alpar@9 131 s.t. fd{j in 1..n, t in 1..kc[j]-1, i in ec[j,t]..lc[j,t]}:
alpar@9 132 x[j,t,i] <= sum{ip in i+sc[j,t]+1..lc[j,t+1]} x[j,t+1,ip];
alpar@9 133 /* column j's (t+1)-th cluster must be placed below its t-th cluster */
alpar@9 134
alpar@9 135 s.t. fe{i in 1..m, j in 1..n}:
alpar@9 136 z[i,j] <= sum{t in 1..kr[i], jp in er[i,t]..lr[i,t]:
alpar@9 137 j-sr[i,t]+1 <= jp and jp <= j} y[i,t,jp];
alpar@9 138 /* the double coverage constraint stating that if row i's j-th pixel
alpar@9 139 is painted black, then at least one of row i's clusters must be
alpar@9 140 placed in such a way that it covers row i's j-th pixel */
alpar@9 141
alpar@9 142 s.t. ff{i in 1..m, j in 1..n}:
alpar@9 143 z[i,j] <= sum{t in 1..kc[j], ip in ec[j,t]..lc[j,t]:
alpar@9 144 i-sc[j,t]+1 <= ip and ip <= i} x[j,t,ip];
alpar@9 145 /* the double coverage constraint making sure that if row i's j-th
alpar@9 146 pixel is painted black, then at least one of column j's clusters
alpar@9 147 covers it */
alpar@9 148
alpar@9 149 s.t. fg{i in 1..m, j in 1..n, t in 1..kr[i], jp in er[i,t]..lr[i,t]:
alpar@9 150 j-sr[i,t]+1 <= jp and jp <= j}: z[i,j] >= y[i,t,jp];
alpar@9 151 /* the constraint to prevent white pixels from being covered by the
alpar@9 152 row clusters */
alpar@9 153
alpar@9 154 s.t. fh{i in 1..m, j in 1..n, t in 1..kc[j], ip in ec[j,t]..lc[j,t]:
alpar@9 155 i-sc[j,t]+1 <= ip and ip <= i}: z[i,j] >= x[j,t,ip];
alpar@9 156 /* the constraint to prevent white pixels from being covered by the
alpar@9 157 column clusters */
alpar@9 158
alpar@9 159 /* this is a feasibility problem, so no objective is needed */
alpar@9 160
alpar@9 161 /*--------------------------------------------------------------------*/
alpar@9 162 /* The following part is used only to check for multiple solutions. */
alpar@9 163
alpar@9 164 param zz{i in 1..m, j in 1..n}, binary, default 0;
alpar@9 165 /* zz[i,j] is z[i,j] for a previously found solution */
alpar@9 166
alpar@9 167 s.t. fz{1..1 : sum{i in 1..m, j in 1..n} zz[i,j] > 0}:
alpar@9 168 sum{i in 1..m, j in 1..n}
alpar@9 169 (if zz[i,j] then (1 - z[i,j]) else z[i,j]) >= 1;
alpar@9 170 /* the constraint to forbid finding a solution, which is identical to
alpar@9 171 the previously found one; this constraint is included in the model
alpar@9 172 only if the previously found solution specified by the parameter zz
alpar@9 173 is provided in the data section */
alpar@9 174
alpar@9 175 solve;
alpar@9 176
alpar@9 177 /*--------------------------------------------------------------------*/
alpar@9 178 /* Print solution to the standard output. */
alpar@9 179
alpar@9 180 for {i in 1..m}
alpar@9 181 { printf{j in 1..n} " %s", if z[i,j] then "#" else ".";
alpar@9 182 printf "\n";
alpar@9 183 }
alpar@9 184
alpar@9 185 /*--------------------------------------------------------------------*/
alpar@9 186 /* Write solution to a text file in PostScript format. */
alpar@9 187
alpar@9 188 param ps, symbolic, default "solution.ps";
alpar@9 189
alpar@9 190 printf "%%!PS-Adobe-3.0\n" > ps;
alpar@9 191 printf "%%%%Creator: GLPK (pbn.mod)\n" >> ps;
alpar@9 192 printf "%%%%BoundingBox: 0 0 %d %d\n",
alpar@9 193 6 * (n + 2), 6 * (m + 2) >> ps;
alpar@9 194 printf "%%%%EndComments\n" >> ps;
alpar@9 195 printf "<</PageSize [%d %d]>> setpagedevice\n",
alpar@9 196 6 * (n + 2), 6 * (m + 2) >> ps;
alpar@9 197 printf "0.1 setlinewidth\n" >> ps;
alpar@9 198 printf "/A { 2 copy 2 copy 2 copy newpath moveto exch 6 add exch line" &
alpar@9 199 "to\n" >> ps;
alpar@9 200 printf "exch 6 add exch 6 add lineto 6 add lineto closepath } bind de" &
alpar@9 201 "f\n" >> ps;
alpar@9 202 printf "/W { A stroke } def\n" >> ps;
alpar@9 203 printf "/B { A fill } def\n" >> ps;
alpar@9 204 printf {i in 1..m, j in 1..n} "%d %d %s\n",
alpar@9 205 (j - 1) * 6 + 6, (m - i) * 6 + 6,
alpar@9 206 if z[i,j] then "B" else "W" >> ps;
alpar@9 207 printf "%%%%EOF\n" >> ps;
alpar@9 208
alpar@9 209 printf "Solution has been written to file %s\n", ps;
alpar@9 210
alpar@9 211 /*--------------------------------------------------------------------*/
alpar@9 212 /* Write solution to a text file in the form of MathProg data section,
alpar@9 213 which can be used later to check for multiple solutions. */
alpar@9 214
alpar@9 215 param dat, symbolic, default "solution.dat";
alpar@9 216
alpar@9 217 printf "data;\n" > dat;
alpar@9 218 printf "\n" >> dat;
alpar@9 219 printf "param zz :" >> dat;
alpar@9 220 printf {j in 1..n} " %d", j >> dat;
alpar@9 221 printf " :=\n" >> dat;
alpar@9 222 for {i in 1..m}
alpar@9 223 { printf " %2d", i >> dat;
alpar@9 224 printf {j in 1..n} " %s", if z[i,j] then "1" else "." >> dat;
alpar@9 225 printf "\n" >> dat;
alpar@9 226 }
alpar@9 227 printf ";\n" >> dat;
alpar@9 228 printf "\n" >> dat;
alpar@9 229 printf "end;\n" >> dat;
alpar@9 230
alpar@9 231 printf "Solution has also been written to file %s\n", dat;
alpar@9 232
alpar@9 233 /*--------------------------------------------------------------------*/
alpar@9 234 /* The following data correspond to the example above. */
alpar@9 235
alpar@9 236 data;
alpar@9 237
alpar@9 238 param m := 10;
alpar@9 239
alpar@9 240 param n := 10;
alpar@9 241
alpar@9 242 param row : 1 2 3 :=
alpar@9 243 1 3 6 .
alpar@9 244 2 1 4 .
alpar@9 245 3 1 1 3
alpar@9 246 4 2 . .
alpar@9 247 5 3 3 .
alpar@9 248 6 1 4 .
alpar@9 249 7 2 5 .
alpar@9 250 8 2 5 .
alpar@9 251 9 1 1 .
alpar@9 252 10 3 . .
alpar@9 253 ;
alpar@9 254
alpar@9 255 param col : 1 2 3 4 :=
alpar@9 256 1 2 3 . .
alpar@9 257 2 1 2 . .
alpar@9 258 3 1 1 1 1
alpar@9 259 4 1 2 . .
alpar@9 260 5 1 1 1 1
alpar@9 261 6 1 2 . .
alpar@9 262 7 2 3 . .
alpar@9 263 8 3 4 . .
alpar@9 264 9 8 . . .
alpar@9 265 10 9 . . .
alpar@9 266 ;
alpar@9 267
alpar@9 268 end;