<p>The well-known Dijkstra's algorithm uses weights to determine the shortest path. The focus here is instead on the opposite problem, does there exist weights for a certain set of shortest paths? OSPF (Open Shortest Path First) is one of several possible protocols that determines how routers will send data in a network like the internet. Network operators would however like to have some control of how the traffic is routed, and being able to determine the weights, which would lead to the desired shortest paths to be used, would be a help in this task.The first part of this thesis is a mathematical explanation of the problem with a lot of examples to make it easier to understand. The focus here is on trying to combine several routing patterns into one, so that the result will be fewer, but more fully spanned, routing patterns, and it can e.g. be shown that there can't exist a common set of weights if two routing patterns can't be combined.The second part is a program that can be used to make several tests and changes to a set of routing patterns. It has a polynomial implementation of a function that can combine routing patterns. The examples that I used to combine routing patterns, showed that this will increase the likelihood of finding and significantly speed up the computation of a “valid cycle”.</p> / Egentligen 30p/45hp, men det fanns inte som alternativ.

<p>Within telecommunication and routing of traffic in IP-networks a protocol named“Open Shortest Path First” (OSPF) is widely used. This means that a server dealswith the routing over a network with given weights by calculating shortest paths touse for routing. If we assume that a desired traffic pattern is given the problem isto find out if it is possible to set the weights so that the desired traffic pattern is apart of a shortest path graph. In this thesis we assume that it is a unique shortestpath. To search for weights that solve the problem leads to a complex LP-model. Analternative is to search in the LP-dual under certain restrictions. These solutions tothe LP-dual are called conflicts and a conflict means that there exists no weights sothat the desired traffic pattern is obtained. The goal of this thesis is to study, classifyand search for conflicts. An algorithm has been developed that finds some kind ofconflicts in polynomial time with respect to the size of the graph.</p> / <p>Inom telekommunikation och ruttning av datatrafik i IP-nätverk så används oftaett protokoll som kallas “Open Shortest Path First” (OSPF). Det innebär att enserver sköter ruttningen över ett nätverk genom att utifrån givna bågkostnaderberäkna billigaste vägar som används för ruttningen. Frågeställningen utgårfrån att vi har ett önskat ruttningsschema och vi vill ta reda på om det gåratt sätta bågkostnader så att det önskade ruttningsschemat ingår i en billigasteväg-graf. I det här examensarbetet splittas inte trafik utan varje billigaste vägär unik mellan två noder. Att söka efter bågkostnader som löser problemet geren krävande LP-modell och ett alternativ är att utgå från LP-dualen undervissa restriktioner. Dessa lösningar till LP-dualen benämns konflikter och enkonflikt motsvarar att det inte finns några bågkostnader så att det önskaderuttningsschemat fås. Målet med examensarbetet är att studera, klassificeraoch söka efter konflikter. En algoritm har tagits fram som hittar vissa typer avsådana konflikter i polynomiell tid, sett till storleken på grafen.</p>

Within telecommunication and routing of traffic in IP-networks a protocol named“Open Shortest Path First” (OSPF) is widely used. This means that a server dealswith the routing over a network with given weights by calculating shortest paths touse for routing. If we assume that a desired traffic pattern is given the problem isto find out if it is possible to set the weights so that the desired traffic pattern is apart of a shortest path graph. In this thesis we assume that it is a unique shortestpath. To search for weights that solve the problem leads to a complex LP-model. Analternative is to search in the LP-dual under certain restrictions. These solutions tothe LP-dual are called conflicts and a conflict means that there exists no weights sothat the desired traffic pattern is obtained. The goal of this thesis is to study, classifyand search for conflicts. An algorithm has been developed that finds some kind ofconflicts in polynomial time with respect to the size of the graph. / Inom telekommunikation och ruttning av datatrafik i IP-nätverk så används oftaett protokoll som kallas “Open Shortest Path First” (OSPF). Det innebär att enserver sköter ruttningen över ett nätverk genom att utifrån givna bågkostnaderberäkna billigaste vägar som används för ruttningen. Frågeställningen utgårfrån att vi har ett önskat ruttningsschema och vi vill ta reda på om det gåratt sätta bågkostnader så att det önskade ruttningsschemat ingår i en billigasteväg-graf. I det här examensarbetet splittas inte trafik utan varje billigaste vägär unik mellan två noder. Att söka efter bågkostnader som löser problemet geren krävande LP-modell och ett alternativ är att utgå från LP-dualen undervissa restriktioner. Dessa lösningar till LP-dualen benämns konflikter och enkonflikt motsvarar att det inte finns några bågkostnader så att det önskaderuttningsschemat fås. Målet med examensarbetet är att studera, klassificeraoch söka efter konflikter. En algoritm har tagits fram som hittar vissa typer avsådana konflikter i polynomiell tid, sett till storleken på grafen.

