Adaptive approach heuristics for the generalized assignment problem

The Generalized Assignment Problem consists in assigning a setof tasks to a set of agents with minimum cost. Each agent hasa limited amount of a single resource and each task must beassigned to one and only one agent, requiring a certain amountof the resource of the agent. We present new metaheuristics forthe generalized assignment problem based on hybrid approaches.One metaheuristic is a MAX-MIN Ant System (MMAS), an improvedversion of the Ant System, which was recently proposed byStutzle and Hoos to combinatorial optimization problems, and itcan be seen has an adaptive sampling algorithm that takes inconsideration the experience gathered in earlier iterations ofthe algorithm. Moreover, the latter heuristic is combined withlocal search and tabu search heuristics to improve the search.A greedy randomized adaptive search heuristic (GRASP) is alsoproposed. Several neighborhoods are studied, including one basedon ejection chains that produces good moves withoutincreasing the computational effort. We present computationalresults of the comparative performance, followed by concludingremarks and ideas on future research in generalized assignmentrelated problems.

Evolving team compositions by agent swapping

Optimizing collective behavior in multiagent systems requires algorithms to find not only appropriate individual behaviors but also a suitable composition of agents within a team. Over the last two decades, evolutionary methods have emerged as a promising approach for the design of agents and their compositions into teams. The choice of a crossover operator that facilitates the evolution of optimal team composition is recognized to be crucial, but so far, it has never been thoroughly quantified. Here, we highlight the limitations of two different crossover operators that exchange entire agents between teams: restricted agent swapping (RAS) that exchanges only corresponding agents between teams and free agent swapping (FAS) that allows an arbitrary exchange of agents. Our results show that RAS suffers from premature convergence, whereas FAS entails insufficient convergence. Consequently, in both cases, the exploration and exploitation aspects of the evolutionary algorithm are not well balanced resulting in the evolution of suboptimal team compositions. To overcome this problem, we propose combining the two methods. Our approach first applies FAS to explore the search space and then RAS to exploit it. This mixed approach is a much more efficient strategy for the evolution of team compositions compared to either strategy on its own. Our results suggest that such a mixed agent-swapping algorithm should always be preferred whenever the optimal composition of individuals in a multiagent system is unknown.

A hybrid algorithm combining metaheuristic with Monte Carlo simulation for solving the Stochastic Flow Shop problem

In this paper, a hybrid simulation-based algorithm is proposed for the StochasticFlow Shop Problem. The main idea of the methodology is to transform the stochastic problem into a deterministic problem and then apply simulation to the latter. In order to achieve this goal, we rely on Monte Carlo Simulation and an adapted version of a deterministic heuristic. This approach aims to provide flexibility and simplicity due to the fact that it is not constrained by any previous assumption and relies in well-tested heuristics.

A hybrid algorithm combining metaheuristic with Monte Carlo simulation for solving the Stochastic Flow Shop problem

In this paper, a hybrid simulation-based algorithm is proposed for the StochasticFlow Shop Problem. The main idea of the methodology is to transform the stochastic problem into a deterministic problem and then apply simulation to the latter. In order to achieve this goal, we rely on Monte Carlo Simulation and an adapted version of a deterministic heuristic. This approach aims to provide flexibility and simplicity due to the fact that it is not constrained by any previous assumption and relies in well-tested heuristics.

Three essays in incomplete contracts

