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.

Computing primal solutions with exact arithmetics in SCIP.

The research for exact solutions of mixed integer problems is an active topic in the scientific community. State-of-the-art MIP solvers exploit a floating- point numerical representation, therefore introducing small approximations. Although such MIP solvers yield reliable results for the majority of problems, there are cases in which a higher accuracy is required. Indeed, it is known that for some applications floating-point solvers provide falsely feasible solutions, i.e. solutions marked as feasible because of approximations that would not pass a check with exact arithmetic and cannot be practically implemented. The framework of the current dissertation is SCIP, a mixed integer programs solver mainly developed at Zuse Institute Berlin. In the same site we considered a new approach for exactly solving MIPs. Specifically, we developed a constraint handler to plug into SCIP, with the aim to analyze the accuracy of provided floating-point solutions and compute exact primal solutions starting from floating-point ones. We conducted a few computational experiments to test the exact primal constraint handler through the adoption of two main settings. Analysis mode allowed to collect statistics about current SCIP solutions' reliability. Our results confirm that floating-point solutions are accurate enough with respect to many instances. However, our analysis highlighted the presence of numerical errors of variable entity. By using the enforce mode, our constraint handler is able to suggest exact solutions starting from the integer part of a floating-point solution. With the latter setting, results show a general improvement of the quality of provided final solutions, without a significant loss of performances.

Lung Nodule Detection by Microdose CT Versus Chest Radiography (Standard and Dual-Energy Subtracted).

OBJECTIVE The purpose of this study was to investigate the feasibility of microdose CT using a comparable dose as for conventional chest radiographs in two planes including dual-energy subtraction for lung nodule assessment. MATERIALS AND METHODS We investigated 65 chest phantoms with 141 lung nodules, using an anthropomorphic chest phantom with artificial lung nodules. Microdose CT parameters were 80 kV and 6 mAs, with pitch of 2.2. Iterative reconstruction algorithms and an integrated circuit detector system (Stellar, Siemens Healthcare) were applied for maximum dose reduction. Maximum intensity projections (MIPs) were reconstructed. Chest radiographs were acquired in two projections with bone suppression. Four blinded radiologists interpreted the images in random order. RESULTS A soft-tissue CT kernel (I30f) delivered better sensitivities in a pilot study than a hard kernel (I70f), with respective mean (SD) sensitivities of 91.1% ± 2.2% versus 85.6% ± 5.6% (p = 0.041). Nodule size was measured accurately for all kernels. Mean clustered nodule sensitivity with chest radiography was 45.7% ± 8.1% (with bone suppression, 46.1% ± 8%; p = 0.94); for microdose CT, nodule sensitivity was 83.6% ± 9% without MIP (with additional MIP, 92.5% ± 6%; p < 10(-3)). Individual sensitivities of microdose CT for readers 1, 2, 3, and 4 were 84.3%, 90.7%, 68.6%, and 45.0%, respectively. Sensitivities with chest radiography for readers 1, 2, 3, and 4 were 42.9%, 58.6%, 36.4%, and 90.7%, respectively. In the per-phantom analysis, respective sensitivities of microdose CT versus chest radiography were 96.2% and 75% (p < 10(-6)). The effective dose for chest radiography including dual-energy subtraction was 0.242 mSv; for microdose CT, the applied dose was 0.1323 mSv. CONCLUSION Microdose CT is better than the combination of chest radiography and dual-energy subtraction for the detection of solid nodules between 5 and 12 mm at a lower dose level of 0.13 mSv. Soft-tissue kernels allow better sensitivities. These preliminary results indicate that microdose CT has the potential to replace conventional chest radiography for lung nodule detection.

Protein Information Resource: a community resource for expert annotation of protein data

