This thesis is a survey of the studies of Ames,Payne and Schaefer about the partial differential equations with nonstandard auxiliary conditions / this is where the values of the solution are prescribed as a combination of initial time t=0 and at a later time t=T. The first chaper is introductory and contains some historical background of the problem,basic definitions and theorems.In Chapter 2 energy bounds and pointwise bounds for the solutions of the nonstandard hyperbolic problems have been investigated and by means of energy bound the uniqueness of solutions is examined. Similar discussions for the nonstandard parabolic problems have been presented in Chapter 3. Lastly in Chapter 4 a new continuous dependence result has been derived for the nonstandard problem.

O objetivo desse trabalho é o de estudar o problema de programação de tarefas num ambiente produtivo com uma única máquina com data comum de entrega. Nesse caso, as tarefas, depois de processadas uma única vez na máquina, devem ser entregues em uma data comum e sofrem penalidades de adiantamento e de atraso conforme o instante em que são completadas. Na prática, esse problema é encontrado em casos de pedidos de lotes de produtos com data de entrega comum préespecificada, embarques para exportação e material químico ou misturas que têm vida média de curta duração. Problemas desse tipo são NP-hard (Hall, Kubiak & Sethi, 1991; Hoogeven & van de Velde, 1991), sendo comumente tratados na literatura através de heurísticas e meta-heurísticas. Visto não ser de nosso conhecimento a existência na literatura de tratamento desse problema através de métodos exatos, propôs-se a utilização de um algoritmo do tipo branch-and-bound para obtenção da solução ótima do problema que minimize a soma das penalidades de adiantamento e de atraso. No desenvolvimento do algoritmo, a utilização de propriedades do problema foi importante na elaboração de limitantes inferiores e regras de dominância que melhoraram a eficiência do modelo. Os experimentos realizados avaliaram o desempenho de diferentes critérios elaborados, como escolha do nó pai, limitante inferior, ordem de execução das estratégias e ordem de construção da seqüência. Os resultados obtidos mostraram-se robustos quando comparados com o benchmark da literatura e revelaram o bom desempenho do modelo para problemas de pequeno porte, superando o desempenho de programas de otimização comerciais. / The objective of this work is to study the single-machine scheduling problem with a common due date. In this case, jobs, after be processed only once in the machine, must be delivered in a common due date and they are penalized of earliness or tardiness according to their completion time. This problem is found in cases of batch production with prespecified common due date, exportation shipping and chemical material that has short half-life period. This kind of problem is NP-hard (Hall, Kubiak & Sethi, 1991; Hoogeven & van de Velde, 1991) and it has been treated in the literature by heuristics and meta-heuristics. Not having knowledge about previous treatment by exact methods in the literature, it was proposed the implementation of a branch-and-bound algorithm to obtain the optimal solution that minimizes the total weighted earliness and tardiness penalties. In the development of the algorithm, the utilization of problem properties was important to the elaboration of lower bounds and pruning rules that have enhanced the efficiency of the model. The realized tests have evaluated the performance of different criteria, like the choice of father node, lower bound, strategy execution order and sequence construction order. The obtained results have demonstrated robustness comparing to benchmark and they have revealed the good working of the model for small problems, overcoming optimization software performance.

Neste trabalho, abordamos métodos de resolução para o problema de dimensionamento de lotes que contempla o planejamento da produção de vários produtos em múltiplas máquinas. A fabricação dos produtos consome tempo de produção e preparação de uma capacidade de produção limitada. A demanda pelos produtos é conhecida e pode ser atendida com atraso durante um horizonte de planejamento finito. O objetivo é minimizar a soma dos custos de produção, preparação para a produção, estoque dos produtos e atraso na entrega destes. Em uma primeira etapa, desenvolvemos uma busca tabu determinística baseada em outra, aleatória, que foi apresentada na literatura. Com isso, realizamos uma análise sobre a influência de fatores aleatórios sobre heurísticas do tipo busca tabu quando aplicadas ao problema estudado. Posteriormente, desenvolvemos um método híbrido baseado em busca tabu, branch-and-cut e programação linear para a resolução do problema. Nos testes computacionais realizados, o método proposto mostrou-se competitivo quando comparado a outras heurísticas apresentadas na literatura / This paper proposes two methods to solve the capacitated lot-sizing problem with multiple products and parallel machines. The manufacturing of products consumes machines capacity (production time and setup time), which is scarce. The demand for the products is known and can be met with backlogging. The objective is to minimize the sum of production, setup, holding and backlog costs. In a first step, we developed a deterministic tabu search heuristic based on a random version from the literature and then conducted an analysis of the influence of random factors on tabu search heuristics when applied to solve the studied problem. Subsequently, we designed a hybrid method based on tabu search, branch-andcut and linear programming. Computational experiments show that this hybrid method is competitive with other heuristics presented in the literature

