Optimeringslära, Publikationer

We suggest here a least-change correction to available finite element (FE) solution. This postprocessing procedure is aimed at recovering the monotonicity and some other important properties that may not be exhibited by the FE solution. Although our approach is presented for FEs, it admits natural extension to other numerical schemes, such as finite differences and finite volumes. For the postprocessing, a priori information about the monotonicity is assumed to be available, either for the whole domain or for a subdomain where the lost monotonicity is to be recovered. The obvious requirement is that such information is to be obtained without involving the exact solution, e.g. from expected symmetries of this solution. less thanbrgreater than less thanbrgreater thanThe postprocessing is based on solving a monotonic regression problem with some extra constraints. One of them is a linear equality-type constraint that models the conservativity requirement. The other ones are box-type constraints, and they originate from the discrete maximum principle. The resulting postprocessing problem is a large scale quadratic optimization problem. It is proved that the postprocessed FE solution preserves the accuracy of the discrete FE approximation. less thanbrgreater than less thanbrgreater thanWe introduce an algorithm for solving the postprocessing problem. It can be viewed as a dual ascent method based on the Lagrangian relaxation of the equality constraint. We justify theoretically its correctness. Its efficiency is demonstrated by the presented results of numerical experiments.

Monotonic regression (MR) is an efficient tool for estimating functions that are monotonic with respect to input variables. A fast and highly accurate approximate algorithm called the GPAV was recently developed for efficient solving large-scale multivariate MR problems. When such problems are too large, the GPAV becomes too demanding in terms of computational time and memory. An approach, that extends the application area of the GPAV to encompass much larger MR problems, is presented. It is based on segmentation of a large-scale MR problem into a set of moderate-scale MR problems, each solved by the GPAV. The major contribution is the development of a computationally efficient strategy that produces a monotonic response using the local solutions. A theoretically motivated trend-following technique is introduced to ensure higher accuracy of the solution. The presented results of extensive simulations on very large data sets demonstrate the high efficiency of the new algorithm.

Hospital wards need to be staffed by nurses round the clock, resulting in irregular working hours for many nurses. Over the years, the nurses influence on the scheduling has been increased in order to improve their working conditions. In Sweden it is common to apply a kind of self-scheduling where each nurse individually proposes a schedule, and then the final schedule is determined through informal negotiations between the nurses. This kind of self-scheduling is very time-consuming and does often lead to conflicts. We present a pilot study which aims at determining if it is possible to create an optimisation tool that automatically delivers a usable schedule based on the schedules proposed by the nurses. The study is performed at a typical Swedish nursing ward, for which we have developed a mathematical model and delivered schedules. The results of this study are very promising and suggest continued work along these lines.

Origin-destination (OD) matrices are essential for various analyses in the field of traffic planning, and they are often estimated from link flow observations. We compare methods for allocating link flow detectors to a traffic network with respect to the quality of the estimated OD-matrix. First, an overview of allocation methods proposed in the literature is presented. Second, we construct a controlled experimental environment where any allocation method can be evaluated, and compared to others, in terms of the quality of the estimated OD-matrix. Third, this environment is used to evaluate and compare three fundamental allocation methods. Studies are made on the Sioux Falls network and on a network modeling the city of Linkoping. Our conclusion is, that the most commonly studied approach for detector allocation, maximizing the coverage of OD-pairs, seems to be unfavorable for the quality of the estimated OD-matrix.

We address the problem of designing IP networks where the traffic is routed using the OSPF protocol. Routers in OSPF networks use link weights set by an administrator for determining how to route the traffic. The routers use all shortest paths when traffic is routed to a destination, and the traffic is evenly balanced by the routers when several paths are equally short. We present a new model for the OSPF network design problem. The model is based on routing patterns and does not explicitly include OSPF weights. The OSPF protocol is modeled by ensuring that all pairs of routing patterns are subpath consistent, which is a necessary condition for the existence of weights. A Lagrangean heuristic is proposed as solution method, and feasible solutions to the problem are generated using a tabu search method. Computational results are reported for random instances and for real-life instances.

Billerud, a Swedish company with four integrated pulp and paper mills, serves specific packaging-market segments. In 2000, the process-engineering department at Billeruds mill in Skarblacka sought to improve the mills bleaching process. It contacted Linkoping University, which collaborated with Eurocon Automation AB to develop a decision-support system, OptCab. Eurocon Automation AB now offers OptCab as a general tool in the market. Its core is an online optimization system that dynamically updates a process description and optimizes the bleaching control process. The system, which has been fully operational since 2004, has provided numerous benefits to Billerud. Chemical use has decreased by approximately 10 percent, saving approximately two million euros since its installation; the environmental impact has also been reduced; and the brightness quality of paper that the mill produces is more uniform and stable. Moreover, OptCab requires less operator time, freeing the operators for development and analysis work.

Many telecommunication networks use the open shortest path first (OSPF) protocol for the routing of traffic. In such networks, each router sends the traffic on the shortest paths to the destination, with respect to the link weights assigned. An interesting question is whether or not a set of desired routing patterns can be obtained in an OSPF network by assigning appropriate weights. If not, we wish to find the source of the infeasibility. We study these issues by formulating a mathematical model and investigating its feasibility. A certain structure, called valid cycle, is found to be present in most infeasible instances. This yields new necessary conditions, stronger than those previously known, for the existence of weights yielding a set of given desired shortest path graphs. A valid cycle indicates which parts of the routing patterns are in conflict and can be used for changing the routing patterns to make the problem feasible. A polynomial algorithm for finding valid cycles is presented, the method is illustrated by a numerical example, and computational tests are reported.

We study the multicommodity network flow problem with fixed costs on paths, with specific application to the empty freight car distribution process of a rail operator. The classification costs for sending a group of cars do not depend on the number of cars in the group, as long as the group is kept together as one unit. Arcs correspond to trains, so we have capacity restrictions on arcs but fixed costs on the paths corresponding to routes for groups of cars. As solution method, we propose a Lagrangian based heuristic using dual subgradient search and primal heuristics based on path information of the Lagrangian subproblem solutions. The method illustrates several ways of exploiting the specific structures of the problem. Computational tests indicate that the method is able to generate fairly good primal feasible solutions and lower bounds on the optimal objective function value. © 2007 Elsevier B.V. All rights reserved.

