Resolução do problema de atribuição de salas a exames

Este trabalho pretende resolver o problema das alocações de salas a exames no Departamento de Engenharia Mecânica do Instituto Superior de Engenharia do Porto. A solução desenvolvida atribui salas a exames respeitando as restrições de capacidade de salas e a restrição de realização dum único exame por sala num determinado período, por forma a minimizar a atribuição de salas e, consequentemente, docentes a exames. Foi criado um modelo matemático, que representa as variáveis relevantes do problema, e realiza a sua implementação numa plataforma informática amigável para o utilizador. O modelo matemático foi validado comparando as suas soluções com as obtidas através do processo manual. Os resultados do novo método demonstram a sua supremacia relativamente ao modelo atual. No futuro, poderá ser estudada a possibilidade de usar esta ferramenta na resolução do mesmo problema em realidades diferentes da do Departamento de Engenharia Mecânica do ISEP.

Scalable and Efficient Configuration of TimeDivision Multiplexed Resources

Consumer-electronics systems are becoming increasingly complex as the number of integrated applications is growing. Some of these applications have real-time requirements, while other non-real-time applications only require good average performance. For cost-efficient design, contemporary platforms feature an increasing number of cores that share resources, such as memories and interconnects. However, resource sharing causes contention that must be resolved by a resource arbiter, such as Time-Division Multiplexing. A key challenge is to configure this arbiter to satisfy the bandwidth and latency requirements of the real-time applications, while maximizing the slack capacity to improve performance of their non-real-time counterparts. As this configuration problem is NP-hard, a sophisticated automated configuration method is required to avoid negatively impacting design time. The main contributions of this article are: 1) An optimal approach that takes an existing integer linear programming (ILP) model addressing the problem and wraps it in a branch-and-price framework to improve scalability. 2) A faster heuristic algorithm that typically provides near-optimal solutions. 3) An experimental evaluation that quantitatively compares the branch-and-price approach to the previously formulated ILP model and the proposed heuristic. 4) A case study of an HD video and graphics processing system that demonstrates the practical applicability of the approach.

The ambivalence of two-part tariffs for bottleneck access

Two-part tariffs, when used at the retail level, increase efficiency by lowering the price of marginal units. The same potential for higher efficiency exists for two-part tariffs at wholesale level for a given market structure, but the fixed part of the wholesale tariff can negatively affect the latter. In a simulated competition model of next-generation telecommunications access networks that has been calibrated with engineering cost data, we show that the latter effects strongly outweigh the former. That is, substituting a cost-based linear wholesale access tariff with revenue-equivalent two-part tariffs reduces the number of access seekers and therefore leads to higher prices and lower welfare and consumer surplus.

Analysis of temporal and spatial variations of forest. A case of study in notheastern Armenia

The forest has a crucial ecological role and the continuous forest loss can cause colossal effects on the environment. As Armenia is one of the low forest covered countries in the world, this problem is more critical. Continuous forest disturbances mainly caused by illegal logging started from the early 1990s had a huge damage on the forest ecosystem by decreasing the forest productivity and making more areas vulnerable to erosion. Another aspect of the Armenian forest is the lack of continuous monitoring and absence of accurate estimation of the level of cuts in some years. In order to have insight about the forest and the disturbances in the long period of time we used Landsat TM/ETM + images. Google Earth Engine JavaScript API was used, which is an online tool enabling the access and analysis of a great amount of satellite imagery. To overcome the data availability problem caused by the gap in the Landsat series in 1988- 1998, extensive cloud cover in the study area and the missing scan lines, we used pixel based compositing for the temporal window of leaf on vegetation (June-late September). Subsequently, pixel based linear regression analyses were performed. Vegetation indices derived from the 10 biannual composites for the years 1984-2014 were used for trend analysis. In order to derive the disturbances only in forests, forest cover layer was aggregated and the original composites were masked. It has been found, that around 23% of forests were disturbed during the study period.

Verfahren zur direkten Implementierung von Algorithmen auf Gatterebene

Bit serial, processing, digital signal processing, transmission, time division, linear programming, linear optimization

Optimal operation of multiproduct batch plants

Multiproduct plants, Dynamic Optimization, Mixed Integer Linear/Non-Linear Programming, Scheduling

General equilibrium with asymmetric information: a dual approach