Orientadores: Ariovaldo Verandio Garcia, Marcos Julio Rider Flores / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-15T23:19:01Z (GMT). No. of bitstreams: 1 Oliveira_MarinaLavoratode_D.pdf: 1360671 bytes, checksum: e66710c118252edf8c3638375c56fdc7 (MD5) Previous issue date: 2010 / Abstract: In this work the Distribution System Integrated Planning (DSIP) problem is modeled as a mixed integer (binary) nonlinear program problem. Two techniques were investigated to solve this problem. First, a specialized Constructive Heuristic Algorithm (CHA) was implemented. A sensitivity index is used in each step of the CHA to add a circuit, a substation, a capacitor bank or a voltage regulator to the distribution system. This sensitivity index is obtained by solving the DSIP problem considering the numbers of circuits and substations to be added as continuous variables (the DSIP relaxed problem). The objective of the DSIP is to minimize the operation costs and the construction costs of circuits, substations, capacitors and voltage regulators, which are subjected to constraints of power balance, voltage magnitude, maximum circuit and substation capacities, taps control and radiality constraint. In addition, a local improvement phase to improve the initial solution of the CHA and a branching technique to avoid the infeasibility cases in the distribution system operation were included / Doutorado / Energia Eletrica / Doutor em Engenharia Elétrica

Orientador: Paulo Augusto Valente Ferreira / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-21T14:52:27Z (GMT). No. of bitstreams: 1 Ashtiani_AlirezaMohebi_D.pdf: 1381601 bytes, checksum: 9ae82bd53a7cf70422fed2348416f8f0 (MD5) Previous issue date: 2012 / Resumo: Muitos problemas práticos em Engenharia, Economia e Planejamento são modelados de maneira conveniente como problemas de Otimização Global. Esta tese tem como objetivo principal apresentar novas técnicas de Otimização Global com foco na resolução de duas importantes classes de problemas: problemas de Programação Multiplicativa Generalizada, os quais envolvem a minimização e a maximização de uma soma finita de produtos de funções convexas e côncavas, respectivamente, e problemas de Programação Fracionária Generalizada, os quais, por sua vez, envolvem a minimização e a maximização de uma soma finita de razões de funções convexa-côncava ou côncava-convexa, respectivamente. Na tese demonstra-se que todos estes problemas podem ser eficientemente resolvidos por um mesmo algoritmo de aproximação externa, a partir da reformulação dos problemas como problemas com infinitas restrições lineares de desigualdade. Um algoritmo baseado em enumeração de restrições e um algoritmo de aproximação externa combinado a uma técnica branch-and-bound são usados para resolver globalmente problemas de Programação Multiplicativa. Em seguida, as mesmas técnicas são empregadas na resolução de problemas de Programação Fracionária. Experiências computacionais atestam a viabilidade e a eficiência dos métodos de Otimização Global propostos, os quais também são facilmente programáveis a partir de pacotes de otimização disponíveis comercialmente / Abstract: Many practical problems in Engineering, Economics and Planning are modeled in a convenient way by Global Optimization problems. The principal objective of this thesis is to introduce new global optimization techniques with focus on the resolution of two important classes of problems: Generalized Multiplicative Programming Problems, in which involve the minimization and maximization of a finite sum of products of convex and concave functions, respectively, and Generalized Fractional Programming Problems, in which, in turn, involve the minimization and maximization of a finite sum of convex-concave and concave-convex ratio functions, respectively. The thesis demonstrates that all these problems can be efficiently solved by the same outer approximation algorithm, from the reformulation of the problems as problems with infinite linear inequality constraints. An algorithm based on a constraint enumeration and an outer approximation algorithm together with a branch-and-bound technique are used to globally solve Multiplicative Programming problems. Then, the same techniques are employed in the resolution of Fractional Programming problems. Computational experiments certify the viability and efficiency of the proposed Global Optimization methods, which are also easily programmable through commercially available optimization packages / Doutorado / Automação / Doutor em Engenharia Elétrica

