Decomposition and reformulation of integer linear programming problems

This thesis deals with an investigation of Decomposition and Reformulation to solve Integer Linear Programming Problems. This method is often a very successful approach computationally, producing high-quality solutions for well-structured combinatorial optimization problems like vehicle routing, cutting stock, p-median and generalized assignment . However, until now the method has always been tailored to the specific problem under investigation. The principal innovation of this thesis is to develop a new framework able to apply this concept to a generic MIP problem. The new approach is thus capable of auto-decomposition and autoreformulation of the input problem applicable as a resolving black box algorithm and works as a complement and alternative to the normal resolving techniques. The idea of Decomposing and Reformulating (usually called in literature Dantzig and Wolfe Decomposition DWD) is, given a MIP, to convexify one (or more) subset(s) of constraints (slaves) and working on the partially convexified polyhedron(s) obtained. For a given MIP several decompositions can be defined depending from what sets of constraints we want to convexify. In this thesis we mainly reformulate MIPs using two sets of variables: the original variables and the extended variables (representing the exponential extreme points). The master constraints consist of the original constraints not included in any slaves plus the convexity constraint(s) and the linking constraints(ensuring that each original variable can be viewed as linear combination of extreme points of the slaves). The solution procedure consists of iteratively solving the reformulated MIP (master) and checking (pricing) if a variable of reduced costs exists, and in which case adding it to the master and solving it again (columns generation), or otherwise stopping the procedure. The advantage of using DWD is that the reformulated relaxation gives bounds stronger than the original LP relaxation, in addition it can be incorporated in a Branch and bound scheme (Branch and Price) in order to solve the problem to optimality. If the computational time for the pricing problem is reasonable this leads in practice to a stronger speed up in the solution time, specially when the convex hull of the slaves is easy to compute, usually because of its special structure.

Modeling and simulation of a synthetic genetic circuit that implements a multicelled behavior in a growing microcolony of E. coli

Synthetic Biology is a relatively new discipline, born at the beginning of the New Millennium, that brings the typical engineering approach (abstraction, modularity and standardization) to biotechnology. These principles aim to tame the extreme complexity of the various components and aid the construction of artificial biological systems with specific functions, usually by means of synthetic genetic circuits implemented in bacteria or simple eukaryotes like yeast. The cell becomes a programmable machine and its low-level programming language is made of strings of DNA. This work was performed in collaboration with researchers of the Department of Electrical Engineering of the University of Washington in Seattle and also with a student of the Corso di Laurea Magistrale in Ingegneria Biomedica at the University of Bologna: Marilisa Cortesi. During the collaboration I contributed to a Synthetic Biology project already started in the Klavins Laboratory. In particular, I modeled and subsequently simulated a synthetic genetic circuit that was ideated for the implementation of a multicelled behavior in a growing bacterial microcolony. In the first chapter the foundations of molecular biology are introduced: structure of the nucleic acids, transcription, translation and methods to regulate gene expression. An introduction to Synthetic Biology completes the section. In the second chapter is described the synthetic genetic circuit that was conceived to make spontaneously emerge, from an isogenic microcolony of bacteria, two different groups of cells, termed leaders and followers. The circuit exploits the intrinsic stochasticity of gene expression and intercellular communication via small molecules to break the symmetry in the phenotype of the microcolony. The four modules of the circuit (coin flipper, sender, receiver and follower) and their interactions are then illustrated. In the third chapter is derived the mathematical representation of the various components of the circuit and the several simplifying assumptions are made explicit. Transcription and translation are modeled as a single step and gene expression is function of the intracellular concentration of the various transcription factors that act on the different promoters of the circuit. A list of the various parameters and a justification for their value closes the chapter. In the fourth chapter are described the main characteristics of the gro simulation environment, developed by the Self Organizing Systems Laboratory of the University of Washington. Then, a sensitivity analysis performed to pinpoint the desirable characteristics of the various genetic components is detailed. The sensitivity analysis makes use of a cost function that is based on the fraction of cells in each one of the different possible states at the end of the simulation and the wanted outcome. Thanks to a particular kind of scatter plot, the parameters are ranked. Starting from an initial condition in which all the parameters assume their nominal value, the ranking suggest which parameter to tune in order to reach the goal. Obtaining a microcolony in which almost all the cells are in the follower state and only a few in the leader state seems to be the most difficult task. A small number of leader cells struggle to produce enough signal to turn the rest of the microcolony in the follower state. It is possible to obtain a microcolony in which the majority of cells are followers by increasing as much as possible the production of signal. Reaching the goal of a microcolony that is split in half between leaders and followers is comparatively easy. The best strategy seems to be increasing slightly the production of the enzyme. To end up with a majority of leaders, instead, it is advisable to increase the basal expression of the coin flipper module. At the end of the chapter, a possible future application of the leader election circuit, the spontaneous formation of spatial patterns in a microcolony, is modeled with the finite state machine formalism. The gro simulations provide insights into the genetic components that are needed to implement the behavior. In particular, since both the examples of pattern formation rely on a local version of Leader Election, a short-range communication system is essential. Moreover, new synthetic components that allow to reliably downregulate the growth rate in specific cells without side effects need to be developed. In the appendix are listed the gro code utilized to simulate the model of the circuit, a script in the Python programming language that was used to split the simulations on a Linux cluster and the Matlab code developed to analyze the data.