The Protein Information Resource, in collaboration with the Munich Information Center for Protein Sequences (MIPS) and the Japan International Protein Information Database (JIPID), produces the most comprehensive and expertly annotated protein sequence database in the public domain, the PIR-International Protein Sequence Database. To provide timely and high quality annotation and promote database interoperability, the PIR-International employs rule-based and classification-driven procedures based on controlled vocabulary and standard nomenclature and includes status tags to distinguish experimentally determined from predicted protein features. The database contains about 200 000 non-redundant protein sequences, which are classified into families and superfamilies and their domains and motifs identified. Entries are extensively cross-referenced to other sequence, classification, genome, structure and activity databases. The PIR web site features search engines that use sequence similarity and database annotation to facilitate the analysis and functional identification of proteins. The PIR-Inter­national databases and search tools are accessible on the PIR web site at http://pir.georgetown.edu/ and at the MIPS web site at http://www.mips.biochem.mpg.de. The PIR-International Protein Sequence Database and other files are also available by FTP.

Low-resolution spectroscopy and spectral energy distributions of selected sources towards σ Orionis

Aims. We study in detail nine sources in the direction of the young σ Orionis cluster, which is considered to be a unique site for studying stellar and substellar formation. The nine sources were selected because of their peculiar properties, such as extremely-red infrared colours or excessively strong Hα emission for their blue optical colours. Methods. We acquired high-quality, low-resolution spectroscopy (R ∼ 500) of the nine targets with ALFOSC at the Nordic Optical Telescope. We also re-analysed [24]-band photometry from MIPS/Spitzer and compiled the highest quality photometric dataset available at the ViJHK_s passbands and the four IRAC/Spitzer channels, for constructing accurate spectral energy distributions between 0.55 and 24 μm. Results. The nine targets were classified into: one Herbig Ae/Be star with a scattering edge-on disc; two G-type stars; one X-ray flaring, early-M, young star with chromospheric Hα emission; one very low-mass, accreting, young spectroscopic binary; two young objects at the brown-dwarf boundary with the characteristics of classical T Tauri stars; and two emission-line galaxies, one undergoing star formation, and another whose spectral energy distribution is dominated by an active galactic nucleus. We also discovered three infrared sources associated with overdensities in a cold cloud of the cluster centre. Conclusions. Low-resolution spectroscopy and spectral energy distributions are a vital tool for measuring the physical properties and evolution of young stars and candidates in the σ Orionis cluster.

Caught in the act: gas and stellar velocity dispersions in a fast Quenching compact star-forming galaxy at z ~ 1.7

We present Keck I MOSFIRE spectroscopy in the Y and H bands of GDN-8231, a massive, compact, star-forming galaxy at a redshift of z ~ 1.7. Its spectrum reveals both Hα and [Nii] emission lines and strong Balmer absorption lines. The Hα and Spitzer MIPS 24 μm fluxes are both weak, thus indicating a low star-formation rate of SFR≲5-10 M_⨀ yr−1. This, added to a relatively young age of ~700 Myr measured from the absorption lines, provides the first direct evidence for a distant galaxy being caught in the act of rapidly shutting down its star formation. Such quenching allows GDN-8231 to become a compact, quiescent galaxy, similar to three other galaxies in our sample, by z ~ 1.5. Moreover, the color profile of GDN-8231 shows a bluer center, consistent with the predictions of recent simulations for an early phase of inside-out quenching. Its line-of-sight velocity dispersion for the gas, σ_LOG^gas = 127 ± 32 km s^−1, is nearly 40% smaller than that of its stars, σ_LOG^* = 215 ± 35 km s^−1. High-resolution hydro-simulations of galaxies explain such apparently colder gas kinematics of up to a factor of ~1.5 with rotating disks being viewed at different inclinations and/or centrally concentrated star-forming regions. A clear prediction is that their compact, quiescent descendants preserve some remnant rotation from their star-forming progenitors.

Análise de métodos de avaliação de eco eficiência.

