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.

Methodische Grundlagen zur Bewahrung und Wiederherstellung großräumig funktionsfähiger ökologischer Beziehungen in der räumlichen Umweltplanung

Mit der Verwirklichung ,Ökologischer Netzwerke‘ werden Hoffnungen zum Stopp des Verlustes der biologischen Vielfalt verknüpft. Sowohl auf gesamteuropäischer Ebene (Pan-European Ecological Network - PEEN) als auch in den einzelnen Staaten entstehen Pläne zum Aufbau von Verbundsystemen. Im föderalen Deutschland werden kleinmaßstäbliche Biotopverbundplanungen auf Landesebene aufgestellt; zum nationalen Biotopverbund bestehen erste Konzepte. Die vorliegende Arbeit ist auf diese überörtlichen, strategisch vorbereitenden Planungsebenen ausgerichtet. Ziele des Verbunds sind der Erhalt von Populationen insbesondere der gefährdeten Arten sowie die Ermöglichung von Ausbreitung und Wanderung. Aufgrund fehlender Datengrundlagen zu den Arten und Populationen ist es nicht ohne weiteres möglich, die Konzepte und Modelle der Populationsökologie in die überörtlichen Planungsebenen zu übertragen. Gemäß der o.g. Zielstellungen sollte sich aber die Planung von Verbundsystemen an den Ansprüchen der auf Verbund angewiesenen Arten orientieren. Ziel der Arbeit war die Entwicklung einer praktikablen GIS-gestützten Planungshilfe zur größtmöglichen Integration ökologischen Wissens unter der Bedingung eingeschränkter Informationsverfügbarkeit. Als Grundlagen dazu werden in Übersichtsform zunächst die globalen, europäisch-internationalen und nationalen Rahmenbedingungen und Anforderungen bezüglich des Aufbaus von Verbundsystemen zusammengestellt. Hier sind die Strategien zum PEEN hervorzuheben, die eine Integration ökologischer Inhalte insbesondere durch die Berücksichtigung räumlich-funktionaler Beziehungen fordern. Eine umfassende Analyse der landesweiten Biotopverbundplanungen der BRD zeigte die teilweise erheblichen Unterschiede zwischen den Länderplanungen auf, die es aktuell nicht ermöglichen, ein schlüssiges nationales Konzept zusammenzufügen. Nicht alle Länder haben landesweite Biotopverbundplanungen und Landeskonzepte, bei denen dem geplanten Verbund die Ansprüche von Arten zugrunde gelegt werden, gibt es nur ansatzweise. Weiterhin wurde eine zielgerichtete Eignungsprüfung bestehender GIS-basierter Modelle und Konzepte zum Verbund unter Berücksichtigung der regelmäßig in Deutschland verfügbaren Datengrundlagen durchgeführt. Da keine integrativen regelorientierten Ansätze vorhanden waren, wurde der vektorbasierte Algorithmus HABITAT-NET entwickelt. Er arbeitet mit ,Anspruchstypen‘ hinsichtlich des Habitatverbunds, die stellvertretend für unterschiedliche ökologische Gruppen von (Ziel-) Arten mit terrestrischer Ausbreitung stehen. Kombiniert wird die Fähigkeit zur Ausbreitung mit einer Grobtypisierung der Biotopbindung. Die wichtigsten Grundlagendaten bilden die jeweiligen (potenziellen) Habitate von Arten eines Anspruchstyps sowie die umgebende Landnutzung. Bei der Bildung von ,Lebensraumnetzwerken‘ (Teil I) werden gestufte ,Funktions- und Verbindungsräume‘ generiert, die zu einem räumlichen System verknüpft sind. Anschließend kann die aktuelle Zerschneidung der Netzwerke durch Verkehrstrassen aufgezeigt werden, um darauf aufbauend prioritäre Abschnitte zur Wiedervernetzung zu ermitteln (Teil II). Begleitend wird das Konzept der unzerschnittenen Funktionsräume (UFR) entworfen, mit dem die Indikation von Habitatzerschneidung auf Landschaftsebene möglich ist. Diskutiert werden schließlich die Eignung der Ergebnisse als kleinmaßstäblicher Zielrahmen, Tests zur Validierung, Vergleiche mit Verbundplanungen und verschiedene Setzungen im GIS-Algorithmus. Erläuterungen zu den Einsatzmöglichkeiten erfolgen beispielsweise für die Bereiche Biotopverbund- und Landschaftsplanung, Raumordnung, Strategische Umweltprüfung, Verkehrswegeplanung, Unterstützung des Konzeptes der Lebensraumkorridore, Kohärenz im Schutzgebietssystem NATURA 2000 und Aufbau von Umweltinformationssystemen. Schließlich wird ein Rück- und Ausblick mit der Formulierung des weiteren Forschungsbedarfs verknüpft.

