Combinatorial auction : study of computable approaches to the brazilian electric sector

Leilões de novos empreendimentos de energia envolvem o compromisso de construí-los e o direito de explorá-los por meio de contratos de outorga. O leiloeiro, cujo objetivo é minimizar o pagamento pela energia contratada, buscando a redução de seu preço para os consumidores finais, fornece o direito de outorga da usina para o vencedor. O licitante é um investidor, e.g., uma empresa de geração que procura maximizar seu benefício com a venda de energia proveniente do empreendimento. Quando a natureza desses empreendimentos é complementar, torna-se possível proporcionar maiores benefícios aos licitantes, e maior eficiência ao leilão, caso sejam negociados em conjunto. Atualmente, o projeto de leilão instituído é composto por uma abordagem híbrida, sequencial e simultânea, que não permite a extração das sinergias entre empreendimentos. Esta tese examina duas metodologias híbridas de leilões reversos, considerando-se o ponto de vista do leiloeiro. O primeiro modelo, centralizado, é composto por duas fases: uma simultânea de lance aberto e outra combinatória de lance fechado. A fase simultânea incentiva a revelação do preço da energia, enquanto a fase combinatória oferece oportunidade aos licitantes de submeterem ofertas mais agressivas através de pacotes de empreendimentos complementares. O modelo centralizado é formulado como um problema de otimização inteiro e combinatório. A função-objetivo consiste em minimizar o pagamento, isso é, energia multiplicada pelo preço (lance) para todas as usinas. A estratégia de solução identifica os vencedores, resolvendo um problema de set-packing restrito. A segunda metodologia utiliza uma abordagem, também, em duas fases. A primeira é um projeto simultâneo de lance aberto, e a segunda fase um projeto combinatório descentralizado. Nesse modelo, a dificuldade do problema aumenta progressivamente à medida que os pacotes são ofertados. A dificuldade da alocação é distribuída entre os licitantes e, por isso, o leiloeiro não necessita resolver um problema de otimização. As metodologias propostas são aplicadas aos leilões de energia nova para o setor elétrico brasileiro. Os resultados mostram que a utilização de ambas as metodologias resolvem o problema de alocação com um tempo computacional aceitável.Auctions for new power plants involve a commitment of constructing and the right of exploring them through power sales contracts. The auctioneer -- whose objective is to minimize the payment for the contracted energy, seeking to reduce prices for consumers -- provides the power plant's right for the winner. The bidder is an investor, for example, a generation company, which aims to maximize benefits of energy sales. When the power plant's nature is complementary, it is possible to provide more benefits to bidders and greater efficiency to the auction if these plants were traded together. Currently, the instituted auction design consists of a hybrid approach -- sequential and simultaneous -- which does not allow the extraction of synergies among plants. This thesis examines two hybrid methods of reverse auctions from the auctioneer's view point. The first model, centralized, consists of two phases: a simultaneous open bid and a combinatorial sealed bid. The simultaneous phase encourages the energy prices revelation. The combinatorial phase allows aggressive bidders to acquire bundles of complementary plants. The centralized model is formulated as an integer and combinatorial optimization problem. The objective function consists of minimizing the payment, that is, energy multiplied by the price (bid) for all plants. The solution strategy identifies the winners solving a restricted set-packing problem. The second method also uses a two phase approach. The first phase is a simultaneous open bid design and the second phase is a decentralized combinatorial design. In this model, the problem difficulty increases gradually. The allocation difficulty is distributed among the bidders; therefore, the auctioneer does not need to solve an optimization problem. The proposed methodologies are applied to new energy auctions on Brazilian electrical energy sector. The results show the use of both methods solving the problem of allocation with an acceptable computational time