UN MODELLO MATEMATICO BASATO SU INSIEMI STABILI PER UN PROBLEMA DI NESTING BIDIMENSIONALE

This work proposes a new mixed integer programming (MIP) model for the strip packing problem by decomposing it into multiple subproblems known as maximal independent set problems (also called maximum stable set problems). This work addresses a recognized gap in the literature where, despite frequent mentions of the potential connection between strip packing and maximum independent set problems, no comprehensive implementation of this approach has been developed. This work evaluates the proposed approach using a well established dataset from current state of the art research, comprising 81 benchmark instances. The methodology focuses primarily on instances preprocessing, where a a conflict graph model is constructed and reformulation techniques are applied to reduce the model size before solving. During the graph construction phase, No-Fit Polygons are generated using Minkowski sums, and subsequently the \textit{conflict graph} is reformulated using clique covering through the state of the art MAX1-EK heuristic. CPLEX is used for analysis around known optimal board length. Preliminary results from CPLEX demonstrate strong bound convergence even without clique covering reformulation. With the clique covering reformulation, the average reduction in coefficent matrix size reaches 98\% (KB), while the constraint count reduction achieves 99.7\%. CPLEX shows excellent performance for subproblems with length values exceeding the known optimal. However, performance becomes challenging for shorter length values, where CPLEX frequently fails to achieve bound convergence and becomes stuck in the search process. This work provides a stepping stone for leveraging existing stable set algorithms in strip packing and opens new research directions for both exact and heuristic approaches. Key findings suggest that strong primary heuristics accelerate convergence toward the optimal board length, while the computational bottleneck for proving optimality lies in subproblems with length values immediately below the optimum (optimal length - 1).

Questo lavoro propone un nuovo modello di programmazione mista intera (MIP) per il problema dello strip packing, ottenuto attraverso la sua decomposizione in una molteplicità di sottoproblemi noti come problemi del massimo insieme stabile. L’articolo affronta una lacuna riconosciuta nella letteratura: sebbene siano frequenti i riferimenti alla potenziale connessione tra strip packing e problemi di massimo insieme stabile, non è mai stata sviluppata un’implementazione completa di tale approccio. L’approccio proposto è valutato mediante un dataset consolidato, utilizzato nelle più recenti ricerche allo stato dell’arte, comprendente 81 istanze di benchmark. La metodologia si concentra principalmente sulla fase di preprocessing delle istanze, in cui viene costruito un modello di grafo di conflitto e sono applicate tecniche di riformulazione finalizzate a ridurre la dimensione del modello prima della risoluzione. Durante la costruzione del grafo, i No-Fit Polygons vengono generati tramite somme di Minkowski; successivamente, il grafo di conflitto è riformulato attraverso una copertura di clique mediante l’euristica avanzata MAX1-EK. L’analisi è condotta con CPLEX, considerando valori di lunghezza della tavola prossimi a quelli ottimali noti. I risultati preliminari con CPLEX mostrano una forte convergenza dei limiti anche senza la riformulazione tramite copertura di clique. Con quest’ultima, la riduzione media della dimensione della matrice dei coefficienti raggiunge il 98% (KB), mentre la riduzione del numero di vincoli arriva al 99,7%. CPLEX evidenzia prestazioni eccellenti nei sottoproblemi con valori di lunghezza superiori all’ottimo noto; tuttavia, la performance diviene critica per valori inferiori, nei quali CPLEX spesso non riesce a raggiungere la convergenza dei limiti, rimanendo intrappolato nel processo di ricerca. Questo lavoro costituisce un punto di partenza per l’impiego di algoritmi già esistenti per l’insieme stabile nel contesto dello strip packing e apre nuove direzioni di ricerca sia per approcci esatti sia per quelli euristici. I risultati principali indicano che robuste euristiche primarie favoriscono una più rapida convergenza verso la lunghezza ottimale dello strip, mentre il principale collo di bottiglia computazionale per la dimostrazione di ottimalità risiede nei sottoproblemi con valori di lunghezza immediatamente inferiori all’ottimo (ottimo − 1).