MPI parallel programming of mixed integer optimization problems using CPLEX with COIN-OR

The aim of this technical report is to present some detailed explanations in order to help to understand and use the Message Passing Interface (MPI) parallel programming for solving several mixed integer optimization problems. We have developed a C++ experimental code that uses the IBM ILOG CPLEX optimizer within the COmputational INfrastructure for Operations Research (COIN-OR) and MPI parallel computing for solving the optimization models under UNIX-like systems. The computational experience illustrates how can we solve 44 optimization problems which are asymmetric with respect to the number of integer and continuous variables and the number of constraints. We also report a comparative with the speedup and efficiency of several strategies implemented for some available number of threads.

Un entorno de programación multinivel y control modular de robots

En este proyecto final de carrera se van a tratar los aspectos referentes a la ampliación de robots. Para ello se utilizará una placa Arduino que se comunicará con el robot por puerto serie. Esta placa, servirá de plataforma de comunicación entre un PC y el robot, ofreciendo una interfaz del robot anterior con la capacidad de ampliación de la placa Arduino. En el transcurso del proyecto se ha realizado una capa intermedia de código C++ que gestiona el uso de la placa Arduino y del robot iRobot Create a través de la misma. Con objeto de dar también soporte a la programación del robot iRobot Create, se ha elegido un simulador y se le ha dado soporte en la capa anteriormente citada.

Beyond Watson and Crick : programming the self-assembly and reconfiguration of DNA nanostructures based on stacking interactions

Life is the result of the execution of molecular programs: like how an embryo is fated to become a human or a whale, or how a person’s appearance is inherited from their parents, many biological phenomena are governed by genetic programs written in DNA molecules. At the core of such programs is the highly reliable base pairing interaction between nucleic acids. DNA nanotechnology exploits the programming power of DNA to build artificial nanostructures, molecular computers, and nanomachines. In particular, DNA origami—which is a simple yet versatile technique that allows one to create various nanoscale shapes and patterns—is at the heart of the technology. In this thesis, I describe the development of programmable self-assembly and reconfiguration of DNA origami nanostructures based on a unique strategy: rather than relying on Watson-Crick base pairing, we developed programmable bonds via the geometric arrangement of stacking interactions, which we termed stacking bonds. We further demonstrated that such bonds can be dynamically reconfigurable.

The first part of this thesis describes the design and implementation of stacking bonds. Our work addresses the fundamental question of whether one can create diverse bond types out of a single kind of attractive interaction—a question first posed implicitly by Francis Crick while seeking a deeper understanding of the origin of life and primitive genetic code. For the creation of multiple specific bonds, we used two different approaches: binary coding and shape coding of geometric arrangement of stacking interaction units, which are called blunt ends. To construct a bond space for each approach, we performed a systematic search using a computer algorithm. We used orthogonal bonds to experimentally implement the connection of five distinct DNA origami nanostructures. We also programmed the bonds to control cis/trans configuration between asymmetric nanostructures.

The second part of this thesis describes the large-scale self-assembly of DNA origami into two-dimensional checkerboard-pattern crystals via surface diffusion. We developed a protocol where the diffusion of DNA origami occurs on a substrate and is dynamically controlled by changing the cationic condition of the system. We used stacking interactions to mediate connections between the origami, because of their potential for reconfiguring during the assembly process. Assembling DNA nanostructures directly on substrate surfaces can benefit nano/microfabrication processes by eliminating a pattern transfer step. At the same time, the use of DNA origami allows high complexity and unique addressability with six-nanometer resolution within each structural unit.

The third part of this thesis describes the use of stacking bonds as dynamically breakable bonds. To break the bonds, we used biological machinery called the ParMRC system extracted from bacteria. The system ensures that, when a cell divides, each daughter cell gets one copy of the cell’s DNA by actively pushing each copy to the opposite poles of the cell. We demonstrate dynamically expandable nanostructures, which makes stacking bonds a promising candidate for reconfigurable connectors for nanoscale machine parts.

Control of dynamical systems with temporal logic specifications

This thesis is motivated by safety-critical applications involving autonomous air, ground, and space vehicles carrying out complex tasks in uncertain and adversarial environments. We use temporal logic as a language to formally specify complex tasks and system properties. Temporal logic specifications generalize the classical notions of stability and reachability that are studied in the control and hybrid systems communities. Given a system model and a formal task specification, the goal is to automatically synthesize a control policy for the system that ensures that the system satisfies the specification. This thesis presents novel control policy synthesis algorithms for optimal and robust control of dynamical systems with temporal logic specifications. Furthermore, it introduces algorithms that are efficient and extend to high-dimensional dynamical systems.

The first contribution of this thesis is the generalization of a classical linear temporal logic (LTL) control synthesis approach to optimal and robust control. We show how we can extend automata-based synthesis techniques for discrete abstractions of dynamical systems to create optimal and robust controllers that are guaranteed to satisfy an LTL specification. Such optimal and robust controllers can be computed at little extra computational cost compared to computing a feasible controller.

