Permutations maximally matching given pairwise order relations

Question

Given $n \in \mathbb{N}$ and a sequence of $T$ pairwise orders $(i_t, j_t)$'s for $1 \leq t \leq T$.

Q: Are there any existing algorithms to find permutations of $[n]$ ($\sigma \in S_n$) such that as many as possible given pairwise orders are satisfied (when it is impossible to satisfy all)?

• A pairwise order $(i_t, j_t)$ is satisfied if $\sigma(i_t) < \sigma(j_t)$
• Algorithms for finding ALL such permutations would be the best, but algorithms for finding one such permutation are also appreciated :D
• Seemingly, the followings questions are related but different: Permutations and partial orders / Number of permutations following given order

Answer 1

We can view $[n]$ as the nodes of a directed graph, and $(i_t,j_t)$ as its arcs. I believe that the problem you are interested in is equivalent to the feedback arc set problem. Here is a paper I found with a heuristic to approximately solve it https://doi.org/10.1016/0020-0190(93)90079-O Maybe there is more literature but I'll leave that up to you.