Made available in DSpace on 2017-07-10T17:37:55Z (GMT). No. of bitstreams: 1 2012_Daiana_Raquel_Pauletti.pdf: 1311951 bytes, checksum: d8f448e788a2e5680266cd4972f13586 (MD5) Previous issue date: 2012-08-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A soil mulching change soil physical and chemical compounds and promotes benefits to lettuce production system. This study aimed to evaluate the effect of mulching on the yield characteristics of lettuce and continuous cultivation of these effects in the physical and chemical soil properties. The aim of this work was conducted from June 2010 to February 2011, in Santa Helena - Paraná. The experiment was conducted in two stages; the first step consisted of growing covering plants until they reach a cutoff point, initiating the second step consisting in the conduct of two consecutive cycles of the lettuce crop, produced on straw. The experiment was conducted in a randomized complete block design in split-split plots with four replications, the plots consist covering plants: oat (Avena strigosa Schreb), pearl millet (Pennisetum glaucum L.), turnip (Raphanus sativus L. var. Oleiferus Metzg), snap bean (Phaseolus vulgaris L.) and control (bare soil), the sub plots of lettuce cultivars (Vanda and Veronica) and subsubplot the lettuce crop cycles (first and second cycle). The lettuce was evaluated for plant height, head diameter, leaf number, fresh and dry mass of stems and leaves, leaf area, total dry weight (leaves + stem), stem diameter and crown projection. For cover covering were determined fresh and dry shoot. During the experiment were also evaluated, the physical attributes (density, macroporosity, micro porosity, total porosity, and resistance to moisture penetration) and chemical (pH, P, K, Ca +2, Mg +2, H +Al , sum of bases, base saturation and organic matter), the experimental area, at two depths and three sampling times. The presence of mulch benefited growing lettuce in the first cycle. The cultivar was superior to cultivate Veronica Vanda conditions of the study. The development of the lettuce crop was damaged due to high temperatures during the period of cultivation of the crop. The millet stood out as cover crop for the excellent potential for biomass. The percentage of macropores appeared above the minimum requirement (10%) required for proper root development of crops. The microporosity increased with the sampling depth, while the macroporosity decreased. The percentage soil moisture was proportional to the amount of weight produced by covering plants. As for soil chemical properties observed accumulation of P in the soil surface layer, the potential acidity (H + Al) tended to increase during the evaluation periods while pH showed some decrease with age, it was not found a significant difference to the levels of organic matter but they were higher in the surface layer / A cobertura morta contribui para melhoria dos componentes físicos e químicos do solo e beneficia o sistema de produção agrícola. O presente trabalho teve como objetivo avaliar o efeito das plantas de cobertura nas características produtivas da alface em cultivo sucessivo, e nos atributos físicos e químicos do solo. A pesquisa foi realizada no período de junho de 2010 a fevereiro de 2011, no município de Santa Helena - Paraná. O experimento foi conduzido em duas etapas, a primeira etapa constou do cultivo das plantas de cobertura até atingirem ponto de corte, e a segunda etapa consistiu na condução de dois ciclos consecutivos da cultura da alface, sobre a palhada produzida. Utilizou-se delineamento experimental de blocos casualizados em parcelas subsubdivididas, com quatro repetições, sendo as parcelas compostas pelas plantas de cobertura aveia (Avena strigosa Schreb), milheto (Pennisetum glaucum L.), nabo forrageiro (Raphanus sativus L. var. oleiferus Metzg.), feijão-vagem (Phaseolus vulgaris L.) e testemunha (sem cobertura, em pousio com controle das plantas espontâneas), as subparcelas constituídas pelas cultivares de alface (Vanda e Verônica) e a subsubparcela pelos ciclos de cultivo da alface (primeiro e segundo ciclo). A cultura da alface foi avaliada quanto a altura da planta, diâmetro da cabeça, número de folhas, massa fresca e seca de caule e folhas, área foliar, massa aérea total (folhas + caule), diâmetro do caule e projeção da copa. Para as plantas de cobertura foram determinados a massa fresca e seca da parte aérea. Durante a condução do experimento foram avaliados também, os atributos físicos (densidade, macroporosidade, microporosidade, porosidade total, umidade e resistência a penetração) e químicos (pH, P, K, Ca+2, Mg+2, H+Al, soma de bases, saturação por bases e matéria orgânica) do solo da área experimental, em duas profundidades e três épocas de avaliação. A presença da cobertura morta beneficiou o cultivo da alface no primeiro ciclo de cultivo. A cultivar Verônica foi superior a cultivar Vanda nas condições do estudo. O milheto destacou-se como planta de cobertura pelo excelente potencial na produção de biomassa. A porcentagem de macroporos apresentou-se acima da exigência mínima (10%) necessária ao adequado desenvolvimento radicular das culturas. A microporosidade aumentou com a profundidade de amostragem, enquanto a macroporosidade diminuiu. O percentual de umidade do solo foi proporcional a quantidade de massa fresca produzida pelas plantas de cobertura. O tratamento composto pela cobertura de feijão vagem e a testemunha de forma geral apresentaram maiores valores de resistência do solo a penetração. Quanto aos atributos químicos do solo observou-se acumulo de P na camada superficial do solo, a acidez potencial (H+Al) apresentou um aumento com o decorrer das épocas de avaliação enquanto o pH apresentou certa redução com as épocas. Não foi verificada diferença significativa para os teores de matéria orgânica, porém estes foram maiores na camada superficial

