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

Simulated Annealing, High-Order Statistics and Mutual Information for Separation of Sources

In this article, the fusion of a stochastic metaheuristic as Simulated Annealing (SA) with classical criteria for convergence of Blind Separation of Sources (BSS), is shown. Although the topic of BSS, by means of various techniques, including ICA, PCA, and neural networks, has been amply discussed in the literature, to date the possibility of using simulated annealing algorithms has not been seriously explored. From experimental results, this paper demonstrates the possible benefits offered by SA in combination with high order statistical and mutual information criteria for BSS, such as robustness against local minima and a high degree of flexibility in the energy function.

Unconstrained optimization with MINTOOLKIT for GNU octave

The paper documents MINTOOLKIT for GNU Octave. MINTOOLKIT provides functions for minimization and numeric differentiation. The main algorithms are BFGS, LBFGS, and simulated annealing. Examples are given.

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

Reconstruction of networks from their betweenness centrality

In this paper we study the reconstruction of a network topology from the values of its betweenness centrality, a measure of the influence of each of its nodes in the dissemination of information over the network. We consider a simple metaheuristic, simulated annealing, as the combinatorial optimization method to generate the network from the values of the betweenness centrality. We compare the performance of this technique when reconstructing different categories of networks –random, regular, small-world, scale-free and clustered–. We show that the method allows an exact reconstruction of small networks and leads to good topological approximations in the case of networks with larger orders. The method can be used to generate a quasi-optimal topology fora communication network from a list with the values of the maximum allowable traffic for each node.

A Negotiation Style Recommender Based on Computational Ecology in Open Negotiation Environments

The system described herein represents the first example of a recommender system in digital ecosystems where agents negotiate services on behalf of small companies. The small companies compete not only with price or quality, but with a wider service-by-service composition by subcontracting with other companies. The final result of these offerings depends on negotiations at the scale of millions of small companies. This scale requires new platforms for supporting digital business ecosystems, as well as related services like open-id, trust management, monitors and recommenders. This is done in the Open Negotiation Environment (ONE), which is an open-source platform that allows agents, on behalf of small companies, to negotiate and use the ecosystem services, and enables the development of new agent technologies. The methods and tools of cyber engineering are necessary to build up Open Negotiation Environments that are stable, a basic condition for predictable business and reliable business environments. Aiming to build stable digital business ecosystems by means of improved collective intelligence, we introduce a model of negotiation style dynamics from the point of view of computational ecology. This model inspires an ecosystem monitor as well as a novel negotiation style recommender. The ecosystem monitor provides hints to the negotiation style recommender to achieve greater stability of an open negotiation environment in a digital business ecosystem. The greater stability provides the small companies with higher predictability, and therefore better business results. The negotiation style recommender is implemented with a simulated annealing algorithm at a constant temperature, and its impact is shown by applying it to a real case of an open negotiation environment populated by Italian companies

The efficiency of indicator groups for the conservation of amphibians in the Brazilian Atlantic Forest

The adequate selection of indicator groups of biodiversity is an important aspect of the systematic conservation planning. However, these assessments differ in the spatial scale, in the methods used and in the groups considered to accomplish this task, which generally produces contradictory results. The quantification of the spatial congruence between species richness and complementarity among different taxonomic groups is a fundamental step to identify potential indicator groups. Using a constructive approach, the main purposes of this study were to evaluate the performance and efficiency of eight potential indicator groups representing amphibian diversity in the Brazilian Atlantic Forest. Data on the geographic range of amphibian species that occur in the Brazilian Atlantic Forest was overlapped to the full geographic extent of the biome, which was divided into a regular equal-area grid. Optimization routines based on the concept of complementarily were applied to verify the performance of each indicator group selected in relation to the representativeness of the amphibians in the Brazilian Atlantic Forest as a whole, which were solved by the algorithm"simulated annealing", through the use of the software MARXAN. Some indicator groups were substantially more effective than others in regards to the representation of the taxonomic groups assessed, which was confirmed by the high significance of data (F = 312.76; p < 0.01). Leiuperidae was considered as the best indicator group among the families analyzed, as it showed a good performance, representing 71% of amphibian species in the Brazilian Atlantic Forest (i.e. 290 species), which may be associated with the diffuse geographic distribution of its species. This study promotes understanding of how the diversity standards of amphibians can be informative for systematic conservation planning on a regional scale.

