I had a similar problem, several constraints (dozen or so, iirc), data set of a few thousand items.
I thought about finding an elegant solution, but in the end decided that just doing a (psuedo-)random selection of the remaining set and then running through the resulting ordered list checking each one for all the constraints (ie, random sort). As soon as it failed a hard constraint, or failed > x soft constraints, toss the list and do another random sort.
Ugly, but it worked. Chose this solution because 1) I knew how big the data set would be, and I knew it would not change size enough to matter; 2) The other, very jr developer could understand the method; 3) The constraints, while semi-complex, were simple to check; 4) would be needed once or twice a year, could run completely off-line, and could be started well in advance of when it was needed; 5) and finally computers are fast & cheap, while my time is finite and valuable
As a result, the decision that "brute force" running on any available workstation for a weekend was an acceptable solution. In it's lifetime, I think the longest time it took to find an acceptable solution was a few hundred thousand sorts, finished in a few minutes.
It's now been retired as the program it supported went away.
I wish I'd had the time to explore better, more proper solutions, but at the time, quick and dirty and done was more important.
I thought about finding an elegant solution, but in the end decided that just doing a (psuedo-)random selection of the remaining set and then running through the resulting ordered list checking each one for all the constraints (ie, random sort). As soon as it failed a hard constraint, or failed > x soft constraints, toss the list and do another random sort.
Ugly, but it worked. Chose this solution because 1) I knew how big the data set would be, and I knew it would not change size enough to matter; 2) The other, very jr developer could understand the method; 3) The constraints, while semi-complex, were simple to check; 4) would be needed once or twice a year, could run completely off-line, and could be started well in advance of when it was needed; 5) and finally computers are fast & cheap, while my time is finite and valuable
As a result, the decision that "brute force" running on any available workstation for a weekend was an acceptable solution. In it's lifetime, I think the longest time it took to find an acceptable solution was a few hundred thousand sorts, finished in a few minutes.
It's now been retired as the program it supported went away.
I wish I'd had the time to explore better, more proper solutions, but at the time, quick and dirty and done was more important.