O problema de seleção de características, no contexto de Reconhecimento de Padrões, consiste na escolha de um subconjunto X de um conjunto S de características, de tal forma que X seja \"ótimo\" dentro de algum critério. Supondo a escolha de uma função custo c apropriada, o problema de seleção de características é reduzido a um problema de busca que utiliza c para avaliar os subconjuntos de S e assim detectar um subconjunto de características ótimo. Todavia, o problema de seleção de características é NP-difícil. Na literatura existem diversos algoritmos e heurísticas propostos para abordar este problema; porém, quase nenhuma dessas técnicas explora o fato que existem funções custo cujos valores são estimados a partir de uma amostra e que descrevem uma \"curva em U\" nas cadeias do reticulado Booleano (P(S),<=), um fenômeno bem conhecido em Reconhecimento de Padrões: conforme aumenta-se o número de características consideradas, há uma queda no custo do subconjunto avaliado, até o ponto em que a limitação no número de amostras faz com que seguir adicionando características passe a aumentar o custo, devido ao aumento no erro de estimação. Em 2010, Ris e colegas propuseram um novo algoritmo para resolver esse caso particular do problema de seleção de características, que aproveita o fato de que o espaço de busca pode ser organizado como um reticulado Booleano, assim como a estrutura de curvas em U das cadeias do reticulado, para encontrar um subconjunto ótimo. Neste trabalho estudamos a estrutura do problema de minimização de funções custo cujas cadeias são decomponíveis em curvas em U (problema U-curve), provando que o mesmo é NP-difícil. Mostramos que o algoritmo de Ris e colegas possui um erro que o torna de fato sub-ótimo, e propusemos uma versão corrigida e melhorada do mesmo, o algoritmo U-Curve-Search (UCS). Apresentamos também duas variações do algoritmo UCS que controlam o espaço de busca de forma mais sistemática. Introduzimos dois novos algoritmos branch-and-bound para abordar o problema, chamados U-Curve-Branch-and-Bound (UBB) e Poset-Forest-Search (PFS). Para todos os algoritmos apresentados nesta tese, fornecemos análise de complexidade de tempo e, para alguns deles, também prova de corretude. Implementamos todos os algoritmos apresentados utilizando o arcabouço featsel, também desenvolvido neste trabalho; realizamos experimentos ótimos e sub-ótimos com instâncias de dados reais e simulados e analisamos os resultados obtidos. Por fim, propusemos um relaxamento do problema U-curve que modela alguns tipos de projeto de classificadores; também provamos que os algoritmos UCS, UBB e PFS resolvem esta versão generalizada do problema. / The feature selection problem, in the context of Pattern Recognition, consists in the choice of a subset X of a set S of features, such that X is \"optimal\" under some criterion. If we assume the choice of a proper cost function c, then the feature selection problem is reduced to a search problem, which uses c to evaluate the subsets of S, therefore finding an optimal feature subset. However, the feature selection problem is NP-hard. Although there are a myriad of algorithms and heuristics to tackle this problem in the literature, almost none of those techniques explores the fact that there are cost functions whose values are estimated from a sample and describe a \"U-shaped curve\" in the chains of the Boolean lattice o (P(S),<=), a well-known phenomenon in Pattern Recognition: for a fixed number of samples, the increase in the number of considered features may have two consequences: if the available sample is enough to a good estimation, then it should occur a reduction of the estimation error, otherwise, the lack of data induces an increase of the estimation error. In 2010, Ris et al. proposed a new algorithm to solve this particular case of the feature selection problem: their algorithm takes into account the fact that the search space may be organized as a Boolean lattice, as well as that the chains of this lattice describe a U-shaped curve, to find an optimal feature subset. In this work, we studied the structure of the minimization problem of cost functions whose chains are decomposable in U-shaped curves (the U-curve problem), and proved that this problem is actually NP-hard. We showed that the algorithm introduced by Ris et al. has an error that leads to suboptimal solutions, and proposed a corrected and improved version, the U-Curve-Search (UCS) algorithm. Moreover, to manage the search space in a more systematic way, we also presented two modifications of the UCS algorithm. We introduced two new branch-and-bound algorithms to tackle the U-curve problem, namely U-Curve-Branch-and-Bound (UBB) and Poset-Forest-Search (PFS). For each algorithm presented in this thesis, we provided time complexity analysis and, for some of them, also proof of correctness. We implemented each algorithm through the featsel framework, which was also developed in this work; we performed optimal and suboptimal experiments with instances from real and simulated data, and analyzed the results. Finally, we proposed a generalization of the U-curve problem that models some kinds of classifier design; we proved the correctness of the UCS, UBB, and PFS algorithms for this generalized version of the U-curve problem.