General Introduction These three chapters, while fairly independent from each other, study economic situations in incomplete contract settings. They are the product of both the academic freedom my advisors granted me, and in this sense reflect my personal interests, and of their interested feedback. The content of each chapter can be summarized as follows: Chapter 1: Inefficient durable-goods monopolies In this chapter we study the efficiency of an infinite-horizon durable-goods monopoly model with a fmite number of buyers. We find that, while all pure-strategy Markov Perfect Equilibria (MPE) are efficient, there also exist previously unstudied inefficient MPE where high valuation buyers randomize their purchase decision while trying to benefit from low prices which are offered once a critical mass has purchased. Real time delay, an unusual monopoly distortion, is the result of this attrition behavior. We conclude that neither technological constraints nor concern for reputation are necessary to explain inefficiency in monopolized durable-goods markets. Chapter 2: Downstream mergers and producer's capacity choice: why bake a larger pie when getting a smaller slice? In this chapter we study the effect of downstream horizontal mergers on the upstream producer's capacity choice. Contrary to conventional wisdom, we find anon-monotonic relationship: horizontal mergers induce a higher upstream capacity if the cost of capacity is low, and a lower upstream capacity if this cost is high. We explain this result by decomposing the total effect into two competing effects: a change in hold-up and a change in bargaining erosion. Chapter 3: Contract bargaining with multiple agents In this chapter we study a bargaining game between a principal and N agents when the utility of each agent depends on all agents' trades with the principal. We show, using the Potential, that equilibria payoffs coincide with the Shapley value of the underlying coalitional game with an appropriately defined characteristic function, which under common assumptions coincides with the principal's equilibrium profit in the offer game. Since the problem accounts for differences in information and agents' conjectures, the outcome can be either efficient (e.g. public contracting) or inefficient (e.g. passive beliefs).

Johdon palkkiojärjestelmätsuomalaisten pörssiyhtiöiden sijoittajaviestinnässä

Tutkimuksen tavoitteena on selvittää, mitä vaatimuksia suomalainen lainsäädäntö, IFRS-standardit, corporate governance - suosituksetja pörssin suositukset asettavat johdon palkkiosta tiedottamiselle ja kuinka laajasti tietoa tosiasiassa annetaan. Pörssiyhtiöiden tiedotuksen avoimuutta lähestytään tutkimalla, millaisia palkkioita ja kannustimia sekä päätöksentekotapoja on olemassa. Yhtiöiden omistuksen ja johtamisen eriytyessä syntyy päämies-agentti-ongelma. Johdon ja omistajien intressejä lähennetään palkkiojärjestelmien avulla. Palkitsemisen tarkoitus on kannustaa yrityksen johtoa toimimaan omistajan edun mukaisesti. Tutkimus on kvalitatiivinen ja tutkimusmenetelmä on deskriptiivinen: kuvailun ja luokittelun kautta pyritään analyysiin yritysten avoimuudesta palkkioiden suhteen. Tutkimus toteutettiinvertaamalla yhtiöiden Internet-sivuja ja vuosikertomuksia vuodelta 2004 määritettyihin kriteereihin. Tutkimuksen aineistona toimivat Helsingin arvopaperipörssin päälistan yhtiöt. Tutkimuksessa havaittiin, että palkkauksen muotoa tärkeämpää on palkitsemisen kokonaisuus ja siihen liittyvä päätöksenteko. Suomalaiset pörssiyhtiöt tiedottavat johdon palkkioista kohtuullisen hyvin, mutta erityisesti palkkioiden perusteista voisi kertoa tarkemminkin. Internetin tarjoamia mahdollisuuksia hyödynnetään kiitettävästi. Liike-vaihdoltaan suurimmatyritykset tiedottavat kautta linjan pienempiä tarkemmin.

Moral Hazard in Repeated Procurement of Services

This paper analyzes repeated procurement of services as a four-stage game divided into two periods. In each period there is (1) a contest stage à la Tullock in which the principal selects an agent and (2) a service stage in which the selected agent provides a service. Since this service effort is non-verifiable, the principal faces a moral hazard problem at the service stages. This work considers how the principal should design the period-two contest to mitigate the moral hazard problem in the period-one service stage and to maximize total service and contest efforts. It is shown that the principal must take account of the agent's past service effort in the period-two contest success function. The results indicate that the optimal way to introduce this `bias' is to choose a certain degree of complementarity between past service and current contest efforts. This result shows that contests with `additive bias' (`multiplicative bias') are optimal in incentive problems when effort cost is low (high). Furthermore, it is shown that the severity of the moral hazard problem increases with the cost of service effort (compared to the cost of contest effort) and the number of agents. Finally, the results are extended to more general contest success functions. JEL classification: C72; D82 Key words: Biased contests; Moral Hazard; Repeated Game; Incentives.