O problema de empacotamento em faixas de peças irregulares consiste em cortar um conjunto de peças bidimensionais a partir de um objeto de largura fixa utilizando o menor comprimento possível. Apesar de sua importância econômica para diversos setores industriais, há poucos trabalhos que abordam o problema de forma exata devido a sua dificuldade de resolução. Recentemente, Toledo et al. (2013) propuseram um modelo inteiro misto para este problema, no qual as peças são posicionadas em uma malha de pontos. Este modelo obteve bons resultados, provando a otimalidade para instâncias com até 21 peças. No entanto, o modelo possui um grande número de restrições de não-sobreposição, que cresce rapidamente de acordo com a discretização utilizada e a quantidade de peças distintas que devem ser alocadas. Neste trabalho, são propostas novas formulações matemáticas baseadas neste modelo, com o objetivo de reduzir o número de restrições. Na primeira abordagem, são propostos dois modelos reduzidos que mostraram ser eficientes para instâncias com poucas repetições de peças. Na segunda abordagem, foi proposto um modelo de cobertura por cliques para o problema. Este modelo obteve desempenho igual ou superior ao modelo da literatura para todas as instâncias avaliadas, obtendo uma solução ótima para instâncias com até 28 peças. / The irregular strip packing problem consists of cutting a set of two-dimensional pieces from an object of fixed width using the smallest possible length. Despite its economic importance for many industrial sectors, few exact studies have been made on this problem due to its difficulty of resolution. Recently, Toledo et al. (2013) proposed a mixed-integer model to this problem in which the pieces are placed on a grid. This model has worked successfully proving the optimality for instances up to 21 pieces. However, the model has a large number of non-overlapping constraints, which grows quickly in accordance with the discretization resolution and number of distinct pieces. In this work, we propose new mathematical formulations based on this model in order to reduce the number of constraints. In the first approach, we present two reduced models that have shown to be effective for instances with few repetitions of pieces. In the second approach, it was proposed a clique covering model for the problem. This model achieved a greater or equal performance than the literature for all instances, getting an optimal solution for instances up to 28 pieces.

