Using Monads in C++ to Solve Constraints: 3. The Tale of Two Monads

For the sample constraint satisfaction problem

       s e n d
     + m o r e
     ---------
     m o n e y

how about considering it as a special case of integer linear programming for which there is an enormous literature of powerful techniques all of which are just applied math and can be coded up in Fortran, ..., C, etc. with no mention at all of functional programming or monads?

Moreover there are several highly polished software packages that implement the applied math.

For a detailed formulation as integer linear programming there is:

     Find

          d, e, m, n, o, r, s, y

     to solve

          maximize z = d + e + m + n + o + r + s + y

     subject to

          1000 * s + 100 * e + 10 * n + d + 1000 * m
          + 100 * o + 10 * r + e - 10000 * m - 1000 *
          o - 100 * n - 10 * e - y <= 0

          d, e, m, n, o, r, s, y <= 9

          d, e, m, n, o, r, s, y >= 0

     and

          d, e, m, n, o, r, s, y

     integers.

More generally, that constraint satisfaction is often just looking for a feasible solution to a linear or linear integer program is part of why ILOG and SAP used the R. Bixby optimization software C-PLEX.

Similarly if functional programming and monads can make good progress on linear and/or linear integer programming, then there are some people in parts of the applied math, operations research, and engineering communities that would be very interested.

And, of course, since integer linear programming is in NP-complete, really good work would win a Clay Math prize of $1 million.

In more detail, at

http://www.zweigmedia.com/RealWorld/simplex.html

can get linear and linear integer programming on-line.

Then for the sample problem, in the format of that on-line solver asking for just linear programming and not integer linear programming, the problem formulation is

     maximize p = d + e + m + n + o + r + s + y

     subject to

     1000 s + 100 e + 10 n + 1 d + 1000 m
     + 100 o + 10 r + 1 e - 10000 m - 1000
     o - 100 n - 10 e - 1 y <= 0,

     d + e + m + n + o + r + s + y >= 1,

     d <= 9,

     e <= 9,

     m <= 9,

     n <= 9,

     o <= 9,

     r <= 9,

     s <= 9,

     y <= 9

Note: In the above, the on-line solver wants the first constraint to be all on one line.

Then from the on-line solver an optimal soluion is:

p = 18;

d = 9, e = 0, m = 0, n = 0, o = 0, r = 0, s = 0, y = 9

in which case this solution to the sample problem becomes just

       9
     + 9
     ---
      18