Formulações para o Problema da Compra Mínima
Resumo
Consideramos o Problema da Compra Mínima, em que um vendedor deseja vender um conjunto I de itens para um conjunto B de compradores. Cada comprador b está disposto a pagar até vib pelo item i. O vendedor deve então definir preços pi para cada i ∈ I de forma a maximizar o seu lucro considerando que cada comprador b comprará (se existir) o item mais barato dentre aqueles que pi ≤ vib. Neste resumo, apresentamos e comparamos duas formulações de programação linear inteira para tal problema.
Referências
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.
Publicado
06/08/2023
Como Citar
ULIANA, Sandro H. C.; SCHOUERY, Rafael C. S..
Formulações para o Problema da Compra Mínima. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (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.
