<p>There exists many applications with so-called costly problems, which means that the objective function you want to maximize or minimize cannot be described using standard functions and expressions. Instead one considers these objective functions as ``black box'' where the parameter values are sent in and a function value is returned. This implies in particular that no derivative information is available.The reason for describing these problems as expensive is that it may take a long time to calculate a single function value. The black box could, for example, solve a large system of differential equations or carrying out a heavy simulation, which can take anywhere from several minutes to several hours!These very special conditions therefore requires customized algorithms. Common optimization algorithms are based on calculating function values every now and then, which usually can be done instantly. But with an expensive problem, it may take several hours to compute a single function value. Our main objective is therefore to create algorithms that exploit all available information to the limit before a new function value is calculated. Or in other words, we want to find the optimal solution using as few function evaluations as possible.A good example of real life applications comes from the automotive industry, where on the development of new engines utilize advanced models that are governed by a dozen key parameters. The goal is to optimize the model by changing the parameters in such a way that the engine becomes as energy efficient as possible, but still meets all sorts of demands on strength and external constraints.</p>

There exists many applications with so-called costly problems, which means that the objective function you want to maximize or minimize cannot be described using standard functions and expressions. Instead one considers these objective functions as ``black box'' where the parameter values are sent in and a function value is returned. This implies in particular that no derivative information is available.The reason for describing these problems as expensive is that it may take a long time to calculate a single function value. The black box could, for example, solve a large system of differential equations or carrying out a heavy simulation, which can take anywhere from several minutes to several hours!These very special conditions therefore requires customized algorithms. Common optimization algorithms are based on calculating function values every now and then, which usually can be done instantly. But with an expensive problem, it may take several hours to compute a single function value. Our main objective is therefore to create algorithms that exploit all available information to the limit before a new function value is calculated. Or in other words, we want to find the optimal solution using as few function evaluations as possible.A good example of real life applications comes from the automotive industry, where on the development of new engines utilize advanced models that are governed by a dozen key parameters. The goal is to optimize the model by changing the parameters in such a way that the engine becomes as energy efficient as possible, but still meets all sorts of demands on strength and external constraints.

This thesis is concerned with problems related to shortest pathrouting (SPR) in Internet protocol (IP) networks. In IP routing, alldata traffic is routed in accordance with an SPR protocol, e.g. OSPF.That is, the routing paths are shortest paths w.r.t. some artificialmetric. This implies that the majority of the Internet traffic isdirected by SPR. Since the Internet is steadily growing, efficientutilization of its resources is of major importance. In theoperational planning phase the objective is to utilize the availableresources as efficiently as possible without changing the actualdesign. That is, only by re-configuration of the routing. This isreferred to as traffic engineering (TE). In this thesis, TE in IPnetworks and related problems are approached by integer linearprogramming. Most TE problems are closely related to multicommodity routingproblems and they are regularly solved by integer programmingtechniques. However, TE in IP networks has not been studied as much,and is in fact a lot harder than ordinary TE problems without IProuting since the complicating shortest path aspect has to be takeninto account. In a TE problem in an IP network the routing isperformed in accordance with an SPR protocol that depends on a metric,the so called set of administrative weights. The major differencebetween ordinary TE problems and TE in IP networks is that all routingpaths must be simultaneously realizable as shortest paths w.r.t. thismetric. This restriction implies that the set of feasible routingpatterns is significantly reduced and that the only means available toadjust and control the routing is indirectly, via the administrativeweights. A constraint generation method for solving TE problems in IP networksis outlined in this thesis. Given an "original" TE problem, the ideais to iteratively generate and augment valid inequalities that handlethe SPR aspect of IP networks. These valid inequalities are derived byanalyzing the inverse SPR problem. The inverse SPR problem is todecide if a set of tentative routing patterns is simultaneouslyrealizable as shortest paths w.r.t. some metric. When this is not thecase, an SPR conflict exists which must be prohibited by a validinequality that is then augmented to the original TE problem. Toderive strong valid inequalities that prohibit SPR conflicts, athorough analysis of the inverse SPR problem is first performed. Inthe end, this allows us to draw conclusions for the design problem,which was the initial primary concern.

