Algoritmo per una soluzione esatta al Problema dell'acquirente in viaggio

Il dominio dei problemi NP-Hard significa che, per quanto riguarda le attuali conoscenze matematiche, il problema può essere risolto solo provando ogni permutazione e scegliendo la risposta corretta.

Se riesci a risolvere il problema in modo più efficiente rispetto al metodo della forza bruta, vincerai un premio Nobel in matematica come bonus. I migliori matematici hanno lavorato su una risposta generale a questo problema per decenni.

Forse, poiché vuoi creare un set di dati di test per il tuo risolutore di problemi NP-Hard, il tuo approccio potrebbe essere quello di progettare i dati di test al contrario - piuttosto che risolvere il problema NP-Hard, creare un problema NP-Hard con una risposta conosciuta - Non so nemmeno se si tratta di un problema NP-Hard a parte.

Puoi provare la programmazione lineare intera, ma posso darti solo formulazione di un commesso viaggiatore , ma non dovrebbe essere difficile da modificare, una volta che si avvia l'idea. Un'altra opzione può essere l'uso di una libreria di programmazione con vincoli (come JaCoP: link ). Nella mia esperienza è possibile risolvere problemi NP-hard con diverse centinaia di nodi usando un normale computer desktop. Se i tuoi dati sono più grandi, dovrai utilizzare qualche approssimazione / programmazione genetica e cose del genere, non sarai in grado di ottenere la soluzione esatta.

Anche se NP-hard, il TPP può essere risolto efficacemente in pratica da molti diversi metodi esatti (come il TSP). La programmazione dinamica, la programmazione matematica (branch-and-cut, branch-and-bound) e gli algoritmi basati sulla programmazione di vincoli esistono e sono stati proposti per il TPP nella letteratura di ricerca operativa / informatica. Vi suggerisco di leggere un sondaggio molto recente sul tema: "Manerba et al., 2017. Il problema dell'acquirente itinerante e le sue varianti, European Journal of operational Research 259, 1-18".

Naturalmente, la complessità pratica del risolvere esattamente il TPP cresce con il numero di mercati e prodotti (specialmente il mercato). Tuttavia, utilizzando i metodi corretti, è possibile trovare soluzioni esatte in tempi ragionevoli sui computer moderni per le istanze con mercati 150/200 e prodotti 200/300.

Alcuni solutori noti (Cplex, Gurobi, ..) sono anche in grado di risolvere esattamente alcune istanze piccole / medie del TPP se il suo modello viene fornito come input. Questo sarà molto utile se hai bisogno di queste soluzioni solo per identificare la tua euristica. In tal caso, la formulazione matematica del problema è un problema critico da affrontare.

PS: per il folclore, se trovi un algoritmo esatto con una complessità temporale polinomiale che risolve un problema NP-difficile, allora risolvi anche il Problema aperto "P vs NP" proposto dall'Istituto Clay come uno dei problemi del Millenium e vincere 1 milione di dollari.