The scope of this thesis is modelling and solving large-scale planning problems in the supply chain within the forest industry. Five research papers are included, the first three of which focus on the modelling, and the last two on the solution methods. All problems included are tactical multi-commodity problems expressed as mixed integer programming (MIP) models. The work has been done in collaboration with two Swedish companies within the forest industry. In Paper I, a problem concerning the supply chain of forest fuel for Sydved Energileveranser AB is modelled and solved. We study the problem of deciding when and where forest residues are to be converted into wood chips, and how the residues and chips are to be transported and stored in order to satisfy energy demand at heating plants. The company has long-term contracts with forest owners and saw mills. Decisions in the model include whether or not additional harvest areas and saw mills are to be contracted and which terminals to use. The planning horizon is one year and monthly time periods are used. Papers II--V are based on planning problems at Södra Cell AB. The planning horizon is normally one year. Papers II--III consider only one time period. In Paper II the supply chain from pulp mills to customers is modelled and the combined problem of deciding terminal locations and which ship routes to use is studied. Shipping vessels chartered on short or long term are used to transport products to terminals in Europe. From each terminal, the products are transported to customers by truck, train, or a combination of both. In addition, trains and trucks can be used for transports directly to customers from mills. In Paper III the entire supply chain, from harvest areas to customers, is considered. Decisions included are transportation of raw materials, production mix, the distribution of pulp products, and the selection of potential orders and their quantities at customers. The ship routes are considered as flow links. In Papers IV--V the problems in Papers II--III are combined into one model and several time periods are used. Lagrangian heuristics based on Lagrangian decomposition are used as solution methods in both papers. In Paper IV, the approach leads to subproblems for each time period, whereas in Paper V, another approach that results in subproblems for different parts of the supply chain is developed. All models are based on real data from the companies. The models are detailed and describe the problems accurately. The solution methods are developed such that the solution time is kept within practical limits. Results from Papers II--III have been used by Södra Cell AB to support the change of the terminal structure as well as in budget planning. / Denna avhandling presenterar matematiska modeller och lösningsmetoder för optimering av olika logistikproblem inom skogsindustrin. Vi studerar försörjningskedjor för skogsbränsle och massaproduker, och beaktar den årliga planeringen i syfte att optimera flödet. Det första problemet behandlar skogsbränsle och är ett samarbete med Sydved Energileveranser AB. Råmaterial i form av grenar och toppar från avverkningsplatser ska flisas och transporteras till värmeverk, eventuellt via terminaler. Det finns möjlighet att flisa både i skogen och på terminaler. Biprodukter från sågverk kan också användas som råmaterial. Vid behov kan utbudet av råmaterial utökas genom att fler avverkningsplatser och sågverk kontrakteras. Värmeverken har en efterfrågan, angiven i kWh per månad, som ska uppfyllas. Exempel på beslut som ska tas är var flisning ska ske, om nya avverkningsplatser ska kontrakteras, var lagring ska ske, samt hur och när skogsbränslet ska transporteras. Nästföljande problem behandlar massaprodukter och är ett samarbete med Södra Cell AB. Olika sorters massaved från skogen och biprodukter från sågverk utgör råmaterial för produktion av massaprodukter. Råmaterialet transporteras till massabruk för tillverkning enligt specificerade recept. De färdiga produkterna transporteras sedan med fartyg till terminaler i Europa. Från terminalerna transporteras produkterna vidare till pappersbruk, vilka är företagets slutkunder. Massaprodukterna transporteras i vissa fall med lastbil eller tåg direkt från massabruken till kunderna. Efterfrågan är angiven inom vissa gränser i olika order. Vissa order är fasta, vilket innebär att dess efterfrågan måste uppfyllas, medan andra order är fria. Exempel på beslut som ska tas är vilka bruk olika produkter ska produceras på, hur många och vilka terminaler som ska användas, samt hur transporterna ska utföras för att ge bästa resultat. Utifrån ovanstående beskrivningar har matematiska modeller formulerats. Ge-nom att lösa dessa kan vi få svar på logistik- och transportfrågorna och ett optimalt flöde kan hittas. För att lösa modellerna har kommersiell programvara använts. Heuristiker och mer avancerade optimeringsmetoder har också utvecklats i syfte att producera bra lösningar snabbare. / Article 4 was a manuscript entitled "Solving a multi-period supply chain problem for a pulp industry using Lagrangian heuristics based on time periods" at the time of the thesis defence.

