Efficient knowledge retrieval to calibrate input variables in forest fire prediction

Forest fires are a serious threat to humans and nature from an ecological, social and economic point of view. Predicting their behaviour by simulation still delivers unreliable results and remains a challenging task. Latest approaches try to calibrate input variables, often tainted with imprecision, using optimisation techniques like Genetic Algorithms. To converge faster towards fitter solutions, the GA is guided with knowledge obtained from historical or synthetical fires. We developed a robust and efficient knowledge storage and retrieval method. Nearest neighbour search is applied to find the fire configuration from knowledge base most similar to the current configuration. Therefore, a distance measure was elaborated and implemented in several ways. Experiments show the performance of the different implementations regarding occupied storage and retrieval time with overly satisfactory results.

Marine biotoxins in the Catalan littoral: could biosensors be integrated into monitoring programmes?

Aquest article descriu els sensors enzimàtics i immunosensors electroquímics que s’han desenvolupat als nostres grups per a la detecció de la biotoxina marina àcid okadaic (OA), i discuteix la possibilitat d’integrar-los en programes de seguiment. Els sensors enzimàtics per a OA que es presenten es basen en la inhibició de la proteïna fosfatasa (PP2A) per aquesta toxina i la mesura electroquímica de l’activitat enzimàtica mitjançant l’ús de substrats enzimàtics apropiats, electroquímicament actius després de la seva desfosforació per l’enzim. Els immunosensors electroquímics descrits en aquest article es basen en un enzimoimmunoassaig sobre fase sòlida competitiu indirecte (ciELISA), amb fosfatasa alcalina (ALP) o peroxidasa (HRP) com a marcatges, i un sistema de reciclatge enzimàtic amb diaforasa (DI). Els biosensors presentats aquí s’han aplicat a l’anàlisi de dinoflagel·lats, musclos i ostres. Les validacions preliminars amb assaigs colorimètrics i LC-MS/MS han demostrat la possibilitat d’utilitzar les bioeines desenvolupades per al cribratge preliminar de biotoxines marines en mostres de camp o de cultiu, que ofereixen informació complementària a la cromatografia. En conclusió, tot i que encara cal optimitzar alguns paràmetres experimentals, la integració dels biosensors a programes de seguiment és viable i podria proporcionar avantatges respecte a altres tècniques analítiques pel que fa al temps d’anàlisi, la simplicitat, la selectivitat, la sensibilitat, el fet de poder ser d’un sol ús i l’efectivitat de cost. This article describes the electrochemical enzyme sensors and immunosensors that have been developed by our groups for the detection of marine biotoxin okadaic acid (OA), and discusses the possibility of integrating them into monitoring programmes. The enzyme sensors for OA reported herein are based on the inhibition of immobilised protein phosphatase 2A (PP2A) by this toxin and the electrochemical measurement of the enzyme activity through the use of appropriate enzyme substrates, which are electrochemically active after dephosphorylation by the enzyme. The electrochemical immunosensors described in this article are based on a competitive indirect Enzyme- Linked ImmunoSorbent Assay (ciELISA), using alkaline phosphatase (ALP) or horseradish peroxidase (HRP) as labels, and an enzymatic recycling system with diaphorase (DI). The biosensors presented herein have been applied to the analysis of dinoflagellates, mussels and oysters. Preliminary validations with colorimetric assays and LC-MS/MS have demonstrated the possibility of using the developed biotools for the preliminary screening of marine biotoxins in field or cultured samples, offering complementary information to chromatography. In conclusion, although optimisation of some experimental parameters is still required, the integration of biosensors into monitoring programmes is viable and may provide advantages over other analytical techniques in terms of analysis time, simplicity, selectivity, sensitivity, disposability of electrodes and cost effectiveness.

Colocaciones léxicas en dicconarios monolingües generales del español

El objetivo de la presente investigación es analizar el tratamiento que algunos de los diccionarios generales monolingües del español aparecidos en los últimos diez años han dado al fenómeno de las colocaciones léxicas, a saber, aquellas combinaciones de palabras que, desde el punto de vista de la norma, presentan ciertas restricciones combinatorias, esencialmente de carácter semántico, impuestas por el uso (Corpas: 1996). Los repertorios objeto de análisis han sido: el "Diccionario Salamanca de la lengua española", dirigido por Juan Gutiérrez (1996); el "Diccionario del español actual", de Manuel Seco, Olimpia Andrés y Gabino Ramos (1999); la vigésima segunda edición del diccionario de la RAE (2001); y el "Gran diccionario de uso del español actual. Basado en el corpus Cumbre", dirigido por Aquilino Sánchez (2001). Nuestro estudio se ha fundamentado en un corpus de 52 colocaciones léxicas confeccionado a partir del análisis de las subentradas contenidas en la letra "b" de cada uno de los diccionarios seleccionados. Posteriormente, hemos examinado las entradas correspondientes a cada uno de los elementos que constituyen la colocación (base y colocativo) con el fin de observar si los diccionarios estudiados dan cuenta de estas mismas combinaciones en otras partes del artículo lexicográfico, como son las definiciones o los ejemplos. A la hora de analizar la información lexicográfica hemos centrado nuestra atención en cuatro aspectos: a) la información contenida en las páginas preliminares de cada una de las obras; b) la ubicación de las colocaciones en el artículo lexicográfico; c) la asignación de la colocación a un artículo determinado; y d) la marcación gramatical.