Para que a sustentabilidade seja gerenciada e praticada de maneira efetiva, ela deve ser mensurada, utilizando-se de métodos de avaliação da sustentabilidade. Estão disponíveis diferentes métodos de avaliação, que geralmente reduzem o resultado desse levantamento à indicadores de desempenho ambiental, econômico e social (POPEA; ANNANDALE; MORISON-SAUNDERSB, 2004). Uma das denominações mais bem aceitas e difundidas para a conjunção da dimensão ambiental e econômica é conhecida por avaliação de eco eficiência (AEE). Eco eficiência é o \"aspecto da sustentabilidade que relaciona o desempenho ambiental de um sistema de produto ao valor do sistema de produto\" (ISO, 2012). Estão disponíveis diferentes métodos de AEE, porém sem evidência das suas semelhanças e particularidades e como essas características influenciam na escolha do método mais adequado de AEE em relação às potenciais aplicações O objetivo desta pesquisa é, portanto, analisar e indicar os tipos de métodos de avaliação de eco eficiência (AEE) mais adequados para ações gerenciais nas quais caibam tais abordagens. Foram selecionados onze métodos de AEE, a partir do estabelecimento de critérios de caracterização desses métodos, a saber: BASF, Bayer, EcoWater, Hahn et al., Kuosmanen e Kortelainen, MIPS, NRTEE, UN ESCAP, UN, TU Delft, e WBCSD. Identificaram-se, ainda, quatro potenciais aplicações: (i) Monitoramento de processo com vistas à melhoria contínua; (ii) Selecção e classificação de produtos; (iii) Atendimento a requisitos legais e outros requisitos; e, (iv) Marketing, rotulagem de produtos e comunicação ambiental. A partir dos elementos metodológicos estabelecidos pela norma ISSO 14045 (2012) e do conhecimento obtido dos métodos de AEE, determinaram-se quatro requisitos pelos quais os métodos e os potenciais aplicações foram avaliados: (i) Tipo de indicador de desempenho ambiental; (ii) Tipo de indicador de valor de sistema de produto; (iii) Abrangência de aplicação; e, (iv) Tipo de indicador de eco eficiência. Aplicando-se estes requisitos nos métodos de AEE e nos potenciais usos, concluiu-se que quanto à aplicações em termos de monitoramento de processos com vistas à melhoria continua os métodos de AEE recomendados foram Bayer, NRTEE, WBCSD e UN. Para situações de seleção e classificação de produtos os métodos BASF, EcoWater, Kuosmanen e Kortelainen, MIPS, Hahn et al., TU Delft, UN ESCAP e UN demonstraram ter boa aderência. No que se refere a usos voltados ao atendimento de requisitos legais e/ou de outras naturezas, os métodos NRTEE, WBCSD e UN são os mais indicados. Em aplicações de marketing, rotulagem e comunicação foram indicados os métodos BASF, EcoWater e MIPS. Finalmente, concluiu-se que, para a escolha adequada da metodologia para uma AEE, conhecimento prévio das características de cada abordagem é necessário.

Grafting of functional brushes on the surface of 5-Fluorouracil molecularly imprinted polymer particles through RAFT polymerization

The grafting of functional brushes on the surface of molecularly imprinted polymer (MIP). particles hás been explored in the last few years to synthesize materiais combining high molecular recognition capabilities and stimulation triggered by changes in the surrounding environment [1, 2]. In the present work, MIP particles for 5-fluorouracil (a drug used in câncer treatment) were produced by precipitation polymerization in acetonitrile, using either MAA or HEMA as imprinting fünctional monomers, and m the presence of different kinds of RAFT agents. In a second step, taking advantage of the RAFT groups present in the surface of the particles, different kinds of fiinctional polymer brushes were grafted on the MIPs considering a "grafting from" process in the presence of a RAFT agent.

A regulatory domain in the C-terminal extension of the yeast glycerol channel Fps1p