The second contribution of this thesis addresses the scalability of control synthesis with LTL specifications. A major limitation of the standard automaton-based approach for control with LTL specifications is that the automaton might be doubly-exponential in the size of the LTL specification. We introduce a fragment of LTL for which one can compute feasible control policies in time polynomial in the size of the system and specification. Additionally, we show how to compute optimal control policies for a variety of cost functions, and identify interesting cases when this can be done in polynomial time. These techniques are particularly relevant for online control, as one can guarantee that a feasible solution can be found quickly, and then iteratively improve on the quality as time permits.

The final contribution of this thesis is a set of algorithms for computing feasible trajectories for high-dimensional, nonlinear systems with LTL specifications. These algorithms avoid a potentially computationally-expensive process of computing a discrete abstraction, and instead compute directly on the system's continuous state space. The first method uses an automaton representing the specification to directly encode a series of constrained-reachability subproblems, which can be solved in a modular fashion by using standard techniques. The second method encodes an LTL formula as mixed-integer linear programming constraints on the dynamical system. We demonstrate these approaches with numerical experiments on temporal logic motion planning problems with high-dimensional (10+ states) continuous systems.

Varieties generated by modular lattices of width four

A variety (equational class) of lattices is said to be finitely based if there exists a finite set of identities defining the variety. Let M^∞_n denote the lattice variety generated by all modular lattices of width not exceeding n. M^∞₁ and M^∞₂ are both the class of all distributive lattices and consequently finitely based. B. Jónsson has shown that M^∞₃ is also finitely based. On the other hand, K. Baker has shown that M^∞_n is not finitely based for 5 ≤ n ˂ ω. This thesis settles the finite basis problem for M^∞₄. M^∞₄ is shown to be finitely based by proving the stronger result that there exist ten varieties which properly contain M^∞₄ and such that any variety which properly contains M^∞₄ contains one of these ten varieties.

The methods developed also yield a characterization of sub-directly irreducible width four modular lattices. From this characterization further results are derived. It is shown that the free M^∞₄ lattice with n generators is finite. A variety with exactly k covers is exhibited for all k ≥ 15. It is further shown that there are 2^Ӄo sub- varieties of M^∞₄.

Relógios biológicos e padrões de alimentação em camundongos normais e com sobrepeso

A saudável interação entre o indivíduo e o meio depende do alinhamento entre a dinâmica fisiológica do primeiro e os periódicos movimentos da natureza. A interação entre tais ritmos por sua vez constitui-se em base e derivação do processo de evolução. O comprometimento de tal alinhamento representa um risco para a sobrevivência das espécies. Neste contexto, os organismos alinham seus ritmos fisiológicos a diferentes ciclos externos. Desta forma, ciclos endógenos são coordenados por relógios biológicos que determinam em nosso organismo, específicos ritmos em fase com a natureza, tais como ritmos circadianos (RC), cujo período aproxima-se de 24 horas. O peso corporal, a ingestão de alimentos e o consumo de energia são processos caracterizados pelo RC e a obesidade está associada a uma dessincronização deste processo. A modulação do RC é resultado da expressão dos clock gens CLOCK e BMAL1 que formam um heterodímero responsável pela transcrição gênica de Per1, Per2, Per3, Cry1 e Cry2. As proteínas codificadas por estes genes, uma vez sintetizadas, formam dímeros (PER-CRY) no citoplasma que, a partir de determinada concentração, retornam ao núcleo, bloqueando a ação do heterodímero CLOCK/BMAL1 na transcrição dos próprios genes, formando assim uma alça de retroalimentação negativa de transcrição e tradução. Estes genes asseguram a periodicidade e são significativamente expressos no núcleo supraquiasmático (SCN) do hipotálamo. Para estudar esse processo em camundongos normais e hiperalimentados, saciados e em estado de fome, foi utilizado um método de registro do comportamento alimentar baseado no som produzido pela alimentação dos animais, e a correlação destes estados metabólicos com a expressão de CLOCK, BMAL1, Per1, Per2, Per3, bem como das proteínas Cry1 e Cry2 no SCN, por análise de imagens obtidas em microscopia confocal. Camundongos suíços controle em estado de fome (CF) e saciados (CS) foram comparados com animais hiperalimentados com fome (HF) e saciados (HS). Nenhum grupo demonstrou diferença nos conteúdos CLOCK e BMAL1, indicando capacidade potencial para modular os ritmos biológicos. No entanto, as proteínas Per1, Per2, Per3 e Cry1 apresentaram menor expressão no grupo CS, mostrando uma diferença significativa quando comparados com o grupo CF (P<0,05), diferença esta não encontrada na comparação entre os grupos HF e HS. A quantidade de proteína Cry2 não foi diferente na mesma comparação. Os resultados do estudo indicaram que as alterações dos ritmos endógenos e exógenos, refletido pelo comportamento hiperfágico observado em camundongos hiperalimentados, pode ser devido a um defeito no mecanismo de feedback negativo associado ao dímero Cry-Per, que não bloqueia a transcrição de Per1 Per2, Per3 e Cry1 pelo heterodímero CLOCK-BMAL1.

Modular integration and on-chip sensing approaches for tunable fluid control polymer microdevices

228 p.