Cut-first branch-and-price-second for the capacitated arc-routing problem

This paper presents the first full-fledged branch-and-price (bap) algorithm for the capacitated arc-routing problem (CARP). Prior exact solution techniques either rely on cutting planes or the transformation of the CARP into a node-routing problem. The drawbacks are either models with inherent symmetry, dense underlying networks, or a formulation where edge flows in a potential solution do not allow the reconstruction of unique CARP tours. The proposed algorithm circumvents all these drawbacks by taking the beneficial ingredients from existing CARP methods and combining them in a new way. The first step is the solution of the one-index formulation of the CARP in order to produce strong cuts and an excellent lower bound. It is known that this bound is typically stronger than relaxations of a pure set-partitioning CARP model.rnSuch a set-partitioning master program results from a Dantzig-Wolfe decomposition. In the second phase, the master program is initialized with the strong cuts, CARP tours are iteratively generated by a pricing procedure, and branching is required to produce integer solutions. This is a cut-first bap-second algorithm and its main function is, in fact, the splitting of edge flows into unique CARP tours.

Analisi di celle solari "back contact" mediante simulatore di reti elettriche distribuite basato su spice

Analisi di celle solari mediante simulatore di reti elettriche distribuite basato su Spice

Models and Algorihtm for the Optimization of Real-World Routing and Logistics Problems

Logistics involves planning, managing, and organizing the flows of goods from the point of origin to the point of destination in order to meet some requirements. Logistics and transportation aspects are very important and represent a relevant costs for producing and shipping companies, but also for public administration and private citizens. The optimization of resources and the improvement in the organization of operations is crucial for all branches of logistics, from the operation management to the transportation. As we will have the chance to see in this work, optimization techniques, models, and algorithms represent important methods to solve the always new and more complex problems arising in different segments of logistics. Many operation management and transportation problems are related to the optimization class of problems called Vehicle Routing Problems (VRPs). In this work, we consider several real-world deterministic and stochastic problems that are included in the wide class of the VRPs, and we solve them by means of exact and heuristic methods. We treat three classes of real-world routing and logistics problems. We deal with one of the most important tactical problems that arises in the managing of the bike sharing systems, that is the Bike sharing Rebalancing Problem (BRP). We propose models and algorithms for real-world earthwork optimization problems. We describe the 3DP process and we highlight several optimization issues in 3DP. Among those, we define the problem related to the tool path definition in the 3DP process, the 3D Routing Problem (3DRP), which is a generalization of the arc routing problem. We present an ILP model and several heuristic algorithms to solve the 3DRP.

Creativite langagiere et contact de langues: Le cas du langage sms et chat chez les jeunes camerounais

Résumé L’apparition de l’internet au Cameroun offre une réelle occasion d’échange, surtout pour les jeunes. Les innovations de la toile sont à considérer à plusieurs niveaux, les linguistes sous tous les cieux ont actuellement à débattre du langage SMS et CHAT, qui est, d’après (Dejond ,2002) « un mélange d’anglicisme, d’abréviation, de sigles et de rebus d’écriture phonétique. On écrit comme on parle. » Cette forme d’écriture facile à transcrire est éloignée des normes orthographiques et grammaticales du français standard. En effet, le langage SMS et CHAT des jeunes camerounais n’obéit qu’à la norme dictée par l’imagination de ses adeptes. Il se caractérise par des phénomènes comme la troncation, l’élision vocalique et consonantique ou l’agglutination à l’intérieur des mots. L’un des phénomènes les plus marquants est l’introduction des chiffres allant de 1 à 9 dans la graphie de certains mots. Ces écritures simplifiées nécessitent souvent l’intuition ou la compétence linguistique des lecteurs pour décrypter le message, le but étant l’interprétation du contenu. De plus, le type de message est strictement communicatif ou expressif et non normatif. Ainsi, l’essentiel est de faire passer un message. Les règles, les principes ou les contraintes qui gouvernent la transcription orthographique d’un mot français sont relégués au second plan. L’écriture texto employé par les jeunes camerounais cherche parcimonieusement à en dire le plus avec un minimum de caractère. Pour cela, on chatte entre amis, parents ou avec des connaissances éparpillée de part le monde qui naissent de ces rencontres virtuelles.