Application Platforms for the Internet of Things: Theory, Architecture, Protocols, Data Formats, and Privacy

The Internet of Things (IoT) is the next industrial revolution: we will interact naturally with real and virtual devices as a key part of our daily life. This technology shift is expected to be greater than the Web and Mobile combined. As extremely different technologies are needed to build connected devices, the Internet of Things field is a junction between electronics, telecommunications and software engineering. Internet of Things application development happens in silos, often using proprietary and closed communication protocols. There is the common belief that only if we can solve the interoperability problem we can have a real Internet of Things. After a deep analysis of the IoT protocols, we identified a set of primitives for IoT applications. We argue that each IoT protocol can be expressed in term of those primitives, thus solving the interoperability problem at the application protocol level. Moreover, the primitives are network and transport independent and make no assumption in that regard. This dissertation presents our implementation of an IoT platform: the Ponte project. Privacy issues follows the rise of the Internet of Things: it is clear that the IoT must ensure resilience to attacks, data authentication, access control and client privacy. We argue that it is not possible to solve the privacy issue without solving the interoperability problem: enforcing privacy rules implies the need to limit and filter the data delivery process. However, filtering data require knowledge of how the format and the semantics of the data: after an analysis of the possible data formats and representations for the IoT, we identify JSON-LD and the Semantic Web as the best solution for IoT applications. Then, this dissertation present our approach to increase the throughput of filtering semantic data by a factor of ten.

The APSEL4D Monolithic Active Pixel Sensor and its Usage in a Single Electron Interference Experiment

We have realized a Data Acquisition chain for the use and characterization of APSEL4D, a 32 x 128 Monolithic Active Pixel Sensor, developed as a prototype for frontier experiments in high energy particle physics. In particular a transition board was realized for the conversion between the chip and the FPGA voltage levels and for the signal quality enhancing. A Xilinx Spartan-3 FPGA was used for real time data processing, for the chip control and the communication with a Personal Computer through a 2.0 USB port. For this purpose a firmware code, developed in VHDL language, was written. Finally a Graphical User Interface for the online system monitoring, hit display and chip control, based on windows and widgets, was realized developing a C++ code and using Qt and Qwt dedicated libraries. APSEL4D and the full acquisition chain were characterized for the first time with the electron beam of the transmission electron microscope and with 55Fe and 90Sr radioactive sources. In addition, a beam test was performed at the T9 station of the CERN PS, where hadrons of momentum of 12 GeV/c are available. The very high time resolution of APSEL4D (up to 2.5 Mfps, but used at 6 kfps) was fundamental in realizing a single electron Young experiment using nanometric double slits obtained by a FIB technique. On high statistical samples, it was possible to observe the interference and diffractions of single isolated electrons traveling inside a transmission electron microscope. For the first time, the information on the distribution of the arrival time of the single electrons has been extracted.

Identity dynamics and the emergence of new organizational arrangements: A multi-level study