Towards Direct Policy Search Reinforcement Learning for Robot Control

This paper proposes a high-level reinforcement learning (RL) control system for solving the action selection problem of an autonomous robot. Although the dominant approach, when using RL, has been to apply value function based algorithms, the system here detailed is characterized by the use of direct policy search methods. Rather than approximating a value function, these methodologies approximate a policy using an independent function approximator with its own parameters, trying to maximize the future expected reward. The policy based algorithm presented in this paper is used for learning the internal state/action mapping of a behavior. In this preliminary work, we demonstrate its feasibility with simulated experiments using the underwater robot GARBI in a target reaching task

Optimización del sistema de transporte en el colegio The English School

La optimización de sistemas y modelos se ha convertido en uno de los factores más importantes a la hora de buscar la mayor eficiencia de un proceso. Este concepto no es ajeno al transporte escolar, ambiente que cambia constantemente al ritmo de las necesidades de sus clientes, y que responde ante una fuerte responsabilidad frente a sus usuarios, los niños que hacen uso del servicio, en cuanto al cumplimiento de tiempos y seguridad, mientras busca constantemente la reducción de costos. Este proyecto expone las problemáticas presentadas en The English School en esta área y propone un modelo de optimización simple que permitirá notables mejoras en términos de tiempos y costos, de tal forma que genere beneficios para la institución en términos financieros y de satisfacción al cliente. Por medio de la implementación de este modelo será posible identificar errores comunes del proceso, se identificarán soluciones prácticas de fácil aplicación en el manejo del transporte y se presentarán los resultados obtenidos en la muestra utilizada para desarrollar el proyecto.

Analysis and compensation of power amplifier nonlinearity in MIMO transmit diversity systems

The nonlinearity of high-power amplifiers (HPAs) has a crucial effect on the performance of multiple-input-multiple-output (MIMO) systems. In this paper, we investigate the performance of MIMO orthogonal space-time block coding (OSTBC) systems in the presence of nonlinear HPAs. Specifically, we propose a constellation-based compensation method for HPA nonlinearity in the case with knowledge of the HPA parameters at the transmitter and receiver, where the constellation and decision regions of the distorted transmitted signal are derived in advance. Furthermore, in the scenario without knowledge of the HPA parameters, a sequential Monte Carlo (SMC)-based compensation method for the HPA nonlinearity is proposed, which first estimates the channel-gain matrix by means of the SMC method and then uses the SMC-based algorithm to detect the desired signal. The performance of the MIMO-OSTBC system under study is evaluated in terms of average symbol error probability (SEP), total degradation (TD) and system capacity, in uncorrelated Nakagami-m fading channels. Numerical and simulation results are provided and show the effects on performance of several system parameters, such as the parameters of the HPA model, output back-off (OBO) of nonlinear HPA, numbers of transmit and receive antennas, modulation order of quadrature amplitude modulation (QAM), and number of SMC samples. In particular, it is shown that the constellation-based compensation method can efficiently mitigate the effect of HPA nonlinearity with low complexity and that the SMC-based detection scheme is efficient to compensate for HPA nonlinearity in the case without knowledge of the HPA parameters.

Multiresolution semantic activity characterisation and abnormality discovery in videos

This paper addresses the issue of activity understanding from video and its semantics-rich description. A novel approach is presented where activities are characterised and analysed at different resolutions. Semantic information is delivered according to the resolution at which the activity is observed. Furthermore, the multiresolution activity characterisation is exploited to detect abnormal activity. To achieve these system capabilities, the focus is given on context modelling by employing a soft computing-based algorithm which automatically enables the determination of the main activity zones of the observed scene by taking as input the trajectories of detected mobiles. Such areas are learnt at different resolutions (or granularities). In a second stage, learned zones are employed to extract people activities by relating mobile trajectories to the learned zones. In this way, the activity of a person can be summarised as the series of zones that the person has visited. Employing the inherent soft relation properties, the reported activities can be labelled with meaningful semantics. Depending on the granularity at which activity zones and mobile trajectories are considered, the semantic meaning of the activity shifts from broad interpretation to detailed description.Activity information at different resolutions is also employed to perform abnormal activity detection.

Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Identifying Heel Contact and Toe-Off Using Forceplate Thresholds With a Range of Digital-Filter Cutoff Frequencies

Analysis of human gait requires accurate measurement of foot-ground contact, often determined using either foot-ground reaction force thresholds or kinematic data. This study examined the differences in calculating event times across five vertical force thresholds and validated a vertical acceleration-based algorithm as a measure of heel contact and toe-off.

Linear causal model discovery using the MML criterion

