Esperimenti computazionali su formulazioni non-lineari del problema di bin-packing

This dissertation is the result of an internship period spent from April 2018 to July 2018 at the FEUP(Faculdade de Engenharia da Universidade do Porto), in Porto(Portugal). The domain of the work carried on is Operation Research. The thesis concern about the analyzing of the Linear and exact formulation of the bin packing problem, the obtaining of the model in a mathematical programming language for performing computational experiments on given set of instances, the binarization of the variable and the use of non linear constraint to remove the binary bond. The nal purpose is to obtain continuous formulation without integer variable, to compute and compare with the achieved solution, in terms of time and optimality.

La tesi è frutto del periodo di tirocinio svolto all' estero tra aprile e luglio 2018, svolto alla facoltà FEUP (Faculdade de Engenharia da Universidade do Porto) a Porto in Portogallo, grazie al progetto europeo Erasmus+Traineeship. Il problema che si è affrontato durante il periodo e in tutto il documento è quello del problema di bin-packing espansione del problema dello zaino e caso specifico del problema di Cutting Stock, in particolare l'obiettivo, dato un insieme di elementi aventi un certo valore di peso o ingombro a una dimensione e un insieme di contenitori con un valore di capacità massima, è quello di ridurre il numero di contenitori utilizzati per impacchettare tutti gli elementi. Una volta analizzati i modelli a disposizione nella letteratura, si è sviluppato attraverso la programmazione matematica quelli che avevano una formulazione esatta (i modelli che restituivano il valore ottimo una volta risolti) e si sono analizzati i risultati ottenuti in termini di esattezza e tempo di risoluzione. L'obiettivo a partire dall' analisi iniziale è stato quello di realizzare modelli matematici continui del problema di bin-packing e osservare quali erano i risultati e confrontarli con quelli ottenuti dagli esperimenti fatti. Per raggiungere l'obiettivo desiderato si sono dovute modificare in primo luogo le caratteristiche delle variabili passando da intere a binarie, in secondo luogo si sono potuti eliminare aggiungendo dei vincoli che costringono la variabile interessata ad assumere valori tra 0 e 1, attraverso l'uguaglianza x = x^2 rendendo il problema Non lineare a causa della moltiplicazioni delle variabili. Attraverso i modelli ottenuti si sono infine svolti degli esperimenti computazionali su solutori non lineari per osservare con quale efficienza ed eficacia gli stessi operano e i modelli si comportano.