Organizational and institutional scholars have advocated the need to examine how processes originating at an individual level can change organizations or even create new organizational arrangements able to affect institutional dynamics (Chreim et al., 2007; Powell & Colyvas, 2008; Smets et al., 2012). Conversely, research on identity work has mainly investigated the different ways individuals can modify the boundaries of their work in actual occupations, thus paying particular attention to ‘internal’ self-crafting (e.g. Wrzesniewski & Dutton, 2001). Drawing from literatures on possible and alternative self and on positive organizational scholarship (e.g., Obodaru, 2012; Roberts & Dutton, 2009), my argument is that individuals’ identity work can go well beyond the boundaries of internal self-crafting to the creation of new organizational arrangements. In this contribution I analyze, through multiple case studies, healthcare professionals who spontaneously participated in the creation of new organizational arrangements, namely health structures called Community Hospitals. The contribution develops this form of identity work by building a grounded model. My findings disclose the process that leads from the search for the enactment of different self-concepts to positive identities, through the creation of a new organizational arrangement. I contend that this is a particularly complex form of collective identity work because it requires, to be successful, concerted actions of several internal, external and institutional actors, and it also requires balanced tensions that – at the same time - enable individuals’ aspirations and organizational equilibrium. I name this process organizational collective crafting. Moreover I inquire the role of context in supporting the triggering power of those unrealized selves. I contribute to the comprehension of the consequences of self-comparisons, organizational identity variance, and positive identity. The study bears important insights on how identity work originating from individuals can influence organizational outcomes and larger social systems.

Shikonin directly targets mitochondria and causes mitochondrial dysfunction in cancer cells

Chemotherapy is a mainstay of cancer treatment. Due to increased drug resistance and the severe side effects of currently used therapeutics, new candidate compounds are required for improvement of therapy success. Shikonin, a natural naphthoquinone, was used in traditional Chinese medicine for the treatment of different inflammatory diseases and recent studies revealed the anticancer activities of shikonin. We found that shikonin has strong cytotoxic effects on 15 cancer cell lines, including multidrug-resistant cell lines. Transcriptome-wide mRNA expression studies showed that shikonin induced genetic pathways regulating cell cycle, mitochondrial function, levels of reactive oxygen species, and cytoskeletal formation. Taking advantage of the inherent fluorescence of shikonin, we analyzed its uptake and distribution in live cells with high spatial and temporal resolution using flow cytometry and confocal microscopy. Shikonin was specifically accumulated in the mitochondria, and this accumulation was associated with a shikonin-dependent deregulation of cellular Ca(2+) and ROS levels. This deregulation led to a breakdown of the mitochondrial membrane potential, dysfunction of microtubules, cell-cycle arrest, and ultimately induction of apoptosis. Seeing as both the metabolism and the structure of mitochondria show marked differences between cancer cells and normal cells, shikonin is a promising candidate for the next generation of chemotherapy.

Modelling and analysis of networked control strategies in smart power distribution grids: development of co-simulation tools

This thesis is focused on Smart Grid applications in medium voltage distribution networks. For the development of new applications it appears useful the availability of simulation tools able to model dynamic behavior of both the power system and the communication network. Such a co-simulation environment would allow the assessment of the feasibility of using a given network technology to support communication-based Smart Grid control schemes on an existing segment of the electrical grid and to determine the range of control schemes that different communications technologies can support. For this reason, is presented a co-simulation platform that has been built by linking the Electromagnetic Transients Program Simulator (EMTP v3.0) with a Telecommunication Network Simulator (OPNET-Riverbed v18.0). The simulator is used to design and analyze a coordinate use of Distributed Energy Resources (DERs) for the voltage/var control (VVC) in distribution network. This thesis is focused control structure based on the use of phase measurement units (PMUs). In order to limit the required reinforcements of the communication infrastructures currently adopted by Distribution Network Operators (DNOs), the study is focused on leader-less MAS schemes that do not assign special coordinating rules to specific agents. Leader-less MAS are expected to produce more uniform communication traffic than centralized approaches that include a moderator agent. Moreover, leader-less MAS are expected to be less affected by limitations and constraint of some communication links. The developed co-simulator has allowed the definition of specific countermeasures against the limitations of the communication network, with particular reference to the latency and loss and information, for both the case of wired and wireless communication networks. Moreover, the co-simulation platform has bee also coupled with a mobility simulator in order to study specific countermeasures against the negative effects on the medium voltage/current distribution network caused by the concurrent connection of electric vehicles.