Determining the causal structure of a domain is a key task in the area of Data Mining and Knowledge Discovery.The algorithm proposed by Wallace et al. [15] has demonstrated its strong ability in discovering Linear Causal Models from given data sets. However, some experiments showed that this algorithm experienced difficulty in discovering linear relations with small deviation, and it occasionally gives a negative message length, which should not be allowed. In this paper, a more efficient and precise MML encoding scheme is proposed to describe the model structure and the nodes in a Linear Causal Model. The estimation of different parameters is also derived. Empirical results show that the new algorithm outperformed the previous MML-based algorithm in terms of both speed and precision.

Concept learning of text documents

Concept learning of text documents can be viewed as the problem of acquiring the definition of a general category of documents. To definite the category of a text document, the Conjunctive of keywords is usually be used. These keywords should be fewer and comprehensible. A naïve method is enumerating all combinations of keywords to extract suitable ones. However, because of the enormous number of keyword combinations, it is impossible to extract the most relevant keywords to describe the categories of documents by enumerating all possible combinations of keywords. Many heuristic methods are proposed, such as GA-base, immune based algorithm. In this work, we introduce pruning power technique and propose a robust enumeration-based concept learning algorithm. Experimental results show that the rules produce by our approach has more comprehensible and simplicity than by other methods.

Route maintenance using mobility prediction for mobile ad hoc networks

Next generation networks (3G & beyond) will support real-time multimedia applications through traditional wide-area networking concepts as well as hot-spot (WLAN) and ad hoc networking concepts. In order to fulfill the vision of next generation networks a method of maintaining a real-time flow despite frequent topology changes and irregularity in user movement is required. Mobility prediction has been identified as having applications in the areas of link availability estimation and pro-active routing in ad hoc networks. In this work we present the mobility prediction based algorithm for route maintenance in mobile ad hoc networks. Simulation study of the algorithm proves it to offer significant benefits to dynamic source routing (DSR)

Finding edging genes from microarray data

Motivation: A set of genes and their gene expression levels are used to classify disease and normal tissues. Due to the massive number of genes in microarray, there are a large number of edges to divide different classes of genes in microarray space. The edging genes (EGs) can be co-regulated genes, they can also be on the same pathway or deregulated by the same non-coding genes, such as siRNA or miRNA. Every gene in EGs is vital for identifying a tissue's class. The changing in one EG's gene expression may cause a tissue alteration from normal to disease and vice versa. Finding EGs is of biological importance. In this work, we propose an algorithm to effectively find these EGs.

Result: We tested our algorithm with five microarray datasets. The results are compared with the border-based algorithm which was used to find gene groups and subsequently divide different classes of tissues. Our algorithm finds a significantly larger amount of EGs than does the border-based algorithm. As our algorithm prunes irrelevant patterns at earlier stages, time and space complexities are much less prevalent than in the border-based algorithm.

Blind separation of mutually correlated sources using precoders

This paper studies the problem of blind source separation (BSS) from instantaneous mixtures with the assumption that the source signals are mutually correlated.We propose a novel approach to BSS by using precoders in transmitters.We show that if the precoders are properly designed, some cross-correlation coefficients of the coded signals can be forced to be zero at certain time lags. Then, the unique correlation properties of the coded signals can be exploited in receiver to achieve source separation. Based on the proposed precoders, a subspace-based algorithm is derived for the blind separation of mutually correlated sources. The effectiveness of the algorithm is illustrated by simulation examples.

AdaBoost.MRF: boosted Markov random forests and application to multilevel activity recognition

Activity recognition is an important issue in building intelligent monitoring systems. We address the recognition of multilevel activities in this paper via a conditional Markov random field (MRF), known as the dynamic conditional random field (DCRF). Parameter estimation in general MRFs using maximum likelihood is known to be computationally challenging (except for extreme cases), and thus we propose an efficient boosting-based algorithm AdaBoost.MRF for this task. Distinct from most existing work, our algorithm can handle hidden variables (missing labels) and is particularly attractive for smarthouse domains where reliable labels are often sparsely observed. Furthermore, our method works exclusively on trees and thus is guaranteed to converge. We apply the AdaBoost.MRF algorithm to a home video surveillance application and demonstrate its efficacy.

Zeroes of Riemann's zeta function on the critical line with 20000 decimal digits accuracy

The first 12000 zeroes of Riemann's zeta function on the critical line with 20000 decimal digits accuracy. Format: the zeroes are in text file listed consecutively in decimal representation, each zero starts on a new line.

Zeroes of zeta function presented in this file were calculated on MASSIVE cluster (www.massive.org.au) using Python and packages MPmath version 0.17 and gmpy version 2.1, with a Newton based algorithm proposed by Fredrik Johansson with precision set to 20000 decimal digits. Partial recalculation with higher precision didn't show any loss of accuracy so we expect that the values are correct up to, possibly, a few last digits. We express our thanks to Fredrik Johansson for this algorithm and for development of MPmath as well.