I've been playing a lot with constraint solving (thanks to my work on coinsayer) and when you have a hammer, everything looks like a nail  so I was thinking of how it'd look if you applied a constraint solver to a bitcoin node's mempool. The goal would be to simplify a lot of the rules, logic and remove the arbitrary limitations and rules that currently exist (that can be both annoying, and pretty incentive incompatible).
So I was thinking, imagine we allowed our mempool to contain transactions that conflict with each other  as long as they don't conflict with the transactions in the blockchain.
So to figure out which transactions should be in the next block is actually a pretty straight forward optimization problem. Basically find the set of transactions that maximizes the fees subject to it not exceed MAX_SIGOPS / MAX_WEIGHT / have any of the same inputs / and input references to an unconfirmed transaction, must then also include that transaction. You could even throw in a few extras without too much work (e.g. tie break on first seen transactions)
Now lets for a second pretend latency is unimportant (I think it's pretty solvable by running the solver, and caching the and incrementally updating it as an approximation).
So the real tricky part is some antiDoS stuff. We need to come up with:
A) a rule that would ban a peer for sending us too much crap b) a rule for knowing which transactions are worthy of forwarding to a peer
And we need to do it such that rule b) never causes our node to be banned by someone following rule a)

Any ideas?