QC 20100601

In this thesis, optimization approaches for intensity-modulated radiation therapy are developed and evaluated with focus on numerical efficiency and treatment delivery aspects. The first two papers deal with strategies for solving fluence map optimization problems efficiently while avoiding solutions with jagged fluence profiles. The last two papers concern optimization of step-and-shoot parameters with emphasis on generating treatment plans that can be delivered efficiently and accurately. In the first paper, the problem dimension of a fluence map optimization problem is reduced through a spectral decomposition of the Hessian of the objective function. The weights of the eigenvectors corresponding to the p largest eigenvalues are introduced as optimization variables, and the impact on the solution of varying p is studied. Including only a few eigenvector weights results in faster initial decrease of the objective value, but with an inferior solution, compared to optimization of the bixel weights. An approach combining eigenvector weights and bixel weights produces improved solutions, but at the expense of the pre-computational time for the spectral decomposition. So-called iterative regularization is performed on fluence map optimization problems in the second paper. The idea is to find regular solutions by utilizing an optimization method that is able to find near-optimal solutions with non-jagged fluence profiles in few iterations. The suitability of a quasi-Newton sequential quadratic programming method is demonstrated by comparing the treatment quality of deliverable step-and-shoot plans, generated through leaf sequencing with a fixed number of segments, for different number of bixel-weight iterations. A conclusion is that over-optimization of the fluence map optimization problem prior to leaf sequencing should be avoided. An approach for dynamically generating multileaf collimator segments using a column generation approach combined with optimization of segment shapes and weights is presented in the third paper. Numerical results demonstrate that the adjustment of leaf positions improves the plan quality and that satisfactory treatment plans are found with few segments. The method provides a tool for exploring the trade-off between plan quality and treatment complexity by generating a sequence of deliverable plans of increasing quality. The final paper is devoted to understanding the ability of the column generation approach in the third paper to find near-optimal solutions with very few columns compared to the problem dimension. The impact of different restrictions on the generated columns is studied, both in terms of numerical behaviour and convergence properties. A bound on the two-norm of the columns results in the conjugate-gradient method. Numerical results indicate that the appealing properties of the conjugate-gradient method on ill-conditioned problems are inherited in the column generation approach of the third paper. / QC 20100709