We study markets where the characteristics or decisions of certain agents are relevant but not known to their trading partners. Assuming exclusive transactions, the environment is described as a continuum economy with indivisible commodities. We characterize incentive efficient allocations as solutions to linear programming problems and appeal to duality theory to demonstrate the generic existence of external effects in these markets. Because under certain conditions such effects may generate non-convexities, randomization emerges as a theoretic possibility. In characterizing market equilibria we show that, consistently with the personalized nature of transactions, prices are generally non-linear in the underlying consumption. On the other hand, external effects may have critical implications for market efficiency. With adverse selection, in fact, cross-subsidization across agents with different private information may be necessary for optimality, and so, the market need not even achieve an incentive efficient allocation. In contrast, for the case of a single commodity, we find that when informational asymmetries arise after the trading period (e.g. moral hazard; ex post hidden types) external effects are fully internalized at a market equilibrium.

A dual characterization of incentive efficiency

We show that incentive efficient allocations in economies with adverse selection and moral hazard can be determined as optimal solutions to a linear programming problem and we use duality theory to obtain a complete characterization of the optima. Our dual analysis identifies welfare effects associated with the incentives of the agents to truthfully reveal their private information. Because these welfare effects may generate non-convexities, incentive efficient allocations may involve randomization. Other properties of incentive efficient allocations are also derived.

Extracción de parámetros de un resonador FBAR por optimización

L’objectiu d’aquest projecte que consisteix a elaborar un algoritme d’optimització que permeti, mitjançant un ajust de dades per mínims quadrats, la extracció dels paràmetres del circuit equivalent que composen el model teòric d’un ressonador FBAR, a partir de les mesures dels paràmetres S. Per a dur a terme aquest treball, es desenvolupa en primer lloc tota la teoria necessària de ressonadors FBAR. Començant pel funcionament i l’estructura, i mostrant especial interès en el modelat d’aquests ressonadors mitjançant els models de Mason, Butterworth Van-Dyke i BVD Modificat. En segon terme, s’estudia la teoria sobre optimització i programació No-Lineal. Un cop s’ha exposat la teoria, es procedeix a la descripció de l’algoritme implementat. Aquest algoritme utilitza una estratègia de múltiples passos que agilitzen l'extracció dels paràmetres del ressonador.

The Multiple-partners assignment game with heterogeneous sales and multi-unit demands: competitive equilibria

A multiple-partners assignment game with heterogeneous sales and multiunit demands consists of a set of sellers that own a given number of indivisible units of (potentially many different) goods and a set of buyers who value those units and want to buy at most an exogenously fixed number of units. We define a competitive equilibrium for this generalized assignment game and prove its existence by using only linear programming. In particular, we show how to compute equilibrium price vectors from the solutions of the dual linear program associated to the primal linear program defined to find optimal assignments. Using only linear programming tools, we also show (i) that the set of competitive equilibria (pairs of price vectors and assignments) has a Cartesian product structure: each equilibrium price vector is part of a competitive equilibrium with all optimal assignments, and vice versa; (ii) that the set of (restricted) equilibrium price vectors has a natural lattice structure; and (iii) how this structure is translated into the set of agents' utilities that are attainable at equilibrium.

Statistical properties of subgroups of free groups

The usual way to investigate the statistical properties of finitely generated subgroups of free groups, and of finite presentations of groups, is based on the so-called word-based distribution: subgroups are generated (finite presentations are determined) by randomly chosen k-tuples of reduced words, whose maximal length is allowed to tend to infinity. In this paper we adopt a different, though equally natural point of view: we investigate the statistical properties of the same objects, but with respect to the so-called graph-based distribution, recently introduced by Bassino, Nicaud and Weil. Here, subgroups (and finite presentations) are determined by randomly chosen Stallings graphs whose number of vertices tends to infinity. Our results show that these two distributions behave quite differently from each other, shedding a new light on which properties of finitely generated subgroups can be considered frequent or rare. For example, we show that malnormal subgroups of a free group are negligible in the raph-based distribution, while they are exponentially generic in the word-based distribution. Quite surprisingly, a random finite presentation generically presents the trivial group in this new distribution, while in the classical one it is known to generically present an infinite hyperbolic group.

A numerical solver for a nonlinear Fokker-Planck equation representation of neuronal network dynamics