Data Collection Agent Framework

Ohjelmistoteollisuudessa pitkiä ja vaikeita kehityssyklejä voidaan helpottaa käyttämällä hyväksi ohjelmistokehyksiä (frameworks). Ohjelmistokehykset edustavat kokoelmaa luokkia, jotka tarjoavat yleisiä ratkaisuja tietyn ongelmakentän tarpeisiin vapauttaen ohjelmistokehittäjät keskittymään sovelluskohtaisiin vaatimuksiin. Hyvin suunniteltujen ohjelmistokehyksien käyttö lisää suunnitteluratkaisujen sekä lähdekoodin uudelleenkäytettävyyttä enemmän kuin mikään muu suunnittelulähestymistapa. Tietyn kohdealueen tietämys voidaan tallentaa ohjelmistokehyksiin, joista puolestaan voidaan erikoistaa viimeisteltyjä ohjelmistotuotteita. Tässä diplomityössä kuvataan ohjelmistoagentteihin (software agents) perustuvaa ohjelmistokehyksen suunnittelua toteutusta. Pääpaino työssä on vaatimusmäärittelyä vastaavan suunnitelman sekä toteutuksen kuvaaminen ohjelmistokehykselle, josta voidaan erikoistaa erilaiseen tiedonkeruuseen kykeneviä ohjelmistoja Internet ympäristöön. Työn kokeellisessa osuudessa esitellään myös esimerkkisovellus, joka perustuu työssä kehitettyyn ohjelmistokehykseen.

Omistus, kontrolli ja päämies-agentti- ongelmat osakeyhtiössä

Tutkielman tavoitteena on selvittää osakeyhtiön määräysvaltasuhteet ja miten päämies-agentti- ongelmat vaikeuttavat määräysvallan käyttöä. Tutkimusmetodi on lainopillinen ja lähestyminen aiheeseen tapahtuu sekä yhtiöoikeudellisesta, että oikeustaloustieteellisestä näkökulmasta. Aineistona tutkielmassa käytetään lähinnä voimassa olevaa lainsäädäntöä ja oikeuskirjallisuutta. Päämies-agentti- ongelmalla tarkoitetaan osakeyhtiössä määräysvallan osittaista luisumista omistajalta (päämies) yritysjohdolle (agentti) tai vähemmistöomistajalta (päämies) kontrolloivalle omistajalle (agentti). Tärkeimpiä ongelman lähteitä ovat epäsymmetrinen informaatio ja intressiristiriidat yhtiön johdon ja omistajien välillä tai toisaalta yhtiötä lähellä olevien omistajien ja muiden omistajien välillä. Epäsymmetrinen informaatio luo osaltaan puitteet agenttitahojen opportunistiselle käyttäytymiselle. Ratkaisuja päämies-agentti- ongelmiin ovat ennen kaikkea päämiestahoja suojaava lainsäädäntö ja ulkoiset yritysjohtajien käyttäytymistä ohjaavat keinot, kuten erilaiset kannustinjärjestelmät ja hyvät hallintotavat. Kontrolloivien omistajien käyttäytymistä on puolestaan vaikea ohjata ja erilaisilla määräysvaltaa keskittävillä omistusrakenteilla onkin taipumus voimistaa päämies-agentti- ongelmien vaikutusta. Erityisiä tilanteita osaltaan luovat myös luonteiltaan erilaiset omistajatahot, kuten institutionaaliset omistajat.

Towards the Construction of a Multi-agent Approach for Discovering the Meaning of Natural Language Collaborative Conversations

Peer-reviewed

Agent-based management systems for many-core platforms : rigorous design and efficient implementation