Made available in DSpace on 2017-05-12T14:42:43Z (GMT). No. of bitstreams: 1 Wellington_Barbosa_da_Silva.pdf: 4552878 bytes, checksum: cced6a1f2d0a0c2426792ba3f3f8ce33 (MD5) Previous issue date: 2011-07-08 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / On the Guarapuava Plateau/Palmas, in a low slope hillside of superficial covering from basaltic origins, on the right bank of the Rio das Pombas, Paraná state, processes of tunnel erosion (pipes) were identified. These are subsuperficial erosion processes with typical features, such as subsidence of the tunnel roof and rebate structures, which tend to evolve to superficial features. The emerging of this erosive process depends on a set of factors, being the main one, the properties of the superficial covering, such as: texture, macroporosity, granulometric composition (chemical matter make-up), density, porosity e chemical elements that make up the matter, those concerning the hydrological conditions and the topography of the hillside. In order to recognize and characterize the superficial covering in the sector of low hillside, sieve analysis was used, as well as real and apparent density, total porosity verified; toposequences were made and X-ray scattering techniques performed. The results showed that the matter which covers the low hillside sector, where the tunnels are, have a sandy texture due to the properties of microagregation generated by clay mineral, gibbsite; leaving the matter with a high porosity level, thus favoring the flowing of water through subsurfaces. The generated flows tend to be exfiltrated to a ditch wall-like surface, which causes the removal of small particles of matter (seepage). With the opening of small gullies through subsurface, the flow tend to become concentrated (tunnel scour) and consequently enlarge the subsuperficial channels by the mechanical action of the water. In a sequence of factors that can be used for the analysis of the process generation, which causes: alteration in basalt rocks, microaggregation of the matter, macroporosity and increase of water flow through subsurface. Therefore, the hydrology conditions in the hillside contributed for erosion mechanisms to emerge in subsurface, development of erosion process, formation of subsuperficial erosion and, ultimately, superficial erosion process development. These both chemical and physical features found in such field of study, show that the superficial covering is a determining factor for the subsuperficial tunnel erosion to originate in the hillside. / No Planalto de Guarapuava/Palmas, em encosta de baixa declividade e cobertura superficial de origem basáltica, à margem direita do Rio das Pombas em Guarapuava (Paraná), foram identificados processos de erosão em túneis (pipes). Trata-se de processos subsuperficiais de erosão que apresentam feições típicas, tais como, subsidência do teto do túnel e estruturas de abatimento, que tendem a evoluir para feições superficiais. A instalação desse processo erosivo depende de um conjunto de fatores, destacando-se como condicionantes, as propriedades da cobertura superficial como: textura, macroporosidade, composição granulométrica, densidade, porosidade e constituintes químicos dos materiais, e aqueles relativos às condições hidrológicas e à topografia da encosta. Buscando-se reconhecer e caracterizar a cobertura superficial do setor de baixa encosta, foram realizadas análises granulométricas, de densidade aparente, real e porosidade total, construção de topossequências e análises químicas de difração de raios-X. Os resultados indicaram que o material que recobre o setor de baixa encosta, onde aparecem os túneis, apresenta textura arenosa devido às propriedades de microagregação gerada pelo argilomineral gibbsita, deixando o material com porosidade alta, favorecendo assim a circulação de água em subsuperficie. Os fluxos gerados tendem a ser exfiltrados para uma superfície de exposição, o que provoca a remoção de pequenas partículas de material (seepage). Com a abertura de pequenos canais em subsuperfície, os fluxos tendem a se concentrar (tunnel scour) e consequentemente ampliar os canais subsuperficiais pela ação mecânica da água. Numa sequência de fatores que possam ser postos para análise da geração do processo, têm-se: alteração da rocha basáltica, microagregação do material, macroporosidade e aumento da circulação de água em subsuperfície. Assume-se que as condições hidrológicas da encosta propiciaram a instalação de mecanismos de erosão em subsuperfície, evolução do processo erosivo, formação de feições erosivas subsuperficiais e, por fim, instalação de feições erosivas superficiais. Essas características físicas e químicas encontradas na área de estudo, demonstram que a cobertura superficial é determinante para a instalação da erosão subsuperficial em túneis na encosta.

This paper is dedicated to the beginning of the development of a book introducing topological games and selection principles. Here, the classical games (such as the Banach-Mazur) and selection principles (such as the Rothberger or Menger properties) are presented. The most notable applications are also displayed both the classical (such as the characterization of Baire spaces with the Banach-Mazur game) and the recent (such as the relation between the Menger property and D-spaces). In addition to the content for the book, a problem in finite combinatorics that was found in the study of positional strategies is presented (as well as a partial solution) together with some results regarding new variations of classical selection principles and games, which give rise to the characterization of some notable spaces. / Este trabalho é dedicado ao início do desenvolvimento de um livro introdutório à jogos topológicos e princípios seletivos. Aqui, são apresentados os clássicos jogos (tais como o de Banach-Mazur) e princípios seletivos (tais como a propriedade de Rothberger ou de Menger). Também são exibidas as aplicações mais notáveis encontradas na literatura tanto as mais tradicionais (tais como a caracterização de espaços de Baire com o jogo de Banach-Mazur), como as mais atuais (tais como a relação entre a propriedade de Menger e D-espaços). Além do conteúdo voltado para o livro, são apresentados um problema de combinatória finita (assim como uma solução parcial para tal) que foi encontrado com o estudo de estratégias posicionais e alguns resultados envolvendo novas variações de princípios de seleção e jogos clássicos, possibilitando a caracterização de alguns espaços notáveis.