Distribution is a major factor in the supply chain for Sodra Cell, a leading manufacturer of pulp intended for paper production. Each year, the company transports large quantities of pulp using ships, trains, and trucks; here we focus on scheduling the ships and optimizing deliveries to minimize distribution costs.

The forwarding of logs at harvest areas once the harvesting is done is planned manually by experienced operators. To improve their efficiency and simplify the planning we have developed and tested a decision support system at a major Swedish forest company. The system is based on a combination of a geographic information system (GIS), global positioning system (GPS), and optimization routines to solve the underlying vehicle routing problem. The routes for the forwarders are found by using a repeated matching algorithm. The solution time is short, and it is possible to find routes dynamically in a real-time environment. The geographic information required is found by using a GPS together with data obtained from the bucking software in the harvesters. To show the routes and location of the forwarder, we make use of a GIS that is connected to the GPS. We report on a study with savings in the distance travelled of 8% and numerical tests on the solution methodology. We also compare the proposed solution method with some well-known routing methods. © 2007 NRC.

We exhibit useful properties of ballstep subgradient methods for convex optimization using level controls for estimating the optimal value. Augmented with simple averaging schemes, they asymptotically find objective and constraint subgradients involved in optimality conditions. When applied to Lagrangian relaxation of convex programs, they find both primal and dual solutions, and have practicable stopping criteria. Up until now, similar results have only been known for proximal bundle methods, and for subgradient methods with divergent series stepsizes, whose convergence can be slow. Encouraging numerical results are presented for large-scale nonlinear multicommodity network flow problems. ©2007 INFORMS.

In this paper we consider integrated planning of transportation of raw material, production and distribution of products of the supply chain at Södra Cell AB, a major European pulp mill company. The strategic planning period is one year. Decisions included in the planning are transportation of raw materials from harvest areas to pulp mills, production mix and contents at pulp mills, distribution of pulp products from mills to customer via terminals or directly and selection of potential orders and their levels at customers. Distribution is carried out by three different transportation modes; vessels, trains and trucks. We propose a mathematical model for the entire supply chain which includes a large number of continuous variables and a set of binary variables to reflect decisions about product mix and order selection at customers. Five different alternatives regarding production mix in a case study carried out at Södra Cell are analyzed and evaluated. Each alternative describes which products will be produced at which pulp mills.

The health care system in Sweden and many other countries is facing increasing costs. The major reason is the changing age distribution of the population with more elderly people in need of support. At the same time, health care systems are often very labor and staff intensive. In this paper, we focus on a staff planning problem arising in Sweden where people receive home care from the local authorities. The objective is to develop visiting schedules for care providers that incorporate some restrictions and soft objectives. Each visit has a particular task to be performed, for example: cleaning, washing, personal hygiene and/or nursing activities. Each staff member has skills and each client should, if possible, be visited by the same contact person. The operational situation is continuously changing and planning is done each day. We describe the development of a decision support system LAPS CARE to aid the planners. The system consists of a number of components including information data bases, maps, optimization routines, and report possibilities. We formulate the problem using a set partitioning model and, for a solution method, we make use of a repeated matching algorithm. The system is currently in operation at a number of home care organizations. We report on the practical impact of the system in the health care organization which was involved in the development. The savings are considerably in terms of saved planning time and in the quality of the routes, as well as the measured quality for the clients. Numerical experiments of the system are presented.

The vast size of real world stochastic programming instances requires sampling to make them practically solvable. In this paper we extend the understanding of how sampling affects the solution quality of multistage stochastic programming problems. We present a new heuristic for determining good feasible solutions for a multistage decision problem. For power and log-utility functions we address the question of how tree structures, number of stages, number of outcomes and number of assets affect the solution quality. We also present a new method for evaluating the quality of first stage decisions.

The well-known and established global optimality conditions based on the Lagrangian formulation of an optimization problem are consistent if and only if the duality gap is zero. We develop a set of global optimality conditions that are structurally similar but are consistent for any size of the duality gap. This system characterizes a primal-dual optimal solution by means of primal and dual feasibility, primal Lagrangian ε-optimality, and, in the presence of inequality constraints, a relaxed complementarity condition analogously called δ-complementarity. The total size ε + δ of those two perturbations equals the size of the duality gap at an optimal solution. Further, the characterization is equivalent to a near-saddle point condition which generalizes the classic saddle point characterization of a primal-dual optimal solution in convex programming. The system developed can be used to explain, to a large degree, when and why Lagrangian heuristics for discrete optimization are successful in reaching near-optimal solutions. Further, experiments on a set-covering problem illustrate how the new optimality conditions can be utilized as a foundation for the construction of new Lagrangian heuristics. Finally, we outline possible uses of the optimality conditions in column generation algorithms and in the construction of core problems. © 2006 INFORMS.

Given an undirected graph with edge costs and both revenues and weights on the vertices, the traveling salesman subtour problem is to find a subtour that includes a depot vertex, satisfies a knapsack constraint on the vertex weights, and that minimizes edge costs minus vertex revenues along the subtour. We propose a decomposition scheme for this problem. It is inspired by the classic side-constrained 1-tree formulation of the traveling salesman problem, and uses stabilized column generation for the solution of the linear programming relaxation. Further, this decomposition procedure is combined with the addition of variable upper bound (VUB) constraints, which improves the linear programming bound. Furthermore, we present a heuristic procedure for finding feasible subtours from solutions to the column generation problems. An extensive experimental analysis of the behavior of the computational scheme is presented. © 2006 Elsevier B.V. All rights reserved.

Mean value cross decomposition is a symmetric primal-dual decomposition method suitable for optimization problems with both primal and dual structures. It uses only easily solvable subproblems and no difficult master problems. Originally developed for linear problems, it is in this paper extended to nonlinear convex optimization problems. Convergence is proved for a somewhat generalized version, allowing more general weights. Computational results are presented for a network routing problem with congestion costs, a large-scale nonlinear problem with structures that enable decomposition both with respect to variables and constraints. The main goals of the tests are to illustrate the procedure and to indicate that this decomposition approach is more efficient than direct solution with a well established general code.