On arc-routing problems

Das Basisproblem von Arc-Routing Problemen mit mehreren Fahrzeugen ist das Capacitated Arc-Routing Problem (CARP). Praktische Anwendungen des CARP sind z.B. in den Bereichen Müllabfuhr und Briefzustellung zu finden. Das Ziel ist es, einen kostenminimalen Tourenplan zu berechnen, bei dem alle erforderlichen Kanten bedient werden und gleichzeitig die Fahrzeugkapazität eingehalten wird. In der vorliegenden Arbeit wird ein Cut-First Branch-and-Price Second Verfahren entwickelt. In der ersten Phase werden Schnittebenen generiert, die dem Master Problem in der zweiten Phase hinzugefügt werden. Das Subproblem ist ein kürzeste Wege Problem mit Ressourcen und wird gelöst um neue Spalten für das Master Problem zu liefern. Ganzzahlige CARP Lösungen werden durch ein neues hierarchisches Branching-Schema garantiert. Umfassende Rechenstudien zeigen die Effektivität dieses Algorithmus. Kombinierte Standort- und Arc-Routing Probleme ermöglichen eine realistischere Modellierung von Zustellvarianten bei der Briefzustellung. In dieser Arbeit werden jeweils zwei mathematische Modelle für Park and Loop und Park and Loop with Curbline vorgestellt. Die Modelle für das jeweilige Problem unterscheiden sich darin, wie zulässige Transfer Routen modelliert werden. Während der erste Modelltyp Subtour-Eliminationsbedingungen verwendet, werden bei dem zweiten Modelltyp Flussvariablen und Flusserhaltungsbedingungen eingesetzt. Die Rechenstudie zeigt, dass ein MIP-Solver den zweiten Modelltyp oft in kürzerer Rechenzeit lösen kann oder bei Erreichen des Zeitlimits bessere Zielfunktionswerte liefert.

First contact imaging of nanoparticular siRNA – From synthesis to application of a prodye concept

Delivery of therapeutic nucleic acid based drugs is still very demanding and difficult to manage and monitor. For this reason, a precise method for the monitoring of RNAi pathways is necessary. This thesis explores a new approach for sensing of potentially therapeutic nucleic acids, using the interaction of so called prodyes with intracellular enzymes in a prodrug manner. To realize this concept, some non-fluorescent, fluorescein based asymmetric dyes were synthesized and their spectroscopic characteristics were studied. Azide-alkyne Click chemistry was applied for conjugation purposes, using a new protocol at weak acidic pH to get intact prodye constructs. Both, an electrophoretic mobility shift assay with polyacrylamide gels and in-cuvette experiments showed remarkable OFF-to-ON behavior of these new siRNA constructs under physiological conditions. After salt-free purification, subsequent hybridization to double-stranded ribonucleic acids and nanoformulation to lipoplexes, the prodye conjugated siRNA was examined in cellular uptake studies for First Contact Imaging. The investigated siRNA-prodye conjugates showed strong sensitivity to esterases, being hydrolyzed at the biolabile function and developing a strong fluorescence which was verified in bulk. As an optimization, a new profluorescent molecule system was designed and synthesized, which has a carbonate as biolabile 6’ protecting group and a highly water soluble 3’ clickable linker. This new non-fluorescent but colored prodye showed 12 - 320 times increased fluorescence intensities between OFF- and ON- states, depending to the deprotection method. This is the first reported molecule model of an asymmetric profluorescent fluorescein, having the very favorable 3’ & 6’ functions.

Sperimentazione di protocolli di routing ip su piattaforme raspberry pi.

Tesi mirata allo studio dei protocolli di routing IP utilizzati per l'inoltro dei pacchetti in una topologia non banale. Sono state utilizzate macchine Linux Raspberry Pi per il loro costo e ingombro per costruire la rete. In particolare, è stata implementata una rete caratterizzata da sette router divisi in tre aree distinte, ai quali sono state connesse sette LAN. Si è installato e utilizzato il software quagga per attivare il protocollo OSPF (Open Shortest Path First). Per limitare i dispositivi fisici si è utilizzato il software Mininet per virtualizzare switch e LAN. Infine, sono stati trattati elementi teorici del routing su Internet, applicati alla rete creata per verificarne il funzionamento.

