O problema de dimensionamento de lotes determina um plano de produção que apoia às tomadas de decisões, a médio prazo, em meios industriais. Este plano de produção indica as quantidades de cada item que devem ser produzidas em cada período do horizonte de planejamento, de acordo com um objetivo dado e satisfazendo a demanda dos clientes. Diversos métodos de solução foram propostas na literatura, considerando a dificuldade de solução de algumas classes de problemas e a necessidade de métodos que gerem soluções de alta qualidade em um tempo computacional adequado. Neste trabalho, abordamos heurísticas baseadas na formulação matemática (LP-and-fix, relax-and-fix e fix-and-optimize), uma metaheurística (algoritmo de abelhas) e dois métodos híbridos, utilizados na solução de dois problemas distintos de dimensionamento de lotes multiestá- gio com limitação de capacidade. Consideramos também, a utilização de três formulações da literatura, para verificar a influência de cada uma sobre as abordagens de solução verificadas. Os resultados computacionais demonstraram que os métodos baseados na formulação matemática do problema se mostraram eficientes, mas limitados normalmente a ótimos locais, enquanto os métodos híbridos puderam superar estes ótimos locais, utilizando conceitos da metaheurística algoritmo de abelhas para isto. Além disso, pudemos verificar a influência de uma formulação \"forte\" sobre as soluções geradas pelas abordagens de solução, demonstrando que métodos baseados em relaxação linear conseguem obter maiores vantagens deste tipo de formulação, mas outras abordagens podem ou não obter estas vantagens, dependendo do problema abordado / The lot-sizing problem determines a production plan, which supports the decision making, in the medium term, at the industrial environment. This production plan indicates the amounts of each item to be produced in each period of the planning horizon, according to a given objective and satisfying customer\'s demand. Diverse solution methods have been proposed in the literature, considering the difficulty of solving some problem classes and the need of methods to generate solutions quickly. In this work, we develop matheuristics (LP-and-fix, relax-and-fix and fix-and-optimize), one metaheuristic (bees algorithm) and two hybrid methods, used to solve two different multilevel capacitated lot-sizing problems. We also consider the use of three different formulations of the literature to verify the influence of each one on the solutions approaches. The computational results show that the matheuristics proved to be efficient, but usually limited to local optima, while the hybrid methods could escape from these local optima, using concepts of bees algorithm to do this. Additionally, we test the effect of a tight formulation on the solutions approaches, demonstrating that LP-based heuristics can obtain further advantages from this type of formulation, but other approaches can take these advantages, depending on the problem addressed

abstract: In this work, the stacked values of battery energy storage systems (BESSs) of various power and energy capacities are evaluated as they provide multiple services such as peak shaving, frequency regulation, and reserve support in an ‘Arizona-based test system’ - a simplified, representative model of Salt River Project’s (SRP) system developed using the resource stack information shared by SRP. This has been achieved by developing a mixed-integer linear programming (MILP) based optimization model that captures the operation of BESS in the Arizona-based test system. The model formulation does not include any BESS cost as the objective is to estimate the net savings in total system operation cost after a BESS is deployed in the system. The optimization model has been formulated in such a way that the savings due to the provision of a single service, either peak shaving or frequency regulation or spinning reserve support, by the BESS, can be determined independently. The model also allows calculation of combined savings due to all the services rendered by the BESS. The results of this research suggest that the savings obtained with a BESS providing multiple services are significantly higher than the same capacity BESS delivering a single service in isolation. It is also observed that the marginal contribution of BESS reduces with increasing BESS energy capacity, a result consistent with the law of diminishing returns. Further, small changes in the simulation environment, such as factoring in generator forced outage rates or projection of future solar penetration, can lead to changes as high as 10% in the calculated stacked value. / Dissertation/Thesis / Masters Thesis Electrical Engineering 2020

