Pricing-based primal and dual bounds for selected packing problems

Several optimization problems ask for finding solutions which define packing of elements while maximizing (minimizing) the objective function. Solving some of these problems can be extremely challenging due to their innate complexity and the corresponding integer formulations can be not suitable to be solved on instances of relevant size. Thus, clever techniques must be devised to achieve good primal and dual bounds. A valid way is to rely on pricing-based algorithms, in which solution components are generated by calling and solving appropriate optimization subproblems. Two main exponents of this group are the delayed column generation (CG) procedure and the sequential value correction (SVC) heuristic: the former provides a dual bound based on the generation of implicit columns by examining the shadow prices of hidden variables; the latter explores the primal solution space by following the dynamic of approximate prices. In this thesis we focus on the application of SVC and CG techniques to find primal and dual bounds for selected packing problems. In particular, we study problems belonging to the family of cutting and packing, where the classical BIN PACKING and CUTTING STOCK are enriched with features derived from the real manufacturing environment. Moreover, the MAXIMUM γ-QUASI-CLIQUE problem is taken into account, in which we seek for the induced γ-quasi-clique with the maximum number of vertices. Computational results are given to assess the performance of the implemented algorithms.

Un ampio insieme di problemi di ottimizzazione richiedono l’individuazione di soluzioni che definiscono un packing di elementi, al fine di massimizzare (minimizzare) la relativa funzione obiettivo. Risolvere all’ottimo alcuni di questi problemi può essere estremamente oneroso a causa della loro complessità innata e le corrispondenti formulazioni intere possono non essere appropriate per approcciare istanze di dimensioni rilevanti. Pertanto, il calcolo di bound primali e duali qualitativamente validi necessita della definizione di tecniche ingegnose ed efficaci. Una metodologia valevole consiste nell’impiego di algoritmi basati su pricing, in cui le componenti delle soluzioni sono generate tramite la risoluzione di sottoproblemi di ottimizzazione specifici. Due principali esponenti di questa famiglia sono la procedura delayed column generation (CG) e l’euristica sequential value correction (SVC): la prima fornisce un bound duale basato sulla generazione delle colonne implicite tramite la valutazione dei prezzi ombra di variabili nascoste; la seconda esplora lo spazio delle soluzioni primali seguendo la dinamica di prezzi approssimati. In questa tesi ci concentriamo sull’applicazione di tecniche SVC e CG per l’individuazione di bound primali e duali per problemi di packing selezionati. In particolare, studiamo i problemi appartenenti alla famiglia del cutting e packing, dove i ben noti BIN PACKING e CUTTING STOCK sono arricchiti con caratteristiche derivanti dagli ambienti produttivi reali. Inoltre, studiamo il problema della MAXIMUM γ-QUASI-CLIQUE in cui si cerca la γ-quasi-clique indotta che massimizzi il numero di vertici selezionati. Risultati computazionali sono presentati al fine di validare le performance degli algoritmi implementati.