GSR deposition along the bullet path in contact shots to composite models

In contact shots, all the materials emerging from the muzzle (combustion gases, soot, powder grains, and metals from the primer) will be driven into the depth of the entrance wound and the following sections of the bullet track. The so-called "pocket" ("powder cavity") under the skin containing soot and gunpowder particles is regarded as a significant indicator of a contact entrance wound since one would expect that the quantity of GSR deposited along the bullet's path rapidly declines towards the exit hole. Nevertheless, experience has shown that soot, powder particles, and carboxyhemoglobin may be found not only in the initial part of the wound channel, but also far away from the entrance and even at the exit. In order to investigate the propagation of GSRs under standardized conditions, contact test shots were fired against composite models of pig skin and 25-cm-long gelatin blocks using 9-mm Luger pistol cartridges with two different primers (Sinoxid® and Sintox®). Subsequently, 1-cm-thick layers of the gelatin blocks were examined as to their primer element contents (lead, barium, and antimony as discharge residues of Sinoxid® as well as zinc and titanium from Sintox®) by means of X-ray fluorescence spectroscopy. As expected, the highest element concentrations were found in the initial parts of the bullet tracks, but also the distal sections contained detectable amounts of the respective primer elements. The same was true for amorphous soot and unburned/partly burned powder particles, which could be demonstrated even at the exit site. With the help of a high-speed motion camera it was shown that for a short time the temporary cavitation extends from the entrance to the exit thus facilitating the unlimited spread of discharge residues along the whole bullet path.

Predicting the pathogen of diabetic toe osteomyelitis by two consecutive ulcer cultures with bone contact

In this study, we investigate the accuracy of two consecutive ulcer cultures with bone contact compared to bone biopsy for the diagnosis of diabetic toe osteomyelitis. The same nurse and orthopaedic surgeon obtained all samples: sample A-1: bone contact swabbing through the ulcer; sample A-2: a second culture swabbing from the bone surface within 24 h; sample B: surgical bone biopsy in the operating theatre. The kappa statistic measure between samples A-1 and A-2 (bone contact swabs) indicated 82.35% agreement. The sensitivity, specificity, positive and negative predictive values of the two samples A compared to B were 96%, 79%, 92% and 88%, respectively, for the causative pathogen. These results were similar with prior antibiotic treatment, discordant bone surface swabs or with monomicrobial infections. As a conclusion, two consecutive diabetic toe cultures with bone contact accurately predict the pathogen of diabetic toe osteomyelitis in 90% of cases.

Nano-stenciled RGD-gold patterns that inhibit focal contact maturation induce lamellipodia formation in fibroblasts

Cultured fibroblasts adhere to extracellular substrates by means of cell-matrix adhesions that are assembled in a hierarchical way, thereby gaining in protein complexity and size. Here we asked how restricting the size of cell-matrix adhesions affects cell morphology and behavior. Using a nanostencil technique, culture substrates were patterned with gold squares of a width and spacing between 250 nm and 2 µm. The gold was functionalized with RGD peptide as ligand for cellular integrins, and mouse embryo fibroblasts were plated. Limiting the length of cell-matrix adhesions to 500 nm or less disturbed the maturation of vinculin-positive focal complexes into focal contacts and fibrillar adhesions, as indicated by poor recruitment of ?5-integrin. We found that on sub-micrometer patterns, fibroblasts spread extensively, but did not polarize. Instead, they formed excessive numbers of lamellipodia and a fine actin meshwork without stress fibers. Moreover, these cells showed aberrant fibronectin fibrillogenesis, and their speed of directed migration was reduced significantly compared to fibroblasts on 2 µm square patterns. Interference with RhoA/ROCK signaling eliminated the pattern-dependent differences in cell morphology. Our results indicate that manipulating the maturation of cell-matrix adhesions by nanopatterned surfaces allows to influence morphology, actin dynamics, migration and ECM assembly of adhering fibroblasts.