The Saccharomyces cerevisiae gene FPS1 encodes an aquaglyceroporin of the major intrinsic protein (MIP) family. The main function of Fps1p seems to be the efflux of glycerol in the adaptation of the yeast cell to lower external osmolarity. Fps1p is an atypical member of the family, because the protein is much larger (669 amino acids) than most MIPs due to long hydrophilic extensions in both termini. We have shown previously that a short domain in the N-terminal extension of the protein is required for restricting glycerol transport through the channel (Tamás, M. J., Karlgren, S., Bill, R. M., Hedfalk, K., Allegri, L., Ferreira, M., Thevelein, J. M., Rydström, J., Mullins, J. G. L., and Hohmann, S. (2003) J. Biol. Chem. 278, 6337-6345). Deletion of the N-terminal domain results in an unregulated channel, loss of glycerol, and osmosensitivity. In this work we have investigated the role of the Fps1p C terminus (139 amino acids). A set of eight truncations has been constructed and tested in vivo in a yeast fps1Δ strain. We have performed growth tests, membrane localization following cell fractionation, and glycerol accumulation measurements as well as an investigation of the osmotic stress response. Our results show that the C-terminal extension is also involved in restricting transport through Fps1p. We have identified a sequence of 12 amino acids, residues 535-546, close to the sixth transmembrane domain. This element seems to be important for controlling Fps1p function. Similar to the N-terminal domain, the C-terminal domain is amphiphilic and has a potential to dip into the membrane.

Molecularly imprinted polymers in the drug discovery process

Since molecularly imprinted polymers (MIPs) are designed to have a memory for their molecular templates it is easy to draw parallels with the affinity between biological receptors and their substrates. Could MIPs take the place of natural receptors in the selection of potential drug molecules from synthetic compound libraries? To answer that question this review discusses the results of MIP studies which attempt to emulate natural receptors. In addition the possible use of MIPs to guide a compound library synthesis towards a desired biological activity is highlighted. © 2005 Elsevier B.V. All rights reserved.

Synthesis and characterisation of imprinted polymeric receptor mimics

Molecularly imprinted polymers (MIPs) are crosslinked polymers containing bespoke functionalised cavities arising from the inclusion of template molecules in the polymerisation mixture and their later extraction. When the polymers are prepared functional polymerisable monomers are included which become part of the polymer matrix and serve to decorate the cavities with functionality appropriate to the template molecules. Overall, binding sites are created which have a memory for the template both in terms of shape and matching functionality. Fluorescent molecularly imprinted polymers have the benefit of a fluorophore in their cavities that may respond to the presence of bound test compound by a change in their fluorescence output. The work presented falls into three main areas. A series of fluorescent MIPs was prepared with a view to generating material capable of mimicking the binding characteristics of the metabolically important cytochrome isoform CYP2D6. The MIPs re-bound their templates and various cross-reactivities were encountered for test compound/drug recognition. One MIP in particular exhibited a rational discrimination amongst the related synthetic templates and was reasonably successful in recognising CYP2D6 substrates from the drug set tested. In order to give some insights into binding modes in MIPs, attempts were made to produce functional monomers containing two or more fluorophores that could be interrogated independently. A model compound was prepared which fitted the dual-fluorophore criteria and which will be the basis for future incorporation into MIPs. A further strand to this thesis is the deliberate incorporation of hydrophobic moieties into fluorescent functional monomers so that the resulting imprinted cavities might be biomimetic in their impersonation of enzyme active sites. Thus the imprinted cavities had specific hydrophobic regions as well as the usual polar functionality with which to interact with binding test compounds.

Design and synthesis of potential antimicrobial agents