Matemàtica i música amb ADN

Treball de recerca realitzat per un alumne d’ensenyament secundari i guardonat amb un Premi CIRIT per fomentar l'esperit científic del Jovent l’any 2005. Estudi sobre l’ADN que té com a finalitat conèixer introductòriament l’utilització del càlcul matemàtic computacional en les investigacions sobre aquest. Els objectius de l’estudi són per una part, conèixer què és l'ADN i quins són els seus mecanismes de duplicació i de transmissió de la informació genètica, així com el paper d'altres molècules que intervenen en aquest procés ; també s’estudia quins han estat els processos de la cèl·lula que l'ésser humà ha estat capaç de copiar o imitar. A partir d’aquesta introducció, es vol conèixer què s'entén concretament per computació amb ADN i alguns dels problemes matemàtics que s'han resolt, així com algunes aplicacions de l'ADN en altres camps. La recerca ha permès arribar a diverses conclusions. Primerament que l'ADN és un excel·lent candidat per poder fer càlculs matemàtics. En segon lloc, tot i que en el present treball no se solucionen problemes computacionalment difícils es mostra la capacitat de les molècules d'ADN per resoldre problemes. En tercer lloc, l'interès mostrat per importants empreses dedicades a la informàtica fa més esperançador que en un futur hi pugui haver ordinadors que funcionin amb molècules d'ADN. Finalment, es demostra que les matemàtiques, la informàtica i la biologia són tres camps que estan interrelacionats. Per tal de trencar una mica amb la serietat del treball, s'acaba descrivint una manera de posar música a les cadenes d'ADN, i es mostren alguns resultats com són les músiques associades als 24 cromosomes humans, així com les corresponents a 29 proteïnes.

Estimation of dynamic latent variable models using simulated nonparametric moments

Given a model that can be simulated, conditional moments at a trial parameter value can be calculated with high accuracy by applying kernel smoothing methods to a long simulation. With such conditional moments in hand, standard method of moments techniques can be used to estimate the parameter. Since conditional moments are calculated using kernel smoothing rather than simple averaging, it is not necessary that the model be simulable subject to the conditioning information that is used to define the moment conditions. For this reason, the proposed estimator is applicable to general dynamic latent variable models. Monte Carlo results show that the estimator performs well in comparison to other estimators that have been proposed for estimation of general DLV models.

Formació de professorat per a una educació matemàtica de familiars en contextos multiculturals

El projecte “Formació de professorat per a una educació matemàtica de familiars en contextos multiculturals” ha consistit en el desenvolupament i anàlisi d’estratègies formatives en matemàtiques per a familiars d’alumnat de primària i secundària. El projecte dóna resposta a la necessitat de donar eines als familiars de l’alumnat per a facilitar-los l’accés a les matemàtiques que estan aprenent els seus fills i filles i poder ajudar-los. D’aquesta manera se superen les distàncies existents entre les matemàtiques que coneixen els pares/les mares i les que s’ensenyen a l’escola, que s’incrementen en el cas de famílies provinents d’altres països, i es contribueix a desenvolupar una educació de qualitat que faciliti l’assoliment d’una igualtat de resultats educatius entre l’alumnat, en el respecte a les diferències entre cultures, i establint lligams entre l’escola i la comunitat. A través del desenvolupament de dos “tallers de matemàtiques” per a familiars, a una escola de primària i a un institut de secundària, i partint del coneixement existent en educació de persones adultes i del diàleg igualitari entre les diferents persones participants, s’han pogut identificar elements rellevants en la formació matemàtica de familiars que faciliten el seu aprenentatge de les matemàtiques, així com estratègies per a ajudar els seus fills/es en l’aprenentatge de les matemàtiques. Partint d’aquestes situacions reals de formació de pares i mares que s’han donat als tallers, s’han creat materials didàctics que poden ser emprats en altres contextos de formació de familiars: per una banda, un recull de materials en format llibre que poden ser emprats per part de professorat que treballi en formació de familiars o pels propis familiars per a treballar amb els seus fills/es; per altra banda, un material audiovisual amb situacions claus que il·lustren estratègies i elements rellevants per a la formació matemàtica de familiars.