In this paper, we consider a combined terminal location and ship routing problem at Södra Cell AB. The purpose is to supply the customers' annual demand for pulp products while minimizing the distribution costs. Customers are supplied with various pulp products from pulp mills in Scandinavia by ships, trains, or lorries. The ship routes go from the pulp mills to terminals in Europe. From each terminal, the products are transported to customers by lorry, train, or barge. Some customers can be supplied directly from the pulp mills by trains or lorries. We have developed a mathematical model to select which terminals to use and, at the same time, determine the shipping routes. The mixed integer programming model was solved directly using a commercial solver. When the number of routes generated is large, the time required to obtain an optimal solution is too long. Hence, we have developed heuristics in order to obtain an acceptable solution in reasonable time. In addition to the basic case, five different scenarios were tested. Our heuristics provide solutions that are within 0.12% of the optimal ones.

Discrete choice models characterize the alternatives in the choice set by utilities/attributes. The decision making is described by a probability distribution over the choice set. In this paper we introduce a welfare measure based on expected payoff and expected freedom of choice for the simple one parameter logit model. In this case the welfare measure turns out to be the so called composite utility. This means that the composite utility can be interpreted as the combined benefit of expected payoff and expected freedom of choice. The proposed welfare measure can be extended to the linear-in-parameters logit model and nested logit models and others. The proposed welfare measure is formulated in terms of the choice probability distribution. It depends on the form of the probabilities, but not on any particular derivation of the distribution.

In this paper, we study a cost-allocation problem that arises in a distribution-planning situation at the Logistics Department at Norsk Hydro Olje AB, Stockholm, Sweden. We consider the routes from one depot during one day. The total distribution cost for these routes is to be divided among the customers that are visited. This cost-allocation problem is formulated as a vehicle-routing game (VRG), allowing the use of vehicles with different capacities. Cost-allocation methods based on different concepts from cooperative game theory, such as the core and the nucleolus, are discussed. A procedure that can be used to investigate whether the core is empty or not is presented, as well as a procedure to compute the nucleolus. Computational results for the Norsk Hydro case are presented and discussed.

In this paper, we consider empty freight car distribution in a scheduled railway system. We analyze the cost structure for the repositioning of empty cars, and conclude that the distribution cost shows an economy-of-scale behavior. In addition to the cost proportional to the number of cars sent from origin to destination, there is a cost related to car-handling operations at yards, which depends on the number of car groups that are handled. Thus, if we can find a transportation pattern in which fewer but larger groups of cars are built, the total distribution cost can be decreased. The objective of the paper is to propose an optimization model that explicitly takes this economy-of-scale effect into account. We use a time-dependent network to describe the possible car movements in time and space, and show how this network can be transformed into a network with fixed costs on links representing movements of cars with identical origin and destination terminals. The resulting optimization model is a capacitated network design model, where each capacity constraint limits the flow on several arcs. We describe a tabu heuristic for solving the model, and present computational results. © 2004 INFORMS.

We present a column generation procedure for the side constrained traffic equilibrium problem. A dual stabilization scheme is introduced to improve the computational performance. Computational experiments for the case of linear side constraints are presented. The test problems are well known traffic equilibrium instances where side constraints of link flow capacity type and general linear side constraints are added. The computational results are promising especially for instances with a relatively small number of side constraints.

Scheduling of staff is an important area, both from an academic and industrial point of view. There has been a lot of attention to develop new and efficient methods and models. In this paper, we consider the problem that given a work-force demand, a set of working rules and regulations find schedules for staff members with individual skills and preferences. The planning horizon is typically one week to several months. The problem both constructs tasks and simultaneously allocates them to staff members. The purpose of this paper is not to develop new theoretical results. Instead it deals with novel applications of known approaches to real-world practice. We describe a general scheduling software called SCHEDULER that includes a number of important features. The model is based on a elastic set-partitioning model and as solution method we use a branch-and-price algorithm. As branching strategy we make use of constraint branching and the column generator is a nested constrained shortest path formulation. An important feature is that only legal schedules are generated and used within the model. The system also allows for task changes within shifts, a general description of legal restrictions, preferences and allowable times. The system is in use at a number of companies and we report on the usage at some companies. We also give some numerical results to illustrate the behavior of some important features.

We consider network design and routing for Internet Protocol (IP) traffic. The design problem concerns capacity dimensioning of communication links, where the design cost consists of fixed charges and linear capacity expansion costs. The optimization problem also concerns determining the amount of traffic demand to be carried by the network and the metric used by a shortest path routing protocol. We present a novel linear mixed-integer mathematical formulation and two heuristic solution procedures. The first heuristic uses mixed-integer programming to generate a sequence of routing solutions. The second solution approach is a simulated annealing meta heuristic. Computational experiments for synthesized and real-life networks show that high-quality solutions can be obtained by both approaches.

We study the supply chain problem of a large international pulp producer with five pulp mills located in Scandinavia. The company currently uses manual planning for most of its supply chain, which includes harvesting and transportation of pulp, production scheduling and distribution of products to customers. We have developed two new mixed integer models that determine daily supply chain decisions over a planning horizon of three months. One model is based on column generation, where the generation phase is to find new production plans using a shortest path network. The second, slightly less flexible, has the daily production decisions explicitly included in the model. In order to solve the models within practical time limits we use a flexible approach that aggregates together the less immediate decisions. We also introduce a novel constraint branching heuristic. The models and solution approaches are intended to become an integrated component in the company’s new management system. In tests and comparisons with today’s manual planning, we have found new strategic policies that significantly reduce the company’s supply chain costs.

We build an investment model based on Stochastic Programming. In the model we buy at the ask price and sell at the bid price. We apply the model to a case where we can invest in a Swedish stock index, call options on the index and the risk-free asset. By reoptimizing the portfolio on a daily basis over a ten-year period, it is shown that options can be used to create a portfolio that outperforms the index. With ex post analysis, it is furthermore shown that we can create a portfolio that dominates the index in terms of mean and variance, i.e. at given level of risk we could have achieved a higher return using options. © 2002 Elsevier Science B.V. All rights reserved.

The multicommodity network-flow model concerns routing of a number of commodities through a capacitated network at minimal cost. In the basic model, it is assumed that for each commodity, the flow can be routed on any path connecting its origin and its destination. In telecommunication applications, where a commodity represents a communication pair, there are often additional time-delay or reliability requirements on paths that are used for routing. These requirements may vary by communication pair, represented by different priority classes. In this paper, we extend the basic multicommodity network-flow model to include such side constraints on paths. The extended problem is script N signscript P sign-hard with the constrained shortest-path problem as a special case. To solve the extended model, we use a column-generation approach, in which the solution is built up successively by path generation. The side constraints are efficiently handled in the path-generation subproblem. We further discuss various enhancements of this approach. Computational results show that the column-generation approach provides an efficient way for solving the extended model, even for fairly large networks.