Due to various advantages such as flexibility, scalability and updatability, software intensive systems are increasingly embedded in everyday life. The constantly growing number of functions executed by these systems requires a high level of performance from the underlying platform. The main approach to incrementing performance has been the increase of operating frequency of a chip. However, this has led to the problem of power dissipation, which has shifted the focus of research to parallel and distributed computing. Parallel many-core platforms can provide the required level of computational power along with low power consumption. On the one hand, this enables parallel execution of highly intensive applications. With their computational power, these platforms are likely to be used in various application domains: from home use electronics (e.g., video processing) to complex critical control systems. On the other hand, the utilization of the resources has to be efficient in terms of performance and power consumption. However, the high level of on-chip integration results in the increase of the probability of various faults and creation of hotspots leading to thermal problems. Additionally, radiation, which is frequent in space but becomes an issue also at the ground level, can cause transient faults. This can eventually induce a faulty execution of applications. Therefore, it is crucial to develop methods that enable efficient as well as resilient execution of applications. The main objective of the thesis is to propose an approach to design agentbased systems for many-core platforms in a rigorous manner. When designing such a system, we explore and integrate various dynamic reconfiguration mechanisms into agents functionality. The use of these mechanisms enhances resilience of the underlying platform whilst maintaining performance at an acceptable level. The design of the system proceeds according to a formal refinement approach which allows us to ensure correct behaviour of the system with respect to postulated properties. To enable analysis of the proposed system in terms of area overhead as well as performance, we explore an approach, where the developed rigorous models are transformed into a high-level implementation language. Specifically, we investigate methods for deriving fault-free implementations from these models into, e.g., a hardware description language, namely VHDL.

Structuring of internal control – a case study

The aim of this Master’s thesis is to find out how should internal control be structured in a Finnish retail company in order to fulfil the requirements set out in the Finnish Corporate Governance Code and to be value adding for the company as well as to analyse the added value that a structured and centrally led internal control can provide for the case company. The underlying fundamental theoretical framework of the study essentially stems from the theory of the firm; the agent-principal problem is the primary motivator for internal control. Regulatory requirements determine the thresholds that the internal control of a company must reach. The research was carried out as a case study and methodically the study is qualitative and the empirical data gathering was conducted by interviews and by participant observation. The data gathered (processes, controls etc.) is used to understand the control environment of the company and to assess the current state of internal control. Deficiencies and other points of development identified are then discussed.

Suomalaisten yliopistojen life science-alan spin-off-yritysten rahoitustilanne, -lähteet ja –riskit

