La contrazione dei grafi consente di sfuggire agli ottimi locali nel MAX-CUT non convesso con risorse di calcolo limitate

Abstract degli autori

Poiché il suo panorama di ottimizzazione binaria contiene un numero esponenziale di ottimi locali, MAX-CUT è molto sensibile all’inizializzazione. Studiamo Particle Polynomial Relaxation (PPR), una riformulazione continua non convessa basata sui momenti, con un panorama di ottimizzazione favorevole. Inizializziamo PPR con Combinatorial Multigrid (CMG), un metodo spettrale di contrazione dei grafi che produce soluzioni iniziali sensibili alla struttura in tempo quasi lineare, senza dati di addestramento. Su \texttt{t2g20} ($n=400$), un’istanza benchmark il cui ottimo esatto è noto, la pipeline combinata CMG+PPR raggiunge in media il $97.5\%$ dell’ottimo e, nella migliore esecuzione, il $98.4\%$. Una variante estesa con perfezionamento mediante ricerca locale discreta raggiunge l’ottimo pubblicato per tutte le 60 istanze Biq Mac valutate da un recente metodo neurale di branch-and-bound. Usando una rappresentazione CSR sparsa, lo stesso approccio si estende alle istanze G-set con fino a $20{,}000$ vertici, riducendo i requisiti di memoria fino a $3333\times$ e mantenendo un miglioramento costante rispetto alla soluzione iniziale prodotta da CMG. I miglioramenti sono maggiori sui grafi sparsi pesati; sui grafi densi integriamo la pipeline con una sparsificazione spettrale.