We present a solution algorithm for an inverse nonlinear multicommodity network flow problem. This problem is to find link cost adjustments that make a given target link flow solution optimal in a nonlinear multicommodity network flow problem, and that are optimal with respect to a specified objective. The solution procedure uses column generation. We present computational results for instances where the nonlinear multicommodity network flow problems are small and medium scale traffic equilibrium problems, and where system optimal link flows are targeted. The computational results show that the solution procedure is a viable approach for solving medium-scale instances of the inverse traffic equilibrium problem.

Optimization models and methods have been used extensively in the forest industry. In this paper we describe the general wood-flow in forestry and a variety of planning problems. These cover planning periods from a fraction of a second to more than one hundred years. The problems are modelled using linear, integer and nonlinear models. Solution methods used depend on the required solution time and include for example dynamic programming, LP methods, branch & bound methods, heuristics and column generation. The importance of modelling and qualitative information is also discussed.

Today most sawmills use optimization techniques to maximize yields from logs. If open market conditions are assumed when maximizing volume or value yields, overproduction of some products and underproduction of others may result. In this study, a system is described that links production with log sawing optimization while also addressing demands for timber products of differing qualities. The system is based on an optimization framework that is implemented in a log sawing simulator, AUTOSAW. Unlike other optimization systems that use static product "values" such as board volume or timber price, dynamic values are used that are updated regularly according to previous timber production. The efficiency of the system was tested with three orderbooks, via comparisons with volume- and value-optimized solutions obtained from sawing pruned Pinus radiata D. Don logs. In each case, product optimization required fewer logs to satisfy all demands than did either volume or value optimization. Furthermore, underproduction was eliminated and overproduction reduced.

A new algorithm for solving smooth large-scale minimization problems with bound constraints is introduced. The way of dealing with active constraints is similar to the one used in some recently introduced quadratic solvers. A limited-memory multipoint symmetric secant method for approximating the Hessian is presented. Positive-definiteness of the Hessian approximation is not enforced. A combination of trust-region and conjugate-gradient approaches is used to explore a useful negative curvature information. Global convergence is proved for a general model algorithm. Results of numerical experiments are presented.

We show that a Riccati-based Multistage Stochastic Programming solver for problems with separable convex linear/nonlinear objective developed in previous papers can be extended to solve more general Stochastic Programming problems. With a Lagrangean relaxation approach, also local and global equality constraints can be handled by the Riccati-based primal interior point solver. The efficiency of the approach is demonstrated on a 10 staged stochastic programming problem containing both local and global equality constraints. The problem has 1.9 million scenarios, 67 million variables and 119 million constraints, and was solved in 97 min on a 32 node PC cluster.

We propose a new method for certain multistage stochastic programswith linear or nonlinear objective function, combining a primal interiorpoint approach with a linear-quadratic control problem over thescenario tree.The latter problem, which is the direction finding problem for thebarrier subproblem is solved through Dynamic Programming usingRiccati equations.In this way we combine the low iteration count of interior pointmethods with an efficient solver for the subproblems.The computational results are promising.We have solved a financial problem with 1,000,000 scenarios,15,777,740 variables and 16,888,850 constraints in 20 hours on amoderate computer.

We apply a recent extension of the Bregman proximal method for convex programming to LP relaxations of 0-1 problems. We allow inexact subproblem solutions obtained via dual ascent, increasing their accuracy successively to retain global convergence. Our framework is applied to relaxations of large-scale set covering problems that arise in airline crew scheduling. Approximate relaxed solutions are used to construct primal feasible solutions via a randomized heuristic. Encouraging preliminary experience is reported.

Detailed three dimensional models are nowadays frequently used in cross-cutting (bucking) tree stems into logs and in breakdown processes of logs into boards and flitches. Such models require increasingly sophisticated optimization models to assist planners (or automated decision support systems) in decision making. In this paper we develop two techniques that are linked to each other. The first is concerned with establishing high quality analytic approximations of full trees that are needed in full stem bucking applications. One important aspect is that inaccuracies due to measurement error can be reduced. The second is a transformation technique that makes it possible to apply curve sawing on logs in a standard straight sawing system. Numerical results based on real data are presented that support the usefulness of the techniques.

Many hospital wards need to be staffed by nurses around the clock every day of the year, and because of that, many nurses have to work irregular hours and according to schedules that have a great impact on their personal lives. Today most schedules are made by hand or with limited computer support, and this is both difficult and very time consuming. A common consequence of making the schedules by hand is that the outcome is neither favourable for the nurses nor satisfactory for the running of the ward.

The nurse scheduling problem is well suited for addressing with operations research methods, but a challenge for automated scheduling of nurses is the ability to adapt the scheduling to the specific conditions on each ward. The intention of this paper is to provide a piece of practical experience that can help bridge the gap between advanced method development and the use of automatic nurse scheduling in practice. Our approach is to take on the real life scheduling problem with all its details, and to use a straightforward meta-heuristic in order to deliver automatically generated schedules. The contribution of the paper is based on the result of two case studies, which will provide insights into examples of real world nurse scheduling, including evaluation and feedback from the wards.

In this research piecewise monotonic models for problemscomprising seasonal cycles and monotonic trends are considered.In contrast to the conventional piecewise monotonicregression algorithms, our approach can efficientlyexploit a priori information about temporal patterns. Itis based on reducing these problems to monotonic regressionproblems defined on partially ordered data sets. Thelatter are large-scale convex quadratic programming problems.They are efficiently solved by the GPAV algorithm.

In this paper, the monotonic regression problem (MR) is considered. We have recentlygeneralized for MR the well-known Pool-Adjacent-Voilators algorithm(PAV) from the case of completely to partially ordered data sets. Thenew algorithm, called GPAV, combines both high accuracy and lowcomputational complexity which grows quadratically with the problemsize. The actual growth observed in practice is typically far lowerthan quadratic. The fitted values of the exact MR solution composeblocks of equal values. Its GPAV approximation has also a blockstructure. We present here a technique for refining blocks produced bythe GPAV algorithm to make the new blocks more close to those in theexact solution. This substantially improves the accuracy of the GPAVsolution and does not deteriorate its computational complexity. Thecomputational time for the new technique is approximately triple thetime of running the GPAV algorithm. Its efficiency is demonstrated byresults of our numerical experiments.