Tuberculosis is one of the most devastating diseases in the world primarily due to several decades of neglect and an emergence of multidrug-resitance strains (MDR) of M. tuberculosis together with the increased incidence of disseminated infections produced by other mycobacterium in AIDS patients. This has prompted the search for new antimycobacterial drugs. A series of pyridine-2-, pyridine-3-, pyridine-4-, pyrazine and quinoline-2-carboxamidrazone derivatives and new classes of carboxamidrazone were prepared in an automated fashion and by traditional synthesis. Over nine hundred synthesized compounds were screened for their anti mycobacterial activity against M. fortutium (NGTG 10394) as a surrogate for M. tuberculosis. The new classes of amidrazones were also screened against tuberculosis H37 Rv and antimicrobial activities against various bacteria. Fifteen tested compounds were found to provide 90-100% inhibition of mycobacterium growth of M. tuberculosis H37 Rv in the primary screen at 6.25 μg mL-1. The most active compound in the carboxamidrazone amide series had an MIG value of 0.1-2 μg mL-1 against M. fortutium. The enzyme dihydrofolate reductase (DHFR) has been a drug-design target for decades. Blocking of the enzymatic activity of DHFR is a key element in the treatment of many diseases, including cancer, bacterial and protozoal infection. The x-ray structure of DHFR from M. tuberculosis and human DHFR were found to have differences in substrate binding site. The presence of glycerol molecule in the Xray structure from M. tuberculosis DHFR provided opportunity to design new antifolates. The new antifolates described herein were designed to retain the pharmcophore of pyrimethamine (2,4- diamino-5(4-chlorophenyl)-6-ethylpyrimidine), but encompassing a range of polar groups that might interact with the M. tuberculosis DHFR glycerol binding pockets. Finally, the research described in this thesis contributes to the preparation of molecularly imprinted polymers for the recognition of 2,4-diaminopyrimidine for the binding the target. The formation of hydrogen bonding between the model functional monomer 5-(4-tert-butyl-benzylidene)-pyrimidine-2,4,6-trione and 2,4-diaminopyrimidine in the pre-polymerisation stage was verified by 1H-NMR studies. Having proven that 2,4-diaminopyrimidine interacts strongly with the model 5-(4-tert-butylbenzylidene)- pyrimidine-2,4,6-trione, 2,4-diaminopyrimidine-imprinted polymers were prepared using a novel cyclobarbital derived functional monomer, acrylic acid 4-(2,4,6-trioxo-tetrahydro-pyrimidin-5- ylidenemethyl)phenyl ester, capable of multiple hydrogen bond formation with the 2,4- diaminopyrimidine. The recognition property of the respective polymers toward the template and other test compounds was evaluated by fluorescence. The results demonstrate that the polymers showed dose dependent enhancement of fluorescence emissions. In addition, the results also indicate that synthesized MIPs have higher 2,4-diaminopyrimidine binding ability as compared with corresponding non-imprinting polymers.

A study of methods used to analyze total oil and polycyclic aromatic hydrocarbons in produced water: steps towards the validation of molecularly imprinted polymers for use in marine environmetns

Produced water is a by-product of offshore oil and gas production, and is released in large volumes when platforms are actively processing crude oil. Some pollutants are not typically removed by conventional oil/water separation methods and are discharged with produced water. Oil and grease can be found dispersed in produced water in the form of tiny droplets, and polycyclic aromatic hydrocarbons (PAHs) are commonly found dissolved in produced water. Both can have acute and chronic toxic effects in marine environments even at low exposure levels. The analysis of the dissolved and dispersed phases are a priority, but effort is required to meet the necessary detection limits. There are several methods for the analysis of produced water for dispersed oil and dissolved PAHs, all of which have advantages and disadvantages. In this work, EPA Method 1664 and APHA Method 5520 C for the determination of oil and grease will be examined and compared. For the detection of PAHs, EPA Method 525 and PAH MIPs will be compared, and results evaluated. APHA Method 5520 C Partition-Infrared Method is a liquid-liquid extraction procedure with IR determination of oil and grease. For analysis on spiked samples of artificial seawater, extraction efficiency ranged from 85 – 97%. Linearity was achieved in the range of 5 – 500 mg/L. This is a single-wavelength method and is unsuitable for quantification of aromatics and other compounds that lack sp³-hybridized carbon atoms. EPA Method 1664 is the liquid-liquid extraction of oil and grease from water samples followed by gravimetric determination. When distilled water spiked with reference oil was extracted by this procedure, extraction efficiency ranged from 28.4 – 86.2%, and %RSD ranged from 7.68 – 38.0%. EPA Method 525 uses solid phase extraction with analysis by GC-MS, and was performed on distilled water and water from St. John’s Harbour, all spiked with naphthalene, fluorene, phenanthrene, and pyrene. The limits of detection in harbour water were 0.144, 3.82, 0.119, and 0.153 g/L respectively. Linearity was obtained in the range of 0.5-10 g/L, and %RSD ranged from 0.36% (fluorene) to 46% (pyrene). Molecularly imprinted polymers (MIPs) are sorbent materials made selective by polymerizing functional monomers and crosslinkers in the presence of a template molecule, usually the analytes of interest or related compounds. They can adsorb and concentrate PAHs from aqueous environments and are combined with methods of analysis including GC-MS, LC-UV-Vis, and desorption electrospray ionization (DESI)- MS. This work examines MIP-based methods as well as those methods previously mentioned which are currently used by the oil and gas industry and government environmental agencies. MIPs are shown to give results consistent with other methods, and are a low-cost alternative improving ease, throughput, and sensitivity. PAH MIPs were used to determine naphthalene spiked into ASTM artificial seawater, as well as produced water from an offshore oil and gas operation. Linearity was achieved in the range studied (0.5 – 5 mg/L) for both matrices, with R² = 0.936 for seawater and R² = 0.819 for produced water. The %RSD for seawater ranged from 6.58 – 50.5% and for produced water, from 8.19 – 79.6%.

