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 A has to come before item B
  • A set of soft constraints whose satisfaction I'd like to maximise, e.g.: It'd be nice if item A came before item B
  • 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?

  • $\begingroup$ Interesting! Two questions: $\endgroup$ – ryanm Jun 22 '18 at 7:59
  • 1
    $\begingroup$ Your problem is known as maximum acyclic subgraph or minimum feedback arc set, with the constraint of out-degree (or in-degree) at most 2, and an additional constraint on the weights. $\endgroup$ – Yuval Filmus Jun 22 '18 at 8:04
  • $\begingroup$ You can replace hard constraints with soft constraints having large enough weight. $\endgroup$ – Yuval Filmus Jun 22 '18 at 8:05
  • $\begingroup$ The standard notion of multiplicative approximation is not suitable for your case, unless you treat the hard constraints as hard constraints (like in your description), but this will make it harder to find information about your problem. $\endgroup$ – Yuval Filmus Jun 22 '18 at 8:06
  • $\begingroup$ Gah, missed the comment edit deadline. My questions were: * Isn't that a distinction without a difference? It should never be possible for a hard constraint to be broken regardless of how many soft constraints contradict it, so wouldn't the two values have to be infinitely distant? * Can you point to a technique that can be used to find an ordering that maximises satisfaction? It sounds like the kind of thing that has a standard approach, but I'm too long out of university to be conversant with it. $\endgroup$ – ryanm Jun 22 '18 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.