Gescannte und vektorisierte technische Zeichnungen werden automatisch unter Nutzung eines Netzes von Modellen in eine hochwertige Datenstruktur migriert. Die Modelle beschreiben die Inhalte der Zeichnungen hierarchisch und deklarativ. Modelle für einzelne Bestandteile der Zeichnungen können paarweise unabhängig entwickelt werden. Dadurch werden auch sehr komplexe Zeichnungsklassen wie Elektroleitungsnetze oder Gebäudepläne zugänglich. Die Modelle verwendet der neue, sogenannte Y-Algorithmus: Hypothesen über die Deutung lokaler Zeichnungsinhalte werden hierarchisch generiert. Treten bei der Nutzung konkurrierender Modelle Konflikte auf, werden diese protokolliert. Mittels des Konfliktbegriffes können konsistente Interpretationen einer kompletten Zeichnung abstrakt definiert und während der Analyse einer konkreten Zeichnung bestimmt werden. Ein wahrscheinlichkeitsbasiertes Gütemaß bewertet jede dieser alternativen, globalen Interpretationen. Das Suchen einer bzgl. dieses Maßes optimalen Interpretation ist ein NP-hartes Problem. Ein Branch and Bound-Algorithmus stellt die adäquate Lösung dar.

Eutrophic Utah Lake receives a large nutrient load from a variety of sources, includingtreated wastewater discharges, runoff and tributaries, recycling from bottom sediments andAtmospheric Deposition (AD). AD was the focus of this study and was comprised of twocomplementary parts. First was a study of nitrogen and phosphorus depositions from theatmosphere, and second was a study of phosphorous as contained in soils near Utah Lake viafractionation methods.The soil samples were found to contain approximately 1,000 mg-P/kg soil for totalphosphorus (TP). A separate phosphorus (P) fractionation gave slightly higher values, excludingthe residual P, we are 95% confident that one gram of sample soil contains between 2.2 and 4.3percent water soluble P, 0.6 to 1.1 percent loosely-bound P, 2.5 to 4.4 percent aluminum andiron-bound P, and 90.7 to 94.2 percent calcium-bound P.AD results indicate that during the period from April 1 to Nov 17, 2018, Utah Lakereceived approximately 58 tons of soluble reactive P, 153 tons of TP, 118 tons of nitrogen (N)from nitrate, and 387 tons of N from ammonium via AD.Nutrient quantities from AD are very large compared to the 17 ton/yr of P needed for aeutrophic loading to the lake. Because of the very large overall nutrient loading to Utah Lake, itis likely that some other limiting growth factors are controlling algal growth.

The objective of this research is to explore the perceptions of UCF Upward Bound Program participants using focus groups and pre-posttest surveys in order to assess students' level of understanding of Science, Technology, Engineering, and Mathematics (STEM) related coursework, secondary education preparation in science and mathematics, and their perceptions of barriers to a STEM college education. Also, this study centers on the summer 2010 science and mathematics residential portion of the Upward Bound Program. Program outcomes and effectiveness were evaluated based on the change in student insight of the Upward Bound Program's stake in their secondary education. In addition, pre-posttest measures and interviews allowed a greater understanding of teacher and parent involvement in high school coursework success. Factors that involve self-efficacy, same or other group orientation and perceptions of student college environment were also analyzed. This research facilitated the understanding of first generation, low income and multicultural student's perceptions and what they view as a benefit or a hindrance to entering and successfully completing degrees in post-secondary institutions, specifically in STEM-related disciplines.

ITC/USA 2009 Conference Proceedings / The Forty-Fifth Annual International Telemetering Conference and Technical Exhibition / October 26-29, 2009 / Riviera Hotel & Convention Center, Las Vegas, Nevada / Data-aided symbol synchronization for bursty communications utilizes a predetermined modulation sequence, i.e., a preamble, preceding the payload. For effective symbol synchronization, this preamble must be designed in accordance with the modulation format. In this paper, we analyze preambles for shaped offset quadrature phase-shift keying (SOQPSK) waveforms. We compare the performance of several preambles by deriving the Cram´er-Rao bound (CRB), and identify a desirable one for the Telemetry Group variant of SOQPSK. We also demonstrate, via simulation, that the maximum likelihood estimator with this preamble approaches the CRB at moderate signal-to-noise ratio.