To describe the collective behavior of large ensembles of neurons in neuronal network, a kinetic theory description was developed in [13, 12], where a macroscopic representation of the network dynamics was directly derived from the microscopic dynamics of individual neurons, which are modeled by conductance-based, linear, integrate-and-fire point neurons. A diffusion approximation then led to a nonlinear Fokker-Planck equation for the probability density function of neuronal membrane potentials and synaptic conductances. In this work, we propose a deterministic numerical scheme for a Fokker-Planck model of an excitatory-only network. Our numerical solver allows us to obtain the time evolution of probability distribution functions, and thus, the evolution of all possible macroscopic quantities that are given by suitable moments of the probability density function. We show that this deterministic scheme is capable of capturing the bistability of stationary states observed in Monte Carlo simulations. Moreover, the transient behavior of the firing rates computed from the Fokker-Planck equation is analyzed in this bistable situation, where a bifurcation scenario, of asynchronous convergence towards stationary states, periodic synchronous solutions or damped oscillatory convergence towards stationary states, can be uncovered by increasing the strength of the excitatory coupling. Finally, the computation of moments of the probability distribution allows us to validate the applicability of a moment closure assumption used in [13] to further simplify the kinetic theory.

Genomics of the divergence continuum in an African plant biodiversity hotspot, I: drivers of population divergence in Restio capensis (Restionaceae).

Understanding the drivers of population divergence, speciation and species persistence is of great interest to molecular ecology, especially for species-rich radiations inhabiting the world's biodiversity hotspots. The toolbox of population genomics holds great promise for addressing these key issues, especially if genomic data are analysed within a spatially and ecologically explicit context. We have studied the earliest stages of the divergence continuum in the Restionaceae, a species-rich and ecologically important plant family of the Cape Floristic Region (CFR) of South Africa, using the widespread CFR endemic Restio capensis (L.) H.P. Linder & C.R. Hardy as an example. We studied diverging populations of this morphotaxon for plastid DNA sequences and >14 400 nuclear DNA polymorphisms from Restriction site Associated DNA (RAD) sequencing and analysed the results jointly with spatial, climatic and phytogeographic data, using a Bayesian generalized linear mixed modelling (GLMM) approach. The results indicate that population divergence across the extreme environmental mosaic of the CFR is mostly driven by isolation by environment (IBE) rather than isolation by distance (IBD) for both neutral and non-neutral markers, consistent with genome hitchhiking or coupling effects during early stages of divergence. Mixed modelling of plastid DNA and single divergent outlier loci from a Bayesian genome scan confirmed the predominant role of climate and pointed to additional drivers of divergence, such as drift and ecological agents of selection captured by phytogeographic zones. Our study demonstrates the usefulness of population genomics for disentangling the effects of IBD and IBE along the divergence continuum often found in species radiations across heterogeneous ecological landscapes.

Pluralized life courses? An exploration of the life trajectories of individuals with psychiatric disorders.

BACKGROUND: : Most of the existing research relating to the life courses of people with psychiatric symptoms focuses on the occurrence and the impact of non-normative events on the onsets of crises; it usually disregards the more regular dimensions of life, such as work, family and intimate partnerships that may be related to the timing and seriousness of psychiatric problems. An additional reason for empirically addressing life trajectories of individuals with psychiatric problems relates to recent changes of family and occupational trajectories in relation to societal trends such as individualization and pluralization of life courses.¦AIM: : This paper explores the life trajectories of 86 individuals under clinical supervision and proposes a typology of their occupational, co-residence and intimacy trajectories. The results are discussed in light of the life-course paradigm.¦METHOD: : A multidimensional optimal matching analysis was performed on a sample of 86 individuals under clinical supervision to create a typology of trajectories. The influence of these trajectories on psychiatric disorders, evaluated using a SCL-90-R questionnaire, was then assessed using linear regression modelling.¦RESULTS: : The typologies of trajectories showed that the patients developed a diversity of life trajectories. Individuals who have developed a standard life course with few institutionalization periods reported more symptoms and distress than individuals with an institutionalized life trajectory.¦CONCLUSION: : The results of this study stress that psychiatric patients are social actors who are influenced by society at large and its ongoing process of change. Therefore, it is essential to take into account the diversity of occupational and family trajectories when dealing with individuals in therapeutic settings.

Generalized low-density codes with BCH constituents for full-diversity near-outage performance

A new graph-based construction of generalized low density codes (GLD-Tanner) with binary BCH constituents is described. The proposed family of GLD codes is optimal on block erasure channels and quasi-optimal on block fading channels. Optimality is considered in the outage probability sense. Aclassical GLD code for ergodic channels (e.g., the AWGN channel,the i.i.d. Rayleigh fading channel, and the i.i.d. binary erasure channel) is built by connecting bitnodes and subcode nodes via a unique random edge permutation. In the proposed construction of full-diversity GLD codes (referred to as root GLD), bitnodes are divided into 4 classes, subcodes are divided into 2 classes, and finally both sides of the Tanner graph are linked via 4 random edge permutations. The study focuses on non-ergodic channels with two states and can be easily extended to channels with 3 states or more.