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.

GRASP with Hybrid Path Relinking for Bi-Objective Winner Determination in Combinatorial Transportation Auctions

The procurement of transportation services via large-scale combinatorial auctions involves a couple of complex decisions whose outcome highly influences the performance of the tender process. This paper examines the shipper's task of selecting a subset of the submitted bids which efficiently trades off total procurement cost against expected carrier performance. To solve this bi-objective winner determination problem, we propose a Pareto-based greedy randomized adaptive search procedure (GRASP). As a post-optimizer we use a path relinking procedure which is hybridized with branch-and-bound. Several variants of this algorithm are evaluated by means of artificial test instances which comply with important real-world characteristics. The two best variants prove superior to a previously published Pareto-based evolutionary algorithm.

Leilões combinados

Mestrado em Controlo de Gestão e dos Negócios

Two protocols without periodicity for the global and preemptive scheduling problem of multi-mode real-time systems upon multiprocessor Platforms

We consider the problem of scheduling a multi-mode real-time system upon identical multiprocessor platforms. Since it is a multi-mode system, the system can change from one mode to another such that the current task set is replaced with a new task set. Ensuring that deadlines are met requires not only that a schedulability test is performed on tasks in each mode but also that (i) a protocol for transitioning from one mode to another is specified and (ii) a schedulability test for each transition is performed. We propose two protocols which ensure that all the expected requirements are met during every transition between every pair of operating modes of the system. Moreover, we prove the correctness of our proposed algorithms by extending the theory about the makespan determination problem.

Tavoitevarastoarvojen määrittäminen uusille tuotteille - case: päivittäistavarakaupan yritys

Tämän tutkielman tarkoituksena oli löytää keinoja uusien tuotteiden tavoitevarastoarvojen määrittämisen helpottamiseksi case-yrityksessä. Ongelma on seurausta siitä, ettei uusille tuotteille ole saatavissa kysyntädataa. Oikeelliset tavoitevarastoarvot on tärkeitä case-yritykselle hävikin minimoimisen ja erityisesti asiakastyytyväisyyden vuoksi. Tutkittavaa aihetta lähestyttiin päivittäistavarakaupan strategisten menestystekijöiden sekä varastonhallinnan kautta. Teoriaosuuden pohjalta toteutettiin empiirinen osio, jossa etsittiin case-yrityksen kahden tuoteryhmän kysyntää selittäviä tekijöitä paneeliregression avulla. Ensin kuitenkin tutkittiin tuoteryhmien yleistä kysynnän rakennetta erilaisten kysyntäkuvaajien sekä korrelaatiomatriisien avulla. Tavoitevarastoarvoon eniten vaikuttava tekijä on kysyntä. Brändi ja hinta muodostuivat puolestaan vahvimmiksi kysyntää määrittäviksi muuttujiksi. Kysyntää arvioitaessa muut sitä nostavat muuttujat tulee aina miettiä tapauskohtaisesti. Mehukeitoilla kysyntää nostivat eniten vahva brändi ja suuri pakkauskoko. Juustoraasteilla puolestaan alhainen hinta ja pieni pakkauskoko olivat keskeisimmät myyntiin vaikuttavat tekijät. Tuoteryhmien muut kysyntää nostavat ominaisuudet olivat samoja, kuin tuoteryhmän suosituimmilla tuotteilla.

Efficient computation of current collection in bare electrodynamic tethers in and beyond OML regime

One key issue in the simulation of bare electrodynamic tethers (EDTs) is the accurate and fast computation of the collected current, an ambient dependent operation necessary to determine the Lorentz force for each time step. This paper introduces a novel semianalytical solution that allows researchers to compute the current distribution along the tether efficient and effectively under orbital-motion-limited (OML) and beyond OML conditions, i.e., if tether radius is greater than a certain ambient dependent threshold. The method reduces the original boundary value problem to a couple of nonlinear equations. If certain dimensionless variables are used, the beyond OML effect just makes the tether characteristic length L ∗ larger and it is decoupled from the current determination problem. A validation of the results and a comparison of the performance in terms of the time consumed is provided, with respect to a previous ad hoc solution and a conventional shooting method.

