Biased Random-key Genetic Algorithms For The Winner Determination Problem In Combinatorial Auctions.

Abstract In this paper, we address the problem of picking a subset of bids in a general combinatorial auction so as to maximize the overall profit using the first-price model. This winner determination problem assumes that a single bidding round is held to determine both the winners and prices to be paid. We introduce six variants of biased random-key genetic algorithms for this problem. Three of them use a novel initialization technique that makes use of solutions of intermediate linear programming relaxations of an exact mixed integer-linear programming model as initial chromosomes of the population. An experimental evaluation compares the effectiveness of the proposed algorithms with the standard mixed linear integer programming formulation, a specialized exact algorithm, and the best-performing heuristics proposed for this problem. The proposed algorithms are competitive and offer strong results, mainly for large-scale auctions.

Explosive Synchronization With Partial Degree-frequency Correlation.

Networks of Kuramoto oscillators with a positive correlation between the oscillators frequencies and the degree of their corresponding vertices exhibit so-called explosive synchronization behavior, which is now under intensive investigation. Here we study and discuss explosive synchronization in a situation that has not yet been considered, namely when only a part, typically a small part, of the vertices is subjected to a degree-frequency correlation. Our results show that in order to have explosive synchronization, it suffices to have degree-frequency correlations only for the hubs, the vertices with the highest degrees. Moreover, we show that a partial degree-frequency correlation does not only promotes but also allows explosive synchronization to happen in networks for which a full degree-frequency correlation would not allow it. We perform a mean-field analysis and our conclusions were corroborated by exhaustive numerical experiments for synthetic networks and also for the undirected and unweighed version of a typical benchmark biological network, namely the neural network of the worm Caenorhabditis elegans. The latter is an explicit example where partial degree-frequency correlation leads to explosive synchronization with hysteresis, in contrast with the fully correlated case, for which no explosive synchronization is observed.