I've got a set of items that I'd like to sort into a list. The items have two independent sets of constraints that the ordering should respect:
- A set of hard constraints that must be satisfied, e.g.: Item
Ahas to come before item
- A set of soft constraints whose satisfaction I'd like to maximise, e.g.: It'd be nice if item
Acame before item
- It can be guaranteed for either constraint set that orderings exist that fully satisfy them, but it's not guaranteed that an ordering exists that satisfies both
- Each item is subject to at most one constrain in each set, i.e.: each has zero or one items that they must come after, and zero or one items that it'd be nice if they came after.
If I had just had the hard constraints then a topological sort is all that's required, but I can't see how to extends those approaches to maximise the satisfaction of the soft constraint set.
Context: this was posted over at stackoverflow and it was suggested it was a better fit here. Of the two approaches suggested in that question, one has obvious counterexamples while the other, once I'd implemented it, turned out to have slightly-less-obvious counterexamples.
So, is there an accepted approach for finding a list order that will fully satisfy one constraint set while maximising the satisfaction of another?