SwePub - search: WFRF:(Holmberg Kaj)

Enumeration	Reference	Cover	Find
1.	Brostrom, Peter, et al. (author) Design of OSPF networks using subpath consistent routing patterns 2009 In: TELECOMMUNICATION SYSTEMS. - : Springer Science and Business Media LLC. - 1018-4864 .- 1572-9451. ; 41:4, s. 293-309 Journal article (peer-reviewed)abstract 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.
2.	Broström, Peter, 1973-, et al. (author) A new derivation of valid cycles 2005 Reports (other academic/artistic)
3.	Broström, Peter, 1973-, et al. (author) Compatible Weights and Valid Cycles in Non-spanning OSPF Routing Patterns 2007 Reports (other academic/artistic)
4.	Broström, Peter, et al. (author) Compatible Weights and Valid Cycles in Non-spanning OSPF Routing Patterns 2009 In: Algorithmic Operations Research. - 1718-3235. ; 4:1, s. 19-35 Journal article (peer-reviewed)abstract Many IP (Internet Protocol) networks use OSPF (Open Shortest Path First) for determining the routing of traffic. OSPF routers compute routing paths using link weights set by the network administrator, and the routers send traffic on all shortest paths to the destination. An interesting question is whether or not a set of prespecified routing patterns can be realized in an OSPF network. If not, we seek structural properties that explain why no such weights exist. Mathematical models for finding weights and for combining routing patterns are presented. We show that two possibly non-spanning routing patterns forming a ``valid cycle'' cannot simultaneously be obtained in an OSPF network. Two new methods for finding valid cycles are presented, illustrated by numerical examples, and shown to be faster that those previously known.
5.	Broström, Peter, 1973-, et al. (author) Design of OSPF Networks using Subpath Consistent Routing Patterns 2007 Reports (other academic/artistic)
6.	Broström, Peter, 1973-, et al. (author) Determining the Non-Existence of a Compatible OSPF Metric 2004 In: Nordic MPS 2004,2004. Conference paper (other academic/artistic)
7.	Broström, Peter, 1973-, et al. (author) Determining the Non-Existence of a Compatible OSPF Metric 2004 Reports (other academic/artistic)abstract Many telecommunication networks use Internet Protocol for deciding the routing of traffic. The specifications OSPF (Open Shortest Path First) and ECM (Equal Cost Multipath) are very common, and state that each router sends the traffic on the shortest path to the destination. If there are several shortest path, the router splits the traffic evenly. In order to have some control over the traffic distribution, the operator can assign weights to the links in the network, and these weights are used by the routers when calculating the shortest paths. It has been shown that by optimizing over the values of the weights, the performance of a network can be much improved. A difficult question is whether or not for a set of desired traffic patterns there exists a compatible metric, i.e. weights making the routers give the specified traffic patterns. There is one known necessary condition for the existence of such a metric, but up to now no sufficient conditions. We investigate this problem, and find more general necessary conditions for the existence of compatible weights for a set of given desired "shortest path"-graphs. A polynomial algorithm that for most cases verifies the non-existence of a compatible metric is presented. The algorithm also indicates which parts of the traffic patterns that are in conflict. A few numer;cal examples are used to illustrate the procedure, and some computational tests are reported.
8.	Broström, Peter, 1973-, et al. (author) Internet Protocol Network Design and Routing 2003 In: 18th International Symposium on Mathematical Programming,2003. Conference paper (other academic/artistic)
9.	Broström, Peter, 1973-, et al. (author) Multiobjective design of survivable IP networks 2004 Reports (other academic/artistic)
10.	Broström, Peter, et al. (author) Multiobjective design of survivable IP networks 2006 In: Annals of Operations Research. - : Springer Science and Business Media LLC. - 0254-5330 .- 1572-9338. ; 147:1, s. 235-253 Journal article (peer-reviewed)abstract Modern communication networks often use Internet Protocol routing and the intra-domain protocol OSPF (Open Shortest Path First). The routers in such a network calculate the shortest path to each destination and send the traffic on these paths, using load balancing. The issue of survivability, i.e. the question of how much traffic the network will be able to accommodate if components fail, is increasingly important. We consider the problem of designing a survivable IP network, which also requires determining the routing of the traffic. This is done by choosing the weights used for the shortest path calculations.
11.	Broström, Peter, 1973-, et al. (author) On the Extremal Structure of an OSPF Related Cone 2007 In: Vietnam journal of mathematics. - 0866-7179. ; 35, s. 507-522 Journal article (peer-reviewed)
12.	Broström, Peter, 1973-, et al. (author) On the Extremal Structure of an OSPF Related Cone 2006 Reports (other academic/artistic)
13.	Broström, Peter, 1973-, et al. (author) Stronger Necessary Conditions for the Existence of a Compatible OSPF Metric 2004 Reports (other academic/artistic)abstract A dominating standard for routing in telecommunication networks is Internet Protocol with OSPF (Open Shortest Path First) and ECM (Equal Cost Multipath). Each router sends the traffic on the shortest path to the destination. If there are several shortest path, the router splits the traffic evenly. The operator can assign weights to the links in the network, which are used by the routers when calculating the shortest paths. An important question is whether or not for a set of desired traffic patterns there exists a compatible metric, i.e. weights making the routers give the specified traffic patterns. We describe necessary conditions, stronger than those previously discovered, for the existence of compatible weights for a set of given desired shortest path-graphs.
14.	Broström, Peter, et al. (author) Valid Cycles: A Source of Infeasibility in Open Shortest Path First Routing 2008 In: Networks. - : Wiley. - 0028-3045 .- 1097-0037. ; 52:4, s. 206-215 Journal article (peer-reviewed)abstract 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.
15.	Burdakov, Oleg, 1953-, et al. (author) A Dual Ascent Method for the Hop-constrained Shortest Path with Application to Positioning of Unmanned Aerial Vehicles 2008 Reports (other academic/artistic)abstract 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.
16.	Burdakov, Oleg, et al. (author) Optimal placement of communications relay nodes 2009 Reports (pop. science, debate, etc.)abstract 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.
17.	Burdakov, Oleg, et al. (author) Optimal placement of UV-based communications relay nodes 2010 In: Journal of Global Optimization. - : Springer. - 0925-5001 .- 1573-2916. ; 48:4, s. 511-531 Journal article (peer-reviewed)abstract 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.
18.	Burdakov, Oleg, et al. (author) Positioning Unmanned Aerial Vehicles As Communication Relays for Surveillance Tasks 2010 In: Robotics. - : MIT Press. - 9780262514637 ; , s. 257-264 Conference paper (peer-reviewed)abstract 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.
19.	Burdakov, Oleg, et al. (author) Relay Positioning for Unmanned Aerial Vehicle Surveillance 2010 In: The international journal of robotics research. - : Sage Publications. - 0278-3649 .- 1741-3176. ; 29:8, s. 1069-1087 Journal article (peer-reviewed)abstract When unmanned aerial vehicles (UAVs) are used for surveillance, information must often be transmitted to a base station in real time. However, limited communication ranges and the common requirement of free line of sight may make direct transmissions from distant targets impossible. This problem can be solved using relay chains consisting of one or more intermediate relay UAVs. This leads to the problem of positioning such relays given known obstacles, while taking into account a possibly mission-specific quality measure. The maximum quality of a chain may depend strongly on the number of UAVs allocated. Therefore, it is desirable to either generate a chain of maximum quality given the available UAVs or allow a choice from a spectrum of Pareto-optimal chains corresponding to different trade-offs between the number of UAVs used and the resulting quality. In this article, we define several problem variations in a continuous three-dimensional setting. We show how sets of Pareto-optimal chains can be generated using graph search and present a new label-correcting algorithm generating such chains significantly more efficiently than the best-known algorithms in the literature. Finally, we present a new dual ascent algorithm with better performance for certain tasks and situations.
20.	Call, Mikael, et al. (author) Inverse Shortest Path Models Based on Fundamental Cycle Bases 2012 In: Operations Research Proceedings 2011. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783642292095 ; , s. 77-82 Book chapter (peer-reviewed)abstract The inverse shortest path problem has received considerable attention in the literature since the seminal paper by Burton and Toint from 1992. Given a graph and a set of paths the problem is to find arc costs such that all specified paths are shortest paths. The quality of the arc costs is measured by the deviation from some ideal arc costs. Our contribution is a novel modeling technique for this problem based on fundamental cycle bases. For LP compatible norms we present a cycle basis model equivalent to the LP dual. The LP dual of our cycle basis model is a path based model that only requires a polynomial number of path constraints. This model is valid also for LP incompatible norms. This yields the first polynomial sized path formulation of the original problem.
21.	Call, Mikael, 1980- (author) Inverse Shortest Path Routing Problems in the Design of IP Networks 2010 Licentiate thesis (other academic/artistic)abstract This thesis is concerned with problems related to shortest pathrouting (SPR) in Internet protocol (IP) networks. In IP routing, alldata traffic is routed in accordance with an SPR protocol, e.g. OSPF.That is, the routing paths are shortest paths w.r.t. some artificialmetric. This implies that the majority of the Internet traffic isdirected by SPR. Since the Internet is steadily growing, efficientutilization of its resources is of major importance. In theoperational planning phase the objective is to utilize the availableresources as efficiently as possible without changing the actualdesign. That is, only by re-configuration of the routing. This isreferred to as traffic engineering (TE). In this thesis, TE in IPnetworks and related problems are approached by integer linearprogramming.Most TE problems are closely related to multicommodity routingproblems and they are regularly solved by integer programmingtechniques. However, TE in IP networks has not been studied as much,and is in fact a lot harder than ordinary TE problems without IProuting since the complicating shortest path aspect has to be takeninto account. In a TE problem in an IP network the routing isperformed in accordance with an SPR protocol that depends on a metric,the so called set of administrative weights. The major differencebetween ordinary TE problems and TE in IP networks is that all routingpaths must be simultaneously realizable as shortest paths w.r.t. thismetric. This restriction implies that the set of feasible routingpatterns is significantly reduced and that the only means available toadjust and control the routing is indirectly, via the administrativeweights.A constraint generation method for solving TE problems in IP networksis outlined in this thesis. Given an "original" TE problem, the ideais to iteratively generate and augment valid inequalities that handlethe SPR aspect of IP networks. These valid inequalities are derived byanalyzing the inverse SPR problem. The inverse SPR problem is todecide if a set of tentative routing patterns is simultaneouslyrealizable as shortest paths w.r.t. some metric. When this is not thecase, an SPR conflict exists which must be prohibited by a validinequality that is then augmented to the original TE problem. Toderive strong valid inequalities that prohibit SPR conflicts, athorough analysis of the inverse SPR problem is first performed. Inthe end, this allows us to draw conclusions for the design problem,which was the initial primary concern.
22.	Call, Mikael (author) Shortest Path Routing Modelling, Infeasibility and Polyhedra 2012 Doctoral thesis (other academic/artistic)abstract The Internet is constantly growing but the available resources, i.e. bandwidth, are limited. Using bandwidth efficiently to provide high quality of service to users is referred to as traffic engineering. This is of utmost importance. Traffic in IP networks is commonly routed along shortest paths with respect to auxiliary link weights, e.g. using the OSPF or IS-IS protocol. Here, shortest path routing is indirectly controlled via the link weights only, and it is therefore crucial to have a profound understanding of the shortest path routing mechanism to solve traffic engineering problems in IP networks. The theoretical aspects of such problems have received little attention.Traffic engineering in IP networks leads to very difficult optimization problems and the key element in exact methods for such problems is an inverse shortest path routing problem. It is used to answer the fundamental question of whether there exist link weights that reproduce a set of tentative paths. Path sets that cannot be obtained correspond to routing conflicts. Valid inequalities are instrumental to prohibit such routing conflicts.We analyze the inverse shortest path routing problem thoroughly. We show that the problem is NP-complete, contrary to what is claimed in the literature, and propose a stronger relaxation. Its Farkas system is used to develop a novel and compact formulation based on cycle bases, and to classify and characterize minimal infeasible subsystems. Valid inequalities that prevent routing conflicts are derived and separation algorithms are developed for such inequalities.We also consider several approaches to modelling traffic engineering problems, especially Dantzig–Wolfe reformulations and extended formulations. We give characterizations of facets for some relaxations of traffic engineering problems.Our results contribute to the theoretical understanding, modelling and solution of problems related to traffic engineering in IP networks.
23.	Constantinescu, Radu, 1966, et al. (author) Proteomic profiling of cerebrospinal fluid in parkinsonian disorders. 2010 In: Parkinsonism & related disorders. - : Elsevier BV. - 1873-5126 .- 1353-8020. ; :16, s. 545-49 Journal article (peer-reviewed)abstract Parkinson's disease (PD) and atypical parkinsonian disorders (APD), including multiple system atrophy (MSA), progressive supranuclear palsy (PSP), and corticobasal degeneration (CBD), are a group of neurodegenerative diseases sharing many similar signs and symptoms but distinguished by their particular clinical features, treatment response, prognosis and mortality. The differential diagnosis may be challenging, especially in early disease stages. Considering the importance of an accurate diagnosis both for clinical management and for research, new diagnostic tools are needed. In this study, we investigated 56 PD, 42 MSA, 39 PSP, 9 CBD patients, and 24 healthy controls. After screening the cerebrospinal fluid (CSF) proteome using surface-enhanced laser desorption/ionization time-of-flight mass spectrometry (SELDI-TOF MS), we identified 4 proteins (ubiquitin [mass-to-charge ratio (m/z) 8590], beta2-microglobulin [m/z 11730], and 2 secretogranin 1 [chromogranin B] fragments [m/z 7260 and m/z 6250]) that differentiated healthy controls and PD patients from patients with APD. However, they could not differentiate PD patients from controls. As none of these changes were APD subgroup-specific, they most likely reflect the intensity and/or extent of the neurodegenerative process in general.
24.	Gottfries, Johan, 1958, et al. (author) Proteomics for drug target discovery 2004 In: Chemom Intel Lab Syst. ; 73, s. 47-53 Journal article (peer-reviewed)
25.	Gottfries, Johan, et al. (author) Proteomics for drug target discovery 2004 In: Chemometrics and Intelligent Laboratory Systems. - : Elsevier B.V.. - 0169-7439. ; 73:1, s. 47-53 Journal article (peer-reviewed)abstract Proteomics, genomics and metabonomics have, during the last decade, provided researchers with huge amounts of data. The choice of transformation of such data into useful information is dependent on the study aims and objectives. In the present study, projection methods (i.e., Principal Components Analysis [PCA] and Partial List Squares-Discriminant Analysis [PLS-DA]) were used to overview results from two-dimensional (2D) protein gel separations. The aim was to unravel possibilities for target discovery options via an in-depth understanding of quantified alterations in tissue or body fluid sample protein levels related to diseases. Two examples will be included comprising (1) data measured in cerebrospinal fluid (CSF) samples from diagnosed dementia patients and healthy volunteers, and (2) data from liver samples of drug-treated animals (i.e., Rosigltazone and Wy14643). The examples reveal clear clustering, using the protein levels as input, coinciding with the clinical diagnoses in example 1 and by treatment group in example 2.
26.	Hajizadeh, Roghayeh, et al. (author) A branch-and-dive heuristic for single vehicle snow removal 2020 In: Networks. - : WILEY. - 0028-3045 .- 1097-0037. ; 76, s. 509-521 Journal article (peer-reviewed)abstract This paper deals with planning of a tour for a vehicle to clear a certain set of streets in a city of snow. Our previous results on the problem contain a heuristic based on reformulation to an asymmetric traveling salesman problem (ATSP) which yields feasible solutions and upper bounds, and a relaxation of a MIP model for obtaining lower bounds. The goal now is to try to improve the solutions and bounds. In this paper we describe a branch-and-dive heuristic which is based on branch-and-bound principles. We discuss how branching can be done so that the fixations can be utilized in both the relaxation and the ATSP model, and how the search for better solutions can be done. The heuristic has been implemented and applied to real life city networks. The method is shown to outperform two other heuristics for the ATSP with precedence constraints.
27.	Hajizadeh, Roghayeh, 1986-, et al. (author) Coordination of vehicles in urban snow removal 2021 Reports (other academic/artistic)abstract Snow removal is an unavoidable problem in Nordic countries like Sweden. A number of streets in a city need to be cleared of snow by a limited number of vehicles. The problem can be formulated as a very large mixed integer programming model, which is practically unsolvable. In order to find a feasible solution, first we break done the work into smaller parts, one for each vehicle. To find which streets a vehicle shall take care of, we solve a weighted k-Chinese postman problem. Based on the allocation obtained, we consider snow removal problems for single vehicles, where details such as turning penalties and precedences are included. These problems can be reformulated to asymmetric traveling salesman problems in extended graphs, and we have a heuristic for finding feasible solution of those. In this paper, we discuss combined solution approaches and coordination of the vehicles to find a feasible solution for the whole original problem including all details. We use an iterative procedure to combine the tours, based on the tools mentioned above, and a procedure for constructive coordination of the tours. We also have new improvement procedures for the combined solution. We have implemented the methods and applied them to real life city networks. The numerical results show that the methods obtain feasible tours for large problems within a reasonable time.
28.	Hajizadeh, Roghayeh, 1986-, et al. (author) In search of good relaxations for the urban snow removal problem 2023 Reports (other academic/artistic)abstract Snow removal is, in Sweden, an infrequently occurring challenge. Doing the snow removal more efficiently could give much benefits for society. Since the amounts of snow vary a lot from day to day, and from year to year, fixed plans are not the best. Optimization of the snow removal tours could save much money. In this paper, we study the multi-vehicle urban snow removal problem from a mixed integer programming perspective. It is a very hard problem, and obtaining the exact optimum seems to be out of reach. Therefore, we study relaxations of the problem. Our goal is simply to find the best bounds for the optimal objective function value that is possible in limited time. We present some promising possibilities, verified by extensive computational tests.
29.	Hajizadeh, Roghayeh, 1986-, et al. (author) Lagrangian relaxation for the urban snow removal problem 2023 Reports (other academic/artistic)abstract Snow removal problem in cities is a challenging task in Nordic countries. The problem is finding optimal tours for a certain number of vehicles with some circumstances in order to clear a number of streets in a city. We have formulated the urban snow removal problem as a time-indexed mixed integer linear programming model which is huge and complicated. In our previous work, we studied the model and its different relaxations which show that the problem is not solvable in practice. Since the problem has many sets of constraints with complicated structures, relaxing them with Lagrangian relaxation might be beneficial. In this paper, we discuss different possibilities of relaxing sets of constraints and develop a Lagrangian heuristic which consists of a suitable Lagrangian relaxation of the problem, a subgradient optimization method for solving the Lagrangian dual, and procedures for obtaining feasible solutions. The heuristic has been implemented and applied to artificial and real life city networks. The results show that the bounds have been improved.
30.	Hajizadeh, Roghayeh, 1986- (author) Optimization of Snow Removal in Cities 2023 Doctoral thesis (other academic/artistic)abstract Removing snow in a city is an unavoidable task in Nordic countries like Sweden. A number of streets in an area need to be cleared of snow by a limited number of vehicles and the tours for the vehicles must be planned in order to minimize the time and/or cost. Since the amount of snow can vary significantly from one year to another, the plans/tours of one year cannot be used for the next year. Hence, new tours need to be planned each time. Snow removal can be done in rural or urban areas and in addition during snowfall or after a snowfall. In this thesis, we study urban snow removal after a snowfall. There are different relevant specifics of the urban snow removal problem. For instance, there are different types of streets which need different numbers of sweeps in order to remove the snow. In addition, some tasks must be done before other tasks can be started. This leads to precedence constraints. Furthermore, each vehicle needs a certain time to switch from a task to another task. The problem can be formulated as a huge time-indexed mixed integer programming which often is not directly solvable in practice. The contributions of this thesis include the study of different relaxations and heuristics to find feasible solutions and improve the bounds on the optimal objective function values which are discussed in five papers. Paper I deals with single vehicle snow removal. A branch-and-dive heuristic based on branch-and-bound principles is given in order to improve the solutions and bounds. In Paper II, feasible solutions for the snow removal problem with a limited number of identical vehicles are obtained. First, the work is broken down into smaller parts, one for each vehicle. Based on the obtained allocation, a feasible tour for each single vehicle snow removal is obtained. Finally, combined solution approaches and co-ordination of the vehicles to find a feasible solution for the original problem are discussed. In order to improve the computational efficiency, one can take advantage of the tree structure, since modern real life city networks often contain parts that are trees. In Paper III, tree parts are studied and a tree elimination procedure is given for the snow removal problem, to be used before searching for optimal tours. Two variations encountered in practice for normal streets are compared in Paper IV. The first variant is doing a middle sweep before the two side sweeps and the second one is doing only side sweeps. Paper V studies the problem from modeling perspective. The problem is formulated as a mixed integer programming model and different relaxations of it are investigated. Finally, Lagrangian relaxation of the problem is studied in Paper VI. Different possibilities for Lagrangian relaxations are investigated and subgradient optimization is used to solve the Lagrangian dual.
31.	Hajizadeh, Roghayeh, 1986-, et al. (author) The Non Zealous Snow Remover Problem 2022 Reports (other academic/artistic)abstract We study designing a tour for a snow removal vehicle. Several sweeps are required to clear a street of snow. We compare two variations for normal streets, the first is doing a middle sweep before the two side sweeps, and the second is not doing the middle sweep. We apply a previously developed method called branch-and-dive, and show that it yields very good results if the middle sweep is not used.
32.	Hajizadeh, Roghayeh, 1986-, et al. (author) Urban snow removal : Tree elimination 2022 Reports (other academic/artistic)abstract Planning urban snow removal, which is a complex optimization problem, is an important task in some countries like Sweden. A number of streets in a city must be cleared of snow by a limited number of vehicles and the tours for the vehicles must be planned in order to minimize the time and/or cost. Since modern real life city networks often contain parts that are trees, one can take advantage of the tree structure, in order to improve the computational eÿciency. In this paper, we study tree parts and develop a tree elimination procedure for the snow removal problem, to be used before searching for optimal tours. We have implemented the procedure and applied it to real life city networks. The numerical results compare obtaining feasible tours for real life city networks with and without tree elimination. It shows that the total solution time is signifcantly decreased with tree elimination, and larger areas can be handled.
33.	Hall, Sara, et al. (author) Accuracy of a panel of 5 cerebrospinal fluid biomarkers in the differential diagnosis of patients with dementia and/or parkinsonian disorders. 2012 In: Archives of neurology. - Chicago, IL United States : American Medical Association (AMA). - 1538-3687 .- 0003-9942. ; 69:11, s. 1445-52 Journal article (peer-reviewed)abstract To assess the ability of 5 cerebrospinal fluid(CSF) biomarkers to differentiate between common dementia and parkinsonian disorders.
34.	Henningsson, Mathias, et al. (author) A column generation approach for a ring network design problem 2003 Reports (other academic/artistic)abstract When designing a telecommunication network, one often wish to include some kind of survivability requirement, for example that there should be at least two paths between every pair of nodes in the network. A design model who fulfills this requirement is a network build up with rings. The network design problem is to choose links from a given network, and compose them into a number of rings. The rings are connected to each other at certain transit nodes. The number of possible rings is enormous, and each possible ring is associated with a certain fixed cost. A ring has a fixed capacity, however, we model it as a linear cost depending on the traffic using the ring and the length of the ring. We describe the problem, and model it is a set covering model, where a column describes how a specific ring is used. Even with a small set of rings, number of possible columns in the model is large. Therefore, a column generation approach is used to solve the set covering model with a given set of rings. An important part of the problem is to generate new rings, were the dual solution from the set covering model gives rewards on the nodes, representing a nodes’ wish to be included in a new ring. The ring generation problem is a modification of a traveling salesman subtour problem. New rings are generated using a heuristic. We present some computational results for a real data network and a number of random generated networks.
35.	Henningsson, Mathias, 1970-, et al. (author) A ring generation problem based on the traveling salesman subtour problem 2003 Reports (other academic/artistic)abstract Survivability and high redundancy are two critical issues in field of telecommunications. If a telecommunication network is built up by rings, high redundancy can be established, since the traffic can be sent in either direction. Traffic is usually sent using one direction, and if a failure occurs, the opposite direction is used. There is often a number of requirements on a ring, such as a limit on the number of connected nodes. This means that the network will include a number of rings, and traffic between rings must be possible. Therefore, a network must include a number of transit nodes, where it is possible to send traffic between the rings. We focus on the case where network includes two transit nodes and each ring must include at least one transit node. Since the number of rings is enormous one needs to generate rings.This paper discusses how to generate new rings, given that each node has a reward for connecting the node to the ring. The problem that occurs is a modification of a traveling salesman subtour problem with a additional constraint on the number of nodes connected. A problem formulation is given and some solution approaches are suggested. Two different scenarios are discussed, one where the aim is to modify an already existing ring, and one where the aim is to build a complete new ring. Some computational results are given for a real data network.
36.	Henningsson, Mathias, 1970-, et al. (author) A ring network design problem and heuristics for generating a set of feasible rings 2003 Reports (other academic/artistic)abstract We discuss the problem of designing a telecommunication network with the survivability requirement that the network should be composed of connected rings of links. The work design problem is then to choose links from a given network, and compose them into a number of rings. Furthermore, the rings should be connected at certain transit nodes. The traffic between rings may pass through other rings. Each ring is associated with a certain fixed cost depending on the length of the ring. We describe the problem, modeled as a linear integer programming problem. We find a feasible solution to the problem by first find good rings in the network using two heuristics, and then solve the optimization model using only these rings. Finally, we give some computational results for different networks.
37.	Henningsson, Mathias, 1970-, et al. (author) A ring network design problem solved by a ring generation and allocation approach 2003 Reports (other academic/artistic)abstract The development of optical fibers in telecommunications has lead large changes in the field. When design a telecommunication network, capacity nowadays is cheap, and the minimal cost design tends to be a tree. Since such a design is very vulnerable for link or node failures, one often wish to include some kind of survivability requirement, for example that the network should be two-edge-connected or two-node-connected. Another form of design model is to prescribe that the network should be composed of connected rings of links. The network design problem is then to choose links from a give network, and compose them into a number of rings. Furthermore, the rings should be connected at certain transit nodes. Each possible ring is associated with a certain fixed cost, and all links in a certain ring are given the same capacity. Traffic between rings may pass through other rings, which is an important element of the problem. Finally, reserve capacity allocation according to certain principles is included. We describe the problem, modeled as a linear integer programming problem, and discuss different formulations and different solution methods. As the problem is quite difficult, we focus on heuristic solution methods, including elements of column generation and Lagrangean relaxation.
38.	Henningsson, Mathias, 1970-, et al. (author) Calculating cost coefficients for generation of rings in network design 2003 Reports (other academic/artistic)abstract We discuss a telecommunication network problem where the aim is to design a network that should be composed of connected rings of links. Each possible ring is associated with a certain fixed cost. The traffic between rings may pass through other rings, where the switch between two rings must be done at certain transit nodes. Each ring must pass at least one transit node. We describe the problem, modeled as a linear integer programming problem. We focus on calculating cost coefficients for ring generation using Lagrangean relaxation.
39.	Henningsson, Mathias, 1970-, et al. (author) Lagrangean price directive ring generation for network design 2003 Reports (other academic/artistic)abstract This paper addresses the problem of designing a telecommunication network with certain survivability requirements, namely that the network should be made up between connected rigs. This way single link failures do not kill the connection between any two nodes. One can make the network two-node-connected by including two specific nodes in all rings. This gives rise to a network design optimization problem with fixed costs on rings. In this paper we describe a solution approach for such problems, based on generation of rings. The approach is in principle a column generation technique, where the dual prices used for pricing out columns are obtained with the help of Lagrange duality, instead of the usual LP-duality. Computational tests are reported.
40.	Henningsson, Mathias, 1970-, et al. (author) Ring Network Design 2006 In: Handbook of Optimization in Telecommunications. - New York : Springer Science + Business Media. - 0387306625 - 9780387301655 ; , s. 291-312 Book chapter (other academic/artistic)abstract "I highly recommend The Handbook of Optimization in Telecommunications as an invaluable resource for anyone interested in understanding the impact of optimization on the most import problems facing the telecommunications industry today.The handbook is unprecedented in the breadth and depth of its coverage, illustrating that telecommunications offers a vast array of interesting and important optimization problems probably exceeding the traditional areas of transportation networks, engineering, economics and military operations.”—Clyde Monma, Retired Chief Scientist, Applied Research Area, Telcordia TechnologiesTelecommunications has had a major impact in all aspects of life in the last century. There is little doubt that the transformation from the industrial age to the information age has been fundamentally influenced by advances in telecommunications.Optimization problems are abundant in the telecommunications industry. The successful solution of these problems has played an important role in the development of telecommunications and its widespread use. Optimization problems arise in the design of telecommunication systems and in their operation.The Handbook of Optimization in Telecommunications brings together experts from around the world who use optimization to solve problems that arise in telecommunications. The editors made an effort to cover recent optimization developments that are frequently applied to telecommunications. The spectrum of topics covered includes planning and design of telecommunication networks, routing, network protection, grooming, restoration, wireless communications, network location and assignment problems, Internet protocol, World Wide Web, and stochastic issues in telecommunications. The editors’ objective is to provide a reference tool for the increasing number of scientists and engineers in telecommunications who depend upon optimization in some way.Each chapter in the handbook is of an expository nature, but of scholarly treatment, and includes a brief overview of the state-of-the-art thinking relative to the topic, as well as pointers to the key references in the field. Specialists as well as nonspecialists should find this handbook stimulating and helpful.
41.	Henningsson, Mathias, et al. (author) Ring network design by Lagrangean based column generation 2002 In: Telecommunications Systems. - 1018-4864 .- 1572-9451. ; 21:2-4, s. 301-318 Journal article (peer-reviewed)abstract We discuss the problem of designing a telecommunication network with the survivability requirement that the network should be composed of connected rings of links. The network design problem is then to choose links from a given network, and compose them into a number of rings. Furthermore, the rings should be connected at certain transit nodes. The traffic between rings may pass through other rings. Each ring is associated with a certain fixed cost depending on the length of the ring. We describe the problem, modeled as a linear integer programming problem, and a heuristic solution method, based on column generation and Lagrangean relaxation.
42.	Holmberg, Kaj, et al. (author) A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem 2000 In: Operations Research. - : Institute for Operations Research and the Management Sciences (INFORMS). - 0030-364X .- 1526-5463. ; 48:3, s. 461-481 Journal article (peer-reviewed)abstract The capacitated network design problem is a multicommodity minimal cost network flow problem with fixed charges on the arcs and is well known to be NP-hard. The problem type is very common in the context of transportation networks, telecommunication networks, etc. In this paper we propose an efficient method for this problem, based on a Lagrangian heuristic within a branch-and-bound framework. The Lagrangian heuristic uses a Lagrangian relaxation to obtain easily solved subproblems and solves the Lagrangian dual by subgradient optimization. It also includes techniques for finding primal feasible solutions. The Lagrangian heuristic is then embedded into a branch-and-bound scheme that yields further primal improvements. Special penalty tests and cutting criteria are developed. The branch-and-bound scheme can either be an exact method that guarantees the optimal solution of the problem or be a quicker heuristic. The method has been tested on networks of various structures and sizes. Computational comparisons between this method and a state-of-the-art mixed-integer code are presented. The method is found to be capable of generating good feasible solutions to large-scale problems within reasonable time and data storage limits.
43.	Holmberg, Kaj, et al. (author) A multicommodity network-flow problem with side constraints on paths solved by column generation 2003 In: INFORMS journal on computing. - : Institute for Operations Research and the Management Sciences (INFORMS). - 1091-9856 .- 1526-5528. ; 15:1, s. 42-57 Journal article (peer-reviewed)abstract 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 NP-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.
44.	Holmberg, Kaj, 1955- (author) A new method for optimal proportional representation 2019 Reports (other academic/artistic)abstract In a democratic proportional election system, it is vital that the mandates in the parliament are allocated as proportionally as possible to the number of votes the parties got in the election. We formulate an optimization model for allocation of seats in a parliament so as to minimize the disproportionality. By applying separable programming techniques, we obtain an easily solvable problem, and present a method for solving it optimally. The obtained solution is thus the feasible solution that has the minimal disproportionality (with the measure chosen), in contrast to the heuristic procedures used in many countries. We apply the approach to real life data from the last three elections in Sweden, and show that the result is better, i.e. more proportional, than what was obtained with the “adjusted odd number rule”, which is presently used. A natural suggestion would be to use our method instead.We also consider the issue about constituencies, and suggest a procedure, based on the same kind of optimization problem, for allocating mandates in the constituencies, without changing the overall allocation with respect to parties. In our approach, the numbers of mandates for the constituencies are based on the number of votes given, not on estimated numbers of inhabitants. This removes the need for fixed and equalization mandates, and also makes the question about sizes of the constituencies less important.
45.	Holmberg, Kaj, 1955-, et al. (author) Complexity of Inverse Shortest Path Routing 2011 In: Network Optimization. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783642215261 - 9783642215278 ; , s. 339-353 Book chapter (peer-reviewed)abstract The inverse shortest path routing problem is to decide if a set of tentative routing patterns is simultaneously realizable. A routing pattern is defined by its destination and two arc subsets of required shortest path arcs and prohibited non-shortest path arcs. A set of tentative routing patterns is simultaneously realizable if there is a cost vector such that for all routing patterns it holds that all shortest path arcs are in some shortest path and no non-shortest path arc is in any shortest path to the destination of the routing pattern. Our main result is that this problem is NP-complete, contrary to what has been claimed earlier in the literature. Inverse shortest path routing problems naturally arise as a subproblem in bilevel programs where the lower level consists of shortest path problems. Prominent applications that fit into this framework include traffic engineering in IP networks using OSPF or IS-IS and in Stackelberg network pricing games. In this paper we focus on the common subproblem that arises if the bilevel program is linearized and solved by branch-and-cut. Then, it must repeatedly be decided if a set of tentative routing patterns is realizable. In particular, an NP-completeness proof for this problem is given.
46.	Holmberg, Kaj (author) Computational Results for Map Matching by Optimization 2015 Reports (other academic/artistic)abstract The problem of map matching appears when evaluating GPS-tracks recorded by service vehicles, and is used to associate the sequences of GPS-points to links in a graph. Difficulties are errors in the GPS-coordinates and possible lack of GPS-points on short street segments. This paper reports computational tests on integer programming models for the problem, and on several heuristic methods, based on shortest paths and rural postman problems. We present extensive computational results for several methods and for both artificial and real life test cases.
47.	Holmberg, Kaj, 1955-, et al. (author) Design of IP/OSPF Networks Using a Lagrangean Heuristic on an In-graph Based Model 2005 In: Proceedings of the International Network Optimization Conference, INOC 2005. - Lisbon, Portugal : University of Lisbon. ; , s. 702- Conference paper (peer-reviewed)abstract This paper address the problem of designing IP networks where traffic is distributed in accordance with the OSPF protocol. Routers use link weights for determining how traffic is distributed. All shortest paths between pairs of routers are used and the traffic is evenly divided when several paths are shortest. We formulate a new model for the design of IP networks with OSPF and ECM distribution where weights are implicitly included. Necessary constraints for representing the shortest paths obtained from link weights by in-graphs are described. A Lagrangean heuristic is developed for verifying the usefulness of the model. Numerical experiments on test problems shows that acceptable gaps are obtained in reasonable time.
48.	Holmberg, Kaj, 1955-, et al. (author) Determining the Non-Existence of a Compatible OSPF Metric 2005 In: International Network Optimization Conference, INOC 2005,2005. - Lisbon, Portugal : University of Lisbon. ; , s. 106- Conference paper (peer-reviewed)
49.	Holmberg, Kaj (author) Experiments with primal - dual decomposition and subgradient methods for the uncapacitatied facility location problem 2001 In: Optimization. - : Informa UK Limited. - 0233-1934 .- 1029-4945. ; 49:5-6, s. 495-516 Journal article (peer-reviewed)abstract For optimization problems that are structured both with respect to the constraints and with respect to the variables, it is possible to use primal–dual solution approaches, based on decomposition principles. One can construct a primal subproblem, by fixing some variables, and a dual subproblem, by relaxing some constraints and king their Lagrange multipliers, so that both these problems are much easier to solve than the original problem. We study methods based on these subproblems, that do not include the difficult Benders or Dantzig-Wolfe master problems, namely primal–dual subgradient optimization methods, mean value cross decomposition, and several comtbinations of the different techniques. In this paper, these solution approaches are applied to the well-known uncapacitated facility location problem. Computational tests show that some combination methods yield near-optimal solutions quicker than the classical dual ascent method of Erlenkotter
50.	Holmberg, Kaj (author) Formation of student groups with the help of optimisation 2019 In: Journal of the Operational Research Society. - : TAYLOR & FRANCIS LTD. - 0160-5682 .- 1476-9360. ; 70:9, s. 1538-1553 Journal article (peer-reviewed)abstract We study the problem of forming groups of students so that the groups are as even as possible with respect to certain aspects and group members are changed as much as possible compared to previous groups, and formulate it as a mixed integer programming problem. We find that standard software cannot solve real life sized instances, so we develop several heuristics and metaheuristics for the problem. Computational tests are made on randomly generated instances as well as real life instances. Some of the heuristics give good solutions in short time, and tests on real life problems indicate that satisfactory solutions can be found within 60 seconds.

Skapa referenser, mejla, bekava och länka

Permalink

Träfflista för sökning "WFRF:(Holmberg Kaj) "

Refine your search

Year