Life science-ala on rahoituksellisesti erittäin haastava, koska tuotekehitysputket ovat 10-15 vuoden pituisia ja voivat vaatia suuria etupainotteisia investointeja. Monet life science-alan yritykset ovat niin Suomessa kuin kansainvälisestikin syntyneet suoraan yliopistosta niin sanottuina spin-off-yrityksinä. Yrityksen perustaminen tutkimustiedon pohjalle on yksi akateemisen yrittäjyyden muodoista. Tässä tutkimuksessa tutkitaan akateemista yrittäjyyttä life science-alalla Suomessa. Suomessa life science-alan osaaminen on kansainvälistä huippua ja alalle on syntynyt useita spin-off-yrityksiä viime vuosina. Aiemmat tutkimukset ovat keskittyneet erityisesti agentti-päämiesongelmiin akateemisessa yrittäjyydessä ja life science alaa puolestaan on käsitelty usein pelkästään yhtenä alana. Tutkimuksessa pyritään analysoimaan life science-alan eri painopiste-alueita tarkemmin rahoitusstrategisesta näkökulmasta, koska ala ei ole homogeeninen. Akateemisen yrittäjyyden agenttiongelmaa pyritään tarkoittamaan Suomen yliopistomaailmassa life science-alalta käsin. Tutkimus toteutetaan kvalitatiivisena haastattelututkimuksena ja sitä tukevana tilinpäätöstietojen analysointina. Tutkimuksen tulokset vahvistavat agentti-päämiesongelmien olemassaolon suomalaisessa yliopistomaailmassa. Ongelmien osapuolina ovat niin akateemikot, yliopiston innovaatiopalvelut kuin TEKES:kin. Yrittäjät kaipaavat kokonaisvaltaisempaa apua, koska kokevat alalla liiketoimintaosaamisen puuttuvan monin paikoin. Alan vaatimien runsaiden tuotekehityspanostusten vuoksi alan yritykset ovat pitkään raskaasti tappiollisia. Yritysten valitsemat rahoitusratkaisut vaihtelevat suuresti. Kaikki tutkitut yritykset pyrkivät kasvamaan nykyisten ydintuotteidensa mukana ja ovat jo jossain määrin hankkineet rahoitusta kasvustrategiaansa varten. Alan pääomaintensiivisyydestä johtuen ovat monet yritykset kuitenkin suunnittelemassa tai jo päätyneet tekemään yhteistyötä integroituen alalla joko vertikaalisesti tai horisontaalisesti. Tutkimuksen tulokset vahvistavat aiemman käsityksen, jonka mukaan life science-alan yrityksiä on vaikea arvioida ulkopuolelta pelkästään tilinpäätöstietojen pohjalta, koska alkuvaiheessa rahoituskierrokset ja tappiolliset vuoden seuraavat toisiaan ja toisaalta yrityksen arvo sitoutuu pitkiin tuotekehitysputkiin, jotka eivät välttämättä näy tilinpäätöksessä. Tulokset tuovat esille merkittäviä yritysten kokemia ongelmia rahoituksen saannissa life science-alalla Suomessa sekä akateemisen yrittäjyyden epäkohtia yritystoiminnan näkökulmasta. Näiden tekijöiden huomioonottaminen ja laajempi kansainvälinen vertailu voivat auttaa suomalaisia yrityksiä tällä vahvalla osaamisalalla eteenpäin.

Conception, synthèse et diversification de l'azaGly-Pro : un mime de tour beta, outil d'étude structure-activité : application au développement d'un nouvel agent tocolytique