When unmanned aerial vehicles (UAVs) are used to survey distant targets, it is important to transmit sensor information back to a base station. As this communication often requires high uninterrupted bandwidth, the surveying UAV often needs afree line-of-sight to the base station, which can be problematic in urban or mountainous areas. Communication ranges may also belimited, especially for smaller UAVs. Though both problems can be solved through the use of relay chains consisting of one or more intermediate relay UAVs, this leads to a new problem: Where should relays be placed for optimum performance? We present two new algorithms capable of generating such relay chains, one being a dual ascent algorithm and the other a modification of the Bellman-Ford algorithm. As the priorities between the numberof hops in the relay chain and the cost of the chain may vary, wecalculate chains of different lengths and costs and let the ground operator choose between them. Several different formulations for edge costs are presented. In our test cases, both algorithms are substantially faster than an optimized version of the original Bellman-Ford algorithm, which is used for comparison.

In this talk we consider the isotonic regression (IR) problem which can beformulated as follows. Given a vector $\bar{x} \in R^n$, find $x_* \in R^n$ which solves the problem:\begin{equation}\label{ir2}\begin{array}{cl}\mbox{min} & \|x-\bar{x}\|^2 \\\mbox{s.t.} & Mx \ge 0.\end{array}\end{equation}The set of constraints $Mx \ge 0$ represents here the monotonicityrelations of the form $x_i \le x_j$ for a given set of pairs of thecomponents of $x$. The corresponding row of the matrix $M$ is composed mainly of zeros,but its $i$th and $j$th elements, which are equal to $-1$ and $+1$,respectively. The most challenging applications of (\ref{ir2}) arecharacterized by very large values of $n$. We introduce new IRalgorithms. Our numerical experiments demonstrate the high efficiencyof our algorithms, especially for very large-scale problems, and theirrobustness. They are able to solve some problems which all existing IRalgorithms fail to solve. We outline also our new algorithms formonotonicity-preserving interpolation of scattered multivariate data.In this talk we focus on application of our IR algorithms inpostprocessing of FE solutions.Non-monotonicity ofthe numerical solution is a typical drawback of the conventionalmethods of approximation, such as finite elements (FE), finite volumes,and mixed finite elements. The problem of monotonicity isparticularly important in cases of highly anisotropic diffusion tensorsor distorted unstructured meshes. For instance, in the nuclear wastetransport simulation, the non-monotonicity results in the presence ofnegative concentrations which may lead to unacceptable concentrationand chemistry calculations failure. Another drawback of the conventionalmethods is a possible violation of the discrete maximum principle, whichestablishes lower and upper bounds for the solution.We suggest here a least-change correction to the available FE solution$\bar{x} \in R^n$. This postprocessing procedure is aimed on recoveringthe monotonicity and some other important properties that may not beexhibited by $\bar{x}$.The mathematical formulation of the postprocessing problemis reduced to the following convex quadratic programming problem\begin{equation}\label{ls2}\begin{array}{cl}\mbox{min} & \|x-\bar{x}\|^2 \\\mbox{s.t.} & Mx \ge 0, \quad l \le x \le u, \quad e^Tx = m,\end{array}\end{equation}where$e=(1,1, \ldots ,1)^T \in R^n$. The set of constraints $Mx \ge 0$ represents here the monotonicityrelations between some of the adjacent mesh cells.The constraints $l \le x \le u$ originate fromthe discrete maximum principle. The last constraint formulates the conservativity requirement.The postprocessing based on (\ref{ls2}) is typically a large scaleproblem. We introduce here algorithms for solving this problem. Theyare based on the observation that, in the presence of the monotonicityconstraints only, problem (\ref{ls2}) is the classical monotonicregression problem, which can be solved efficiently by some of theavailable monotonic regression algorithms. This solution is used thenfor producing the optimal solution to problem (\ref{ls2}) in thepresence of all the constraints. We present results of numericalexperiments to illustrate the efficiency of our algorithms.

Isotonicregression problem (IR) has numerous importantapplications in statistics, operations research, biology, image andsignal processing and other areas. IR is a minimization problemwiththe objective function defined by the distance from a given pointto aconvex set defined by monotonicity constraints of the form: i-thcomponent of the decision vector is less or equal to its j-thcomponent. The distance in IR is usually associated with the Lpnorm,whereas the norms L1 and L2 are of the highest practical interest.Theconventional optimization methods are unable to solve large-scaleIRproblems originating from large data sets.Historically, the major efforts were focused on IR problem in theL2norm. Exact algorithms such as the minimum lower sets algorithm byBrunk, the min-max algorithm by Lee, the network flow algorithm byMaxwell & Muchstadt and the IBCR algorithm by Block et al. weredeveloped. Among them the IBCR algorithm has been proved to be themostnumerically efficient, but it is not robust enough. An alternativeapproach is related to solving IR problem approximately. Followingthisapproach, Burdakov et al. developed GPAV algorithm whose blockrefinement extension, GPAVR, is able to solve IR problem with highaccuracy in a far shorter time than the exact algorithms. Apartfromthis, GPAVR is a very robust algorithm.Unfortunately, for the norm L1 there are no algorithms which are asefficient as those in L2 norm. In our talk, we introduce newalgorithms, GPAVR1 and IBCR1. They are extensions of the algorithmsGPAV and IBCR to L1 norm. We present also results of numericalexperiments, which demonstrate the high efficiency of the newalgorithms, especially for very large-scaleproblems.

In [Euro. J. Operat. Res. 143 (2002) 452, Opt. Meth. Software 17 (2002) 383] a Riccati-based primal interior point method for multistage stochastic programmes was developed. This algorithm has several interesting features. It can solve problems with a nonlinear node-separable convex objective, local linear constraints and global linear constraints. This paper demonstrates that the algorithm can be efficiently parallelized. The solution procedure in the algorithm allows for a simple but efficient method to distribute the computations. The parallel algorithm has been implemented on a low-budget parallel computer, where we experience almost perfect linear speedup and very good scalability of the algorithm. © 2003 Elsevier Science B.V. All rights reserved.

