Regras de empacotamento para leilão combinatório [recurso eletrônico] : aplicação no setor elétrico brasileiro
Rafael Esteves Albieri
DISSERTAÇÃO
Português
T/UNICAMP AL14r
[Packing rules for combinatorial auction]
Campinas, SP : [s.n.], 2021.
1 recurso online (109 p.) : il., digital, arquivo PDF.
Orientador: Paulo de Barros Correia
Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecânica
Resumo: Os leilões combinatórios permitem que os participantes explorem as sinergias de itens complementares sem que incorram no risco de vencer apenas parte dos itens desejados. Por se permitir a realização de lances em pacotes de itens é necessário resolver o Problema de Identificação do Vencedor...
Ver mais
Resumo: Os leilões combinatórios permitem que os participantes explorem as sinergias de itens complementares sem que incorram no risco de vencer apenas parte dos itens desejados. Por se permitir a realização de lances em pacotes de itens é necessário resolver o Problema de Identificação do Vencedor (PIV), que consiste em identificar os melhores lances vencedores do leilão sem que um mesmo empreendimento seja atribuído em mais de um pacote vencedor e, para leilões reversos, que a demanda do leilão seja atendida. O PIV é um problema combinatório classificado como NP-hard, tratável apenas para instâncias pequenas do problema. O desafio para implementação do Leilão Combinatório (LC) é garantir que o PIV resultante seja uma instância tratável. A aplicação de regras de empacotamento visa atingir uma instância tratável, restringindo os pacotes permitidos do leilão e, consequentemente, o tamanho do problema resultante. Este trabalho enumera algumas das regras de empacotamento propostas para LC padrão e realiza experimentos com aplicações dessas regras em Leilão Reverso Combinatório (LRC). Nos experimentos são testadas duas das regras de empacotamento identificadas como mais promissoras para aplicação no setor elétrico, e comparadas com a regra que permite todos os pacotes possíveis. Os experimentos são realizados em dois tipos de leilão: Leilões de Geração e Leilão de Transmissão. Esses leilões possuem dois tipos de restrição para o atendimento da demanda do leilão: atendimento de uma capacidade de geração e uma restrição de particionamento, com a possibilidade da inclusão de algumas restrições específicas. Os tempos de formulação e de resolução dos PIVs são avaliados e apresentam um crescimento polinomial em relação ao número de pacotes permitidos. As regras de empacotamento testadas podem ser aplicadas em um LRC para permitir uma quantidade maior de itens leiloados, uma vez que sem a aplicação destas regras o aumento exponencial do número de pacotes permitidos rapidamente torna o PIV intratável
Ver menos
Abstract: Combinatorial auctions allow participants to exploit synergies of complementary items without the risk of winning only part of the desired items. As it allows bidding on packages of items, it is necessary to solve the Winner Determination Problem (WDP), which consists of identifying the...
Ver mais
Abstract: Combinatorial auctions allow participants to exploit synergies of complementary items without the risk of winning only part of the desired items. As it allows bidding on packages of items, it is necessary to solve the Winner Determination Problem (WDP), which consists of identifying the best winning bids of the auction without the same item being assigned in more than one winning package and, for reverse auctions, that an auction demand is met. The WDP is a combinatorial problem classified as NP-hard and is treatable only for small instances of the problem. The challenge for the implementation of the combinatorial auction is to ensure that the resulting WDP is a treatable instance. The application of packing rules aims to reach a treatable instance, restricting the allowed packages of the auction and, consequently, the size of the resulting problem. This work lists some of the packing rules proposed for standard combinatorial auction and performs some experiments with applications of these rules in a reverse combinatorial auction. In the experiments, two packing rules identified as the most promising for application in the electric sector are tested and compared to the rule that allows all possible packages. These experiments are carried out in two auction formats: Generation Auctions and Transmission Auction. These auctions have two types of constraints to meet the auction’s demand: meeting a generation capacity and partitioning constraints, with the possibility of including some specific constraints. The elapsed times to formulate and solve the WDPs are evaluated and present polynomial growth with the number of allowed packages. The tested packaging rules can be applied to a reverse combinatorial auction to allow a larger quantity of items to be auctioned since without the application of these rules the exponential increase in the number of allowed packages quickly makes the WDP intractable
Ver menos
Requisitos do sistema: Software para leitura de arquivo em PDF
Correia, Paulo de Barros, 1954-
Orientador
Walter, Igor Alexandre
Avaliador
Regras de empacotamento para leilão combinatório [recurso eletrônico] : aplicação no setor elétrico brasileiro
Rafael Esteves Albieri
Regras de empacotamento para leilão combinatório [recurso eletrônico] : aplicação no setor elétrico brasileiro
Rafael Esteves Albieri