Re: Assignmnet problem with rules

Since you can't afford exhaustive search, it's impossible to say how
you can do better without knowing what the rules are and how they
change.

The general methods that apply are
* "relaxation," where you solve a restricted, nearby problem and then
try to modify it to solve your real problem.
* "heuristic search," which is a refinement of exhaustive search.

Or if you are lucky and there is some useful structure in your rules,
you many be able to use a known algorithm like weighted bipartite
matching, which is O(n^2 log n)

.