<div><div><div><p>It is well-known that the sum of reciprocals of twin primes converges or is a finite sum.</p><p>In the same spirit, Samuel Wagstaff proved in 2021 that the sum of reciprocals of primes p</p><p>such that ap + b is prime also converges or is a finite sum for any a, b where gcd(a, b) = 1</p><p>and 2 | ab. Wagstaff gave upper and lower bounds in the case that ab is a power of 2. Here,</p><p>we expand on his work and allow any a, b satisfying gcd(a, b) = 1 and 2 | ab. Let Πa,b be the</p><p>product of p−1 over the odd primes p dividing ab. We show that the upper bound of these p−2</p><p>sums is Πa,b times the upper bound found by Wagstaff and provide evidence as to why we cannot hope to do better than this. We also give several examples for specific pairs (a, b).</p><p><br></p><p>Next, we turn our attention to elliptic Carmichael numbers. In 1987, Dan Gordon defined the notion of an elliptic Carmichael number as a composite integer n which satisfies a Fermat- like criterion on elliptic curves with complex multiplication. More recently, in 2018, Thomas Wright showed that there are infinitely such numbers. We build off the work of Wright to prove that there are infinitely many elliptic Carmichael numbers of the form a (mod M) for a certain M, using an improved lower bound due to Carl Pomerance. We then apply this result to comment on the infinitude of strong pseudoprimes and strong Lucas pseudoprimes.</p><p><br></p><p>Finally, we consider the problem of classifying for which k does one have Φk(x) | Φn(x)−1, where Φn(x) is the nth cyclotomic polynomial. We provide a motivating example as to how this can be applied to primality proving. Then, we complete the case k = 8 and give a partial characterization for the case k = 16. This leads us to conjecture necessary and sufficient conditions for when Φk(x) | Φn(x) − 1 whenever k is a power of 2.</p></div></div></div>

This thesis introduces a Large Neighborhood Search (LNS) method to solve a multi-processor avionics scheduling problem. In a typical scheduling problem, tasks are scheduled with exact starting times. In this thesis however, tasks will instead be assigned to disjoint time segments, called buckets. For an assignment to be feasible, precedence relations and capacity constraints related to network and computing resources need to be fulfilled. The introduced LNS method relies on solving Mixed-Integer Programming (MIP)-models. To make progress in the search for a feasible assignment, we construct a MIP-model that allows violation of the problem constraints at a cost of increased objective value. The LNS method uses two operators, a destroy operator that chooses a set of tasks that are allowed to change buckets, and a repair operator that through solving the MIP-model creates a new schedule. This thesis develops 11 types of destroy operators and 30 (concrete) variants of them. The MIP-based LNS is evaluated on a set of 60 instances with up to 84 000 tasks and 21 processors. The instances belongs to six categories of varying difficulty. The MIP-based LNS solves 50 instances within our time limit, and the largest instance solved has 77 757 tasks. This is significantly better than solving the complete MIP-model in a single step. With this approach only 36 instances can be solved within our time limit and the largest instance solved has 48554 tasks.

The Course Timetabling Problem is a widely studied optimization problem where a number of sections are scheduled in concert with the assignment of students to sections in order to maximize the desirability of the resulting schedule for all stakeholders. This problem is commonly solved as a linear program with variables for each student or group of students with identical schedules. In this paper we explore an alternative formulation that aggregates binary student variables into integer variables denoting the number of students enrolled in a course. Our solution method assumes decomposition of the general schedule into time blocks, and applies a unique set theory based, integer linear programming formulation that seeks to maximize the total number of students enrolled in their desired sections across the time blocks. Once the problem has been solved, the simpler problem of disaggregating the solution is resolved. This approach can be used to find exact solutions, given sufficient computing power, or simplified to quickly find solutions within calculable bounds of optimality. Case studies with a local elementary school and a local high school show that the new formulation is significantly faster and can be made to be reasonably accurate.