Computing hypergraph width measures exactly

Hypergraph width measures are a class of hypergraph invariants important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exact exponential algorithm for a large variety of these measures. A connection between these and tree decompositions is established. This enables us to almost seamlessly adapt the combinatorial and algorithmic results known for tree decompositions of graphs to the case of hypergraphs and obtain fast exact algorithms. As a consequence, we provide algorithms which, given a hypergraph H on n vertices and m hyperedges, compute the generalized hypertree-width of H in time O*(2n) and compute the fractional hypertree-width of H in time O(1.734601n.m).1

Efecto de los contenidos de C, Mn y Si en el comportamiento a fluencia en caliente de aceros de construcción al carbono y microaleados: aplicación a la obtención de grano ultrafino en productos largos laminados

Després d’aplicar alguns tractaments d’elaboració i conservació als aliments, queden bacteris lesionats. Aquests bacteris perden la capacitat de créixer en els medis de cultiu selectiu convencionals, de manera que se’n subestima el recompte. Malgrat això, poden recuperar-se als aliments i suposar un risc per la salut, ja que alguns encara poden mantenir activitat metabòlica i integritat estructural. En aquest projecte, es van optimitzar protocols de preparació de mostres per citometria de flux (CF) per avaluar l’estat fisiològic de patògens alimentaris (Escherichia coli O157:H7, Salmonella Enteritidis i Listeria monocytogenes) sotmesos a estrès. Es van estudiar principalment dos paràmetres fisiològics: la integritat de membrana, mitjançant iodur de propidi i fluorocroms de la família SYTO; i l’activitat respiratòria, per la reducció intracel•lular d’una sal de tetrazole, el CTC. En primer lloc, es van avaluar variables de protocol, com la concentració de colorant, la ràtio entre colorants, la solució de tinció i el temps d’incubació, en mostres control (cèl•lules sanes i mortes). A continuació, els protocols optimitzats es van aplicar a suspensions bacterianes en medi de cultiu que prèviament havien estat sotmeses a estressos físics i fisicoquímics. Durant l’etapa final del projecte, els coneixements adquirits sobre la preparació de mostres per CF es van aplicar a l’anàlisi de mostres de matriu complexa: amanides comercials inoculades amb E. coli O157:H7. Als assajos amb indicadors d’integritat de membrana en suspensions bacterianes sotmeses a estrès, es van poder quantificar cèl•lules amb la membrana parcialment danyada (presumptes cèl•lules lesionades). El recompte de cèl•lules que mantingueren l’activitat respiratòria després de ser sotmeses a estrès va ser superior al que es va obtenir mitjançant recompte en placa convencional, cosa que va evidenciar la presència de cèl•lules actives però no cultivables. La introducció d’estratègies per reduir les interferències provocades per les partícules alimentàries i l’ús d’un anticòs amb marcatge fluorescent va permetre detectar selectivament les cèl•lules d’E. coli O157:H7 i avaluar-ne la integritat de membrana simultàniament. L’anàlisi de cèl•lules bacterianes per CF requereix de la exhaustiva optimització dels protocols, que són específics per cada soca i matriu. Malgrat això, i a diferència del mètode convencional per recompte en placa, ofereix la possibilitat d’obtenir una gran quantitat d’informació sobre el sovint complex estat fisiològic d’una mostra.

Decision Support Methods for Global Optomization

Immobile location-allocation (LA) problems is a type of LA problem that consists in determining the service each facility should offer in order to optimize some criterion (like the global demand), given the positions of the facilities and the customers. Due to the complexity of the problem, i.e. it is a combinatorial problem (where is the number of possible services and the number of facilities) with a non-convex search space with several sub-optimums, traditional methods cannot be applied directly to optimize this problem. Thus we proposed the use of clustering analysis to convert the initial problem into several smaller sub-problems. By this way, we presented and analyzed the suitability of some clustering methods to partition the commented LA problem. Then we explored the use of some metaheuristic techniques such as genetic algorithms, simulated annealing or cuckoo search in order to solve the sub-problems after the clustering analysis

Solving Large Location-Allocation problems by Clustering and Simulated Annealing

