simplex-glpk with modified glpk for fpgaHEADmaster

18 files changed, 1708 insertions, 0 deletions

diff --git a/glpk-5.0/examples/pbn/9dom.dat b/glpk-5.0/examples/pbn/9dom.dat
new file mode 100644
index 0000000..80ece7a
--- /dev/null
+++ b/glpk-5.0/examples/pbn/9dom.dat
@@ -0,0 +1,65 @@
+/* 9dom.dat */
+
+/***********************************************************************
+*  Web Paint-by-Number Puzzle #8098 from <www.webpbn.com>.
+*  Copyright (C) 2010 by Josh Greifer. Used by permission.
+*
+*  Domino Logic III (Abstract pattern)
+*
+*  created by Josh Greifer
+*  Apr 5, 2010
+*
+*  Encoded in GNU MathProg by Andrew Makhorin <mao@gnu.org>.
+***********************************************************************/
+
+data;
+
+param m := 19;
+
+param n := 19;
+
+param row : 1  2  :=
+      1     3  .
+      2     1  .
+      3     3  1
+      4     1  .
+      5     3  1
+      6     1  .
+      7     3  1
+      8     1  .
+      9     3  1
+      10    1  .
+      11    3  1
+      12    1  .
+      13    3  1
+      14    1  .
+      15    3  1
+      16    1  .
+      17    3  1
+      18    1  .
+      19    1  .
+;
+
+param col : 1  2  :=
+      1     1  .
+      2     1  .
+      3     1  3
+      4     1  .
+      5     1  3
+      6     1  .
+      7     1  3
+      8     1  .
+      9     1  3
+      10    1  .
+      11    1  3
+      12    1  .
+      13    1  3
+      14    1  .
+      15    1  3
+      16    1  .
+      17    1  3
+      18    1  .
+      19    3  .
+;
+
+end;
diff --git a/glpk-5.0/examples/pbn/README b/glpk-5.0/examples/pbn/README
new file mode 100644
index 0000000..43dc82c
--- /dev/null
+++ b/glpk-5.0/examples/pbn/README
@@ -0,0 +1,6 @@
+This subdirectory contains examples, which illustrate how to use
+GLPK and the GNU MathProg modeling language for practical solving the
+paint-by-numbers puzzle.
+
+For details please see the document "Solving Paint-By-Numbers Puzzles
+with GLPK" included in this subdirectory (file pbn.pdf).
diff --git a/glpk-5.0/examples/pbn/bucks.dat b/glpk-5.0/examples/pbn/bucks.dat
new file mode 100644
index 0000000..5dfc4f1
--- /dev/null
+++ b/glpk-5.0/examples/pbn/bucks.dat
@@ -0,0 +1,77 @@
+/* bucks.dat */
+
+/***********************************************************************
+*  Web Paint-by-Number Puzzle #27 from <www.webpbn.com>.
+*  Copyright (C) 2004 by Jan Wolter. Used by permission.
+*
+*  Party at the Right [Political]
+*
+*  created by Jan Wolter
+*  Apr 6, 2004
+*
+*  Encoded in GNU MathProg by Andrew Makhorin <mao@gnu.org>.
+***********************************************************************/
+
+data;
+
+param m := 23;
+
+param n := 27;
+
+param row : 1  2  3  4  5  6  7  8  :=
+      1     11 .  .  .  .  .  .  .
+      2     17 .  .  .  .  .  .  .
+      3     3  5  5  3  .  .  .  .
+      4     2  2  2  1  .  .  .  .
+      5     2  1  3  1  3  1  4  .
+      6     3  3  3  3  .  .  .  .
+      7     5  1  3  1  3  1  3  .
+      8     3  2  2  4  .  .  .  .
+      9     5  5  5  5  .  .  .  .
+      10    23 .  .  .  .  .  .  .
+      11    .  .  .  .  .  .  .  .
+      12    23 .  .  .  .  .  .  .
+      13    1  1  .  .  .  .  .  .
+      14    1  1  .  .  .  .  .  .
+      15    1  2  1  .  .  .  .  .
+      16    1  1  1  1  .  .  .  .
+      17    1  1  1  1  .  .  .  .
+      18    1  10 1  2  1  .  .  .
+      19    1  1  1  1  1  1  3  .
+      20    1  1  1  1  1  1  1  1
+      21    1  1  1  1  1  1  1  .
+      22    1  1  1  1  2  2  .  .
+      23    5  5  3  .  .  .  .  .
+;
+
+param col : 1  2  3  4  5  6  :=
+      1     4  12 .  .  .  .
+      2     6  1  1  .  .  .
+      3     8  1  1  .  .  .
+      4     3  2  2  1  1  .
+      5     2  1  1  2  1  6
+      6     1  1  1  1  .  .
+      7     3  1  1  2  1  1
+      8     3  2  3  1  1  .
+      9     10 1  1  .  .  .
+      10    4  2  2  1  1  .
+      11    3  1  1  2  1  1
+      12    2  1  1  1  .  .
+      13    3  1  1  2  1  1
+      14    3  2  3  1  6  .
+      15    10 1  1  .  .  .
+      16    4  2  2  1  1  .
+      17    3  1  1  2  1  1
+      18    1  1  1  9  .  .
+      19    2  1  1  2  1  1
+      20    2  2  3  1  3  .
+      21    8  1  5  .  .  .
+      22    6  1  1  .  .  .
+      23    4  9  1  .  .  .
+      24    1  1  .  .  .  .
+      25    2  1  .  .  .  .
+      26    1  1  .  .  .  .
+      27    4  .  .  .  .  .
+;
+
+end;
diff --git a/glpk-5.0/examples/pbn/cat.dat b/glpk-5.0/examples/pbn/cat.dat
new file mode 100644
index 0000000..a655411
--- /dev/null
+++ b/glpk-5.0/examples/pbn/cat.dat
@@ -0,0 +1,67 @@
+/* cat.dat */
+
+/***********************************************************************
+*  Web Paint-by-Number Puzzle #6 from <www.webpbn.com>.
+*  Copyright (C) 2004 by Jan Wolter. Used by permission.
+*
+*  Scardy Cat
+*
+*  created by Jan Wolter
+*  Mar 24, 2004
+*
+*  Encoded in GNU MathProg by Andrew Makhorin <mao@gnu.org>.
+***********************************************************************/
+
+data;
+
+param m := 20;
+
+param n := 20;
+
+param row : 1  2  3  4  :=
+      1     2  .  .  .
+      2     2  .  .  .
+      3     1  .  .  .
+      4     1  .  .  .
+      5     1  3  .  .
+      6     2  5  .  .
+      7     1  7  1  1
+      8     1  8  2  2
+      9     1  9  5  .
+      10    2  16 .  .
+      11    1  17 .  .
+      12    7  11 .  .
+      13    5  5  3  .
+      14    5  4  .  .
+      15    3  3  .  .
+      16    2  2  .  .
+      17    2  1  .  .
+      18    1  1  .  .
+      19    2  2  .  .
+      20    2  2  .  .
+;
+
+param col : 1  2  3  :=
+      1     5  .  .
+      2     5  3  .
+      3     2  3  4
+      4     1  7  2
+      5     8  .  .
+      6     9  .  .
+      7     9  .  .
+      8     8  .  .
+      9     7  .  .
+      10    8  .  .
+      11    9  .  .
+      12    10 .  .
+      13    13 .  .
+      14    6  2  .
+      15    4  .  .
+      16    6  .  .
+      17    6  .  .
+      18    5  .  .
+      19    6  .  .
+      20    6  .  .
+;
+
+end;
diff --git a/glpk-5.0/examples/pbn/dancer.dat b/glpk-5.0/examples/pbn/dancer.dat
new file mode 100644
index 0000000..42e3057
--- /dev/null
+++ b/glpk-5.0/examples/pbn/dancer.dat
@@ -0,0 +1,42 @@
+/* dancer.dat */
+
+/***********************************************************************
+*  Web Paint-by-Number Puzzle #1 from <www.webpbn.com>.
+*  Copyright (C) 2004 by Jan Wolter. Used by permission.
+*
+*  Demo Puzzle from Front Page
+*
+*  created by Jan Wolter
+*  Mar 24, 2004
+*
+*  Encoded in GNU MathProg by Andrew Makhorin <mao@gnu.org>.
+***********************************************************************/
+
+data;
+
+param m := 10;
+
+param n := 5;
+
+param row : 1  2  3  :=
+      1     2  .  .
+      2     2  1  .
+      3     1  1  .
+      4     3  .  .
+      5     1  1  .
+      6     1  1  .
+      7     2  .  .
+      8     1  1  .
+      9     1  2  .
+      10    2  .  .
+;
+
+param col : 1  2  3  :=
+      1     2  1  .
+      2     2  1  3
+      3     7  .  .
+      4     1  3  .
+      5     2  1  .
+;
+
+end;
diff --git a/glpk-5.0/examples/pbn/disney.dat b/glpk-5.0/examples/pbn/disney.dat
new file mode 100644
index 0000000..2eab1fe
--- /dev/null
+++ b/glpk-5.0/examples/pbn/disney.dat
@@ -0,0 +1,115 @@
+/* disney.dat */
+
+data;
+
+param m := 50;
+
+param n := 50;
+
+param row : 1  2  3  4  5  6  7  :=
+      1     8  .  .  .  .  .  .
+      2     7  15 .  .  .  .  .
+      3     2  2  19 .  .  .  .
+      4     1  2  16 1  2  .  .
+      5     1  5  14 1  .  .  .
+      6     2  4  13 1  1  .  .
+      7     6  12 5  .  .  .  .
+      8     1  5  6  11 .  .  .
+      9     1  4  5  4  8  .  .
+      10    1  4  1  18 .  .  .
+      11    1  5  2  11 4  .  .
+      12    1  8  2  6  3  .  .
+      13    1  7  1  3  2  .  .
+      14    1  13 2  .  .  .  .
+      15    1  12 1  .  .  .  .
+      16    1  2  7  4  2  .  .
+      17    2  3  4  2  .  .  .
+      18    5  4  3  1  .  .  .
+      19    8  4  3  1  .  .  .
+      20    10 3  2  1  .  .  .
+      21    12 1  1  .  .  .  .
+      22    13 1  1  1  .  .  .
+      23    15 1  1  3  .  .  .
+      24    3  5  5  1  2  1  .
+      25    4  5  5  2  4  2  .
+      26    3  3  5  1  1  2  1
+      27    3  3  2  4  2  2  .
+      28    2  3  2  3  3  2  .
+      29    2  4  3  3  5  .  .
+      30    2  7  4  1  4  3  .
+      31    3  13 1  4  5  .  .
+      32    9  4  1  4  7  6  1
+      33    8  1  1  2  1  15 .
+      34    6  6  3  1  1  6  6
+      35    6  3  8  1  2  6  6
+      36    2  5  13 3  1  .  .
+      37    5  1  11 3  4  .  .
+      38    9  8  4  3  .  .  .
+      39    9  6  3  10 3  .  .
+      40    10 5  3  2  2  3  .
+      41    10 6  3  2  10 .  .
+      42    10 4  2  1  9  .  .
+      43    11 3  2  2  4  .  .
+      44    11 2  2  1  1  2  3
+      45    8  2  2  2  8  .  .
+      46    5  1  2  2  4  4  .
+      47    6  2  2  2  3  4  .
+      48    8  2  2  2  3  3  .
+      49    10 2  4  3  1  5  4
+      50    12 7  7  4  7  .  .
+;
+
+param col : 1  2  3  4  5  6  7  8  9  10 :=
+      1     14 .  .  .  .  .  .  .  .  .
+      2     9  15 .  .  .  .  .  .  .  .
+      3     28 .  .  .  .  .  .  .  .  .
+      4     7  5  14 .  .  .  .  .  .  .
+      5     6  4  14 .  .  .  .  .  .  .
+      6     5  5  8  4  .  .  .  .  .  .
+      7     7  6  8  3  .  .  .  .  .  .
+      8     19 8  3  .  .  .  .  .  .  .
+      9     16 9  2  .  .  .  .  .  .  .
+      10    15 2  5  2  .  .  .  .  .  .
+      11    8  3  1  3  1  .  .  .  .  .
+      12    4  7  2  2  3  1  .  .  .  .
+      13    2  12 6  3  1  2  .  .  .  .
+      14    1  1  12 1  2  .  .  .  .  .
+      15    1  4  9  2  1  2  .  .  .  .
+      16    1  6  5  6  1  .  .  .  .  .
+      17    1  7  5  3  5  1  1  .  .  .
+      18    1  8  8  6  2  1  .  .  .  .
+      19    2  1  7  5  9  1  .  .  .  .
+      20    2  2  7  6  9  1  .  .  .  .
+      21    6  15 9  2  .  .  .  .  .  .
+      22    7  5  4  14 1  .  .  .  .  .
+      23    8  4  4  3  6  1  1  .  .  .
+      24    9  5  2  7  3  2  3  .  .  .
+      25    9  7  4  10 1  2  1  .  .  .
+      26    8  2  4  2  5  2  2  2  1  .
+      27    7  2  6  2  3  5  2  1  .  .
+      28    7  4  4  2  5  2  2  1  .  .
+      29    7  3  4  1  1  2  1  .  .  .
+      30    7  3  4  1  2  2  2  .  .  .
+      31    8  6  1  1  2  1  .  .  .  .
+      32    6  1  3  1  2  1  2  .  .  .
+      33    4  1  3  2  2  1  2  2  .  .
+      34    4  1  3  1  3  1  2  2  2  .
+      35    3  5  1  1  1  2  1  1  1  2
+      36    2  6  1  1  3  1  1  3  .  .
+      37    2  5  1  5  6  1  3  .  .  .
+      38    2  6  2  6  3  2  .  .  .  .
+      39    1  4  2  6  2  2  1  .  .  .
+      40    2  5  3  4  1  2  2  .  .  .
+      41    3  7  3  1  10 .  .  .  .  .
+      42    5  2  1  9  .  .  .  .  .  .
+      43    3  2  2  2  6  .  .  .  .  .
+      44    2  1  1  2  3  2  .  .  .  .
+      45    4  2  2  2  1  .  .  .  .  .
+      46    4  1  2  3  1  .  .  .  .  .
+      47    4  1  1  2  3  2  .  .  .  .
+      48    6  4  6  .  .  .  .  .  .  .
+      49    3  3  5  .  .  .  .  .  .  .
+      50    3  2  3  .  .  .  .  .  .  .
+;
+
+end;
diff --git a/glpk-5.0/examples/pbn/dragon.dat b/glpk-5.0/examples/pbn/dragon.dat
new file mode 100644
index 0000000..d2b8b14
--- /dev/null
+++ b/glpk-5.0/examples/pbn/dragon.dat
@@ -0,0 +1,61 @@
+/* dragon.dat */
+
+/***********************************************************************
+*  Hard 20x20 paint-by-numbers puzzle designed by Won Yoon Jo
+*  from the article "Painting by Numbers" by Robert A. Bosch (2000),
+*  <http://www.oberlin.edu/~math/faculty/bosch/pbn-page.html>.
+*
+*  Encoded in GNU MathProg by Andrew Makhorin <mao@gnu.org>.
+***********************************************************************/
+
+data;
+
+param m := 20;
+
+param n := 20;
+
+param row :    1  2  3  4  5 :=
+          1    7  1  .  .  .
+          2    1  1  2  .  .
+          3    2  1  2  .  .
+          4    1  2  2  .  .
+          5    4  2  3  .  .
+          6    3  1  4  .  .
+          7    3  1  3  .  .
+          8    2  1  4  .  .
+          9    2  9  .  .  .
+          10   2  1  5  .  .
+          11   2  7  .  .  .
+          12   14 .  .  .  .
+          13   8  2  .  .  .
+          14   6  2  2  .  .
+          15   2  8  1  3  .
+          16   1  5  5  2  .
+          17   1  3  2  4  1
+          18   3  1  2  4  1
+          19   1  1  3  1  3
+          20   2  1  1  2  . ;
+
+param col :    1  2  3  4  5 :=
+          1    1  1  1  2  .
+          2    3  1  2  1  1
+          3    1  4  2  1  1
+          4    1  3  2  4  .
+          5    1  4  6  1  .
+          6    1  11 1  .  .
+          7    5  1  6  2  .
+          8    14 .  .  .  .
+          9    7  2  .  .  .
+          10   7  2  .  .  .
+          11   6  1  1  .  .
+          12   9  2  .  .  .
+          13   3  1  1  1  .
+          14   3  1  3  .  .
+          15   2  1  3  .  .
+          16   2  1  5  .  .
+          17   3  2  2  .  .
+          18   3  3  2  .  .
+          19   2  3  2  .  .
+          20   2  6  .  .  . ;
+
+end;
diff --git a/glpk-5.0/examples/pbn/edge.dat b/glpk-5.0/examples/pbn/edge.dat
new file mode 100644
index 0000000..cdd1864
--- /dev/null
+++ b/glpk-5.0/examples/pbn/edge.dat
@@ -0,0 +1,48 @@
+/* edge.dat */
+
+/***********************************************************************
+*  Web Paint-by-Number Puzzle #23 from <www.webpbn.com>.
+*  Copyright (C) 2004 by Jan Wolter. Used by permission.
+*
+*  Nonrepresentational Test Pattern
+*
+*  created by Jan Wolter
+*  Apr 5, 2004
+*
+*  Encoded in GNU MathProg by Andrew Makhorin <mao@gnu.org>.
+***********************************************************************/
+
+data;
+
+param m := 11;
+
+param n := 10;
+
+param row : 1  :=
+      1     1
+      2     3
+      3     1
+      4     2
+      5     1
+      6     3
+      7     3
+      8     1
+      9     2
+      10    2
+      11    4
+;
+
+param col : 1  2  :=
+      1     1  .
+      2     3  .
+      3     1  .
+      4     2  2
+      5     2  .
+      6     4  .
+      7     1  .
+      8     3  .
+      9     3  .
+      10    1  .
+;
+
+end;
diff --git a/glpk-5.0/examples/pbn/forever.dat b/glpk-5.0/examples/pbn/forever.dat
new file mode 100644
index 0000000..e3bebf7
--- /dev/null
+++ b/glpk-5.0/examples/pbn/forever.dat
@@ -0,0 +1,77 @@
+/* forever.dat */
+
+/***********************************************************************
+*  Web Paint-by-Number Puzzle #6574 from <www.webpbn.com>.
+*  Copyright (C) 2009 by Gator. Used by permission.
+*
+*  Lasts Forever
+*
+*  created by Gator
+*  Aug 24, 2009
+*
+*  Encoded in GNU MathProg by Andrew Makhorin <mao@gnu.org>.
+***********************************************************************/
+
+data;
+
+param m := 25;
+
+param n := 25;
+
+param row : 1  2  3  4  5  6  7  8  :=
+      1     1  2  2  2  2  2  1  .
+      2     1  2  2  2  2  2  1  1
+      3     1  1  .  .  .  .  .  .
+      4     1  1  .  .  .  .  .  .
+      5     1  3  1  .  .  .  .  .
+      6     1  13 1  .  .  .  .  .
+      7     1  13 1  .  .  .  .  .
+      8     1  13 1  .  .  .  .  .
+      9     1  4  4  1  .  .  .  .
+      10    1  4  3  4  1  .  .  .
+      11    1  4  5  4  1  .  .  .
+      12    1  7  1  .  .  .  .  .
+      13    1  7  1  .  .  .  .  .
+      14    1  7  1  .  .  .  .  .
+      15    1  7  1  .  .  .  .  .
+      16    1  1  5  1  .  .  .  .
+      17    1  2  6  1  .  .  .  .
+      18    1  4  6  1  .  .  .  .
+      19    1  6  6  1  .  .  .  .
+      20    1  3  1  .  .  .  .  .
+      21    1  1  1  .  .  .  .  .
+      22    1  1  .  .  .  .  .  .
+      23    1  1  .  .  .  .  .  .
+      24    1  1  2  2  2  2  2  1
+      25    1  2  2  2  2  2  1  .
+;
+
+param col : 1  2  3  4  5  6  7  8  :=
+      1     1  2  2  2  2  2  1  .
+      2     1  1  2  2  2  2  2  1
+      3     1  1  .  .  .  .  .  .
+      4     1  1  .  .  .  .  .  .
+      5     1  1  .  .  .  .  .  .
+      6     1  2  1  .  .  .  .  .
+      7     1  6  1  1  .  .  .  .
+      8     1  6  2  1  .  .  .  .
+      9     1  6  3  1  .  .  .  .
+      10    1  4  8  1  .  .  .  .
+      11    1  3  5  2  1  .  .  .
+      12    1  4  8  2  1  .  .  .
+      13    1  4  9  2  1  .  .  .
+      14    1  4  11 1  .  .  .  .
+      15    1  3  9  1  .  .  .  .
+      16    1  4  8  1  .  .  .  .
+      17    1  6  3  1  .  .  .  .
+      18    1  6  2  1  .  .  .  .
+      19    1  6  1  1  .  .  .  .
+      20    1  2  1  .  .  .  .  .
+      21    1  1  .  .  .  .  .  .
+      22    1  1  .  .  .  .  .  .
+      23    1  1  .  .  .  .  .  .
+      24    1  2  2  2  2  2  1  1
+      25    1  2  2  2  2  2  1  .
+;
+
+end;
diff --git a/glpk-5.0/examples/pbn/knot.dat b/glpk-5.0/examples/pbn/knot.dat
new file mode 100644
index 0000000..b9e12d7
--- /dev/null
+++ b/glpk-5.0/examples/pbn/knot.dat
@@ -0,0 +1,95 @@
+/* knot.dat */
+
+/***********************************************************************
+*  Web Paint-by-Number Puzzle #16 from <www.webpbn.com>.
+*  Copyright (C) 2004 by Jan Wolter. Used by permission.
+*
+*  Probably Not
+*
+*  created by Jan Wolter
+*  Mar 27, 2004
+*
+*  Encoded in GNU MathProg by Andrew Makhorin <mao@gnu.org>.
+***********************************************************************/
+
+data;
+
+param m := 34;
+
+param n := 34;
+
+param row : 1  2  3  4  5  6  7  8 :=
+      1     1  1  .  .  .  .  .  .
+      2     2  2  .  .  .  .  .  .
+      3     3  3  .  .  .  .  .  .
+      4     2  1  1  2  .  .  .  .
+      5     2  1  1  2  .  .  .  .
+      6     1  1  1  1  .  .  .  .
+      7     1  1  1  1  .  .  .  .
+      8     18 .  .  .  .  .  .  .
+      9     2  1  1  1  1  2  .  .
+      10    1  1  1  1  1  1  .  .
+      11    1  1  1  1  1  1  .  .
+      12    26 .  .  .  .  .  .  .
+      13    2  1  1  1  1  1  1  2
+      14    2  1  1  2  2  1  1  2
+      15    2  1  1  2  2  1  1  2
+      16    14 14 .  .  .  .  .  .
+      17    1  1  1  1  .  .  .  .
+      18    1  1  1  1  .  .  .  .
+      19    14 14 .  .  .  .  .  .
+      20    2  1  1  2  2  1  1  2
+      21    2  1  1  2  2  1  1  2
+      22    2  1  1  1  1  1  1  2
+      23    26 .  .  .  .  .  .  .
+      24    1  1  1  1  1  1  .  .
+      25    1  1  1  1  1  1  .  .
+      26    2  1  1  1  1  2  .  .
+      27    18 .  .  .  .  .  .  .
+      28    1  1  1  1  .  .  .  .
+      29    1  1  1  1  .  .  .  .
+      30    2  1  1  2  .  .  .  .
+      31    2  1  1  2  .  .  .  .
+      32    3  3  .  .  .  .  .  .
+      33    2  2  .  .  .  .  .  .
+      34    1  1  .  .  .  .  .  .
+;
+
+param col : 1  2  3  4  5  6  7  8 :=
+      1     1  1  .  .  .  .  .  .
+      2     2  2  .  .  .  .  .  .
+      3     3  3  .  .  .  .  .  .
+      4     2  1  1  2  .  .  .  .
+      5     2  1  1  2  .  .  .  .
+      6     1  1  1  1  .  .  .  .
+      7     1  1  1  1  .  .  .  .
+      8     18 .  .  .  .  .  .  .
+      9     2  1  1  1  1  2  .  .
+      10    1  1  1  1  1  1  .  .
+      11    1  1  1  1  1  1  .  .
+      12    26 .  .  .  .  .  .  .
+      13    2  1  1  1  1  1  1  2
+      14    2  1  1  2  2  1  1  2
+      15    2  1  1  2  2  1  1  2
+      16    14 14 .  .  .  .  .  .
+      17    1  1  1  1  .  .  .  .
+      18    1  1  1  1  .  .  .  .
+      19    14 14 .  .  .  .  .  .
+      20    2  1  1  2  2  1  1  2
+      21    2  1  1  2  2  1  1  2
+      22    2  1  1  1  1  1  1  2
+      23    26 .  .  .  .  .  .  .
+      24    1  1  1  1  1  1  .  .
+      25    1  1  1  1  1  1  .  .
+      26    2  1  1  1  1  2  .  .
+      27    18 .  .  .  .  .  .  .
+      28    1  1  1  1  .  .  .  .
+      29    1  1  1  1  .  .  .  .
+      30    2  1  1  2  .  .  .  .
+      31    2  1  1  2  .  .  .  .
+      32    3  3  .  .  .  .  .  .
+      33    2  2  .  .  .  .  .  .
+      34    1  1  .  .  .  .  .  .
+;
+
+end;
diff --git a/glpk-5.0/examples/pbn/light.dat b/glpk-5.0/examples/pbn/light.dat
new file mode 100644
index 0000000..1ffc5d4
--- /dev/null
+++ b/glpk-5.0/examples/pbn/light.dat
@@ -0,0 +1,122 @@
+/* light.dat */
+
+/***********************************************************************
+*  Web Paint-by-Number Puzzle #803 from <www.webpbn.com>.
+*  Copyright (C) 2007 by Robert Kummerfeldt. Used by permission.
+*
+*  You light up my life
+*
+*  created by Robert Kummerfeldt
+*  Mar 15, 2007
+*
+*  Encoded in GNU MathProg by Andrew Makhorin <mao@gnu.org>.
+***********************************************************************/
+
+data;
+
+param m := 45;
+
+param n := 50;
+
+param row : 1  2  3  4  :=
+      1     .  .  .  .
+      2     1  .  .  .
+      3     1  .  .  .
+      4     3  .  .  .
+      5     2  2  .  .
+      6     1  1  .  .
+      7     7  .  .  .
+      8     1  1  .  .
+      9     1  3  1  .
+      10    1  3  1  .
+      11    1  1  .  .
+      12    11 .  .  .
+      13    1  1  .  .
+      14    1  1  .  .
+      15    2  2  .  .
+      16    1  1  .  .
+      17    1  1  .  .
+      18    1  1  .  .
+      19    1  1  .  .
+      20    2  2  .  .
+      21    1  1  .  .
+      22    1  1  .  .
+      23    1  1  .  .
+      24    1  1  .  .
+      25    1  1  .  .
+      26    1  1  .  .
+      27    1  1  .  .
+      28    1  1  .  .
+      29    1  1  .  .
+      30    1  1  .  .
+      31    2  2  .  .
+      32    1  1  .  .
+      33    1  1  .  .
+      34    1  1  .  .
+      35    1  1  .  .
+      36    1  1  .  .
+      37    1  4  1  .
+      38    1  1  1  1
+      39    1  1  1  1
+      40    1  1  1  1
+      41    1  1  1  1
+      42    25 .  .  .
+      43    6  5  .  .
+      44    5  6  .  .
+      45    4  5  .  .
+;
+
+param col : 1  2  3  4  5  :=
+      1     1  .  .  .  .
+      2     1  .  .  .  .
+      3     1  .  .  .  .
+      4     2  .  .  .  .
+      5     1  .  .  .  .
+      6     1  .  .  .  .
+      7     1  .  .  .  .
+      8     2  .  .  .  .
+      9     1  .  .  .  .
+      10    1  .  .  .  .
+      11    1  .  .  .  .
+      12    1  .  .  .  .
+      13    2  .  .  .  .
+      14    1  .  .  .  .
+      15    1  .  .  .  .
+      16    1  .  .  .  .
+      17    5  .  .  .  .
+      18    7  1  .  .  .
+      19    6  1  .  .  .
+      20    6  1  .  .  .
+      21    1  6  1  .  .
+      22    4  1  .  .  .
+      23    7  1  .  .  .
+      24    1  1  1  1  .
+      25    2  1  2  1  1
+      26    3  1  2  1  1
+      27    2  1  2  1  1
+      28    1  1  1  1  .
+      29    7  6  .  .  .
+      30    4  1  1  .  .
+      31    1  6  1  1  .
+      32    6  6  .  .  .
+      33    6  1  .  .  .
+      34    5  1  .  .  .
+      35    7  .  .  .  .
+      36    1  .  .  .  .
+      37    2  .  .  .  .
+      38    1  .  .  .  .
+      39    1  .  .  .  .
+      40    1  .  .  .  .
+      41    2  .  .  .  .
+      42    1  .  .  .  .
+      43    1  .  .  .  .
+      44    1  .  .  .  .
+      45    1  .  .  .  .
+      46    2  .  .  .  .
+      47    1  .  .  .  .
+      48    1  .  .  .  .
+      49    1  .  .  .  .
+      50    1  .  .  .  .
+;
+
+end;
diff --git a/glpk-5.0/examples/pbn/mum.dat b/glpk-5.0/examples/pbn/mum.dat
new file mode 100644
index 0000000..a1baf50
--- /dev/null
+++ b/glpk-5.0/examples/pbn/mum.dat
@@ -0,0 +1,101 @@
+/* mum.dat */
+
+/***********************************************************************
+*  Web Paint-by-Number Puzzle #65 from <www.webpbn.com>.
+*  Copyright (C) 2004 by Jan Wolter. Used by permission.
+*
+*  Mum's the Word [has only one solution]
+*
+*  created by Jan Wolter
+*  Jul 10, 2004
+*
+*  Encoded in GNU MathProg by Andrew Makhorin <mao@gnu.org>.
+***********************************************************************/
+
+data;
+
+param m := 40;
+
+param n := 34;
+
+param row : 1  2  3  4  5  6  7  8  9  :=
+      1     12 .  .  .  .  .  .  .  .
+      2     5  2  5  .  .  .  .  .  .
+      3     5  2  2  5  .  .  .  .  .
+      4     1  2  2  2  2  2  1  .  .
+      5     4  2  2  4  2  2  4  .  .
+      6     4  2  2  4  2  2  4  .  .
+      7     1  2  2  2  2  2  1  .  .
+      8     6  2  2  2  2  2  6  .  .
+      9     6  2  2  2  2  2  6  .  .
+      10    1  14 1  .  .  .  .  .  .
+      11    10 10 .  .  .  .  .  .  .
+      12    8  3  3  8  .  .  .  .  .
+      13    1  1  2  1  1  2  1  1  .
+      14    9  2  2  2  2  9  .  .  .
+      15    9  9  .  .  .  .  .  .  .
+      16    1  1  1  1  1  1  .  .  .
+      17    12 2  12 .  .  .  .  .  .
+      18    12 12 .  .  .  .  .  .  .
+      19    1  1  4  1  1  .  .  .  .
+      20    14 14 .  .  .  .  .  .  .
+      21    12 12 .  .  .  .  .  .  .
+      22    2  1  4  1  2  .  .  .  .
+      23    9  4  9  .  .  .  .  .  .
+      24    1  7  4  7  1  .  .  .  .
+      25    1  1  1  4  1  1  1  .  .
+      26    1  7  4  7  1  .  .  .  .
+      27    1  7  4  7  1  .  .  .  .
+      28    1  2  1  2  1  2  1  .  .
+      29    1  7  2  7  1  .  .  .  .
+      30    1  1  6  2  6  1  1  .  .
+      31    1  1  1  1  2  1  1  1  1
+      32    1  1  6  2  6  1  1  .  .
+      33    1  1  5  5  1  1  .  .  .
+      34    1  1  1  8  1  1  1  .  .
+      35    1  1  4  4  1  1  .  .  .
+      36    1  2  6  2  1  .  .  .  .
+      37    2  4  4  2  .  .  .  .  .
+      38    2  6  2  .  .  .  .  .  .
+      39    4  4  .  .  .  .  .  .  .
+      40    6  .  .  .  .  .  .  .  .
+;
+
+param col : 1  2  3  4  5  6  7  8  9  10 11 12 :=
+      1     5  .  .  .  .  .  .  .  .  .  .  .
+      2     3  2  1  .  .  .  .  .  .  .  .  .
+      3     3  2  2  1  .  .  .  .  .  .  .  .
+      4     3  2  2  2  2  .  .  .  .  .  .  .
+      5     3  2  2  2  2  3  .  .  .  .  .  .
+      6     1  2  2  2  2  2  16 .  .  .  .  .
+      7     1  2  2  2  2  2  2  1  2  .  .  .
+      8     1  2  2  2  2  2  2  13 1  .  .  .
+      9     3  2  2  2  2  2  2  4  1  1  .  .
+      10    6  5  2  2  2  2  6  1  1  .  .  .
+      11    1  7  3  2  2  2  2  2  1  1  1  .
+      12    3  4  1  2  2  2  2  2  2  1  1  1
+      13    6  1  2  3  2  2  2  2  1  1  1  .
+      14    1  7  2  16 1  1  .  .  .  .  .  .
+      15    1  4  1  1  1  1  1  1  1  1  1  .
+      16    1  2  1  3  1  1  6  1  1  1  1  .
+      17    2  7  1  1  11 1  1  1  1  .  .  .
+      18    2  7  1  1  11 1  1  1  1  .  .  .
+      19    1  2  1  3  1  1  6  1  1  1  1  .
+      20    1  4  1  1  1  1  1  1  1  1  1  .
+      21    1  7  2  16 1  1  .  .  .  .  .  .
+      22    6  1  2  3  2  2  2  2  1  1  1  .
+      23    3  4  1  2  2  2  2  2  2  1  1  1
+      24    1  7  3  2  2  2  2  2  1  1  1  .
+      25    6  5  2  2  2  2  6  1  1  .  .  .
+      26    3  2  2  2  2  2  2  4  1  1  .  .
+      27    1  2  2  2  2  2  2  13 1  .  .  .
+      28    1  2  2  2  2  2  2  1  2  .  .  .
+      29    1  2  2  2  2  2  16 .  .  .  .  .
+      30    3  2  2  2  2  3  .  .  .  .  .  .
+      31    3  2  2  2  2  .  .  .  .  .  .  .
+      32    3  2  2  1  .  .  .  .  .  .  .  .
+      33    3  2  1  .  .  .  .  .  .  .  .  .
+      34    5  .  .  .  .  .  .  .  .  .  .  .
+;
+
+end;
diff --git a/glpk-5.0/examples/pbn/pbn.mod b/glpk-5.0/examples/pbn/pbn.mod
new file mode 100644
index 0000000..c4a1b2c
--- /dev/null
+++ b/glpk-5.0/examples/pbn/pbn.mod
@@ -0,0 +1,268 @@
+/* PBN, Paint-By-Numbers Puzzle */
+
+/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
+
+/* NOTE: See also the document "Solving Paint-By-Numbers Puzzles with
+         GLPK", which is included in the GLPK distribution. */
+
+/* A paint-by-numbers puzzle consists of an m*n grid of pixels (the
+   canvas) together with m+n cluster-size sequences, one for each row
+   and column. The goal is to paint the canvas with a picture that
+   satisfies the following constraints:
+
+   1. Each pixel must be blank or white.
+
+   2. If a row or column has cluster-size sequence s1, s2, ..., sk,
+      then it must contain k clusters of black pixels - the first with
+      s1 black pixels, the second with s2 black pixels, and so on.
+
+   It should be noted that "first" means "leftmost" for rows and
+   "topmost" for columns, and that rows and columns need not begin or
+   end with black pixels.
+
+   Example:
+                  1   1
+                  1   1
+              2 1 1 1 1 1 2 3
+              3 2 1 2 1 2 3 4 8 9
+
+        3 6   # # # . # # # # # #
+        1 4   # . . . . . # # # #
+      1 1 3   . . # . # . . # # #
+          2   . . . . . . . . # #
+        3 3   . . # # # . . # # #
+        1 4   # . . . . . # # # #
+        2 5   # # . . . # # # # #
+        2 5   # # . . . # # # # #
+        1 1   . . . # . . . . . #
+          3   . . # # # . . . . .
+
+   (In Russia such puzzles are known as "Japanese crosswords".)
+
+   References:
+   Robert A. Bosch, "Painting by Numbers", 2000.
+   <http://www.oberlin.edu/~math/faculty/bosch/pbn-page.html> */
+
+/*--------------------------------------------------------------------*/
+/* Main part based on the formulation proposed by Robert Bosch. */
+
+param m, integer, >= 1;
+/* the number of rows */
+
+param n, integer, >= 1;
+/* the number of columns */
+
+param row{i in 1..m, 1..(n+1) div 2}, integer, >= 0, default 0;
+/* the cluster-size sequence for row i (raw data) */
+
+param col{j in 1..n, 1..(m+1) div 2}, integer, >= 0, default 0;
+/* the cluster-size sequence for column j (raw data) */
+
+param kr{i in 1..m} := sum{t in 1..(n+1) div 2: row[i,t] > 0} 1;
+/* the number of clusters in row i */
+
+param kc{j in 1..n} := sum{t in 1..(m+1) div 2: col[j,t] > 0} 1;
+/* the number of clusters in column j */
+
+param sr{i in 1..m, t in 1..kr[i]} := row[i,t], integer, >= 1;
+/* the cluster-size sequence for row i */
+
+param sc{j in 1..n, t in 1..kc[j]} := col[j,t], integer, >= 1;
+/* the cluster-size sequence for column j */
+
+check{i in 1..m}: sum{t in 1..kr[i]} sr[i,t] <= n - (kr[i] - 1);
+/* check that the sum of the cluster sizes in each row is valid */
+
+check{j in 1..n}: sum{t in 1..kc[j]} sc[j,t] <= m - (kc[j] - 1);
+/* check that the sum of the cluster sizes in each column is valid */
+
+check: sum{i in 1..m, t in 1..kr[i]} sr[i,t] =
+       sum{j in 1..n, t in 1..kc[j]} sc[j,t];
+/* check that the sum of the cluster sizes in all rows is equal to the
+   sum of the cluster sizes in all columns */
+
+param er{i in 1..m, t in 1..kr[i]} :=
+   if t = 1 then 1 else er[i,t-1] + sr[i,t-1] + 1;
+/* the smallest value of j such that row i's t-th cluster can be
+   placed in row i with its leftmost pixel occupying pixel j */
+
+param lr{i in 1..m, t in 1..kr[i]} :=
+   if t = kr[i] then n + 1 - sr[i,t] else lr[i,t+1] - sr[i,t] - 1;
+/* the largest value of j such that row i's t-th cluster can be
+   placed in row i with its leftmost pixel occupying pixel j */
+
+param ec{j in 1..n, t in 1..kc[j]} :=
+   if t = 1 then 1 else ec[j,t-1] + sc[j,t-1] + 1;
+/* the smallest value of i such that column j's t-th cluster can be
+   placed in column j with its topmost pixel occupying pixel i */
+
+param lc{j in 1..n, t in 1..kc[j]} :=
+   if t = kc[j] then m + 1 - sc[j,t] else lc[j,t+1] - sc[j,t] - 1;
+/* the largest value of i such that column j's t-th cluster can be
+   placed in column j with its topmost pixel occupying pixel i */
+
+var z{i in 1..m, j in 1..n}, binary;
+/* z[i,j] = 1, if row i's j-th pixel is painted black
+   z[i,j] = 0, if row i's j-th pixel is painted white */
+
+var y{i in 1..m, t in 1..kr[i], j in er[i,t]..lr[i,t]}, binary;
+/* y[i,t,j] = 1, if row i's t-th cluster is placed in row i with its
+                 leftmost pixel occupying pixel j
+   y[i,t,j] = 0, if not */
+
+var x{j in 1..n, t in 1..kc[j], i in ec[j,t]..lc[j,t]}, binary;
+/* x[j,t,i] = 1, if column j's t-th cluster is placed in column j with
+                 its topmost pixel occupying pixel i
+   x[j,t,i] = 0, if not */
+
+s.t. fa{i in 1..m, t in 1..kr[i]}:
+     sum{j in er[i,t]..lr[i,t]} y[i,t,j] = 1;
+/* row i's t-th cluster must appear in row i exactly once */
+
+s.t. fb{i in 1..m, t in 1..kr[i]-1, j in er[i,t]..lr[i,t]}:
+     y[i,t,j] <= sum{jp in j+sr[i,t]+1..lr[i,t+1]} y[i,t+1,jp];
+/* row i's (t+1)-th cluster must be placed to the right of its t-th
+   cluster */
+
+s.t. fc{j in 1..n, t in 1..kc[j]}:
+     sum{i in ec[j,t]..lc[j,t]} x[j,t,i] = 1;
+/* column j's t-th cluster must appear in column j exactly once */
+
+s.t. fd{j in 1..n, t in 1..kc[j]-1, i in ec[j,t]..lc[j,t]}:
+     x[j,t,i] <= sum{ip in i+sc[j,t]+1..lc[j,t+1]} x[j,t+1,ip];
+/* column j's (t+1)-th cluster must be placed below its t-th cluster */
+
+s.t. fe{i in 1..m, j in 1..n}:
+     z[i,j] <= sum{t in 1..kr[i], jp in er[i,t]..lr[i,t]:
+                   j-sr[i,t]+1 <= jp and jp <= j} y[i,t,jp];
+/* the double coverage constraint stating that if row i's j-th pixel
+   is painted black, then at least one of row i's clusters must be
+   placed in such a way that it covers row i's j-th pixel */
+
+s.t. ff{i in 1..m, j in 1..n}:
+     z[i,j] <= sum{t in 1..kc[j], ip in ec[j,t]..lc[j,t]:
+                   i-sc[j,t]+1 <= ip and ip <= i} x[j,t,ip];
+/* the double coverage constraint making sure that if row i's j-th
+   pixel is painted black, then at least one of column j's clusters
+   covers it */
+
+s.t. fg{i in 1..m, j in 1..n, t in 1..kr[i], jp in er[i,t]..lr[i,t]:
+     j-sr[i,t]+1 <= jp and jp <= j}: z[i,j] >= y[i,t,jp];
+/* the constraint to prevent white pixels from being covered by the
+   row clusters */
+
+s.t. fh{i in 1..m, j in 1..n, t in 1..kc[j], ip in ec[j,t]..lc[j,t]:
+     i-sc[j,t]+1 <= ip and ip <= i}: z[i,j] >= x[j,t,ip];
+/* the constraint to prevent white pixels from being covered by the
+   column clusters */
+
+/* this is a feasibility problem, so no objective is needed */
+
+/*--------------------------------------------------------------------*/
+/* The following part is used only to check for multiple solutions. */
+
+param zz{i in 1..m, j in 1..n}, binary, default 0;
+/* zz[i,j] is z[i,j] for a previously found solution */
+
+s.t. fz{1..1 : sum{i in 1..m, j in 1..n} zz[i,j] > 0}:
+     sum{i in 1..m, j in 1..n}
+         (if zz[i,j] then (1 - z[i,j]) else z[i,j]) >= 1;
+/* the constraint to forbid finding a solution, which is identical to
+   the previously found one; this constraint is included in the model
+   only if the previously found solution specified by the parameter zz
+   is provided in the data section */
+
+solve;
+
+/*--------------------------------------------------------------------*/
+/* Print solution to the standard output. */
+
+for {i in 1..m}
+{  printf{j in 1..n} " %s", if z[i,j] then "#" else ".";
+   printf "\n";
+}
+
+/*--------------------------------------------------------------------*/
+/* Write solution to a text file in PostScript format. */
+
+param ps, symbolic, default "solution.ps";
+
+printf "%%!PS-Adobe-3.0\n" > ps;
+printf "%%%%Creator: GLPK (pbn.mod)\n" >> ps;
+printf "%%%%BoundingBox: 0 0 %d %d\n",
+       6 * (n + 2), 6 * (m + 2) >> ps;
+printf "%%%%EndComments\n" >> ps;
+printf "<</PageSize [%d %d]>> setpagedevice\n",
+       6 * (n + 2), 6 * (m + 2) >> ps;
+printf "0.1 setlinewidth\n" >> ps;
+printf "/A { 2 copy 2 copy 2 copy newpath moveto exch 6 add exch line" &
+       "to\n" >> ps;
+printf "exch 6 add exch 6 add lineto 6 add lineto closepath } bind de" &
+       "f\n" >> ps;
+printf "/W { A stroke } def\n" >> ps;
+printf "/B { A fill } def\n" >> ps;
+printf {i in 1..m, j in 1..n} "%d %d %s\n",
+       (j - 1) * 6 + 6, (m - i) * 6 + 6,
+       if z[i,j] then "B" else "W" >> ps;
+printf "%%%%EOF\n" >> ps;
+
+printf "Solution has been written to file %s\n", ps;
+
+/*--------------------------------------------------------------------*/
+/* Write solution to a text file in the form of MathProg data section,
+   which can be used later to check for multiple solutions. */
+
+param dat, symbolic, default "solution.dat";
+
+printf "data;\n" > dat;
+printf "\n" >> dat;
+printf "param zz :" >> dat;
+printf {j in 1..n} " %d", j >> dat;
+printf " :=\n" >> dat;
+for {i in 1..m}
+{  printf " %2d", i >> dat;
+   printf {j in 1..n} " %s", if z[i,j] then "1" else "." >> dat;
+   printf "\n" >> dat;
+}
+printf ";\n" >> dat;
+printf "\n" >> dat;
+printf "end;\n" >> dat;
+
+printf "Solution has also been written to file %s\n", dat;
+
+/*--------------------------------------------------------------------*/
+/* The following data correspond to the example above. */
+
+data;
+
+param m := 10;
+
+param n := 10;
+
+param row : 1  2  3  :=
+      1     3  6  .
+      2     1  4  .
+      3     1  1  3
+      4     2  .  .
+      5     3  3  .
+      6     1  4  .
+      7     2  5  .
+      8     2  5  .
+      9     1  1  .
+      10    3  .  .
+;
+
+param col : 1  2  3  4  :=
+      1     2  3  .  .
+      2     1  2  .  .
+      3     1  1  1  1
+      4     1  2  .  .
+      5     1  1  1  1
+      6     1  2  .  .
+      7     2  3  .  .
+      8     3  4  .  .
+      9     8  .  .  .
+      10    9  .  .  .
+;
+
+end;
diff --git a/glpk-5.0/examples/pbn/pbn.pdf b/glpk-5.0/examples/pbn/pbn.pdf
new file mode 100644
index 0000000..8342189
--- /dev/null
+++ b/glpk-5.0/examples/pbn/pbn.pdf
diff --git a/glpk-5.0/examples/pbn/pbn.tex b/glpk-5.0/examples/pbn/pbn.tex
new file mode 100644
index 0000000..c73a441
--- /dev/null
+++ b/glpk-5.0/examples/pbn/pbn.tex
@@ -0,0 +1,279 @@
+%* pbn.tex *%
+
+\documentclass[11pt,draft]{article}
+\usepackage{amssymb}
+
+\begin{document}
+
+\title{Solving Paint-By-Numbers Puzzles with GLPK}
+
+\author{Andrew Makhorin {\tt<mao@gnu.org>}}
+
+\date{August 2011}
+
+\maketitle
+
+\section{Introduction$^1$}
+
+\footnotetext[1]{This section is based on the material from [1].}
+
+A {\it paint-by-numbers} puzzle consists of an $m\times n$ grid of
+pixels (the {\it canvas}) together with $m+n$ {\it cluster-size
+sequences}, one for each row and column. The goal is to paint the canvas
+with a picture that satisfies the following constraints:
+
+1. Each pixel must be blank or white.
+
+2. If a row or column has cluster-size sequence $s_1$, $s_2$, \dots,
+$s_k$, then it must contain $k$ clusters of black pixels---the first
+with $s_1$ black pixels, the second with $s_2$ black pixels, and so on.
+
+It should be noted that ``first'' means ``leftmost'' for rows and
+``topmost'' for columns, and that rows and columns need not begin or end
+with black pixels.
+
+\subsubsection*{Example}
+
+\def\arraystretch{.8}
+
+\begin{center}
+\begin{tabular}{*{3}{@{$\;\;$}c}c*{10}{@{\ }c}@{}}
+ & & && & &1& &1& & & & & \\
+ & & && & &1& &1& & & & & \\
+ & & &&2&1&1&1&1&1&2&3& & \\
+ & & &&3&2&1&2&1&2&3&4&8&9\\
+\\
+ &3&6&&$\blacksquare$&$\blacksquare$&$\blacksquare$&$\square$&
+$\blacksquare$&$\blacksquare$&$\blacksquare$&$\blacksquare$&
+$\blacksquare$&$\blacksquare$\\
+ &1&4&&$\blacksquare$&$\square$&$\square$&$\square$&$\square$&
+$\square$&$\blacksquare$&$\blacksquare$&$\blacksquare$&$\blacksquare$\\
+1&1&3&&$\square$&$\square$&$\blacksquare$&$\square$&$\blacksquare$&
+$\square$&$\square$&$\blacksquare$&$\blacksquare$&$\blacksquare$\\
+ & &2&&$\square$&$\square$&$\square$&$\square$&$\square$&$\square$&
+$\square$&$\square$&$\blacksquare$&$\blacksquare$\\
+ &3&3&&$\square$&$\square$&$\blacksquare$&$\blacksquare$&$\blacksquare$&
+$\square$&$\square$&$\blacksquare$&$\blacksquare$&$\blacksquare$\\
+ &1&4&&$\blacksquare$&$\square$&$\square$&$\square$&$\square$&$\square$&
+$\blacksquare$&$\blacksquare$&$\blacksquare$&$\blacksquare$\\
+ &2&5&&$\blacksquare$&$\blacksquare$&$\square$&$\square$&$\square$&
+$\blacksquare$&$\blacksquare$&$\blacksquare$&$\blacksquare$&
+$\blacksquare$\\
+ &2&5&&$\blacksquare$&$\blacksquare$&$\square$&$\square$&$\square$&
+$\blacksquare$&$\blacksquare$&$\blacksquare$&$\blacksquare$&
+$\blacksquare$\\
+ &1&1&&$\square$&$\square$&$\square$&$\blacksquare$&$\square$&$\square$&
+$\square$&$\square$&$\square$&$\blacksquare$\\
+ & &3&&$\square$&$\square$&$\blacksquare$&$\blacksquare$&$\blacksquare$&
+$\square$&$\square$&$\square$&$\square$&$\square$\\
+\end{tabular}
+\end{center}
+
+\def\arraystretch{1}
+
+\section{Solving a puzzle}
+
+The Paint-By-Numbers puzzle can be formulated as a 0-1 integer
+feasibility problem. The formulation used in GLPK was proposed in [1].
+
+For solving puzzles there are used two components, which both are
+coded in the GNU MathProg modeling language [2]: the model section and
+the data section. The model section is common for all puzzles and
+placed in file \verb|pbn.mod|. This file is included in the GLPK
+distribution and can be found in subdirectory \verb|examples/pbn|.
+
+To solve a particular puzzle the user only needs to prepare the data
+section, which defines input data to the puzzle. The data section for
+the example puzzle from the previous section may look like follows
+(here \verb|m| is the number of rows, and \verb|n| is the number of
+columns):
+
+\begin{footnotesize}
+\begin{verbatim}
+data;
+
+param m := 10;
+
+param n := 10;
+
+param row : 1  2  3  :=
+      1     3  6  .
+      2     1  4  .
+      3     1  1  3
+      4     2  .  .
+      5     3  3  .
+      6     1  4  .
+      7     2  5  .
+      8     2  5  .
+      9     1  1  .
+      10    3  .  .
+;
+
+param col : 1  2  3  4  :=
+      1     2  3  .  .
+      2     1  2  .  .
+      3     1  1  1  1
+      4     1  2  .  .
+      5     1  1  1  1
+      6     1  2  .  .
+      7     2  3  .  .
+      8     3  4  .  .
+      9     8  .  .  .
+      10    9  .  .  .
+;
+
+end;
+\end{verbatim}
+\end{footnotesize}
+
+\newpage
+
+Let the data section for a puzzle be placed in file \verb|foo.dat|.
+Then to solve the puzzle the user should enter the following command:
+
+\begin{verbatim}
+   glpsol --minisat -m pbn.mod -d foo.dat
+\end{verbatim}
+
+\noindent
+This command invokes \verb|glpsol|, the GLPK LP/MIP stand-alone solver,
+which reads the model section from file \verb|pbn.mod|, the data section
+from file \verb|foo.dat|, translates them to an internal representation,
+and solves the resulting 0-1 integer feasibility problem. The option
+\verb|--minisat| tells \verb|glpsol| to translate the feasibility
+problem to a CNF satisfiability problem and then use the MiniSat solver
+[3] to solve it.
+
+If a solution to the puzzle has been found, that is indicated by the
+message \verb|SATISFIABLE|, \verb|glpsol| prints the solution to the
+standard output (terminal), writes it to file \verb|solution.ps| in the
+PostScript format, and also writes it to file \verb|solution.dat| in the
+form of MathProg data section, which can be used later to check for
+multiple solutions, if necessary (for details see the next section).
+The message \verb|UNSATISFIABLE| means that the puzzle has no solution.
+
+Usually the time taken to solve a puzzle of moderate size (up to 50 rows
+and columns) varies from several seconds to several minutes. However,
+hard or large puzzles may require much more time.
+
+Data sections for some example puzzles included in the GLPK distribution
+can be found in subdirectory \verb|examples/pbn|.
+
+\section{Checking for multiple solutions}
+
+Sometimes the user may be interested to know if the puzzle has exactly
+one (unique) solution or it has multiple solutions. To check that the
+user should solve the puzzle as explained above in the previous section
+and then enter the following command:
+
+\begin{verbatim}
+   glpsol --minisat -m pbn.mod -d foo.dat -d solution.dat
+\end{verbatim}
+
+\noindent
+In this case \verb|glpsol| reads an additional data section from file
+\verb|solution.dat|, which contains the previously found solution,
+activates an additional constraint in the model section to forbid
+finding the solution specified in the additional data section, and
+attempts to find another solution. The message \verb|UNSATISFIABLE|
+reported by \verb|glpsol| will mean that the puzzle has a unique
+solution, while the message \verb|SATISFIABLE| will mean that the puzzle
+has at least two different solutions.
+
+\newpage
+
+\section{Solution times}
+
+The table on the next page shows solution times on a sample set of
+the paint-by-numbers puzzles from the \verb|<webpbn.com>| website.
+This sample set was used in the survey [4] to compare efficiency of
+existing PBN solvers.
+
+The authors of some puzzles from the sample set have given permission
+for their puzzles to be freely redistributed as long as the original
+attribution and copyright statement are retained. In the table these
+puzzles are marked by an asterisk (*). The files containing the
+MathProg data sections for these puzzles are included in the GLPK
+distribution and can be found in subdirectory \verb|examples/pbn|.
+
+All runs were performed on Intel Pentium 4 (CPU 3GHz, 2GB of RAM).
+The C compiler used was GCC 3.4.4 with default optimization options.
+
+The column `Sol.Time' shows the time, in seconds, taken by the
+\verb|glpsol| solver to find a solution to corresponding puzzle. The
+column `Chk.Time' shows the time, in seconds, taken by \verb|glpsol| to
+check for multiple solutions, i.e. either to prove that the puzzle has
+a unique solution or find another solution to the puzzle. Both these
+times do not include the time used to translate the MathProg model and
+data sections into an internal MIP representation, but include the time
+used to translate the 0-1 feasibility problem to a CNF satisfiability
+problem.
+
+\begin{thebibliography}{10}
+
+\bibitem{1}
+Robert A. Bosch, ``Painting by Numbers'', 2000.\\
+\verb|<http://www.oberlin.edu/~math/faculty/bosch/pbn-page.html>|.
+
+\bibitem{2}
+GLPK: Modeling Language GNU MathProg. Language Reference. (This
+document is included in the GLPK distribution and can be found in
+subdirectory \verb|doc|.)
+
+\bibitem{3}
+Niklas E\'en, Niklas S\"orensson, ``An Extensible SAT-solver'',
+Chalmers University of Technology, Sweden. \verb|<http://minisat.se/>|.
+
+\bibitem{4}
+Jan Wolter, ``Survey of Paint-by-Number Puzzle Solvers''.\\
+\verb|<http://webpbn.com/survey/>|.
+
+\end{thebibliography}
+
+\newpage
+
+\begin{table}
+\caption{Solution times on the sample set of puzzles from [4]}
+\begin{center}
+\begin{tabular}{@{}lllcrr@{}}
+\hline
+\multicolumn{2}{c}{Puzzle}&Size&Notes&Sol.Time, s&Chk.Time, s\\
+\hline
+\#1&Dancer*    &$10\times 5$&L&$<1$&$<1$\\
+\#6&Cat*       &$20\times 20$&L&$<1$&$<1$\\
+\#21&Skid*     &$25\times 14$&L, B&$<1$&$<1$\\
+\#27&Bucks*    &$23\times 27$&B&$<1$&$<1$\\
+\#23&Edge*     &$11\times 10$&&$<1$&$<1$\\
+\#2413&Smoke   &$20\times 20$&&$<1$&$<1$\\
+\#16&Knot*     &$34\times 34$&L&1&1\\
+\#529&Swing*   &$45\times 45$&L&1&1\\
+\#65&Mum*      &$40\times 34$&&1&1\\
+\#7604&DiCap   &$55\times 55$&&10&10\\
+\#1694&Tragic  &$50\times 45$&&3&3\\
+\#1611&Merka   &$60\times 55$&B&4&4\\
+\#436&Petro*   &$35\times 40$&&1&1\\
+\#4645&M\&M    &$70\times 50$&B&5&6\\
+\#3541&Signed  &$50\times 60$&&7&7\\
+\#803&Light*   &$45\times 50$&B&1&1\\
+\#6574&Forever*&$25\times 25$&&1&1\\
+\#2040&Hot     &$60\times 55$&&6&6\\
+\#6739&Karate  &$40\times 40$&M&2&2\\
+\#8098&9-Dom*  &$19\times 19$&&1&2\\
+\#2556&Flag    &$45\times 65$&M, B&2&2\\
+\#2712&Lion    &$47\times 47$&M&11&12\\
+\#10088&Marley &$63\times 52$&M&135&226\\
+\#9892&Nature  &$40\times 50$&M&850&1053\\
+\hline
+\end{tabular}
+
+\begin{tabular}{@{}lp{102mm}@{}}
+*&Puzzle designer has given permission to redistribute the puzzle.\\
+L&Puzzle is line solvable. That is, it can be solved one line at a
+time.\\
+B&Puzzle contains blank rows or columns.\\
+M&Puzzle has multiple solutions.\\
+\end{tabular}
+\end{center}
+\end{table}
+
+\end{document}
diff --git a/glpk-5.0/examples/pbn/petro.dat b/glpk-5.0/examples/pbn/petro.dat
new file mode 100644
index 0000000..15ccc4a
--- /dev/null
+++ b/glpk-5.0/examples/pbn/petro.dat
@@ -0,0 +1,102 @@
+/* petro.dat */
+
+/***********************************************************************
+*  Web Paint-by-Number Puzzle #436 from <www.webpbn.com>.
+*  Copyright (C) 2006 by Jan Wolter. Used by permission.
+*
+*  Old Stone Face
+*
+*  created by Jan Wolter
+*  Jun 17, 2006
+*
+*  Encoded in GNU MathProg by Andrew Makhorin <mao@gnu.org>.
+***********************************************************************/
+
+data;
+
+param m := 35;
+
+param n := 40;
+
+param row : 1  2  3  4  5  6  7  8  9  :=
+      1     2  2  .  .  .  .  .  .  .
+      2     2  3  2  .  .  .  .  .  .
+      3     3  3  3  2  .  .  .  .  .
+      4     3  3  3  3  .  .  .  .  .
+      5     2  3  3  3  3  2  .  .  .
+      6     3  3  3  3  3  3  .  .  .
+      7     4  2  3  2  2  4  .  .  .
+      8     4  2  2  2  2  3  1  .  .
+      9     3  1  2  2  2  3  3  .  .
+      10    3  2  2  2  2  2  4  .  .
+      11    3  2  15 2  4  .  .  .  .
+      12    5  19 4  .  .  .  .  .  .
+      13    6  4  3  3  .  .  .  .  .
+      14    6  4  4  .  .  .  .  .  .
+      15    2  4  6  2  .  .  .  .  .
+      16    2  2  3  3  3  2  .  .  .
+      17    9  2  2  2  3  9  .  .  .
+      18    10 2  2  2  2  2  10 .  .
+      19    4  2  3  3  2  2  3  2  5
+      20    2  5  2  4  2  .  .  .  .
+      21    5  3  2  2  5  .  .  .  .
+      22    6  3  2  3  7  .  .  .  .
+      23    6  8  9  7  .  .  .  .  .
+      24    4  8  7  5  .  .  .  .  .
+      25    4  .  .  .  .  .  .  .  .
+      26    2  .  .  .  .  .  .  .  .
+      27    2  .  .  .  .  .  .  .  .
+      28    14 .  .  .  .  .  .  .  .
+      29    16 .  .  .  .  .  .  .  .
+      30    3  3  .  .  .  .  .  .  .
+      31    2  2  .  .  .  .  .  .  .
+      32    2  2  .  .  .  .  .  .  .
+      33    4  4  .  .  .  .  .  .  .
+      34    16 .  .  .  .  .  .  .  .
+      35    12 .  .  .  .  .  .  .  .
+;
+
+param col : 1  2  3  4  5  6  7  :=
+      1     1  .  .  .  .  .  .
+      2     3  2  .  .  .  .  .
+      3     2  3  3  .  .  .  .
+      4     3  3  3  .  .  .  .
+      5     3  3  3  3  .  .  .
+      6     4  2  2  2  .  .  .
+      7     3  3  2  3  .  .  .
+      8     3  2  2  2  .  .  .
+      9     3  2  6  .  .  .  .
+      10    2  9  .  .  .  .  .
+      11    2  3  3  .  .  .  .
+      12    4  4  3  2  4  .  .
+      13    7  2  5  2  6  .  .
+      14    12 2  3  2  3  2  .
+      15    3  1  2  2  2  3  .
+      16    2  2  3  2  2  2  .
+      17    6  2  6  2  2  2  .
+      18    12 4  3  2  2  .  .
+      19    12 2  2  2  .  .  .
+      20    2  6  2  .  .  .  .
+      21    2  6  5  2  .  .  .
+      22    10 9  2  2  .  .  .
+      23    12 3  3  2  2  .  .
+      24    6  2  2  2  2  2  2
+      25    2  2  3  2  2  2  .
+      26    4  3  2  2  2  3  .
+      27    7  3  3  2  3  2  .
+      28    5  3  5  2  6  .  .
+      29    4  3  3  3  4  .  .
+      30    3  5  3  .  .  .  .
+      31    3  9  .  .  .  .  .
+      32    4  2  6  .  .  .  .
+      33    4  2  2  2  .  .  .
+      34    4  2  2  3  .  .  .
+      35    3  2  2  3  .  .  .
+      36    3  3  3  .  .  .  .
+      37    3  3  3  .  .  .  .
+      38    4  3  3  .  .  .  .
+      39    2  3  3  .  .  .  .
+      40    2  1  .  .  .  .  .
+;
+
+end;
diff --git a/glpk-5.0/examples/pbn/skid.dat b/glpk-5.0/examples/pbn/skid.dat
new file mode 100644
index 0000000..865c73b
--- /dev/null
+++ b/glpk-5.0/examples/pbn/skid.dat
@@ -0,0 +1,66 @@
+/* skid.dat */
+
+/***********************************************************************
+*  Web Paint-by-Number Puzzle #21 from <www.webpbn.com>.
+*  Copyright (C) 2004 by Jan Wolter. Used by permission.
+*
+*  Slippery Conditions
+*
+*  created by Jan Wolter
+*  Apr 4, 2004
+*
+*  Encoded in GNU MathProg by Andrew Makhorin <mao@gnu.org>.
+***********************************************************************/
+
+data;
+
+param m := 25;
+
+param n := 14;
+
+param row : 1  2  3  :=
+      1     9  .  .
+      2     1  1  .
+      3     1  1  1
+      4     1  3  1
+      5     13 .  .
+      6     13 .  .
+      7     13 .  .
+      8     13 .  .
+      9     2  2  .
+      10    2  2  .
+      11    .  .  .
+      12    2  2  .
+      13    2  2  .
+      14    2  2  .
+      15    2  2  .
+      16    2  2  .
+      17    2  2  .
+      18    2  2  .
+      19    2  2  .
+      20    2  2  .
+      21    2  2  .
+      22    2  2  .
+      23    2  2  .
+      24    2  2  .
+      25    2  2  .
+;
+
+param col : 1  2  3  4  5  :=
+      1     2  .  .  .  .
+      2     4  6  .  .  .
+      3     9  4  4  2  .
+      4     1  6  2  6  .
+      5     1  5  2  .  .
+      6     1  6  .  .  .
+      7     1  5  .  .  .
+      8     1  4  .  .  .
+      9     1  4  .  .  .
+      10    1  4  2  .  .
+      11    1  4  6  .  .
+      12    1  6  4  4  2
+      13    9  2  6  .  .
+      14    4  2  .  .  .
+;
+
+end;
diff --git a/glpk-5.0/examples/pbn/swing.dat b/glpk-5.0/examples/pbn/swing.dat
new file mode 100644
index 0000000..547e0db
--- /dev/null
+++ b/glpk-5.0/examples/pbn/swing.dat
@@ -0,0 +1,117 @@
+/* swing.dat */
+
+/***********************************************************************
+*  Web Paint-by-Number Puzzle #529 from <www.webpbn.com>.
+*  Copyright (C) 2006 by Jan Wolter. Used by permission.
+*
+*  Swing
+*
+*  created by Jan Wolter
+*  Sep 28, 2006
+*
+*  Encoded in GNU MathProg by Andrew Makhorin <mao@gnu.org>.
+***********************************************************************/
+
+data;
+
+param m := 45;
+
+param n := 45;
+
+param row : 1  2  3  4  5  6  7  8  9  10 11 12 13 14 :=
+      1     7  1  1  1  1  1  .  .  .  .  .  .  .  .
+      2     3  1  3  1  4  1  4  1  5  1  5  1  2  .
+      3     1  1  1  3  1  4  1  4  1  5  1  5  1  2
+      4     2  1  2  1  1  1  1  6  2  .  .  .  .  .
+      5     3  30 1  5  .  .  .  .  .  .  .  .  .  .
+      6     1  5  8  1  1  7  1  1  3  .  .  .  .  .
+      7     3  4  8  1  5  1  2  .  .  .  .  .  .  .
+      8     3  20 6  6  .  .  .  .  .  .  .  .  .  .
+      9     3  3  7  2  5  1  .  .  .  .  .  .  .  .
+      10    3  3  1  1  9  1  1  5  6  .  .  .  .  .
+      11    2  3  8  1  3  4  2  .  .  .  .  .  .  .
+      12    5  3  1  10 4  5  2  .  .  .  .  .  .  .
+      13    1  2  3  8  4  6  .  .  .  .  .  .  .  .
+      14    2  2  3  11 10 .  .  .  .  .  .  .  .  .
+      15    2  2  3  10 7  .  .  .  .  .  .  .  .  .
+      16    2  3  1  7  12 2  .  .  .  .  .  .  .  .
+      17    2  3  1  4  11 2  .  .  .  .  .  .  .  .
+      18    4  1  2  1  11 2  .  .  .  .  .  .  .  .
+      19    9  1  2  9  .  .  .  .  .  .  .  .  .  .
+      20    6  2  1  4  11 .  .  .  .  .  .  .  .  .
+      21    2  5  1  2  6  6  .  .  .  .  .  .  .  .
+      22    6  2  4  8  4  .  .  .  .  .  .  .  .  .
+      23    4  2  16 1  .  .  .  .  .  .  .  .  .  .
+      24    2  2  15 2  .  .  .  .  .  .  .  .  .  .
+      25    3  2  15 4  .  .  .  .  .  .  .  .  .  .
+      26    3  3  13 4  .  .  .  .  .  .  .  .  .  .
+      27    4  12 9  .  .  .  .  .  .  .  .  .  .  .
+      28    1  9  10 .  .  .  .  .  .  .  .  .  .  .
+      29    2  1  17 7  2  .  .  .  .  .  .  .  .  .
+      30    2  2  8  3  8  2  .  .  .  .  .  .  .  .
+      31    2  3  6  3  8  2  .  .  .  .  .  .  .  .
+      32    2  4  5  4  7  2  .  .  .  .  .  .  .  .
+      33    2  5  5  4  6  .  .  .  .  .  .  .  .  .
+      34    4  4  5  4  9  .  .  .  .  .  .  .  .  .
+      35    1  4  6  4  4  .  .  .  .  .  .  .  .  .
+      36    4  3  6  4  3  2  .  .  .  .  .  .  .  .
+      37    2  1  2  7  4  4  2  .  .  .  .  .  .  .
+      38    2  2  2  9  5  5  2  .  .  .  .  .  .  .
+      39    2  2  2  10 6  6  .  .  .  .  .  .  .  .
+      40    3  2  1  9  18 .  .  .  .  .  .  .  .  .
+      41    8  4  23 .  .  .  .  .  .  .  .  .  .  .
+      42    1  2  1  2  2  1  1  1  2  .  .  .  .  .
+      43    2  1  4  2  1  4  1  5  1  3  1  2  .  .
+      44    2  1  5  4  4  1  5  1  3  1  2  .  .  .
+      45    1  10 1  1  1  .  .  .  .  .  .  .  .  .
+;
+
+param col : 1  2  3  4  5  6  7  8  9  10 11 12 13 14 :=
+      1     7  1  1  1  1  1  .  .  .  .  .  .  .  .
+      2     2  2  4  1  4  1  5  1  4  1  4  1  2  .
+      3     3  1  4  1  4  1  14 4  1  2  .  .  .  .
+      4     1  1  5  1  2  3  4  1  .  .  .  .  .  .
+      5     3  13 1  10 .  .  .  .  .  .  .  .  .  .
+      6     1  9  4  .  .  .  .  .  .  .  .  .  .  .
+      7     6  7  2  2  .  .  .  .  .  .  .  .  .  .
+      8     8  4  1  4  .  .  .  .  .  .  .  .  .  .
+      9     2  8  3  2  5  3  .  .  .  .  .  .  .  .
+      10    10 1  3  7  2  .  .  .  .  .  .  .  .  .
+      11    8  6  2  8  1  2  .  .  .  .  .  .  .  .
+      12    1  1  2  2  8  1  1  .  .  .  .  .  .  .
+      13    2  1  1  1  2  1  3  1  3  3  1  .  .  .
+      14    2  1  1  1  5  4  2  1  .  .  .  .  .  .
+      15    2  1  1  1  1  7  2  1  .  .  .  .  .  .
+      16    2  1  1  2  9  1  2  1  .  .  .  .  .  .
+      17    4  6  12 1  3  .  .  .  .  .  .  .  .  .
+      18    16 13 3  2  .  .  .  .  .  .  .  .  .  .
+      19    12 21 2  .  .  .  .  .  .  .  .  .  .  .
+      20    2  13 23 .  .  .  .  .  .  .  .  .  .  .
+      21    2  14 19 .  .  .  .  .  .  .  .  .  .  .
+      22    2  14 20 2  .  .  .  .  .  .  .  .  .  .
+      23    2  13 7  2  8  2  .  .  .  .  .  .  .  .
+      24    12 8  1  7  2  .  .  .  .  .  .  .  .  .
+      25    5  1  1  1  2  8  1  5  2  .  .  .  .  .
+      26    2  1  1  1  9  1  1  4  .  .  .  .  .  .
+      27    2  1  1  1  6  1  3  5  .  .  .  .  .  .
+      28    2  2  1  5  6  2  .  .  .  .  .  .  .  .
+      29    2  1  3  1  3  7  3  2  .  .  .  .  .  .
+      30    2  3  2  1  1  2  4  4  2  .  .  .  .  .
+      31    2  2  1  1  2  3  1  8  2  .  .  .  .  .
+      32    9  3  1  7  2  .  .  .  .  .  .  .  .  .
+      33    12 4  1  6  2  .  .  .  .  .  .  .  .  .
+      34    7  4  1  2  5  .  .  .  .  .  .  .  .  .
+      35    2  6  6  5  6  .  .  .  .  .  .  .  .  .
+      36    8  8  6  3  .  .  .  .  .  .  .  .  .  .
+      37    3  10 8  4  2  .  .  .  .  .  .  .  .  .
+      38    5  11 9  5  2  .  .  .  .  .  .  .  .  .
+      39    3  1  12 16 2  .  .  .  .  .  .  .  .  .
+      40    3  1  12 16 .  .  .  .  .  .  .  .  .  .
+      41    5  2  13 21 .  .  .  .  .  .  .  .  .  .
+      42    6  1  3  3  1  1  .  .  .  .  .  .  .  .
+      43    5  1  3  1  3  1  1  2  1  4  1  3  1  3
+      44    5  1  3  1  3  1  4  1  4  1  3  1  3  .
+      45    1  1  1  1  1  1  .  .  .  .  .  .  .  .
+;
+
+end;