Analisi Sperimentale dell'Algoritmo Horowitz-Sahni per il Problema dello Zaino con Vincoli di Cardinalità

This thesis investigates the knapsack problem in the 0/1 and bounded variants, with a focus on a bounded formulation including a cardinality constraint applied to a selected subset of items. The goal is to design and evaluate an exact solver based on a Horowitz–Sahni Branch-and-Bound approach, using a fractional-relaxation upper bound to drive pruning and a best-bound search strategy. The solver is implemented in C++ with attention to numerical issues (double precision and tolerances) and robustness on large instances, including memory-exception handling and a configurable timeout mechanism that, when triggered, returns a primal bound, an upper bound, and the corresponding optimality gap. An experimental campaign is carried out on systematically generated instance classes, varying the number of items, the maximum cardinality, and the percentage of constrained items. Results show that for sufficiently high cardinality the constraint often becomes non-binding in terms of optimal value, while it may still affect running time depending on instance size. Solution correctness is validated against a reference model solved with AMPL; for instances with thousands of items, practical limitations related to time and memory also arise and are discussed.

In questa tesi viene studiato il problema dello zaino nelle varianti 0/1 e bounded, con particolare attenzione alla versione bounded con vincolo di cardinalità applicato a un sottoinsieme di oggetti. L’obiettivo è progettare e valutare un risolutore esatto basato su Branch-and-Bound di Horowitz–Sahni, adottando un upper bound ottenuto tramite rilassamento frazionario per guidare la potatura e una strategia di visita best-bound. L’implementazione è stata realizzata in C++ con gestione di aspetti numerici (uso di double e tolleranze), e con accorgimenti per la robustezza su istanze grandi, introducendo la gestione di eccezioni di memoria e un meccanismo di timeout che, in caso di interruzione, restituisce primal bound, upper bound e gap di ottimalità. La sperimentazione è condotta su classi di istanze generate in modo controllato, variando numero di oggetti, cardinalità massima e percentuale di oggetti soggetti al vincolo. I risultati mostrano che, per cardinalità elevate, il vincolo tende a non influire sul valore ottimo, mentre può incidere sui tempi di esecuzione in funzione della dimensione dell’istanza. La correttezza dei risultati è validata tramite confronto con un modello di riferimento risolto in AMPL; su istanze dell’ordine delle migliaia emergono inoltre limiti pratici legati a tempo e memoria, che vengono discussi nell’analisi dei risultati.