Constraint-guided evolutionary algorithm for solving the winner determination problem

Combinatorial Auctions (CAs) allow the participants to bid on a bundle of items and can result in more cost-effective deals than traditional auctions if the goods are complementary. However, solving the Winner Determination Problem (WDP) in CAs is an NP-hard problem. Since Evolutionary Algorithms (E...

Full description

Saved in:
Bibliographic Details
Published in:Journal of heuristics 2021-12, Vol.27 (6), p.1111-1150
Main Authors: Kazama, Fernanda Nakano, Araujo, Aluizio Fausto Ribeiro, de Barros Correia, Paulo, Guerrero-Peña, Elaine
Format: Article
Language:English
Subjects:
Artificial Intelligence
Auctioning
Calculus of Variations and Optimal Control
Optimization
Combinatorial analysis
Evolutionary algorithms
Genetic algorithms
Management Science
Mathematics
Mathematics and Statistics
Operations Research
Operations Research/Decision Theory
Polynomials
Transmission lines
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Combinatorial Auctions (CAs) allow the participants to bid on a bundle of items and can result in more cost-effective deals than traditional auctions if the goods are complementary. However, solving the Winner Determination Problem (WDP) in CAs is an NP-hard problem. Since Evolutionary Algorithms (EAs) can find good solutions in polynomial time within a huge search space, the use of EAs has become quite suitable for solving this type of problem. In this paper, we introduce a new Constraint-Guided Evolutionary Algorithm (CGEA) for the WDP. It employs a penalty component to represent each constraint in the fitness function and introduces new variation operators that consider each package value and each type of violated constraint to induce the generation of feasible solutions. CGEA also presents a survivor selection operator that maintains the exploration versus exploitation balance in the evolutionary process. The performance of CGEA is compared with that of three other evolutionary algorithms to solve a WDP in a Combinatorial Reverse Auction (CRA) of electricity generation and transmission line assets. Each of the algorithms compared employs different methods to deal with constraints. They are tested and compared on several problem instances. The results show that CGEA is competitive and results in better performance in most cases.
ISSN:1381-1231
1572-9397
DOI:10.1007/s10732-021-09485-x