We propose a new method for certain multistage stochastic programs with linear or nonlinear objective function, combining a primal interior point approach with a linear-quadratic control problem over the scenario tree. The latter problem, which is the direction finding problem for the barrier subproblem is solved through dynamic programming using Riccati equations. In this way we combine the low iteration count of interior point methods with an efficient solver for the subproblems. The computational results are promising. We have solved a financial problem with 1,000,000 scenarios, 15,777,740 variables and 16,888,850 constraints in 20 hours on a moderate computer. © 2002 Elsevier Science B.V. All rights reserved.

The thesis consists of five papers. The first three deal with topics within costly global optimization and the last two concern military decision support systems.

The first part of the thesis addresses so-called costly problems where the objective function is seen as a “black box” to which the input parameter values are sent and a function value is returned. This means in particular that no information about derivatives is available. The black box could, for example, solve a large system of differential equations or carry out   timeconsuming simulation, where a single function evaluation can take several hours! This is the reason for describing such problems as costly and why they require customized algorithms. The goal is to construct algorithms that find a (near)-optimal solution using as few function evaluations as possible. A good example of a real life application comes from the automotive industry, where the development of new engines utilizes advanced mathematical models that are governed by a dozen key parameters. The objective is to optimize the engine by changing these parameters in such a way that it becomes as energy efficient as possible, but still meets all sorts of demands on strength and external constraints. The first three papers describe algorithms and implementation details for these costly global optimization problems.

The second part deals with military mission planning, that is, problems that concern logistics, allocation and deployment of military resources. Given a fleet of resource, the decision problem is to allocate the resources against the enemy so that the overall mission success is optimized. We focus on the problem of the attacker and consider two separate problem classes. In the fourth paper we introduce an effect oriented planning approach to an advanced weapon-target allocation problem, where the objective is to maximize the expected outcome of a coordinated attack. We present a mathematical model together with efficient solution techniques. Finally, in the fifth paper, we introduce a military aircraft mission planning problem, where an aircraft fleet should attack a given set of targets. Aircraft routing is an essential part of the problem, and the objective is to maximize the expected mission success while minimizing the overall mission time. The problem is stated as a generalized vehicle routing model with synchronization and precedence side constraints.

Open-pit mining is an operation in which blocks from the ground are dug to extract the ore contained in them, and in this process a deeper and deeper pit is formed until the mining operation ends. Mining is often a highly complex industrial operation, with respect to both technological and planning aspects. The latter may involve decisions about which ore to mine and in which order. Furthermore, mining operations are typically capital intensive and long-term, and subject to uncertainties regarding ore grades, future mining costs, and the market prices of the precious metals contained in the ore. Today, most of the high-grade or low-cost ore deposits have already been depleted, and to obtain sufficient profitability in mining operations it is therefore today often a necessity to achieve operational efficiency with respect to both technological and planning issues.

In this thesis, we study the open-pit design problem, the open-pit mining scheduling problem, and the open-pit design problem with geological and price uncertainty. These problems give rise to (mixed) discrete optimization models that in real-life settings are large scale and computationally challenging.

The open-pit design problem is to find an optimal ultimate contour of the pit, given estimates of ore grades, that are typically obtained from samples in drill holes, estimates of costs for mining and processing ore, and physical constraints on mining precedence and maximal pit slope. As is well known, this problem can be solved as a maximum flow problem in a special network. In a first paper, we show that two well known parametric procedures for finding a sequence of intermediate contours leading to an ultimate one, can be interpreted as Lagrangian dual approaches to certain side-constrained design models. In a second paper, we give an alternative derivation of the maximum flow problem of the design problem.

We also study the combined open-pit design and mining scheduling problem, which is the problem of simultaneously finding an ultimate pit contour and the sequence in which the parts of the orebody shall be removed, subject to mining capacity restrictions. The goal is to maximize the discounted net profit during the life-time of the mine. We show in a third paper that the combined problem can also be formulated as a maximum flow problem, if the mining capacity restrictions are relaxed; in this case the network however needs to be time-expanded.

In a fourth paper, we provide some suggestions for Lagrangian dual heuristic and time aggregation approaches for the open-pit scheduling problem. Finally, we study the open-pit design problem under uncertainty, which is taken into account by using the concept of conditional value-atrisk. This concept enables us to incorporate a variety of possible uncertainties, especially regarding grades, costs and prices, in the planning process. In real-life situations, the resulting models would however become very computationally challenging.

Integer programming can be used to provide solutionsto complex decision and planning problems occurring in a wide varietyof situations. Applying integer programming to a real life problembasically involves a first phase where a mathematical model isconstructed, and a second phase where the problem described by themodel is solved. While the nature of the challenges involved in therespective two phases differ, the strong relationship between theproperties of models, and which methods that are appropriate for theirsolution, links the two phases. This thesis constitutes of threepapers, of which the third one considers the modeling phase, while thefirst and second one consider the solution phase.

Many applications of column generation yield master problems of setpartitioning type, and the first and second papers presentmethodologies for solving such problems. The characteristics of themethodologies presented are that all successively found solutions arefeasible and integral, where the retention of integrality is a majordistinction from other column generation methods presented in theliterature.

The third paper concerns nurse scheduling and describes the results ofa pilot implementation of a scheduling tool at a Swedish nursing ward.This paper focuses on the practical aspects of modeling and thechallenges of providing a solution to a complex real life problem.

The focus of this thesis is the use of Operations Research for pplications in the forest industry. Optimization models and methods have been developed for problems in the forest supply chain and they have been integrated in decision support systems. The problems considered in this thesis are operative with a planning horizon of less than a month. Short solution times for the methods and the feasibility of the models used are important aspects. The body of this thesis consists of eight research papers where six of them consider operative problems and follows the forest supply chain. The industrial applications include routing of forwarders, routing of logging trucks, a process control problem, and roll cutting problems. The other two papers consider an operative planning problem in the home care sector. They are spin offs from one of the other projects in this thesis. In these applications both linear and nonlinear problems occur.