Measuring star formation in high-z massive galaxies: a mid-infrared to submillimetre study of the GOODS NICMOS Survey sample

We present measurements of the mean mid-infrared to submillimetre flux densities of massive (M_*≳ 10^11 M_⊙) galaxies at redshifts 1.7 < z < 2.9, obtained by stacking positions of known objects taken from the GOODS NICMOS Survey (GNS) catalogue on maps at 24 μm (Spitzer/MIPS); 70, 100 and 160 μm (Herschel/PACS); 250, 350 and 500 μm (BLAST); and 870 μm (LABOCA). A modified blackbody spectrum fit to the stacked flux densities indicates a median [interquartile] star formation rate (SFR) of SFR = 63[48, 81] M_⊙ yr^−1. We note that not properly accounting for correlations between bands when fitting stacked data can significantly bias the result. The galaxies are divided into two groups, disc-like and spheroid-like, according to their Sérsic indices, n. We find evidence that most of the star formation is occurring in n≤ 2 (disc-like) galaxies, with median [interquartile] SFR = 122[100, 150] M_⊙ yr^−1, while there are indications that the n > 2 (spheroid-like) population may be forming stars at a median [interquartile] SFR = 14[9, 20] M_⊙ yr^−1, if at all. Finally, we show that star formation is a plausible mechanism for size evolution in this population as a whole, but find only marginal evidence that it is what drives the expansion of the spheroid-like galaxies.

Improving the identification of high-z Herschel sources with position priors and optical/NIR and FIR/mm photometric redshifts

We present preliminary results about the detection of high redshift (U)LIRGs in the Bullet cluster field by the PACS and SPIRE instruments within the Herschel Lensing Survey (HLS) Program. We describe in detail a photometric procedure designed to recover robust fluxes and deblend faint Herschel sources near the confusion noise. The method is based on the use of the positions of Spitzer/MIPS 24 μm sources as priors. Our catalogs are able to reliably (5σ) recover galaxies with fluxes above 6 and 10 mJy in the PACS 100 and 160 μm channels, respectively, and 12 to 18 mJy in the SPIRE bands. We also obtain spectral energy distributions covering the optical through the far-infrared/millimeter spectral ranges of all the Herschel detected sources, and analyze them to obtain independent estimations of the photometric redshift based on either stellar population or dust emission models. We exemplify the potential of the combined use of Spitzer position priors plus independent optical and IR photometric redshifts to robustly assign optical/NIR counterparts to the sources detected by Herschel and other (sub-)mm instruments.