@techreport{TR-IC-PFG-16-09,
   number = {IC-PFG-16-09},
   author   =  {Fabio  Yudi  {Murakami}  e  Rafael  Crivellari  Saliba 
                   {Schouery}},
   title  =  {{Heurísticas  para  o  Problema de Precificação Livre de
                   Inveja}},
   month = {December},
   year = {2016},
   institution = {Institute of Computing, University of Campinas},
   note = {In Portuguese, 21 pages.
    \par\selectlanguage{brazil}\textbf{Resumo}
       Problemas  de  precificação visam determinar o preço de itens a
       serem vendidos com o objetivo de maximizar o lucro do vendedor.
       Neste  trabalho propomos uma nova heurística para o problema de
       precificação  livre  de  inveja  com  demanda  unitária.  Nesse 
       problema  temos como entrada os valores que os consumidores dão
       para  os itens, e como saída uma precificação, isto é, um preço
       para  cada item, bem como a alocação de itens à consumidores. A
       metaheurística   utilizada   foi  o  \textit{Biased  Random-Key 
       Genetic  Algorithm}  (BRKGA)  que é um algoritmo genético. Além
       disso,  duas  heurísticas  previamente definidas na literatura,
       \textit{Equal  Price}  e  \textit{Maximum  Reservation  Price}, 
       foram  utilizadas  para  gerar  soluções  a serem injetadas nas
       populações   iniciais   do   algoritmo.   A  decodificação  foi 
       aprimorada  utilizando  uma rotina chamada \textit{Improvement}
       que melhora o \textit{fitness} de cada cromossomo. Ela faz isso
       encontrando  os caminhos mínimos num grafo auxiliar. Esse grafo
       é  construído  com  base na alocação encontrada a partir de uma
       precificação.  De modo geral, o BRKGA conseguiu bons resultados
       em termos de qualidade das soluções e muitas vezes foi melhor e
       em outras ficou muito perto dos algoritmos da literatura, sendo
       melhor  em  aproximadamente  65\%  das  instâncias  testadas  e 
       ficando  a  pelo  menos  97\%  do  melhor  valor nas instâncias
       restantes.  Ele peca em relação ao tempo de execução, porém com
       alguns  ajustes  e  pequenas  otimizações foi possível melhorar
       tais tempos.
  }
}