The forwarding problem is to decide routes for forwarders to pick up the small piles of logs the harvesters have left in the harvest areas. The forwarders then put the logs adjacent to forest roads. The logging truck problem is to decide routes for logging trucks to pick up the piles created by the forwarders and transport them to demand points, for example pulp or paper mills. The process control problem appear in the bleaching stage of a pulp mill where the control variables are the bleaching chemical charges. The cost of bleaching chemicals is minimized while a finishing brightness within target values is ensured. Mainly two roll cutting problems are studied. One is to minimize the number of cutting patterns and one is to minimize the number of reels when defects in the papper reels are considered. The solution methods developed for the forwarding problem have also been applied to a routing problem which appears in staff planning for home care operations.

The different DSS developed and implemented have been tested and several are in daily industrial use. In each of the papers, we have developed robust OR models and quick and effective OR methods. The savings from using the systems vary but are typically in the range 5-20%.

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.

The routing in OSPF Telecommunication networks is determined by computing shortest paths with respect to link weights set by the network operator. All shortest paths to a destination are used by the routers when traffic is routed, and the routers split the traffic evenly when alternative shortest paths exist.

This thesis includes models and methods for various problems related to OSPF networks and OSPF routing. Two different models for the design of OSPF networks are presented. One model ensures that the network is capable of accommodating large parts of the traffic even if a single link fails. The OSPF protocol is modeled using constraints based on weights, and a heuristical method uses the link weights for generating good feasible solutions. The second model is based on routing patterns and does not include the link weights. The OSPF protocol is modeled by ensuring that no pair of routing patterns contains different paths between the same pair of nodes, which is a necessary condition for the existence of weights. A Lagrangean heuristic is proposed as solution method.

The thesis also includes models that can be used for determining if a set of desired routing patterns is obtainable in an OSPF network. The models are infeasible if no link weights yield shortest path graphs which are identical to the patterns, and this means that the patterns can not be used simultaneously in an OSPF network. Infeasible instances are characterized using LP-duality, and a certain structure called “valid cycle” is found in most infeasible instances. A valid cycle involves two routing patterns and indicates which parts of the patterns that are in conflict. This information can be used for finding weights that yields slightly modified patterns. Polynomial methods which can be used for finding valid cycles are presented. There are however also some infeasible instances where no valid cycle exists, so the absence of valid cycles is a necessary condition for the existence of weights. In this case, the conflict involves more than two routing patterns, and such conflicts are characterized by a structure called “3-valid set of cycles”. The absence of 3-valid sets of cycles is a stronger necessary condition for the existence of weights.

The purpose of this thesis is to contribute to the development and the use of optimization models and methods to support efficient decision making in Swedish forestry. The main problem areas concerned are forest road upgrade planning and operational harvest planning. Today much of the planning is done manually by experienced managers. Forest management has a natural hierarchical structure based on the wide range of planning periods and organisational structure. The hierarchical harvest planning and the subdivision into strategic, tactical and operational levels are described from an Operations Research perspective. The description of the hierarchical structure differs between countries and there is a focus on the Swedish situation.

Road upgrading is becoming an increasingly important planning problem to secure a continuous supply of wood. In Sweden, during the periods of thawing and periods of heavy rain there is an uncertain accessibility to parts of the road network due to unfirm ground. The thesis addresses the optimization problem to minimize the combined road upgrade and transportation costs while meeting requirements on road standard such that accessibility to harvest areas is secured during all weather conditions. In this work mixed integer linear programming (MILP) models including multiple assortments, several time periods and a set of road classes are developed. For a typical forest district, the road upgrade problem becomes large and techniques to improve solution performance through model reformulations are discussed. The models are tested in a case study for a major Swedish company. For practical usage of the models we present the development of a new decision support system called RoadOpt. The development has involved the Forestry Research Institute of Sweden, two software companies and several participating forest companies. The system uses a GIS-based map user-interface to present and analyse data and results. The recently developed Swedish road database is an important part. The system is tested on a case study from Stora Enso.

The harvest planning problems addressed cover planning periods ranging from one year down to one month. Annual plans are required for budgeting, contracting harvest teams, contracting transportation firms and assuring road access. The main decisions deal with which areas to harvest, and by which team, during an annual period so that the industries receive the required volume of assortments. Overall decisions about transportation and storage are included. The monthly planning problem includes detailed scheduling of harvest crews, that is, the sequencing of areas for each team. The thesis addresses these planning problems and provides MILP models for each problem. Methods based on both a commercial solver and developed LP based heuristics are used. Models and methods are tested on case studies from Holmen Skog.

The heat transfer in the filling phase of injection moulding is studied, based on Gunnar Aronsson’s distance model for flow expansion ([Aronsson], 1996).

The choice of a thermoplastic materials model is motivated by general physical properties, admitting temperature and pressure dependence. Two-phase, per-phase-incompressible, power-law fluids are considered. The shear rate expression takes into account pseudo-radial flow from a point inlet.

Instead of using a finite element (FEM) solver for the momentum equations a general analytical viscosity expression is used, adjusted to current axial temperature profiles and yielding expressions for axial velocity profile, pressure distribution, frozen layer expansion and special front convection.

The nonlinear energy partial differential equation is transformed into its conservative form, expressed by the internal energy, and is solved differently in the regions of streaming and stagnant flow, respectively. A finite difference (FD) scheme is chosen using control volume discretization to keep truncation errors small in the presence of non-uniform axial node spacing. Time and pseudo-radial marching is used. A local system of nonlinear FD equations is solved. In an outer iterative procedure the position of the boundary between the “solid” and “liquid” fluid cavity parts is determined. The uniqueness of the solution is claimed. In an inner iterative procedure the axial node temperatures are found. For all physically realistic material properties the convergence is proved. In particular the assumptions needed for the Newton-Mysovskii theorem are secured. The metal mould PDE is locally solved by a series expansion. For particular material properties the same technique can be applied to the “solid” fluid.

In the circular plate application, comparisons with the commercial FEM-FD program Moldflow (Mfl) are made, on two Mfl-database materials, for which model parameters are estimated/adjusted. The resulting time evolutions of pressures and temperatures are analysed, as well as the radial and axial profiles of temperature and frozen layer. The greatest differences occur at the flow front, where Mfl neglects axial heat convection. The effects of using more and more complex material models are also investigated. Our method performance is reported.

