Formulare i problemi di taglio multistadio come QUBO

Abstract degli autori

I problemi di taglio sono di grande rilevanza per diversi settori industriali. Qui presentiamo una formulazione di programmazione lineare per una versione ristretta del problema di taglio 2D multistadio con tagli a ghigliottina e la testiamo su istanze benchmark pubblicate. In seguito, ricaviamo una riformulazione non esatta in forma di ottimizzazione binaria quadratica non vincolata (QUBO) tramite penalizzazione non bilanciata, che mostriamo poter offrire possibili vantaggi nel modellare il problema con scarti riutilizzabili. Questo lavoro considera principalmente la formulazione ristretta, in cui le dimensioni di ciascun taglio sono determinate da quelle di un singolo pezzo richiesto. Discutiamo inoltre come estendere l’approccio al problema non ristretto, che ammette schemi di taglio più generali, con tagli le cui dimensioni coinvolgono più pezzi richiesti, e dà naturalmente luogo a termini quadratici nelle disuguaglianze della formulazione del problema. Presentiamo soluzioni ottenute con un solver di ricottura simulata per la classe di problemi ristretti, studiando soprattutto le prestazioni del metodo iterativo del lagrangiano aumentato. Discutiamo inoltre le possibili applicazioni dell’annealing quantistico in questo contesto, che costituisce una forte motivazione per la ricerca sulle formulazioni QUBO.