La programació al servei de la matemàtica

Treball de recerca realitzat per un alumne d'ensenyament secundari i guardonat amb un Premi CIRIT per fomentar l'esperit cientí­fic del Jovent l'any 2009. La programació al servei de la matemàtica és un programa informàtic fet amb Excel i Visual Basic. Resol equacions de primer grau, equacions de segon grau, sistemes d'equacions lineals de dues equacions i dues incògnites, sistemes d'equacions lineals compatibles determinats de tres equacions i tres incògnites i troba zeros de funcions amb el teorema de Bolzano. En cadascun dels casos, representa les solucions gràficament. Per a això, en el treball s'ha hagut de treballar, en matemàtiques, amb equacions, nombres complexos, la regla de Cramer per a la resolució de sistemes, i buscar la manera de programar un mètode iteratiu pel teorema de Bolzano. En la part gràfica, s'ha resolt com fer taules de valors amb dues i tres variables i treballar amb rectes i plans. Per la part informàtica, s'ha emprat un llenguatge nou per l'alumne i, sobretot, ha calgut saber decidir on posar una determinada instrucció, ja que el fet de variar-ne la posició una sola lí­nea ho pot canviar tot. A més d'això, s'han resolt altres problemes de programació i també s'ha realitzat el disseny de pantalles.

Estimation of dynamic latent variable models using simulated nonparametric moments

Abstract. Given a model that can be simulated, conditional moments at a trial parameter value can be calculated with high accuracy by applying kernel smoothing methods to a long simulation. With such conditional moments in hand, standard method of moments techniques can be used to estimate the parameter. Because conditional moments are calculated using kernel smoothing rather than simple averaging, it is not necessary that the model be simulable subject to the conditioning information that is used to define the moment conditions. For this reason, the proposed estimator is applicable to general dynamic latent variable models. It is shown that as the number of simulations diverges, the estimator is consistent and a higher-order expansion reveals the stochastic difference between the infeasible GMM estimator based on the same moment conditions and the simulated version. In particular, we show how to adjust standard errors to account for the simulations. Monte Carlo results show how the estimator may be applied to a range of dynamic latent variable (DLV) models, and that it performs well in comparison to several other estimators that have been proposed for DLV models.

Les TIC a l'ensenyament de la modelització matemàtica en Ciències Econòmiques i en Ciències Experimentals

Aquest projecte proposa materials didàctics per a un nou plantejament de les assignatures de Matemàtiques dels primers cursos de Ciències Empresarials i d'Enginyeria Tècnica, més acord amb el procés de convergència europea, basat en la realització de projectes que anomenem “Tallers de Modelització Matemàtica” (TMM) en els quals: (1) Els alumnes parteixen de situacions i problemes reals per als quals han de construir per sí mateixos els models matemàtics més adients i, a partir de la manipulació adequada d’aquests models, poden obtenir la informació necessària per donar-los resposta. (2) El treball de construcció, experimentació i avaluació dels models es realitza amb el suport de la calculadora simbòlica Wiris i del full de càlcul Excel com a instruments “normalitzats” del treball matemàtic d’estudiants i professors. (3) S’adapten els programes de les assignatures de matemàtiques de primer curs per tal de poder-les associar a un petit nombre de Tallers que parteixen de situacions adaptades a cada titulació. L’assignatura de Matemàtiques per a les Ciències Empresarials s’articula entorn de dos tallers independents: “Matrius de transició” pel que fa a l’àlgebra lineal i “Previsió de vendes” per a la modelització funcional en una variable. L’assignatura de Matemàtiques per a l’Enginyeria s’articula entorn d’un únic taller, “Models de poblacions”, que abasta la majoria de continguts del curs: successions i models funcionals en una variable, àlgebra lineal i equacions diferencials. Un conjunt d’exercicis interactius basats en la calculadora simbòlica WIRIS (Wiris-player) serveix de suport per al treball tècnic imprescindible per al desenvolupament de les dues assignatures. L’experimentació d’aquests tallers durant 2 cursos consecutius (2006/07 i 2007/08) en dues universitats catalanes (URL i UAB) ha posat en evidència tant els innegables avantatges del nou dispositiu docent per a l’aprenentatge dels estudiants, així com les restriccions institucionals que actualment dificulten la seva gestió i difusió.

