25 Nov 2024
10:00 Master's Defense Room 53 of IC2
Theme
Exact Algorithms and Heuristics for Positioning Banner Advertisements
Student
Jorge Menezes dos Santos
Advisor / Teacher
Rafael Crivellari Saliba Schouery
Brief summary
In this work, we propose and address a problem of advertisement placement in digital banners, called MAXSPACE-P. MAXSPACE-P is a variant of the NP-Hard combinatorial optimization problem, MAXSPACE. Its key idea is to value the attraction factor conferred by advertisements that appear first on a web page, at the top of a digital banner. To address the problem, we developed three mixed-integer linear programming formulations, together with some valid inequalities and preprocessing routines. We also developed two heuristics: one based on Tabu Search and the other based on Column Generation. We evaluated the performance of the proposed algorithms with a set of instances from the literature. In our computational experiments, the mathematical formulation that stood out the most solved about 38% of the small instances, presenting an average final gap of 0,09%, this being the only type of instance in which they could be executed due to the requirement of high computational resources to execute larger instances. From the point of view of heuristics, the column generation-based heuristic was the second best algorithm among the five proposed for small instances, behind only the Positional Formulation. For medium and large instances, Tabu Search obtained the best results and proved to be a good alternative, given the difficulty of applying mathematical formulations to large instances.
Examination Board
Headlines:
| Rafael Crivellari Saliba Schouery | IC / UNICAMP |
| Pedro Henrique Del Bianco Hokama | IMC / UNIFEI |
| Santiago Valdés Ravelo | IC / UNICAMP |
Substitutes:
| Flávio Keidi Miyazawa | IC / UNICAMP |
| Uéverton dos Santos Souza | IC / UFF |