No description available.

Spectral moment interpolation find application in a wide array of use cases: robust control, system identification, model reduction to name the most notable ones. This thesis aims to expand the theory of such methods in three different directions. The first main contribution concerns the practical applicability. From this point of view various solving algorithm and their properties are considered. This study lead to identify a globally convergent method with excellent numerical properties. The second main contribution is the introduction of an extended interpolation problem that allows to model ARMA spectra without any explicit information of zero’s positions. To this end it was necessary for practical reasons to consider an approximated interpolation insted. Finally, the third main contribution is the application to some problems such as graphical model identification and ARMA spectral approximation. / QC 20110906

The main body of this thesis consists of six appended papers.The papers are about the theory of the positive real interpolationwith McMillan degree constraint.In Paper A, a parameterization of the positive real residue interpolantswith McMillan degree constraint is given.For a given interpolation data and for each free parameter,a positive real interpolant, of which McMillan degree isequal to the McMillan degree of the maximum entropy interpolant, is obtained bysolving a nonlinear equation, which is homotopic to a nonlinear equation to determinethe maximum entropy interpolant.In Paper B,the state-space realization of the multivariable rational interpolant with bounded McMillan degreeis given by the block discrete-time Schwarz form.A characterization of the positive realness of the block discrete-time Schwarz form isgiven by a linear matrix inequality.In Paper C,a robust controller synthesis for the mismatch of delay in terms ofthe Nevanlinna-Pick interpolation is presented.In Paper D,a Smith predictor synthesis for unstable and minimum-phaseinput delay system and for a first orderunstable distributed delay system is given in terms of the Nevanlinna-Pick interpolation.In Paper E , we study an approximation of spectral density in termsof the generalized Kullback-Leibler distance minimization.For a given spectral density,we seek a spectraldensity by minimizingthe generalized Kullback-Leibler distance subject to a constraint onthe tangential second-orderstatistics.In Paper F, a property of Schur polynomial of real coefficientsand real Toeplitz matrix is given.Suppose that the vector of coefficients of a Schur polynomial annihilatesa Toeplitz matrix, then the Toeplitz matrix is in facta zero matrix. / QC 20100727

<p>The harsh competition in the airline industry continuously forces airline carriers to streamline their production and cut back on costs. Manpower constitutes the largest expense in Scandinavian Airline System, closely followed by fuel costs. Thus effective crew planning is vital to face the competition from international actors and low cost carriers.</p><p>Creating efficient schedules for airline crew is a very complex combinatorial task and the process is heavily dependent on optimization. A large set of constraints comprised of union- and governmental rules as well as company policies and quality factors must be taken into consideration when the schedules are created.</p><p>This master thesis examines how the distribution of rank in the SAS international pilot corps affects the total cost associated with flight deck crew.</p><p>Long haul flights at SAS intercontinental are manned with a captain, a first officer and a relief pilot. Pilots may man lower ranking positions on any given flight in order to make efficient use of the pilot corps and to minimize the need of full time equivalents.</p><p>This work discusses the development and evaluation of a simulation environment developed in order to create and analyze fictitious crew populations with different distributions of rank. Furthermore the solution methods to the scheduling problem implemented at SAS and the optimization theory associated with them are discussed.</p><p>The project has resulted in an evaluation of the developed simulation environment and a discussion about the difficulties of analyzing crew populations with the systems currently in use at SAS.</p>