'Alternate-goal bias' in antisaccades and the influence of expectation

Saccadic performance depends on the requirements of the current trial, but also may be influenced by other trials in the same experiment. This effect of trial context has been investigated most for saccadic error rate and reaction time but seldom for the positional accuracy of saccadic landing points. We investigated whether the direction of saccades towards one goal is affected by the location of a second goal used in other trials in the same experimental block. In our first experiment, landing points ('endpoints') of antisaccades but not prosaccades were shifted towards the location of the alternate goal. This spatial bias decreased with increasing angular separation between the current and alternative goals. In a second experiment, we explored whether expectancy about the goal location was responsible for the biasing of the saccadic endpoint. For this, we used a condition where the saccadic goal randomly changed from one trial to the next between locations on, above or below the horizontal meridian. We modulated the prior probability of the alternate-goal location by showing cues prior to stimulus onset. The results showed that expectation about the possible positions of the saccadic goal is sufficient to bias saccadic endpoints and can account for at least part of this phenomenon of 'alternate-goal bias'.

Differences in the quality of interpersonal care in complementary and conventional medicine

The study was part of a nationwide evaluation of complementary and alternative medicine (CAM) in Swiss primary care. The aim of the study was to compare patient-physician relationships and the respective patient-reported relief of symptoms between CAM and conventional primary care (COM).

Complementary medicine courses in Swiss medical schools: actual status and students' experience

In line with growing public popularity of complementary and alternative medicine (CAM), courses in CAM have been implemented in Medical Schools internationally, but as yet in an uncoordinated and heterogeneous way. In Switzerland, comprehensive data about CAM education at Medical Faculties are lacking.

Mobile phone technologies and advanced data analysis towards the enhancement of diabetes self-management

Advances in the area of mobile and wireless communication for healthcare (m-Health) along with the improvements in information science allow the design and development of new patient-centric models for the provision of personalised healthcare services, increase of patient independence and improvement of patient's self-control and self-management capabilities. This paper comprises a brief overview of the m-Health applications towards the self-management of individuals with diabetes mellitus and the enhancement of their quality of life. Furthermore, the design and development of a mobile phone application for Type 1 Diabetes Mellitus (T1DM) self-management is presented. The technical evaluation of the application, which permits the management of blood glucose measurements, blood pressure measurements, insulin dosage, food/drink intake and physical activity, has shown that the use of the mobile phone technologies along with data analysis methods might improve the self-management of T1DM.

[Drug therapy of acute and chronic abdominal pain]

For drug therapy a differentiation of acute and chronic pain is essential. In emergency situations of acute abdominal pain a fast diagnosis is mandatory. Analgesia should be provided as soon as possible. The different groups of analgesics should be used according to their known effects, side effects and contraindications. Postoperative pain after abdominal surgery has to be considered as a special condition of acute abdominal pain. Main treatment options are non opioid analgesics and opioids. Opioids can be administered intravenously via patient controlled analgesia (PCA) devices. In major abdominal surgery neuroaxial analgesia, preferentially administered via an epidural catheter provides excellent pain relief with positive impact on gastrointestinal motility and patients' recovery. Because of difficulties to allocate chronic abdominal pain to a specific organ, causal treatment often turns out to be difficult. Peripheral and central sensitization, as well as an alteration of the endogenous pain modulation comes to the fore in these chronic pain conditions. Co-analgesics like anticonvulsants and antidepressants are utilized to reduce sensitization and improve the endogenous pain modulating system. Non drug approaches and alternative treatment options might be useful. In contrast, orally or transcutaneously administered opioids are the principal corner stone for the treatment of cancer pain.

Homeopathic Preparations of Quartz, Sulfur and Copper Sulfate Assessed by UV-Spectroscopy

