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.

Fisionomia e organização da vegetação do carrasco no planalto da Ibiapaba, estado do Ceará

Is the carrasco on the Ibiapaba plateau a unique plant formation? To answer this question the vertical height (except of climbers) and the stem basal diameter (from 3cm on) of woody plants were measured, and soil extracts (0-50 and 50-100cm depth) were taken from 100 random plots (10x10m) at Jaburuna (3º54'34S and 40º59'24W, altitudes near 830m), municipality of Ubajara, Ceará State. Data on climate, soil, diameter height, density, basal area, and physiognomy were compared with those surveyed by other researchers from the carrasco, caatinga, and cerrado in Northeastern Brazil. The carrasco occurs under an annual rainfall of between 668 and 1,289mm and temperatures from 22 to 24ºC, on alic Quartz Sand soils, at altitudes between 700 and 900m: it has a larger density and a smaller basal area than the caatinga and the cerrado, small and similar diameters, and an average vertical height between 3,7 and 5,4m. It differs from the caatinga, cerrado (and cerradão) and secondary forest in many items of lhe ecotope, organization and physiognomy, thus being a unique plain formation, which can be characterized as a deciduous, high, closed, and unistratified shrubland intermingled by lianas, with an irregular canopy and sparse, emergent trees.