21August2026
10:00 Master's Defense Room 85 of IC2
Topic on
Exact Combinatorial Algorithms for Packing and Knapsack Problems
Student
Renan Fernando Franco da Silva
Advisor / Teacher
Rafael Crivellari Saliba Schouery
Brief summary
This dissertation investigates exact algorithms for classical combinatorial optimization problems related to cutting, packing, and knapsack. The focus is on combinatorial methods that directly exploit the structure of the problems and do not depend on general integer or linear programming solvers. The first study develops an exact solver for the Knapsack and Bounded Knapsack Problems, based on core dynamic programming and combined with reductions, dominance rules, surrogate relaxations, and primal heuristics. The second study investigates two instance classes introduced in the literature for the Packing and Cutting Stock Problems as hard benchmarks for general exact solvers. The first class satisfies the Integer Round-Up Property (IRUP) and is called Augmented IRUP (AI), while the second does not satisfy this property and is called Augmented Non-IRUP (ANI). This second study shows that the particular structure of these classes can be exploited to obtain polynomial algorithms for AI instances and pseudopolynomial algorithms for ANI instances, which can also be extended to the Skiving Stock Problem. The third study proposes a branch-and-bound combinatorial algorithm for the Packing and Stock Cutting Problems, combining an arc-flow satisfiability model, combinatorial reductions, flow relaxations, and primal heuristics into an independent exact solver. Taken together, these results show that the structural properties of knapsack, cutting, and packing problems can be exploited to obtain theoretically grounded, computationally competitive, and general mathematical programming-independent exact algorithms.
Examination Board
Headlines:
| Rafael Crivellari Saliba Schouery | IC / UNICAMP |
| José Manuel Vasconcelos Valério de Carvalho | UMinho/Portugal |
| David Pisinger | DTU/Denmark |
Substitutes:
| Flávio Keidi Miyazawa | IC / UNICAMP |
| Teobaldo Leite Bulhões Júnior | DCC/UFPB |