The paper deals with elliptic theory on manifolds with boundary represented as a covering space. We compute the index for a class of nonlocal boundary value problems. For a nontrivial covering, the index defect of the Atiyah-Patodi-Singer boundary value problem is computed. We obtain the Poincaré duality in the K-theory of the corresponding manifolds with singularities.

This dissertation studies optimization problems that involve probabilistic covering constraints. A probabilistic constraint evaluates and requires that the probability that a set of constraints involving random coefficients with known distributions hold satisfy a minimum requirement. A covering constraint involves a linear inequality on non-negative variables with a greater or equal to sign and non-negative coefficients. A variety of applications, such as set cover problems, node/edge cover problems, crew scheduling, production planning, facility location, and machine learning, in uncertain settings involve probabilistic covering constraints. In the first part of this dissertation we consider probabilistic covering linear programs. Using the sampling average approximation (SAA) framework, a probabilistic covering linear program can be approximated by a covering k-violation linear program (CKVLP), a deterministic covering linear program in which at most k constraints are allowed to be violated. We show that CKVLP is strongly NP-hard. Then, to improve the performance of standard mixed-integer programming (MIP) based schemes for CKVLP, we (i) introduce and analyze a coefficient strengthening scheme, (ii) adapt and analyze an existing cutting plane technique, and (iii) present a branching technique. Through computational experiments, we empirically verify that these techniques are significantly effective in improving solution times over the CPLEX MIP solver. In particular, we observe that the proposed schemes can cut down solution times from as much as six days to under four hours in some instances. We also developed valid inequalities arising from two subsets of the constraints in the original formulation. When incorporating them with a modified coefficient strengthening procedure, we are able to solve a difficult probabilistic portfolio optimization instance listed in MIPLIB 2010, which cannot be solved by existing approaches. In the second part of this dissertation we study a class of probabilistic 0-1 covering problems, namely probabilistic k-cover problems. A probabilistic k-cover problem is a stochastic version of a set k-cover problem, which is to seek a collection of subsets with a minimal cost whose union covers each element in the set at least k times. In a stochastic setting, the coefficients of the covering constraints are modeled as Bernoulli random variables, and the probabilistic constraint imposes a minimal requirement on the probability of k-coverage. To account for absence of full distributional information, we define a general ambiguous k-cover set, which is ``distributionally-robust." Using a classical linear program (called the Boolean LP) to compute the probability of events, we develop an exact deterministic reformulation to this ambiguous k-cover problem. However, since the boolean model consists of exponential number of auxiliary variables, and hence not useful in practice, we use two linear program based bounds on the probability that at least k events occur, which can be obtained by aggregating the variables and constraints of the Boolean model, to develop tractable deterministic approximations to the ambiguous k-cover set. We derive new valid inequalities that can be used to strengthen the linear programming based lower bounds. Numerical results show that these new inequalities significantly improve the probability bounds. To use standard MIP solvers, we linearize the multi-linear terms in the approximations and develop mixed-integer linear programming formulations. We conduct computational experiments to demonstrate the quality of the deterministic reformulations in terms of cost effectiveness and solution robustness. To demonstrate the usefulness of the modeling technique developed for probabilistic k-cover problems, we formulate a number of problems that have up till now only been studied under data independence assumption and we also introduce a new applications that can be modeled using the probabilistic k-cover model.

Given a set of unit disks in the plane with union area A, what fraction of A can be covered by selecting a pairwise disjoint subset of the disks? Richard Rado conjectured 1/4 and proved 1/4.41. In this thesis, we consider a variant of this problem where the disjointness constraint is relaxed: selected disks must be k-colourable with disks of the same colour pairwise-disjoint. Rado's problem is then the case where k = 1, and we focus our investigations on what can be proven for k > 1. Motivated by the problem of channel-assignment for Wi-Fi wireless access points, in which the use of 3 or fewer channels is a standard practice, we show that for k = 3 we can cover at least 1/2.09 and for k = 2 we can cover at least 1/2.82. We present a randomized algorithm to select and colour a subset of n disks to achieve these bounds in O(n) expected time. To achieve the weaker bounds of 1/2.77 for k = 3 and 1/3.37 for k = 2 we present a deterministic O(n^2) time algorithm. We also look at what bounds can be proven for arbitrary k, presenting two different methods of deriving bounds for any given k and comparing their performance. One of our methods is an extension of the method used to prove bounds for k = 2 and k = 3 above, while the other method takes a novel approach. Rado's proof is constructive, and uses a regular lattice positioned over the given set of disks to guide disk selection. Our proofs are also constructive and extend this idea: we use a k-coloured regular lattice to guide both disk selection and colouring. The complexity of implementing many of the constructions used in our proofs is dominated by a lattice positioning step. As such, we discuss the algorithmic issues involved in positioning lattices as required by each of our proofs. In particular, we show that a required lattice positioning step used in the deterministic O(n^2) algorithm mentioned above is 3SUM-hard, providing evidence that this algorithm is optimal among algorithms employing such a lattice positioning approach. We also present evidence that a similar lattice positioning step used in the constructions for our better bounds for k = 2 and k = 3 may not have an efficient exact implementation.

