Formulações para o Problema da Compra Mínima
Abstract
We consider the Min-Buying Problem, where 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. For this, the seller must define prices pi for each i ∈ I in order to maximize his profit considering that each buyer b will buy, if any, the most unexpensive item among those that pi ≤ vib. In this paper, we present and compare two integer linear programming formulations for such a problem.
References
Aggarwal, G., Feder, T., Motwani, R., and Zhu, A. (2004). Algorithms for multi-product pricing. In International Colloquium on Automata, Languages, and Programming, pages 72–83. Springer.
Briest, P. and Krysta, P. (2007). Buying cheap is expensive: Hardness of non-parametric multi-product pricing. In SODA, volume 7, pages 716–725. Citeseer.
Fernandes, C. G., Ferreira, C. E., Franco, A. J., and Schouery, R. C. (2016). The envy-free pricing problem, unit-demand markets and connections with the network pricing problem. Discrete Optimization, 22:141–161.
Heilporn, G., Labbé, M., Marcotte, P., and Savard, G. (2010). A polyhedral study of the network pricing problem with connected toll arcs. Networks: An International Journal, 55(3):234–246.
Myklebust, T. G., Sharpe, M., and Tunçel, L. (2016). Efficient heuristic algorithms for maximum utility product pricing problems. Computers & Operations Research, 69:25–39.
Rusmevichientong, P., Van Roy, B., and Glynn, P. W. (2006). A nonparametric approach to multiproduct pricing. Operations Research, 54(1):82–98.
Shioda, R., Tunçel, L., and Myklebust, T. G. (2011). Maximum utility product pricing models and algorithms based on reservation price. Computational Optimization and Applications, 48(2):157–198.
Briest, P. and Krysta, P. (2007). Buying cheap is expensive: Hardness of non-parametric multi-product pricing. In SODA, volume 7, pages 716–725. Citeseer.
Fernandes, C. G., Ferreira, C. E., Franco, A. J., and Schouery, R. C. (2016). The envy-free pricing problem, unit-demand markets and connections with the network pricing problem. Discrete Optimization, 22:141–161.
Heilporn, G., Labbé, M., Marcotte, P., and Savard, G. (2010). A polyhedral study of the network pricing problem with connected toll arcs. Networks: An International Journal, 55(3):234–246.
Myklebust, T. G., Sharpe, M., and Tunçel, L. (2016). Efficient heuristic algorithms for maximum utility product pricing problems. Computers & Operations Research, 69:25–39.
Rusmevichientong, P., Van Roy, B., and Glynn, P. W. (2006). A nonparametric approach to multiproduct pricing. Operations Research, 54(1):82–98.
Shioda, R., Tunçel, L., and Myklebust, T. G. (2011). Maximum utility product pricing models and algorithms based on reservation price. Computational Optimization and Applications, 48(2):157–198.
Published
2023-08-06
How to Cite
ULIANA, Sandro H. C.; SCHOUERY, Rafael C. S..
Formulações para o Problema da Compra Mínima. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 8. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 150-154.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2023.230556.