Globalization involves several facility location problems that need to be handled at large scale. Location Allocation (LA) is a combinatorial problem in which the distance among points in the data space matter. Precisely, taking advantage of the distance property of the domain we exploit the capability of clustering techniques to partition the data space in order to convert an initial large LA problem into several simpler LA problems. Particularly, our motivation problem involves a huge geographical area that can be partitioned under overall conditions. We present different types of clustering techniques and then we perform a cluster analysis over our dataset in order to partition it. After that, we solve the LA problem applying simulated annealing algorithm to the clustered and non-clustered data in order to work out how profitable is the clustering and which of the presented methods is the most suitable

Algorithm creation and optimization for the crew pairing problem

Algoritmo que optimiza y crea pairings para tripulaciones de líneas aéreas mediante la posterior programación en Java.

The achievable region approach to the optimal control of stochastic systems

The achievable region approach seeks solutions to stochastic optimisation problems by: (i) characterising the space of all possible performances(the achievable region) of the system of interest, and (ii) optimisingthe overall system-wide performance objective over this space. This isradically different from conventional formulations based on dynamicprogramming. The approach is explained with reference to a simpletwo-class queueing system. Powerful new methodologies due to the authorsand co-workers are deployed to analyse a general multiclass queueingsystem with parallel servers and then to develop an approach to optimalload distribution across a network of interconnected stations. Finally,the approach is used for the first time to analyse a class of intensitycontrol problems.

A multi-objective model for a multi-period distribution management problem

The problems arising in commercial distribution are complex and involve several players and decision levels. One important decision is relatedwith the design of the routes to distribute the products, in an efficient and inexpensive way.This article deals with a complex vehicle routing problem that can beseen as a new extension of the basic vehicle routing problem. The proposed model is a multi-objective combinatorial optimization problemthat considers three objectives and multiple periods, which models in a closer way the real distribution problems. The first objective is costminimization, the second is balancing work levels and the third is amarketing objective. An application of the model on a small example, with5 clients and 3 days, is presented. The results of the model show the complexity of solving multi-objective combinatorial optimization problems and the contradiction between the several distribution management objective.

Iterated local search

Iterated Local Search has many of the desirable features of a metaheuristic: it is simple, easy to implement, robust, and highly effective. The essential idea of Iterated Local Search lies in focusing the search not on the full space of solutions but on a smaller subspace defined by the solutions that are locally optimal for a given optimization engine. The success of Iterated Local Search lies in the biased sampling of this set of local optima. How effective this approach turns out to be depends mainly on the choice of the local search, the perturbations, and the acceptance criterion. So far, in spite of its conceptual simplicity, it has lead to a number of state-of-the-art results without the use of too much problem-specific knowledge. But with further work so that the different modules are well adapted to the problem at hand, Iterated Local Search can often become a competitive or even state of the artalgorithm. The purpose of this review is both to give a detailed description of this metaheuristic and to show where it stands in terms of performance.

Assigning proctors to exams with scatter search

In this paper we present an algorithm to assign proctors toexams. This NP-hard problem is related to the generalized assignmentproblem with multiple objectives. The problem consists of assigningteaching assistants to proctor final exams at a university. We formulatethis problem as a multiobjective integer program (IP) with a preferencefunction and a workload-fairness function. We then consider also a weightedobjective that combines both functions. We develop a scatter searchprocedure and compare its outcome with solutions found by solving theIP model with CPLEX 6.5. Our test problems are real instances from aUniversity in Spain.

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.

Female labour supply in Spain: The importance of behavioural assumptions and unobserved heterogeneity specification

We estimate four models of female labour supply using a Spanish sampleof married women from 1994, taking into account the complete form of theindividual s budget set. The models differ in the hypotheses relating tothe presence of optimisation errors and/or the way non-workers contributeto the likelihood function. According to the results, the effects of wagesand non-labour income on the labour supply of Spanish married women dependon the specification used. The model which has both preference andoptimisation errors and allows for both voluntarily and involuntarilyunemployed females desiring to participate seems to better fit the evidencefor Spanish married women.

Metaheuristics for the bus-driver scheduling problem

We present new metaheuristics for solving real crew scheduling problemsin a public transportation bus company. Since the crews of thesecompanies are drivers, we will designate the problem by the bus-driverscheduling problem. Crew scheduling problems are well known and severalmathematical programming based techniques have been proposed to solvethem, in particular using the set-covering formulation. However, inpractice, there exists the need for improvement in terms of computationalefficiency and capacity of solving large-scale instances. Moreover, thereal bus-driver scheduling problems that we consider can present variantaspects of the set covering, as for example a different objectivefunction, implying that alternative solutions methods have to bedeveloped. We propose metaheuristics based on the following approaches:GRASP (greedy randomized adaptive search procedure), tabu search andgenetic algorithms. These metaheuristics also present some innovationfeatures based on and genetic algorithms. These metaheuristics alsopresent some innovation features based on the structure of the crewscheduling problem, that guide the search efficiently and able them tofind good solutions. Some of these new features can also be applied inthe development of heuristics to other combinatorial optimizationproblems. A summary of computational results with real-data problems ispresented.