In the polygonal star-shaped plate application a geometric cavity model is developed. Comparison runs with the commercial FEM-FD program Cadmould (Cmd) are performed, on two Cmd-database materials, in an equilateral triangular mould cavity, and materials model parameters are estimated/adjusted. The resulting average temperatures at the end of filling are compared, on rays of different angular deviation from the closest corner ray and on different concentric circles, using angular and axial (cavity-halves) symmetry. The greatest differences occur in narrow flow sectors, fatal for our 2D model for a material with non-realistic viscosity model. We present some colour plots, e.g. for the residence time.

The classical square-root increase by time of the frozen layer is used for extrapolation. It may also be part of the front model in the initial collision with the cold metal mould. An extension of the model is found which describes the radial profile of the frozen layer in the circular plate application accurately also close to the inlet.

The well-posedness of the corresponding linearized problem is studied, as well as the stability of the linearized FD-scheme.

This paper deals with a Military Aircraft Mission Planning Problem, where the problem is to find time efficient flight paths for a given aircraft fleet that should attack a number of ground targets. Due to the nature of the attack, two aircraft need to rendezvous at the target, that is, they need to be synchronized in both space and time. At the attack, one aircraft is launching a guided weapon, while the other is illuminating the target. Each target is associated with multiple attack and illumination options. Further, there may be precedence constraints between targets, limiting the order of the attacks. The objective is to maximize the outcome of the entire attack, while also minimizing the mission time span. We present two mathematical models for this problem and compare their efficiency on some small test cases. We also provide some heuristic approaches since direct application of a general MIP solver to the mathematical model is only practical for smaller scenarios. The heuristics are compared and they successfully provide solutions to a number of scenarios.

The multilinear least-squares (MLLS) problem is an extension of the linear least-squares problem. The difference is that a multilinearoperator is used in place of a matrix-vector product. The MLLS istypically a large-scale problem characterized by a large number of local minimizers. It originates, for instance, from the design of filter networks. We present a global search strategy that allows formoving from one local minimizer to a better one. The efficiencyof this strategy isillustrated by results of numerical experiments performed forsome problems related to the design of filter networks.

We suggest here a least-change correction to available finite element (FE) solution.This postprocessing procedure is aimed at recoveringthe monotonicity and some other important properties that may not beexhibited by the FE solution. It is based on solvinga monotonic regression problem with some extra constraints.One of them is a linear equality-type constraint which models the conservativityrequirement. The other ones are box-type constraints, andthey originate from the discrete maximum principle.The resulting postprocessing problem is a large scale quadratic optimization problem. It is proved that the postprocessedFE solution preserves the accuracy of the discrete FE approximation.We introduce an algorithm for solving the postprocessingproblem. It can be viewed as a dual ascent method basedon the Lagrangian relaxation of the equality constraint.We justify theoretically its correctness.Its efficiency is demonstrated by the presented results of numerical experiments.

We consider a constrained optimization problem with mixed integer and real variables. It models optimal placement of communications relay nodes in the presence of obstacles. This problem is widely encountered, for instance, in robotics, where it is required to survey some target located in one point and convey the gathered information back to a base station located in another point. One or more unmanned aerial or ground vehicles (UAVs or UGVs) can be used for this purpose as communications relays. The decision variables are the number of unmanned vehicles (UVs) and the UV positions. The objective function is assumed to access the placement quality. We suggest one instance of such a function which is more suitable for accessing UAV placement. The constraints are determined by, firstly, a free line of sight requirement for every consecutive pair in the chain and, secondly, a limited communication range. Because of these requirements, our constrained optimization problem is a difficult multi-extremal problem for any fixed number of UVs. Moreover, the feasible set of real variables is typically disjoint. We present an approach that allows us to efficiently find a practically acceptable approximation to a global minimum in the problem of optimal placement of communications relay nodes. It is based on a spatial discretization with a subsequent reduction to a shortest path problem. The case of a restricted number of available UVs is also considered here. We introduce two label correcting algorithms which are able to take advantage of using some peculiarities of the resulting restricted shortest path problem. The algorithms produce a Pareto solution to the two-objective problem of minimizing the path cost and the number of hops. We justify their correctness. The presented results of numerical 3D experiments show that our algorithms are superior to the conventional Bellman-Ford algorithm tailored to solving this problem.

The set partitioning polytope has the quasi-integrality propertythat enables the use of simplex pivot based methods for finding animproved integer solution, which thereby is associated with a linearprogramming basis and a corresponding dual solution. Presented in thispaper is a framework for an all-integer column generation methodologyfor set partitioning problems that utilises the quasi-integralityproperty of the feasible polytope.In the presented methodology, each successively found solution to arestricted master problem is feasible, integer and associated with acorresponding dual solution, which is then used in the columngeneration step. The column generation problem is tailored to producecolumns that maintain integrality when pivoted into the basis.Furthermore, criteria for verifying optimality are presented.

We study the problem of positioning unmanned aerial vehicles (UAVs) to maintain an unobstructed flow of communication from a surveying UAV to some base station through the use of multiple relay UAVs. This problem can be modeled as a hopconstrained shortest path problem in a large visibility graph. We propose a dual ascent method for solving this problem, optionally within a branch-and-bound framework. Computational tests show that realistic problems can be solved in a reasonably short time, and that the proposed method is faster than the classical dynamic programming approach.

Inom vården utförs ofta schemaläggning av personal manuellt, vilket kräver mycket tid och resurser. Att planera arbetet för en grupp läkare, med dess ofta mycket komplexa sammansättning vad gäller exempelvis arbetsuppgifter och kompetenser, är ingen lätt uppgift. Detta examensarbete studerar huruvida en automatiserad taktisk bemanningsplanering med en tidshorisont på ett halvår till ett år, skulle kunna underlätta denna uppgift.

I rapporten presenteras en måloptimeringsmodell som implementerats i AMPL för att med CPLEX som lösare generera förslag till bemanningsplaner. För att utveckla en matematisk modell som väl representerar de förutsättningar som råder vid bemanningsplanering av läkare har alternativa formuleringar provats och utvärderats. Den mest lovande av modellerna, som baseras på måloptimering, har i en pilotstudie testats på data från Onkologiska kliniken vid Linköpings universitetssjukhus. Flexibiliteten i modellen gjorde att den enkelt kunde användas på de data som erhölls därifrån. Resultatet från pilotstudien indikerar att den utvecklade modellen har kapacitet att ge förslag till rimliga bemanningsplaner.

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.