Cette thèse est consacrée à une étude approfondie du Rank Pricing Problem (RPP) et de deux généralisations. Le RPP est un problème d'optimisation combinatoire qui vise à fixer le prix des produits d'une entreprise afin de maximiser son profit. Elle concerne les clients à la demande, c'est-à-dire les clients qui sont intéressés par plusieurs produits de l'entreprise, mais qui n'ont l'intention d'en acheter qu'un. Les clients disposent d'un budget fixe et classent les produits qui les intéressent du "meilleur" au "pire". Lorsque l'entreprise fixe les prix, chaque client achètera son produit préféré parmi ceux qu'il peut se permettre. Dans le RPP, nous supposons que les produits sont offerts en quantité illimitée, ce qui convient si l'on considère que l'entreprise a suffisamment de produits pour satisfaire la demande, ou lorsque les produits peuvent être fabriqués rapidement avec un coût négligeable (par exemple, les biens numériques).Cette thèse se compose de quatre chapitres. Le premier est un chapitre d'introduction au problème et aux concepts mathématiques présents dans la thèse, tandis que les trois chapitres suivants se concentrent sur chacun des problèmes étudiés :le RPP et deux généralisations. Ainsi, le troisième chapitre est consacré à l'étude du Rank Pricing Problem with Ties (RPPT). Dans cette extension du problème, nous supposons que les clients peuvent exprimer leur indifférence entre les produits qui les intéressent au moyen de liens dans leur liste de préférences. Enfin, le dernier chapitre de la thèse comprend l'étude du Capacitated Rank Pricing Problem (CRPP) avec envie. Dans cette extension, nous avons supposé des prix de réserve pour les clients qui reflètent ce qu'ils sont prêts à payer pour chaque produit, plutôt qu'un budget unique par consommateur. Cependant, la principale différence est que dans le cas du CRPP, l'entreprise dispose d'un nombre limité de produits et peut ne pas être en mesure de satisfaire la demande de tous les clients. L'objectif de la thèse est d'obtenir des formulations linéaires en nombres entiers mixtes pour les trois problèmes étudiés, et de les comparer sur le plan théorique et/ou computationnel. À cette fin, la méthodologie utilisée est basée sur la proposition de variables de décision et de contraintes appropriées qui modélisent le problème. L'objectif suivant est l'amélioration de ces formulations au moyen d'inégalités valides qui réduisent l’ensemble admissible de la relaxation du problème et permettent d'obtenir une meilleure borne de la relaxation linéaire. Et enfin, un troisième objectif est la proposition d'algorithmes de résolution pour chacun de ces modèles, et leur comparaison ultérieure au moyen d'études computationnelles et de résolution au moyen de logiciels d'optimisation commerciaux. / This doctorate is entirely devoted to an in-depth study of the Rank Pricing Problem (RPP) and two generalizations. The RPP is a combinatorial optimization problem which aims at setting the prices of a series of products of a company to maximize its revenue. This problem is specified by a set of unit-demand customers, that is, customers interested in a subset of the products offered by the company which intend to buy at most one of them. To do so, they count on a fixed budget, and they rank the products of their interest from the “best” to the “worst”. Once the prices are established by the company, they will purchase their highest-ranked product among the ones they can afford. In the RPP, it is assumed an unlimited supply of products, which is consistent with a company having enough copies of a product to satisfy the demand, or with a setting where the products can be produced quickly at negligible cost (e.g. digital goods). This dissertation consists of four chapters. The first chapter introduces the RPP problem and the mathematical concepts present in the work, whereas each of the next three chapters tackles the resolution of each of the problems of study: the RPP and two generalizations. Thus, Chapter 3 is dedicated to the Rank Pricing Problem with Ties (RPPT), an extension of the RPP where we consider that customers can express indifference among products in their preference list. And the last chapter of the thesis is devoted to a generalization of the problem that we have named the Capacitated Rank Pricing Problem (CRPP) with envy. For this generalization, we have considered reservation prices of customers for the different products that reflect their willingness to pay, instead of a single budget per customer. However, the main difference is that, in the CRPP, the company has a limited supply of products and might not be able to satisfy all the customers’ requests. This is a realistic assumption that we can find in many companies.The aim of this thesis is the proposal of mixed-integer linear formulations for the three problems of study, and their theoretical and/or computational comparison. The methodology used is based on the introduction of decision variables and adequate restrictions to model the problems. Another objective consists in strengthening the formulations by means of valid inequalities that reduce the feasible region of the relaxed problem and allow us to obtain better linear relaxation bounds. Finally, a third goal is to derive resolution algorithms for each of these models and compare them computationally, using commercial solvers. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

The diploma thesis deals with linear integer optimization in production logistics via mathematical programming. This tool is used for optimization of the time production schedule with a number of various jobs performed by a company with limited resources. The thesis solves the problem in conjunction with TOSHULIN, a.s. company, which is interested in solving the problem. As a result is the software implementation in which Gantt chart is created as its output.