This thesis consists of six papers. The main topic of all these papers is modeling a class of linear time-invariant systems. The system class is parameterized in the context of interpolation theory with a degree constraint. In the papers included in the thesis, this parameterization is the key tool for the design of dynamical system models in fields such as spectral estimation and model reduction. A problem in spectral estimation amounts to estimating a spectral density function that captures characteristics of the stochastic process, such as covariance, cepstrum, Markov parameters and the frequency response of the process. A  model reduction problem consists in finding a small order system which replaces the original one so that the behavior of both systems is similar in an appropriately defined sense.  In Paper A a new spectral estimation technique based on the rational covariance extension theory is proposed. The novelty of this approach is in the design of a spectral density that optimally matches covariances and approximates the frequency response of a given process simultaneously.In Paper B  a model reduction problem is considered. In the literature there are several methods to perform model reduction. Our attention is focused on methods which preserve, in the model reduction phase, the stability and the positive real properties of the original system. A reduced-order model is computed employing the analytic interpolation theory with a degree constraint. We observe that in this theory there is a freedom in the placement of the spectral zeros and interpolation points. This freedom can be utilized for the computation of a rational positive real function of low degree which approximates the best a given system. A problem left open in Paper B is how to select spectral zeros and interpolation points in a systematic way in order to obtain the best approximation of a given system. This problem is the main topic in Paper C. Here, the problem is investigated in the analytic interpolation context and spectral zeros and interpolation points are obtained as solution of a optimization problem.In Paper D, the problem of modeling a floating body by a positive real function is investigated. The main focus is  on modeling the radiation forces and moment. The radiation forces are described as the forces that make a floating body oscillate in calm water. These forces are passive and usually they are modeled with system of high degree. Thus, for efficient computer simulation it is necessary to obtain a low order system which approximates the original one. In this paper, the procedure developed in Paper C is employed. Thus, this paper demonstrates the usefulness of the methodology described in Paper C for a real world application.In Paper E, an algorithm to compute the steady-state solution of a discrete-type Riccati equation, the Covariance Extension Equation, is considered. The algorithm is based on a homotopy continuation method with predictor-corrector steps. Although this approach does not seem to offer particular advantage to previous solvers, it provides insights into issues such as positive degree and model reduction, since the rank of the solution of the covariance extension problem coincides with the degree of the shaping filter. In Paper F a new algorithm for the computation of the analytic interpolant of a bounded degree is proposed. It applies to the class of non-strictly positive real interpolants and it is capable of treating the case with boundary spectral zeros. Thus, in Paper~F, we deal with a class of interpolation problems which could not be treated by the optimization-based algorithm proposed by Byrnes, Georgiou and Lindquist. The new procedure computes interpolants by solving a system of nonlinear equations. The solution of the system of nonlinear equations is obtained by a homotopy continuation method. / QC 20100721

This thesis is divided into two parts. The first part deals with theNevanlinna-Pick interpolation problem, a problem which occursnaturally in several applications such as robust control, signalprocessing and circuit theory. We consider the problem of shaping andapproximating solutions to the Nevanlinna-Pick problem in a systematicway. In the second part, we study distance measures between powerspectra for spectral estimation. We postulate a situation where wewant to quantify robustness based on a finite set of covariances, andthis leads naturally to considering the weak*-topology. Severalweak*-continuous metrics are proposed and studied in this context.In the first paper we consider the correspondence between weighted entropyfunctionals and minimizing interpolants in order to find appropriateinterpolants for, e.g., control synthesis. There are two basic issues that weaddress: we first characterize admissible shapes of minimizers bystudying the corresponding inverse problem, and then we developeffective ways of shaping minimizers via suitable choices of weights.These results are used in order to systematize feedback controlsynthesis to obtain frequency dependent robustness bounds with aconstraint on the controller degree.The second paper studies contractive interpolants obtained as minimizersof a weighted entropy functional and analyzes the role of weights andinterpolation conditions as design parameters for shaping theinterpolants. We first show that, if, for a sequence of interpolants,the values of the corresponding entropy gains converge to theoptimum, then the interpolants converge in H_2, but not necessarily inH-infinity. This result is then used to describe the asymptoticbehaviour of the interpolant as an interpolation point approaches theboundary of the domain of analyticity.A quite comprehensive theory of analytic interpolation with degreeconstraint, dealing with rational analytic interpolants with an apriori bound, has been developed in recent years. In the third paper,we consider the limit case when this bound is removed, and only stableinterpolants with a prescribed maximum degree are sought. This leadsto weighted H_2 minimization, where the interpolants areparameterized by the weights. The inverse problem of determining theweight given a desired interpolant profile is considered, and arational approximation procedure based on the theory is proposed. Thisprovides a tool for tuning the solution for attaining designspecifications. The purpose of the fourth paper is to study the topology and develop metricsthat allow for localization of power spectra, based on second-orderstatistics. We show that the appropriate topology is theweak*-topology and give several examples on how to construct suchmetrics. This allows us to quantify uncertainty of spectra in anatural way and to calculate a priori bounds on spectral uncertainty,based on second-order statistics. Finally, we study identification ofspectral densities and relate this to the trade-off between resolutionand variance of spectral estimates.In the fifth paper, we present an axiomatic framework for seekingdistances between power spectra. The axioms requirethat the sought metric respects the effects of additive andmultiplicative noise in reducing our ability to discriminate spectra.They also require continuity of statistical quantities withrespect to perturbations measured in the metric. We then present aparticular metric which abides by these requirements. The metric isbased on the Monge-Kantorovich transportation problem and iscontrasted to an earlier Riemannian metric based on theminimum-variance prediction geometry of the underlying time-series. Itis also being compared with the more traditional Itakura-Saitodistance measure, as well as the aforementioned prediction metric, ontwo representative examples. / QC 20100817