Homeopathic preparations are used in homeopathy and anthroposophic medicine. Although there is evidence of effectiveness in several clinical studies, including double-blinded randomized controlled trials, their nature and mode of action could not be explained with current scientific approaches yet. Several physical methods have already been applied to investigate homeopathic preparations but it is yet unclear which methods are best suited to identify characteristic physicochemical properties of homeopathic preparations. The aim of this study was to investigate homeopathic preparations with UV-spectroscopy. In a blinded, randomized, controlled experiment homeopathic preparations of copper sulfate (CuSO(4); 11c-30c), quartz (SiO(2); 10c-30c, i.e., centesimal dilution steps) and sulfur (S; 11×-30×, i.e., decimal dilution steps) and controls (one-time succussed diluent) were investigated using UV-spectroscopy and tested for contamination by inductively coupled plasma mass spectrometry (ICP-MS). The UV transmission for homeopathic preparations of CuSO(4) preparations was significantly lower than in controls. The transmission seemed to be also lower for both SiO(2) and S, but not significant. The mean effect size (95% confidence interval) was similar for the homeopathic preparations: CuSO(4) (pooled data) 0.0544% (0.0260-0.0827%), SiO(2) 0.0323% (-0.0064% to 0.0710%) and S 0.0281% (-0.0520% to 0.1082%). UV transmission values of homeopathic preparations had a significantly higher variability compared to controls. In none of the samples the concentration of any element analyzed by ICP-MS exceeded 100 ppb. Lower transmission of UV light may indicate that homeopathic preparations are less structured or more dynamic than their succussed pure solvent.

Similarities and differences between physician and non-physician acupuncturists in using diagnostic methods - an explorative study

Purpose: Acupuncture is one of the complementary medicine therapies with the greatest demand in Switzerland and many other countries in the West and in Asia. Over the past decades, the pool of scientific literature in acupuncture has markedly increased. The diagnostic methods upon which acupuncture treatment is based, have only been addressed sporadically in scientific journals. The goal of this study is to assess the use of different diagnostic methods in the acupuncture practices and to investigate similarities and differences in using these diagnostic methods between physician and non-physician acupuncturists. Methods: 44 physician acupuncturists with certificates of competence in acupuncture – traditional chinese medicine (TCM) from ASA (Assoziation Schweizer Ärztegesellschaften für Akupunktur und Chinesische Medizin: the Association of Swiss Medical Societies for Acupuncture and Chinese Medicine) and 33 non-physician acupuncturists listed in the EMR (Erfahrungsmedizinisches Register: a national register, which assigns a quality label for CAM therapists in complementary and alternative medicine) in the cantons Basel-Stadt and Basel-Land were asked to fill out a questionnaire on diagnostic methods. The responder rate was 46.8% (69.7% non-physician acupuncturists and 29, 5% physician acupuncturists). Results: The results show that both physician and non-physician acupuncturists take patients’ medical history (94%), use pulse diagnosis (89%), tongue diagnosis (83%) and palpation of body and ear acupuncture points (81%) as diagnostic methods to guide their acupuncture treatments. Between the two groups, there were significant differences in the diagnostic tools being used. Physician acupuncturists do examine their patients significantly more often with western medical methods (p<.05) than this is the case for nonphysician acupuncturists. Non-physician acupuncturists use pulse diagnosis more often than physicians (p<.05). A highly significant difference was observed in the length of time spent with collecting patients’ medical history, where nonphysician acupuncturists clearly spent more time (p<.001). Conclusion: Depending on the educational background of the acupuncturist, different diagnostic methods are used for making the diagnosis. Especially the more time consuming methods like a comprehensive anamnesis and pulse diagnosis are more frequently employed by non-physician practitioners. Further studies will clarify if these results are valid for Switzerland in general, and to what extent the differing use of diagnostic methods has an impact on the diagnosis itself and on the resulting treatment methods, as well as on the treatment success and the patients’ satisfaction.

Distribution and Transmission of Medicinal Plant Knowledge in the Andean Highlands: A Case Study from Peru and Bolivia

This paper presents a study of patterns in the distribution and transmission of medicinal plant knowledge in rural Andean communities in Peru and Bolivia. Interviews and freelisting exercises were conducted with 18 households at each study site. The amount of medicinal plant knowledge of households was compared in relation to their socioeconomic characteristics. Cluster analysis was applied to identify households that possessed similar knowledge. The different modes of knowledge transmission were also assessed. Our study shows that while the amount of plant knowledge is determined by individual motivation and experience, the type of knowledge is influenced by the community of residence, age, migratory activity, and market integration. Plant knowledge was equally transmitted vertically and horizontally, which indicates that it is first acquired within the family but then undergoes transformations as a result of subsequent contacts with other knowledge sources, including age peers.