Aula matemàtica, 2a. part. : un projecte per a la millora de l'aprenentatge de les matemàtiques a la UAB

El projecte Aula Matemàtica consta de dues parts. 1. Elaborar un material d'autoaprenentatge en suport digital que cobreixi tots els temes de Matemàtiques de 1r. curs de les carreres de Ciències (Biologia, Química, etc.) i les Enginyeries. Aquest material, accessible des de qualsevol ordinador connectat a Internet, és una base de dades de problemes que els alumnes poden utilitzar per a treballar el temes explicats a classe, o be per cobrir deficiències a la seva formació pre-universitària. Al mateix temps, es poden realitzar exàmens, i els alumnes poden practicar amb els problemes d'examen. 2. Durant unes hores cada dia, oferir una (o diverses) aules d'informàtica al campus de la UAB amb presència de personal de suport (professors, o becaris de darrers cursos de matemàtiques o doctorat) per tal que els alumnes que vulguin (o necessitin) puguin practicar amb ajuda, i consultat els dubtes que tinguin. En la fase actual del projecte s’han fet les següents actuacions: 1. S’ha obert una aula d’informàtica amb suport de becaris a la facultat de Ciències, on a més de practicar els alumnes, s’han efectuat exàmens. 2. S’ha treballat en el programa per tal de fer-lo més amigable. 3. S’ha ampliat la base de problemes fins a 1450, i cobrir totes les assignatures de Matemàtiques i Estadística de 1r. curs de la facultat de Ciències i l’Escola Tècnica Superior d’Enginyeries. 4. S’ha començat a treballar per a la utilització del programa a Secundària. 5. S’han fet avanços molt importants per tal d’incorporar problemes amb resposta oberta. 6. El programa és accessible des de qualsevol ordenador amb Internet.

Pla de millora de la docència del Departament de Matemàtica Econòmica, Financera i Actuarial

La finalitat del projecte (bianual 2007-09) era aconseguir una millora de la docència que imparteix el Departament de Matemàtica Econòmica, Financera i Actuarial. La nostra tasca principal ha consistit en obtenir uns indicadors que ens permetessin conèixer millor el nostre alumnat, per tal de tenir la màxima informació a l'hora de plantejar la revisió global que representa la implantació dels nous graus d’acord amb les directrius del procés de Convergència Europea. En aquest projecte han participat tots els coordinadors de les assignatures obligatòries del Departament i els tres Grups d’Innovació Docent formats per membres del Departament. S’han analitzat les dades de les assignatures des del curs 2000-01 fins 2006-07 per tal de tenir informació sobre l’eficàcia de cursar les assignatures d’Introducció a les Matemàtiques i la seva incidència en els aprovats a Matemàtiques I i II . També s’han estudiat dades sobre el col·lectiu de repetidors. Com a resultat d’aquest estudi i de les enquestes que s’han fet, s’han redactat dos articles: “Propuesta de mejora de la actuación docente a partir de las características del alumnado de primer curso de Matemáticas en la Facultad de Economía y Empresa de la Universidad de Barcelona” y “Estudio del perfil del alumnado de primer curso en la Facultad de Economía y Empresa de la Universidad de Barcelona” que s’han presentat a dos congressos d’Innovació Docent (Burgos, setembre-2009 i Vigo, juliol-2009).