Les accouchements prématurés constituent un problème médical majeur en constante augmentation et ce, malgré tous les efforts mis en œuvre afin de contrer le déclenchement des contractions avant terme. Cette thèse relate du ''design'' rationnel d'un nouvel agent thérapeutique (i.e., tocolytique) qui serait capable de 1) arrêter les contractions, et 2) prolonger la gestation. Pour ce faire, une nouvelle cible, la prostaglandine F2α et son récepteur ont été sélectionnés et le peptidomimétisme a été choisi afin de résoudre cette problématique. L'introduction contient un historique rapide de la conception à la synthèse (''drug design'') du peptide parent, le PDC113, premier peptide a avoir démontré des aptitudes tocolytiques suffisantes pour faire du peptidomimétisme. La deuxième partie de l'introduction présente les concepts du peptidomimétisme appliqués au PDC113 qui ont permis d'accéder au PDC113.824, inhibiteur allostérique du récepteur de la prostaglandine F2α, et explique comment ce mime nous a permis d'élucider les mécanismes de signalisation intracellulaire impliqués dans la contraction musculaire lisse. Cette thèse présente la conception, la synthèse et l'étude structure-activité de mimes de repliement de tour β au sein du mime peptidique original (PDC113.824) dans lequel nous avons remplacé l'azabicycloalkane central (l'indolizidin-2-one) par une série d'autres azabicycloalcanes connus et des acides aza-aminés dont nous avons élaboré la synthèse. Dans un premier temps, une nouvelle stratégie de synthèse en solution de l'aza-glycyl-proline à partir de la diphényle hydrazone et du chloroformate de p-nitrophényle a été réalisée. Cette stratégie a permis d'éliminer les réactions secondaires de cyclisation intramoléculaires communément obtenues lors de l'introduction d'acides aza-aminés avec les protections traditionnelles de type carbamate en présence de phosgène, mais aussi de faciliter l'accès en une étape à des dérivés peptidiques du type aza-glycyle. L'élongation de l'aza-glycyl-proline en solution nous a permis d'accéder à un nouveau mime tetrapeptidique du Smac, un activateur potentiel de l'apoptose au sein de cellules cancéreuses. Par la suite, nous avons développé une stratégie de diversification sélective de l'azote α du résidu azaglycine en utilisant différents types d'halogénures d'alkyle en présence de tert-butoxyde de potassium. Afin de valider le protocole d'alkylation de l'aza-dipeptide, différents halogénures d'alkyle ont été testés. Nous avons également démontré l'utilité des aza-dipeptides résultants en tant que ''building block'' afin d'accéder à une variété d'azapeptides. En effet, l'aza-dipeptide a été déprotégée sélectivement soit en N-terminal soit en C-terminal, respectivement. D'autre part, la libération de l'amine de l'ester méthylique de l'aza-alkylglycyl-proline a conduit à une catégorie de composés à potentiel thérapeutique, les azadicétopipérazines (aza-DKP) par cyclisation intramoléculaire. Enfin, notre intérêt quant au développement d'un nouvel agent tocolytique nous a amené à développer une nouvelle voie de synthèse en solution du PDC113.824 permettant ainsi d'élucider les voies de signalisation intracellulaires du récepteur de la prostaglandine F2α. Afin de valider l'importance de la stéréochimie et d'étudier la relation structure/ activité du mime, nous avons remplacé l'indolizidin-2-one (I2aa) centrale du PDC113.824 par une série d'autres azabicycloalcanes et azadipeptides. Les azabicycloalcanes D-I2aa, quinolizidinone, et indolizidin-9-one ont été synthétisés et incorporés au sein du dit peptide ne donnant aucune activité ni in vitro ni ex vivo, validant ainsi l'importance du tour β de type II' pour le maintien de l'activité biologique du PDC113.824. Finalement, l'insertion d'une série de dérivés aza(alkyl)glycyl-prolyles a mené à de nouveaux inhibiteurs allostériques du récepteur de la PGF2α, l'un contenant l'azaglycine et l'autre, l'azaphénylalanine. Cette thèse a ainsi contribué, grâce à la conception et l'application de nouvelles méthodes de synthèse d'aza-peptides, au développement de nouveaux composés à potentiel thérapeutique afin d'inhiber le travail prématuré.

The berth allocation problem at port terminals : a column generation framework

Le problème d'allocation de postes d'amarrage (PAPA) est l'un des principaux problèmes de décision aux terminaux portuaires qui a été largement étudié. Dans des recherches antérieures, le PAPA a été reformulé comme étant un problème de partitionnement généralisé (PPG) et résolu en utilisant un solveur standard. Les affectations (colonnes) ont été générées a priori de manière statique et fournies comme entrée au modèle %d'optimisation. Cette méthode est capable de fournir une solution optimale au problème pour des instances de tailles moyennes. Cependant, son inconvénient principal est l'explosion du nombre d'affectations avec l'augmentation de la taille du problème, qui fait en sorte que le solveur d'optimisation se trouve à court de mémoire. Dans ce mémoire, nous nous intéressons aux limites de la reformulation PPG. Nous présentons un cadre de génération de colonnes où les affectations sont générées de manière dynamique pour résoudre les grandes instances du PAPA. Nous proposons un algorithme de génération de colonnes qui peut être facilement adapté pour résoudre toutes les variantes du PAPA en se basant sur différents attributs spatiaux et temporels. Nous avons testé notre méthode sur un modèle d'allocation dans lequel les postes d'amarrage sont considérés discrets, l'arrivée des navires est dynamique et finalement les temps de manutention dépendent des postes d'amarrage où les bateaux vont être amarrés. Les résultats expérimentaux des tests sur un ensemble d'instances artificielles indiquent que la méthode proposée permet de fournir une solution optimale ou proche de l'optimalité même pour des problème de très grandes tailles en seulement quelques minutes.