26 February 2025
14:00 Master's Defense IC3 Auditorium
Topic
Integer Linear Programming Formulations for the Minimum Purchase Problem
Student
Sandro Henrique Uliana Catabriga
Advisor / Teacher
Rafael Crivellari Saliba Schouery
Brief summary
Pricing problems are problems within combinatorial optimization that involve determining the prices of a seller's products so that their revenue, resulting from the sale of the items, is maximum. Among the existing pricing problems, we consider the Minimum Purchase Problem, in which a seller wants to sell a set I of items to a set B of buyers. Each buyer b is willing to pay up to vib for item i. The seller must then set prices pi for each i ∈ I in order to maximize their revenue, considering that each buyer b will buy (if any) the cheapest item among those for which pi ≤ vib. In this work, we propose four Linear Programming formulations for the Minimum Purchase Problem, one of which is Integer Linear Programming (ILP) and three of Mixed Integer Linear Programming (MILP). We explored two main approaches to solving the Minimum Purchase Problem, one by determining the prices of items and the prices paid by buyers, and then indirectly determining the allocation of items to buyers, and another by determining the allocation directly. Valid inequalities were introduced in 3 models to create strengthened models, aiming to reduce the execution time and increase the number of solved instances. A theorem was presented, demonstrating that it is sufficient to consider a subset of prices for each item, corresponding to the valuations offered to it. With this, it was possible to reduce the number of variables and constraints of the models. We evaluated the formulations using three classes of sparse instances, Characteristics, Neighborhood and Popularity, which simulate different practical scenarios of consumer preferences, and also dense, or complete, instances, where every buyer offers a valuation for every item. The experiments showed that valid inequalities improved the results of 2 models. The strengthened PLI model achieved the best result for sparse instances, while a PLIM model achieved the best result for dense instances. One of the PLIM models achieved the best balance among all models, standing out as the best PLIM model for sparse instances and solving all dense instances in a good time.
Examination Board
Headlines:
| Rafael Crivellari Saliba Schouery | IC / UNICAMP |
| Ruben Interian Kovaliova | IC / UNICAMP |
| Mauro Henrique Mulati | DIN/UEM |
Substitutes:
| Santiago Valdés Ravelo | IC / UNICAMP |
| Pedro Henrique Del Bianco Hokama | IMC / UNIFEI |