Message Boards Message Boards

GROUPS:

Is there a way to give Solve "hints" ...

Posted 6 years ago
8249 Views
|
4 Replies
|
0 Total Likes
|

Solve is a wonder, but in my current application is seems to be "slow", relatively.

I'm finding positive integer solutions to constraints that are sums (of positive integers) and minimums (of positive integers).

When I use pencil and paper to get a solution I sort the constraints and apply them in a certain - data driven - order. I'm thinking my manual solution runs in time that is linear in the number of constraints. However, programming this approach would be tedious - which is why it's wonderful to have Solve.

I've tried telling Solve that the solution desired is in Integers, but this just makes it run more slowly.

Am I missing something in my use of Solve?

4 Replies

I don't think you can Solve hints. You can break the problem down into parts and use Solve repeatedly. I've done that Reduce.

To answer my own question: Following the suggestion from FrankK above, the reason I can solve my problem with pencil and paper in reasonable time when Solve takes more time than seems necessary is that I am exploiting the simple cases.

It turns out that there are eight cases to be considered, meaning that eight different ways that the constraints need to be applied. In the simplest case - #1 - Solve isn't even necessary. With case #8 I wouldn't want to try solving it with pencil and paper. Cases #2-#7 have increasing complexity, accordingly.

The next time I implement this I'll formulate some boolean tests to see which case is applicable and if it's Cases #1-7 I can simplify the constraints accordingly.

Obviously, Solve has to assume the worst case, and that - I'm assuming - is why it takes so long.

You may wish to not use Solve at all but use the constraints to eliminate cases that aren't satisfied, in a sequential manner, alternatively generating cases and eliminating most of them with the constraints. I've done Sudoku and KenKen that way in Mathematica, problems too large for Solve or Reduce to handle.

Yes!

I've been thinking about this, and will be trying something like what you suggest. So I appreciate the encouragement and suggestions.

In summary, it's been really great to have Solve, but, ultimately, it may be an impediment to scaling, and I'll need to implement my own approach.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract