In this thesis, we study the Euclidean Steiner tree problem (ESTP) which arises in the field of combinatorial optimization. The ESTP asks for a network of minimal total edge length spanning a set of given terminal points in Rd with the ability to add auxiliary connecting points (Steiner points) to decrease the overall length of the network. The graph theory literature contains extensive studies of exact, approximation, and heuristic algorithms for ESTP in the plane, but less is known in higher dimensions. The contributions of this thesis include a heuristic algorithm and enhancements to an exact algorithm for solving the ESTP. We present a local search heuristic for the ESTP in Rd for d ≥ 2. The algorithm utilizes the Delaunay triangulation to generate candidate Steiner points for insertion, the minimum spanning tree to create a network on the inserted points, and second order cone programming to optimize the locations of Steiner points. Unlike other ESTP heuristics relying on the Delaunay triangulation, the algorithm inserts Steiner points probabilistically into Delaunay triangles to achieve different subtrees on subsets of terminal points. The algorithm extends effectively into higher dimensions, and we present computational results on benchmark test problems in Rd for 2 ≤ d ≤ 5. We develop new geometric conditions derived from properties of Steiner trees which bound below the number of Steiner points on paths between terminals in the Steiner minimal tree. We describe conditions for trees with a Steiner topology and show how these conditions relate to the Voronoi diagram. We describe more restrictive conditions for trees with a full Steiner topology and their implementation into the algorithm of Smith (1992). We present computational results on benchmark test problems in Rd for 2 ≤ d ≤ 5.

Historically, credit market conditions have been shown to impact economic activity, at times severely. For instance, in the late 2000s, the United States experienced a financial crisis that seized domestic and foreign credit markets. The ensuing lack of access to credit brought about a steep decline in output and a sluggish recovery. Accordingly, policymakers commonly take steps to mitigate the effects of adverse credit market conditions and, at times, conduct unconventional monetary policy once traditional policy tools become ineffective. This dissertation is a collection of essays regarding monetary policy, the flow of credit, financial crises, and the macroeconomy. Specifically, I describe monetary policy’s impact on the allocation of credit in the U.S. and analyze the role of upstream and downstream credit conditions and financial crises on international trade in a global supply chain. The first chapter assesses the impact of monetary policy shocks on credit reallocation and evaluates the importance of theoretical transmission mechanisms. Compustat data covering 1974 through 2017 is used to compute quarterly measures of credit flows. I find that expansionary monetary policy is associated with positive long-term credit creation and credit reallocation. These impacts are larger for long-term credit and for credit of financially constrained firms and firms that are perceived as risky to the lender. This is predicted by the balance sheet channel of monetary policy and mechanisms that reduce lenders’ risk perceptions and increase the tendency to search for yield. Furthermore, I find that, on average, the largest increases in credit creation resulting from monetary expansion are to firms that exhibit relatively low investment efficiency. These estimation results suggest that expansionary monetary policy may have a negative impact on future economic growth. The second chapter evaluates the quantitative effects of unconventional monetary policy in the late 2000s and early 2010s. This was a period when the traditional monetary policy tool (the federal funds rate) was constrained by the zero lower bound. We compute credit flow measures using Compustat data, and we employ a factor augmented vector autoregression to analyze unconventional monetary policy’s impact on the allocation of credit during the zero lower bound period. By employing policy counterfactuals, we find that unconventional monetary policy has a positive and simultaneous impact on credit creation and credit destruction and these impacts are larger in long-term credit markets. Applying this technique to analyze the flows of financially constrained and non-financially constrained borrowing firms, we find that unconventional monetary policy operates through the easing of collateral constraints because these effects are larger for small firms or those with high default probabilities. During the zero lower bound period, we also find that unconventional monetary policy brings about increases in credit creation for firms of relatively high investment efficiency. The third chapter pertains to the global trade collapse of the late 2000s. This collapse was due, in part, to strained credit markets and the vulnerability of exporters to adverse credit market conditions. The chapter evaluates the impact of upstream and downstream credit conditions and the differential effects of financial crises on bilateral trade. I find that upstream and downstream sectors’ needs for external financing is negatively associated with trade flows when the exporting or importing country’s cost of credit is high. However, I find that this effect is dampened for downstream sectors. I also find that downstream sectors’ value of collateral is positively associated with trade when the cost of credit is high in the importing country. High downstream trade credit dependence coupled with high costs of credit in the importing country also cause declines in imports. There are amplifying effects of credit costs for sectors that are highly dependent on external financing when the importing or exporting country is in financial crisis. Further, the magnitude is larger when the exporting country is in financial crisis. Finally, I find that these effects on trade flows are large when the exporting country is a developed economy, but they are muted for developing economies.

Some first-generation and low-income students enrolled in an Upward Bound (UB) program in a university in the southeastern United States are not prepared to transition from high school to college; therefore, they may need additional guidance, support, resources, and tools to help them with the process. For this reason, precollege programs such as the UB program were designed to prepare first-generation, low-income students for transitioning from high school to college. The purpose of this bounded qualitative case study was to describe first-generation, low-income students' perspectives of the UB program. The conceptual framework for this case study was Tinto's student integration model. Purposeful sampling was used to select 7 UB graduates who were enrolled in the program for at least 2 years. Opened-ended interview questions were used to gather data for open coding and axial coding data analysis process. The results of this study were used to develop an UB Report which described UB gradates' perspectives of the program. Included in the report are the findings, which revealed that UB graduates identified benefits (motivation, social exposure, and student experiences) and resources (services and guest speakers) as major components of the program that contributed to their transition from high school to college. Reporting the perspectives of UB graduates will help UB directors and secondary and postsecondary administrators better understand how the UB program positively affects first-generation, low-income students' successful transition from high school to college.

We generalize a simple New Keynesian model and show that a flattening of the Phillips curve reduces the size of fiscal multipliers at the zero lower bound (ZLB) on the nominal interest rate. The factors behind the flatting are consistent with micro- and macroeconomic empirical evidence: it is a result of, not a higher level of price rigidity, but an increase in the degree of strategic complementarity in price-setting -- invoked by the assumption of a specific instead of an economy-wide labour market, and decreasing instead of constant-returns-to-scale. In normal times, the efficacy of fiscal policy and resulting multipliers tends to be small because negative wealth effects crowd out consumption, and because monetary policy endogenously reacts to fiscally-driven increases in inflation and output by raising rates, offsetting part of the stimulus. In times of a binding ZLB and a fixed nominal rate, an increase in (expected) inflation instead lowers the real rate, leading to larger fiscal multipliers. Conditional on being in a ZLB-environment, under a flatter Phillips curve, increases in expected inflation are lower, so that fiscal multipliers at the ZLB tend to be lower. Finally, we also discuss the role of solution methods in determining the size of fiscal multipliers. / Series: Department of Economics Working Paper Series

La nécessité d’économiser de l'énergie est l’un des axes importants de ces dernières décennies, d’où le besoin de surveiller la consommation d'énergie des processus résidentiels et industriels. Le travail de recherche présenté dans ce manuscrit s’inscrit plus particulièrement dans le suivi de la consommation électrique afin de permettre l’économie d’énergie. Le but final étant d'avoir une connaissance précise et fiable d'un réseau électrique donné. Cela passe par la décomposition de la consommation électrique globale du réseau électrique étudié afin de fournir une analyse détaillée de l'énergie consommée par usage. L’objectif de cette thèse est la mise en place d’une approche non-intrusive permettant de réaliser les étapes de détection d’évènements et d’extraction de caractéristiques, qui précédent les étapes de classification et d’estimation de la consommation électrique par usage. L’algorithme résultant des travaux effectués durant cette thèse permet de détecter les évènements qui surviennent sur le courant et d’y associer un vecteur d’information contenant des paramètres caractérisant le régime permanent et le régime transitoire. Ce vecteur d’information permet ensuite de reconnaître tous les évènements liés à la même charge électrique. / The need to save energy is an important focus of recent decades, hence the need to monitor the energy consumption of residential and industrial processes. The research works presented in this manuscript are within the monitoring power consumption area in order to enable energy saving. The final goal is to have a clear and reliable knowledge of a given grid. This involves the decomposition of the overall power consumption of the electrical network to provide a detailed analysis of the consumed energy. The objective of this thesis is to develop a non-intrusive approach to achieve the event detection and feature extraction steps, which precede the classification and the power consumption estimation steps. The algorithm resulting from the works performed in this thesis can detect events which occur on the current and associates to them an information vector containing the parameters characterizing the steady and transient states. Then this information vector is used to recognize all the events linked to the same electrical load.

Let Fqt be the finite field with qt elements and let F*qt be its multiplicative group. We study the diagonal equation axq−1 + byq−1 = c, where a,b and c ∈ F*qt. This equation can be written as xq−1+αyq−1 = β, where α, β ∈ F ∗ q t . Let Nt(α, β) denote the number of solutions (x,y) ∈ F*qt × F*qt of xq−1 + αyq−1 = β and I(r; a, b) be the number of monic irreducible polynomials f ∈ Fq[x] of degree r with f(0) = a and f(1) = b. We show that Nt(α, β) can be expressed in terms of I(r; a, b), where r | t and a, b ∈ F*q are related to α and β. A recursive formula for I(r; a, b) will be given and we illustrate this by computing I(r; a, b) for 2 ≤ r ≤ 4. We also show that N3(α, β) can be expressed in terms of the number of monic irreducible cubic polynomials over Fq with prescribed trace and norm. Consequently, N3(α, β) can be expressed in terms of the number of rational points on a certain elliptic curve. We give a proof that given any a, b ∈ F*q and integer r ≥ 3, there always exists a monic irreducible polynomial f ∈ Fq[x] of degree r such that f(0) = a and f(1) = b. We also use the result on N2(α, β) to construct a new family of planar functions.

Cette thèse est principalement consacrée à l'association des méthodes de points intérieurs et des techniques de l'optimisation DC et DCA pour résoudre les problèmes d'optimisation non convexes de grande taille.<br />La thèse comporte trois parties : <br />la première partie est consacrée aux techniques d'optimisations locales et s'articule autour des méthodes de points intérieurs et de la programmation DC. Nous y développons deux algorithmes. Après une présentation non exhaustive de la programmation DC, des méthodes de points intérieurs et des propriétés essentielles de la classe des matrices quasi-définies au chapitre un, nous présentons au chapitre deux un nouvel algorithme basé sur une reformulation des conditions d'optimalité de Karush-Kuhn-Tucker. Le troisième chapitre est consacré à l'intégration des techniques d'optimisation DC dans un schéma de points intérieurs, c'est l'algorithme IPDCA.<br />La seconde partie de la thèse est consacrée aux solutions globales de problèmes de programmation quadratique. Dans le premier chapitre de cette partie nous explorons l'intégration d'IPDCA dans un schéma B&B. Le second chapitre de la partie est consacré à la résolution de problèmes quadratiques à variables 0-1 par un schéma B\&B dans lequel nous faisons intervenir IPDCA. Le troisième chapitre est quant à lui consacré à l'optimisation monotone due au Professeur Tuy. Nous examinons plus particulièrement son intégration dans un B&B dans lequelle DCA est appelé pour améliorer la borne supérieure.<br />Le quatrième et dernier chapitre de cette partie est consacré à une procédure de redémarrage de DCA. <br />La dernière partie de la thèse est consacrée aux applications industrielles. Nous y appliquons les deux algorithmes développés dans la première partie de la thèse à un problème de mécanique de structure de grande dimension et à un problème en Data Mining.

<p>This thesis contributes to theoretical and quantitative aspects of machine scheduling. In fact, it is dedicated to the issue of scheduling n jobs on one single machine. The scope is limited to deterministic problems - i.e. those with all data available and known with certainty in advance - with tardiness involved objectives; hence, the common denominator of all problems addressed are jobs with a predetermined due date assigned to. A job is finished on time as long as it is completed before its due date, otherwise it is said to be tardy. Since the single machine utilized is assumed to be restricted to process at most one job at a time, the aim is to find a proper sequence - a schedule - of how to process the jobs in order to best fulfill a certain objective. The contribution of this thesis aims at giving a state of the art survey and detailed review of research effort considering the objectives "minimizing the number of tardy jobs" and "minimizing the weighted number of tardy jobs". Further, the objectives of "minimizing the total tardiness", "minimizing the total weighted tardiness" and "minimizing the maximum tardiness" are adumbrated but reduced to a rough overview of research effort made.</p>

In the oil industry, there is a special class of pipelines used for the transportation of refined products. The problem of sequencing the inputs to be pumped through this type of pipeline seeks to generate the optimal sequence of batches of products and their destination as well as the amount of product to be pumped such that the total operational cost of the system, or another operational objective, is optimized while satisfying the product demands according to the requirements set by the customers. This dissertation introduces a new modeling approach and proposes a solution methodology for this problem capable of dealing with the topology of all the scenarios reported in the literature so far. The system representation is based on a 1-0 multi commodity network flow formulation that models the dynamics of the system, including aspects such as conservation of product flow constraints at the depots, travel time of products from the refinery to their depot destination and what happens upstream and downstream the line whenever a product is being received at a given depot while another one is being injected into the line at the refinery. It is assumed that the products are already available at the refinery and their demand at each depot is deterministic and known beforehand. The model provides the sequence, the amounts, the destination and the trazability of the shipped batches of different products from their sources to their destinations during the entire horizon planning period while seeking the optimization of pumping and inventory holding costs satisfying the time window constraints. A survey for the available literature is presented. Given the problem structure, a decomposition based solution procedure is explored with the intention of exploiting the network structure using the network simplex method. A branch and bound algorithm that exploits the dynamics of the system assigning priorities for branching to a selected set of variables is proposed and its computational results for the solution, obtained via GAMS/CPLEX, of the formulation for random instances of the problem of different sizes are presented. Future research directions on this field are proposed.

Real-time system refers to the computing, communication, and information system with deadline requirements. To meet these deadline requirements, most systems use a mechanism known as the schedulability test which determines whether each of the admitted tasks can meet its deadline. A new task will not be admitted unless it passes the schedulability test. Schedulability tests can be either direct or indirect. The utilization based schedulability test is the most common schedulability test approach, in which a task can be admitted only if the total system utilization is lower than a pre-derived bound. While the utilization bound based schedulability test is simple and effective, it is often difficult to derive the bound. For its analytical complexity, utilization bound results are usually obtained on a case-by-case basis. In this dissertation, we develop a general framework that allows effective derivation of schedulability bounds for different workload patterns and schedulers. We introduce an analytical model that is capable of describing a wide range of tasks' and schedulers'€™ behaviors. We propose a new definition of utilization, called workload rate. While similar to utilization, workload rate enables flexible representation of different scheduling and workload scenarios and leads to uniform proof of schedulability bounds. We introduce two types of workload constraint functions, s-shaped and r-shaped, for flexible and accurate characterization of the task workloads. We derive parameterized schedulability bounds for arbitrary static priority schedulers, weighted round robin schedulers, and timed token ring schedulers. Existing utilization bounds for these schedulers are obtained from the closed-form formula by direct assignment of proper parameters. Some of these results are applied to a cluster computing environment. The results developed in this dissertation will help future schedulability bound analysis by supplying a unified modeling framework and will ease the implementation practical real-time systems by providing a set of ready to use bound results.