Analytical interpolation theory has several applications in systems and control. In particular, solutions of low degree, or more generally of low complexity, are of special interest since they allow for synthesis of simpler systems. The study of degree constrained analytic interpolation was initialized in the early 80's and during the past decade it has had significant progress. This thesis contributes in three different aspects to complexity constrained analytic interpolation: theory, numerical algorithms, and design paradigms. The contributions are closely related; shortcomings of previous design paradigms motivate development of the theory, which in turn calls for new robust and efficient numerical algorithms. Mainly two theoretical developments are studied in the thesis. Firstly, the spectral Kullback-Leibler approximation formulation is merged with simultaneous cepstral and covariance interpolation. For this formulation, both uniqueness of the solution, as well as smoothness with respect to data, is proven. Secondly, the theory is generalized to matrix-valued interpolation, but then only allowing for covariance-type interpolation conditions. Again, uniqueness and smoothness with respect to data is proven. Three algorithms are presented. Firstly, a refinement of a previous algorithm allowing for multiple as well as matrix-valued interpolation in an optimization framework is presented. Secondly, an algorithm capable of solving the boundary case, that is, with spectral zeros on the unit circle, is given. This also yields an inherent numerical robustness. Thirdly, a new algorithm treating the problem with both cepstral and covariance conditions is presented. Two design paradigms have sprung out of the complexity constrained analytical interpolation theory. Firstly, in robust control it enables low degree Hinf controller design. This is illustrated by a low degree controller design for a benchmark problem in MIMO sensitivity shaping. Also, a user support for the tuning of controllers within the design paradigm for the SISO case is presented. Secondly, in ARMA estimation it provides unique model estimates, which depend smoothly on the data as well as enables frequency weighting. For AR estimation, a covariance extension approach to frequency weighting is discussed, and an example is given as an illustration. For ARMA estimation, simultaneous cepstral and covariance matching is generalized to include prefiltering. An example indicates that this might yield asymptotically efficient estimates. / QC 20100928

Many companies have traveling salesmen that market and sell their products.This results in much traveling by car due to the daily customer visits. Thiscauses costs for the company, in form of travel expenses compensation, and environmentaleffects, in form of carbon dioxide pollution. As many companies arecertified according to environmental management systems, such as ISO 14001,the environmental work becomes more and more important as the environmentalconsciousness increases every day for companies, authorities and public.The main task of this thesis is to compute reasonable limits on the mileage ofthe salesmen; these limits are based on specific conditions for each salesman’sdistrict. The objective is to implement a heuristic algorithm that optimizes thecustomer tours for an arbitrary chosen month, which will represent a “standard”month. The output of the algorithm, the computed distances, will constitute amileage limit for the salesman.The algorithm consists of a constructive heuristic that builds an initial solution,which is modified if infeasible. This solution is then improved by a local searchalgorithm preceding a genetic algorithm, which task is to improve the toursseparately.This method for computing mileage limits for traveling salesmen generates goodsolutions in form of realistic tours. The mileage limits could be improved if theinput data were more accurate and adjusted to each district, but the suggestedmethod does what it is supposed to do.