Water scarcity has become a global problem due to diminishing water resource and pollution of the remaining resources. The problems arising fromwater scarcity are exacerbated rapid urbanisation and industrialisation. Water quality management systems are introduced. Numerous water management methods exist some of which, if applied e ectively, can remedy these problems. In South Africa, water management systems are urgently needed to start addressing issues around the longterm sustainability of our limited water resource. Water quality modelling is one of the tools employed to assist in validating decisions made during the planning phase of a water quality management system. It also provides a means of exploring viable options to be considered when these decisions are to be made. A range of management options exist and implementing all of them may prove costly, therefore optimisation techniques are utilised to narrow down options to the most e ective and least costly among the available choices. Commonly, water quality models are used to predict concentrations in the river from which constraint equations are generated. The constraint equations are used in optimisation models to generate feasible solutions by either maximising or minimising the objective function. In this case the objective function is wastewater treatment cost. Constraints equations are based on the set in-stream water quality standard at selected theoretical measuring stations (checkpoints) in the stream and a feasible solution is one that suggests a treatment method that will ensure water quality standards are met at the lowest regional treatment cost. This study focused on the Upper Olifants river catchment near Witbank in Mpumalanga province. This catchment is subjected to extensive wastewater e uents from various mining operations and wastewater treatment plants. The aim here was to develop a water quality model for predicting dissolved oxygen (DO) concentration in the river, and to use a modelling approach to generate constraint equations for the system. A Streeter-Phelps stream simulation model was employed to predict DO concentration in the river. A mixed-integer programming technique was then used to evaluate the impact of nine wastewater treatment facilities discharging e uent into the river. Treatment levels were varied to test model reliability. The coupled stream simulation and optimisation model produced feasible solutions under 2 minutes, with each solution suggesting a range of treatment levels which ensured that the critical DO concentration was above 5 mg/L and the most stringent DO concentration the system could manage without violations anywhere else in the stream was obtained to be 7mg/L. / Dissertation (MEng)--University of Pretoria, 2013. / gm2014 / Chemical Engineering / unrestricted

Orthology and paralogy distinguish whether a pair of genes originated by a speciation or a gene duplication event, whereas xenology refers to horizontal gene transfer. These concepts play a key role in phylogenomics and species tree inference is one of its prevalent tasks. Commonly, species tree inference is performed using sequence-based phylogenetic methods which heavily rely on the initial data sets to be solely composed of 1:1 orthologs. Such approaches are strongly restricted to a small set of genes that provide information about the species tree. In this work, it is shown that the restriction to 1:1 orthologs is not necessary to reconstruct a reliable hypothesis on the evolutionary history of species. Besides orthology, knowledge on all three major driving forces of gene evolution can be considered: speciation, gene duplication, and horizontal gene transfer. The corresponding concepts of orthology, paralogy, and xenology imply binary relations on pairs of genes. These relations, in turn, convey meaningful phylogenetic information and allow the inference of plausible phylogenetic species trees. To this end, it is shown that orthology, paralogy, and xenology have to fulfill certain mathematical properties. In particular, they have to be representable as a tree – the so-called gene tree. This work investigates the theoretical concepts of tree representable sets of binary relations to unfold the underlying mathematical structure. Various novel characterizations for those relations are given and the close connection between tree representable sets of binary relations and cographs, symbolic ultrametrics, and so-called unp 2-structures is revealed. Based on the novel characterizations, polynomial-time recognition algorithms for tree representable sets of relations are presented. In the case, a set of relations is tree representable, the corresponding tree representation can be found in polynomial time as well. Moreover, for the NP-complete problems of editing a given set of relations to its closest tree representable set, exact algorithms are developed by means of formulations as integer linear program. Finally, all algorithms have been implemented in the software ParaPhylo, a species tree inference method based on orthology and paralogy data. It is demonstrated on simulated data sets, as well as real-life data sets, that non-trivial phylogenies can indeed be reconstructed from tree-free orthology estimates alone.

This work contains a study of CeRuSn, which undergoes two structural transitions at 290 K and 256 K both connected with large temperature hysteresis. During the transitions the lattice shrinks along the c axis. At low temperatures the compound orders antiferromagnetically below 2.8(1) K. A strong magnetocrystalline anisotropy is caused by very shortened Ce-Ru separations pointing approximately along the c axis. Due to a strong hybridization, two thirds of Cerium atoms are in a non integer valence state. For the first time synthesized single-crystals of YbPt2Si2 a Yb2Pt3Si5 show no magnetic ordering. A maximum, which is visible in the temperature dependences of magnetic susceptibility originate in thermal population of the magnetic Yb3+ state. Powered by TCPDF (www.tcpdf.org)