Estimation of the satellite ephemerides of Saturn using optical navigation pictures of Cassini

The goal of this dissertation thesis is the estimation of the Saturnian satellites ephemerides using optical data of Cassini. In the first part we describe the software employed for the reduction of the images showing its main features and the accuracy that can be achieved comparing the results with published astrometry. Afterwards we describe the orbit determination problem (ODP) with particular focus on the weights selection for the estimation process. The third chapter describes the dynamical model used and the sources of potential errors in the residuals. The model have been validated trying to replicate JPL's published ephemerides SAT365, SAT375, SAT389 and SAT409. The final part investigates the residuals and the estimated ephemerides with particular focus on the giant moon Titan, the only in the solar system with an atmosphere other than the Earth. No astrometry have been retrieved in literature of Titan using optical observables, thus this represents one of the first investigations of the giant.

Simulation of optical observables for space missions to small bodies

The navigation of deep space spacecraft requires accurate measurement of the probe’s state and attitude with respect to a body whose ephemerides may not be known with good accuracy. The heliocentric state of the spacecraft is estimated through radiometric techniques (ranging, Doppler, and Delta-DOR), while optical observables can be introduced to improve the uncertainty in the relative position and attitude with respect to the target body. In this study, we analyze how simulated optical observables affect the estimation of parameters in an orbit determination problem, considering the case of the ESA’s Hera mission towards the binary asteroid system composed of Didymos and Dimorphos. To this extent, a shape model and a photometric function are used to create synthetic onboard camera images. Then, using a stereophotoclinometry technique on some of the simulated images, we create a database of maplets that describe the 3D geometry of the surface around a set of landmarks. The matching of maplets with the simulated images provides the optical observables, expressed as pixel coordinates in the camera frame, which are fed to an orbit determination filter to estimate a certain number of solve-for parameters. The noise introduced in the output optical observables by the image processing can be quantified using as a metric the quality of the residuals, which is used to fine-tune the maplet-matching parameters. In particular, the best results are obtained when using small maplets, with high correlation coefficients and occupation factors.

Methane combustion kinetic rate constants determination: an ill-posed inverse problem analysis

Methane combustion was studied by the Westbrook and Dryer model. This well-established simplified mechanism is very useful in combustion science, for computational effort can be notably reduced. In the inversion procedure to be studied, rate constants are obtained from [CO] concentration data. However, when inherent experimental errors in chemical concentrations are considered, an ill-conditioned inverse problem must be solved for which appropriate mathematical algorithms are needed. A recurrent neural network was chosen due to its numerical stability and robustness. The proposed methodology was compared against Simplex and Levenberg-Marquardt, the most used methods for optimization problems.

The winner takes it all? Characteristics of adolescents at-risk/problem gamblers in Switzerland

Background: Gambling has and still entertains people in almost all societies throughout the world. Western societies have faced considerable changes in the amount and accessibility of gambling possibilities during the last decades, and the rates of both adolescent gamblers and problem gamblers have increased significantly. Objective: To determine the characteristics of at-risk and problem adolescent gamblers in Switzerland. Subjects: The study population consisted of 3134 students (1669 females) attending post-mandatory education in 15 randomly chosen centres. Participants were divided into non- (n=2207), non-problematic (n=754) and at-risk/ problematic gamblers (n=176). Methods: Both gambling groups were compared to non-gamblers on socio-demographic measures, substance use and Internet use. Overall, 29.6% had gambled during the past year and 5.6% had gambled in a risky or problematic way. Compared to non-gamblers and after controlling for potential confounders, non-problem gamblers were significantly more likely to be male, apprentices and to misuse alcohol. At-risk/problematic gamblers were additionally more likely to smoke cannabis, to be problematic Internet users and to be non-Swiss than non-gamblers. Conclusion: At-risk and problematic adolescent gambling is associated with other health risk behaviours. Health practitioners should include gambling in the psycho-social screening and preventive counselling of adolescents.

Species determination of Brazilian mammals implicated in the epidemiology of rabies based on the control region of mitochondrial DNA