<p>Syftet med detta examensarbete var att på uppdrag av Skellefteå Kraft AB studera produktionsplanering för regleringsbar vattenkraft och avgöra hur vatten i ett magasin kan värderas. Vidare skulle även en applikation skapas för att kunna beräkna dessa vattenvärden.</p><p> </p><p>Produktionsplanering för vattenkraft visade sig oftast delas upp i tre nivåer, i en lång-, säsong- och korttidsplaneringsdel, där detaljrikedomen i modellbeskrivningarna ökar med minskande tidshorisont. Anledningen till uppdelningen är en följd av att både noggrannhet och långsiktighet önskas, tanken är därmed att låta den högre nivån ge den lägre en långsiktighet den annars saknat. Möjliga kopplingar mellan nivåerna diskuterades, där en priskoppling genom vattenvärden argumenterades för att vara den bästa.</p><p> </p><p>Därefter studerades metoder för vattenvärdeberäkningar och matematiska villkor för optimal produktion, varvid ett eget program i Matlab kunde skrivas. Programmet beräknar vattenvärden vid en enmagasinmodell utifrån tillrinnings- och prisprognoser, där prognoserna tillåts att delas upp i ett valfritt antal scenarion.</p><p> </p><p>Testkörningar av programmet visar att vattenvärdena går ned inför en prognostiserad vårflod, för att på så vis skapa plats åt det inkommande vattnet. Det visas även att vattenvärdenas ISO-kurvor, som markerar var i tid och magasinsnivå ett visst vattenvärde gäller, blir flackare vid större magasin och djupare vid mindre inför den kommande vårfloden. Men även att ISO-kurvorna påverkas av produktionskapaciteten.</p><p> </p><p>Vidare visar testkörningarna att vattenvärdena är starkt kopplade till både tillrinningarnas- och prisprognosernas form och nivå, eftersom att spill vill undvikas samtidigt som produktionen önskas styras till perioder av höga priser.</p><p> </p><p>Innan vattenvärdena från programmet används i praktiken bör ytterligare testkörningar göras för att jämföra ekonomiskt utfall i förhållande till nuvarande arbetssätt. Därför är detta också ett förslag på vidare arbete, tillsammans med en eventuell utvidgning av programmet till en flermagasinsmodell.</p> / <p>The purpose of this master's thesis was to study hydropower production scheduling on behalf of Skellefteå Kraft AB and to determine how water in a reservoir could be priced. Furthermore an application for calculating these water values was to be made.</p><p> </p><p>Hydropower production scheduling was found most often divided into three levels, into a long-, medium- and short-term scheduling part, where the degree of detail increases with decreasing time horizon. The reason for this breakdown into levels are that a high detail in the model descriptions is desired, while still maintaining a good long-term planning. The idea is thus to let the higher level give the lower one an insight for future events it would otherwise lack. Possible couplings between the levels was discussed, where a coupling through price and water values was argued to be the best.</p><p> </p><p>Subsequently methods for water value calculations and mathematical conditions for optimal production was studied, in which an own program in Matlab could be written. The program calculates water values at a single reservoir model by the help of forecasts of future inflow and price, where the forecasts are allowed to be divided into any number of scenarios.</p><p> </p><p>Test runs of the program shows that water levels are reduced before the spring flood, thus to make room for the incoming water. It is also shown that the ISO-curves for the water values, which indicates where in time and reservoir level a certain water value is located, becomes flatter at larger reservoirs and steeper at smaller reservoirs before the incoming spring flood. But also that the ISO-curves are affected by the production capacity.</p><p> </p><p>The test runs further shows that the water values are strongly linked to both the shape and level of the inflow and price forecasts, since it is desired to avoid spill while directing the production to periods of high prices.</p><p> </p><p>Additional runs to compare the economic outcomes relative to current practice should be made before using the water values of the program in practice. Therefore this is also a proposal for further work, along with a possible extension of the program into a multi-reservoir model.</p>

The harsh competition in the airline industry continuously forces airline carriers to streamline their production and cut back on costs. Manpower constitutes the largest expense in Scandinavian Airline System, closely followed by fuel costs. Thus effective crew planning is vital to face the competition from international actors and low cost carriers. Creating efficient schedules for airline crew is a very complex combinatorial task and the process is heavily dependent on optimization. A large set of constraints comprised of union- and governmental rules as well as company policies and quality factors must be taken into consideration when the schedules are created. This master thesis examines how the distribution of rank in the SAS international pilot corps affects the total cost associated with flight deck crew. Long haul flights at SAS intercontinental are manned with a captain, a first officer and a relief pilot. Pilots may man lower ranking positions on any given flight in order to make efficient use of the pilot corps and to minimize the need of full time equivalents. This work discusses the development and evaluation of a simulation environment developed in order to create and analyze fictitious crew populations with different distributions of rank. Furthermore the solution methods to the scheduling problem implemented at SAS and the optimization theory associated with them are discussed. The project has resulted in an evaluation of the developed simulation environment and a discussion about the difficulties of analyzing crew populations with the systems currently in use at SAS.

