Il problema dell’ordinamento lineare è un problema combinatorio NP-hard con un gran numero di applicazioni. Contrariamente ad un altro problema molto popolare della stessa categoria, il problema del commesso viaggiatore, relativamente poco spazio in letteratura è stato dedicato finora al problema dell’ordinamento lineare. Questo è particolarmente vero per la questione dello sviluppo di buoni algoritmi euristici che risolvono questo problema.
In questo articolo proponiamo un nuovo algoritmo euristico che risolve il problema dell’ordinamento lineare. In questo algoritmo abbiamo fatto uso dell’ordinamento attraverso il modello di inserimento e dell’operazione di inversione di permutazione. L’effetto sorprendentemente positivo dell’operazione di inversione, giustificato in parte teoricamente e confermato in esempi computazionali, sembra essere il risultato di una proprietà unica del problema, chiamata nel documento la simmetria del problema di ordinamento lineare. Questa proprietà consiste nel fatto che se una data permutazione è una soluzione ottimale del problema con la funzione di criterio massimizzata, allora la permutazione invertita è una soluzione del problema con la stessa funzione di criterio minimizzata.