4 ms·

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

28 points by andrzejsz 11y ago

graycat 11y ago
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 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
- dllthomas 11y ago
  You omitted the uniqueness constraint.
  - BartoszMilewski 11y ago
    And the condition that s != 0 and m != 0
    - graycat 11y ago
      Sorry I didn't see a statement of the other conditions. Actually, from what I saw, just setting all the variables to 0 would have been a feasible solution. At least I got a solution with some of the variables not 0.
- juliangamble 11y ago
  You can see an answer to the problem here: http://strasheela.sourceforge.net/strasheela/doc/ConstraintProgramming.html#sec13 http://strasheela.sourceforge.net/strasheela/doc/ConstraintP...

28 points by andrzejsz 11y ago

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 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

dllthomas 11y ago
You omitted the uniqueness constraint.
- BartoszMilewski 11y ago
  And the condition that s != 0 and m != 0
  - graycat 11y ago
    Sorry I didn't see a statement of the other conditions. Actually, from what I saw, just setting all the variables to 0 would have been a feasible solution. At least I got a solution with some of the variables not 0.
juliangamble 11y ago
You can see an answer to the problem here: http://strasheela.sourceforge.net/strasheela/doc/ConstraintProgramming.html#sec13 http://strasheela.sourceforge.net/strasheela/doc/ConstraintP...