Identification of animals that are decomposing or have been run over or burnt and cannot be visually identified is a problem in the surveillance and control of infectious diseases. Many of these animals are wild and represent a valuable source of information for epidemiologic research as they may be carriers of an infectious agent. This article discusses the results obtained using a method for identifying mammals genetically by sequencing their mitochondrial DNA control region. Fourteen species were analyzed and identified. These included the main reservoirs and transmitters of rabies virus, namely, canids, chiroptera and primates. The results prove that this method of genetic identification is both efficient and simple and that it can be used in the surveillance of infectious diseases which includes mammals in their epidemiologic cycle, such as rabies.

Determination of pore size distributions by regularization and finite element collocation

The problem of extracting pore size distributions from characterization data is solved here with particular reference to adsorption. The technique developed is based on a finite element collocation discretization of the adsorption integral, with fitting of the isotherm data by least squares using regularization. A rapid and simple technique for ensuring non-negativity of the solutions is also developed which modifies the original solution having some negativity. The technique yields stable and converged solutions, and is implemented in a package RIDFEC. The package is demonstrated to be robust, yielding results which are less sensitive to experimental error than conventional methods, with fitting errors matching the known data error. It is shown that the choice of relative or absolute error norm in the least-squares analysis is best based on the kind of error in the data. (C) 1998 Elsevier Science Ltd. All rights reserved.

Protein sequence threading, the alignment problem, and a two-step strategy

Conventionally, protein structure prediction via threading relies on some nonoptimal method to align a protein sequence to each member of a library of known structures. We show how a score function (force field) can be modified so as to allow the direct application of a dynamic programming algorithm to the problem. This involves an approximation whose damage can be minimized by an optimization process during score function parameter determination. The method is compared to sequence to structure alignments using a more conventional pair-wise score function and the frozen approximation. The new method produces results comparable to the frozen approximation, but is faster and has fewer adjustable parameters. It is also free of memory of the template's original amino acid sequence, and does not suffer from a problem of nonconvergence, which can be shown to occur with the frozen approximation. Alignments generated by the simplified score function can then be ranked using a second score function with the approximations removed. (C) 1999 John Wiley & Sons, Inc.

FURTHER INSIGHTS TOWARD VITAMIN C DETERMINATION AND STABILITY. PROPOSAL OF A NEW QUANTIFICATION METHOD

This work aimed at an evaluation of the classical iodine method for quantification of vitamin C (L-ascorbic acid) in fruit juices, as well as at a search into the stability of this so popular vitamin under different conditions of pH, temperature and light exposition, in addition to a proposal of a new quantification method. Our results point to the persistent reversibility of the blue color of the starch-triiodide complex at the end point when using the classical iodine titration, and the overestimation of the true vitamin concentration in fruit juices. A new quantification method is proposed in order to overcome this problem. Surprising conclusions were obtained regarding the controversial stability of L-ascorbic acid toward atmospheric oxygen, at low pH, even in fruit juice and at room temperature, showing that the major problem concerned with aging of fruit juices is proliferation of microorganisms rather than expontaneous oxidation of L-ascorbic acid.

Gravitational waves : a 100-year tool applied to the dark energy problem

Recent observations from type Ia Supernovae and from cosmic microwave background (CMB) anisotropies have revealed that most of the matter of the Universe interacts in a repulsive manner, composing the so-called dark energy constituent of the Universe. Determining the properties of dark energy is one of the most important tasks of modern cosmology and this is the main motivation for this work. The analysis of cosmic gravitational waves (GW) represents, besides the CMB temperature and polarization anisotropies, an additional approach in the determination of parameters that may constrain the dark energy models and their consistence. In recent work, a generalized Chaplygin gas model was considered in a flat universe and the corresponding spectrum of gravitational waves was obtained. In the present work we have added a massless gas component to that model and the new spectrum has been compared to the previous one. The Chaplygin gas is also used to simulate a L-CDM model by means of a particular combination of parameters so that the Chaplygin gas and the L-CDM models can be easily distinguished in the theoretical scenarios here established. We find that the models are strongly degenerated in the range of frequencies studied. This degeneracy is in part expected since the models must converge to each other when some particular combinations of parameters are considered.