Given a set of unit disks in the plane with union area A, what fraction of A can be covered by selecting a pairwise disjoint subset of the disks? Richard Rado conjectured 1/4 and proved 1/4.41. In this thesis, we consider a variant of this problem where the disjointness constraint is relaxed: selected disks must be k-colourable with disks of the same colour pairwise-disjoint. Rado's problem is then the case where k = 1, and we focus our investigations on what can be proven for k > 1. Motivated by the problem of channel-assignment for Wi-Fi wireless access points, in which the use of 3 or fewer channels is a standard practice, we show that for k = 3 we can cover at least 1/2.09 and for k = 2 we can cover at least 1/2.82. We present a randomized algorithm to select and colour a subset of n disks to achieve these bounds in O(n) expected time. To achieve the weaker bounds of 1/2.77 for k = 3 and 1/3.37 for k = 2 we present a deterministic O(n^2) time algorithm. We also look at what bounds can be proven for arbitrary k, presenting two different methods of deriving bounds for any given k and comparing their performance. One of our methods is an extension of the method used to prove bounds for k = 2 and k = 3 above, while the other method takes a novel approach. Rado's proof is constructive, and uses a regular lattice positioned over the given set of disks to guide disk selection. Our proofs are also constructive and extend this idea: we use a k-coloured regular lattice to guide both disk selection and colouring. The complexity of implementing many of the constructions used in our proofs is dominated by a lattice positioning step. As such, we discuss the algorithmic issues involved in positioning lattices as required by each of our proofs. In particular, we show that a required lattice positioning step used in the deterministic O(n^2) algorithm mentioned above is 3SUM-hard, providing evidence that this algorithm is optimal among algorithms employing such a lattice positioning approach. We also present evidence that a similar lattice positioning step used in the constructions for our better bounds for k = 2 and k = 3 may not have an efficient exact implementation.

The minimum set cover problem is, without question, among the most ubiquitous and well-studied problems in computer science. Its theoretical hardness has been fully characterized--logarithmic approximability has been established, and no sublogarithmic approximation exists unless P=NP. However, the gap between real-world instances and the theoretical worst case is often immense--many covering problems of practical relevance admit much better approximations, or even solvability in polynomial time. Simple combinatorial or geometric structure can often be exploited to obtain improved algorithms on a problem-by-problem basis, but there is no general method of determining the extent to which this is possible. In this thesis, we aim to shed light on the relationship between the structure and the hardness of covering problems. We discuss several measures of structural complexity of set cover instances and prove new algorithmic and hardness results linking the approximability of a set cover problem to its underlying structure. In particular, we provide: - An APX-hardness proof for a wide family of problems that encode a simple covering problem known as Special-3SC. - A class of polynomial dynamic programming algorithms for a group of weighted geometric set cover problems having simple structure. - A simplified quasi-uniform sampling algorithm that yields improved approximations for weighted covering problems having low cell complexity or geometric union complexity. - Applications of the above to various capacitated covering problems via linear programming strengthening and rounding. In total, we obtain new results for dozens of covering problems exhibiting geometric or combinatorial structure. We tabulate these problems and classify them according to their approximability.

In this study, our aim is to determine the locations of bottle banks used in collecting recycled glass. The collection of recycled glass is done by a fleet of vehicles that visit some predetermined collection points, like restaurants and hospitals. The location of bottle banks depends on the closeness of the banks to the population zones where the recycled class is generated, and to the closeness of the banks to the predetermined collection points. A mathematical model, which combines the maximal covering problem in the presence of partial coverage and vehicle routing problem with profits, is presented. Heuristic procedures are proposed for the solution of the problem. Computational results based on generated test problems are provided. We also discuss a case study, where bottle banks are located in Yenimahalle, a district of Ankara