Das lineare Ordnungsproblem ist ein NP-hartes kombinatorisches Problem mit einer großen Anzahl von Anwendungen. Im Gegensatz zu einem anderen sehr populären Problem aus der gleichen Kategorie, dem Travelling-Salesman-Problem, wurde dem linearen Ordnungsproblem in der Literatur bisher relativ wenig Raum gewidmet. Dies gilt insbesondere für die Frage der Entwicklung guter heuristischer Algorithmen, die dieses Problem lösen.
In diesem Papier schlagen wir einen neuen heuristischen Algorithmus vor, der das lineare Ordnungsproblem löst. In diesem Algorithmus haben wir sowohl die Sortierung durch Einfügemuster als auch die Operation der Permutationsumkehr genutzt. Die überraschend positive Wirkung der Umkehroperation, die zum Teil theoretisch begründet und in Rechenbeispielen bestätigt wurde, scheint das Ergebnis einer einzigartigen Eigenschaft des Problems zu sein, die in diesem Papier als Symmetrie des linearen Ordnungsproblems bezeichnet wird. Diese Eigenschaft besteht darin, dass, wenn eine gegebene Permutation eine optimale Lösung des Problems ist, bei der die Kriteriumsfunktion maximiert wird, dann ist die umgekehrte Permutation eine Lösung des Problems, bei der die gleiche Kriteriumsfunktion minimiert wird.