Un algoritmo esatto per risolvere problemi hard
l Max-Cut, ovvero trovare il taglio di peso massimo in un grafo pesato, è uno dei problemi più studiati in ottimizzazione combinatoria che, oltre ad avere molteplici connessioni con altri problemi di matematica discreta, si presenta in numerose applicazioni dell'ottimizzazione. Esempi di Max-Cut si trovano nell'ambito di studio dei materiali magnetici, per trovare uno stato di minima energia in una configurazione di vetri di spin, oppure nell'ambito dell'allocazione ottima di risorse, per assegnare, per esempio, una di due frequenze a ciascuno di un dato insieme di ripetitori radio-televisivi, in modo da produrre la minima interferenza globale possibile. Classificato come problema NP-hard, il Max-Cut è di solito affrontato con procedimenti euristici, che però non riescono a valutare di quanto la soluzione trovata si discosti da quel- la ottima. Se invece, come avviene per alcune applicazioni, si richiede una soluzione esatta, il compito diventa molto più difficile: se si usano semplici tecniche enumerative, anche con i più moderni computer è possibile trattare solo grafi non più grandi di appena 20 nodi. Per grafi più grandi le tecniche più efficaci oggi in uso si basano su due possibili rilassamenti del problema: quello poliedrale e quello semide- finito. Il primo è particolarmente adatto per grafi molto sparsi mentre il secondo è preferibile per grafi più densi. Nell'ambito di una collaborazione tra IASI-CNR e l'Università di Klagenfurt, viene proposto un nuovo algoritmo esatto (utilizzabile dal sito biqmac.uni-klu.ac.at) che utilizza, integrandoli, entrambi i rilassamenti. Il codice di calcolo prodotto, ha trovato e certificato l'ottimo di istanze benchmark. Per i problemi di ottimizzazione più studiati sono stati predisposti archivi di istanze benchmark, liberamente accessibili, con cui solitamente vengono preparati questi test contenuti in vari archivi di problemi e ancora irrisolte, per grafi aventi fino a 250 nodi, ed è probabilmente il più veloce oggi disponibile per la soluzione esatta del Max-Cut in grafi densi.
Autori: G. Rinaldi, Solving Max-Cut to Optimality by Intersecting Semidefinite and Polyhedral Relaxations
Titolo: Solving Max-Cut to Optimality by Intersecting Semidefinite and Polyhedral Relaxations
Rivista: Mathematical Programming
Anno: 2009
Riferimenti bibliografici: 2009 (IF=2.336)