Syftet med detta examensarbete var att på uppdrag av Skellefteå Kraft AB studera produktionsplanering för regleringsbar vattenkraft och avgöra hur vatten i ett magasin kan värderas. Vidare skulle även en applikation skapas för att kunna beräkna dessa vattenvärden.   Produktionsplanering för vattenkraft visade sig oftast delas upp i tre nivåer, i en lång-, säsong- och korttidsplaneringsdel, där detaljrikedomen i modellbeskrivningarna ökar med minskande tidshorisont. Anledningen till uppdelningen är en följd av att både noggrannhet och långsiktighet önskas, tanken är därmed att låta den högre nivån ge den lägre en långsiktighet den annars saknat. Möjliga kopplingar mellan nivåerna diskuterades, där en priskoppling genom vattenvärden argumenterades för att vara den bästa.   Därefter studerades metoder för vattenvärdeberäkningar och matematiska villkor för optimal produktion, varvid ett eget program i Matlab kunde skrivas. Programmet beräknar vattenvärden vid en enmagasinmodell utifrån tillrinnings- och prisprognoser, där prognoserna tillåts att delas upp i ett valfritt antal scenarion.   Testkörningar av programmet visar att vattenvärdena går ned inför en prognostiserad vårflod, för att på så vis skapa plats åt det inkommande vattnet. Det visas även att vattenvärdenas ISO-kurvor, som markerar var i tid och magasinsnivå ett visst vattenvärde gäller, blir flackare vid större magasin och djupare vid mindre inför den kommande vårfloden. Men även att ISO-kurvorna påverkas av produktionskapaciteten.   Vidare visar testkörningarna att vattenvärdena är starkt kopplade till både tillrinningarnas- och prisprognosernas form och nivå, eftersom att spill vill undvikas samtidigt som produktionen önskas styras till perioder av höga priser.   Innan vattenvärdena från programmet används i praktiken bör ytterligare testkörningar göras för att jämföra ekonomiskt utfall i förhållande till nuvarande arbetssätt. Därför är detta också ett förslag på vidare arbete, tillsammans med en eventuell utvidgning av programmet till en flermagasinsmodell. / The purpose of this master's thesis was to study hydropower production scheduling on behalf of Skellefteå Kraft AB and to determine how water in a reservoir could be priced. Furthermore an application for calculating these water values was to be made.   Hydropower production scheduling was found most often divided into three levels, into a long-, medium- and short-term scheduling part, where the degree of detail increases with decreasing time horizon. The reason for this breakdown into levels are that a high detail in the model descriptions is desired, while still maintaining a good long-term planning. The idea is thus to let the higher level give the lower one an insight for future events it would otherwise lack. Possible couplings between the levels was discussed, where a coupling through price and water values was argued to be the best.   Subsequently methods for water value calculations and mathematical conditions for optimal production was studied, in which an own program in Matlab could be written. The program calculates water values at a single reservoir model by the help of forecasts of future inflow and price, where the forecasts are allowed to be divided into any number of scenarios.   Test runs of the program shows that water levels are reduced before the spring flood, thus to make room for the incoming water. It is also shown that the ISO-curves for the water values, which indicates where in time and reservoir level a certain water value is located, becomes flatter at larger reservoirs and steeper at smaller reservoirs before the incoming spring flood. But also that the ISO-curves are affected by the production capacity.   The test runs further shows that the water values are strongly linked to both the shape and level of the inflow and price forecasts, since it is desired to avoid spill while directing the production to periods of high prices.   Additional runs to compare the economic outcomes relative to current practice should be made before using the water values of the program in practice. Therefore this is also a proposal for further work, along with a possible extension of the program into a multi-reservoir model.