liu.seSearch for publications in DiVA
Change search
Refine search result
12 1 - 50 of 72
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Brostrom, Peter
    et al.
    Ragn Sells AB.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Design of OSPF networks using subpath consistent routing patterns2009In: TELECOMMUNICATION SYSTEMS, ISSN 1018-4864, Vol. 41, no 4, p. 293-309Article in journal (Refereed)
    Abstract [en]

    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.

    Download full text (pdf)
    FULLTEXT01
  • 2.
    Broström, Peter
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Holmberg, Kaj
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    A new derivation of valid cycles2005Report (Other academic)
  • 3.
    Broström, Peter
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Holmberg, Kaj
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Compatible Weights and Valid Cycles in Non-spanning OSPF Routing Patterns2007Report (Other academic)
  • 4.
    Broström, Peter
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Compatible Weights and Valid Cycles in Non-spanning OSPF Routing Patterns2009In: Algorithmic Operations Research, ISSN 1718-3235, Vol. 4, no 1, p. 19-35Article in journal (Refereed)
    Abstract [en]

    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
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Holmberg, Kaj
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Design of OSPF Networks using Subpath Consistent Routing Patterns2007Report (Other academic)
  • 6.
    Broström, Peter
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Holmberg, Kaj
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Determining the Non-Existence of a Compatible OSPF Metric2004In: Nordic MPS 2004,2004, 2004Conference paper (Other academic)
  • 7.
    Broström, Peter
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Determining the Non-Existence of a Compatible OSPF Metric2004Report (Other academic)
    Abstract [en]

    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
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Holmberg, Kaj
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Internet Protocol Network Design and Routing2003In: 18th International Symposium on Mathematical Programming,2003, 2003Conference paper (Other academic)
  • 9.
    Broström, Peter
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Holmberg, Kaj
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Multiobjective design of survivable IP networks2004Report (Other academic)
  • 10.
    Broström, Peter
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Multiobjective design of survivable IP networks2006In: Annals of Operations Research, ISSN 0254-5330, E-ISSN 1572-9338, Vol. 147, no 1, p. 235-253Article in journal (Refereed)
    Abstract [en]

    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
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Holmberg, Kaj
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    On the Extremal Structure of an OSPF Related Cone2007In: Vietnam journal of mathematics, ISSN 0866-7179, Vol. 35, p. 507-522Article in journal (Refereed)
  • 12.
    Broström, Peter
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Holmberg, Kaj
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    On the Extremal Structure of an OSPF Related Cone2006Report (Other academic)
  • 13.
    Broström, Peter
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Stronger Necessary Conditions for the Existence of a Compatible OSPF Metric2004Report (Other academic)
    Abstract [en]

    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.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Valid Cycles: A Source of Infeasibility in Open Shortest Path First Routing2008In: Networks, ISSN 0028-3045, E-ISSN 1097-0037, Vol. 52, no 4, p. 206-215Article in journal (Refereed)
    Abstract [en]

    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
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Doherty, Patrick
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Kvarnström, Jonas
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Olsson, Per-Magnus
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Positioning Unmanned Aerial Vehicles As Communication Relays for Surveillance Tasks2010In: Robotics: Science and Systems V / [ed] Jeff Trinkle, Yoky Matsuoka, Jose Castellanos, MIT Press, 2010, p. 257-264Conference paper (Refereed)
    Abstract [en]

    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.

  • 16.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Doherty, Patrick
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Kvarnström, Jonas
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Olsson, Per-Magnus
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Relay Positioning for Unmanned Aerial Vehicle Surveillance2010In: The international journal of robotics research, ISSN 0278-3649, E-ISSN 1741-3176, Vol. 29, no 8, p. 1069-1087Article in journal (Refereed)
    Abstract [en]

    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.

  • 17.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Doherty, Patrick
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Olsson, Per-Magnus
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Optimal placement of UV-based communications relay nodes2010In: Journal of Global Optimization, ISSN 0925-5001, E-ISSN 1573-2916, Vol. 48, no 4, p. 511-531Article in journal (Refereed)
    Abstract [en]

    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.

    Download full text (pdf)
    FULLTEXT01
  • 18.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Doherty, Patrick
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Olsson, Per-Magnus
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Optimal placement of communications relay nodes2009Report (Other (popular science, discussion, etc.))
    Abstract [en]

    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.

  • 19.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Olsson, Per-Magnus
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    A Dual Ascent Method for the Hop-constrained Shortest Path with Application to Positioning of Unmanned Aerial Vehicles2008Report (Other academic)
    Abstract [en]

    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.

  • 20.
    Call, Mikael
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Inverse Shortest Path Models Based on Fundamental Cycle Bases2012In: Operations Research Proceedings 2011: Selected Papers of the International Conference on Operations Research (OR 2011), August 30 - September 2, 2011, Zurich, Switzerland / [ed] Diethard Klatte, Hans-Jakob Lüthi, Karl Schmedders, Springer Berlin/Heidelberg, 2012, p. 77-82Chapter in book (Refereed)
    Abstract [en]

    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.
    Henningsson, Mathias
    et al.
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    A ring generation problem based on the traveling salesman subtour problem2003Report (Other academic)
    Abstract [en]

    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.

  • 22.
    Henningsson, Mathias
    et al.
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Calculating cost coefficients for generation of rings in network design2003Report (Other academic)
    Abstract [en]

    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.

  • 23.
    Henningsson, Mathias
    et al.
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Lagrangean price directive ring generation for network design2003Report (Other academic)
    Abstract [en]

    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.

  • 24.
    Henningsson, Mathias
    et al.
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Rönnqvist, Mikael
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Värbrand, Peter
    Linköping University, Department of Science and Technology. Linköping University, The Institute of Technology.
    A column generation approach for a ring network design problem2003Report (Other academic)
    Abstract [en]

    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.

  • 25.
    Henningsson, Mathias
    et al.
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Rönnqvist, Mikael
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Värbrand, Peter
    Linköping University, Department of Science and Technology. Linköping University, The Institute of Technology.
    A ring network design problem and heuristics for generating a set of feasible rings2003Report (Other academic)
    Abstract [en]

    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.

  • 26.
    Henningsson, Mathias
    et al.
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Rönnqvist, Mikael
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Värbrand, Peter
    Linköping University, Department of Science and Technology. Linköping University, The Institute of Technology.
    A ring network design problem solved by a ring generation and allocation approach2003Report (Other academic)
    Abstract [en]

    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.

  • 27.
    Henningsson, Mathias
    et al.
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Holmberg, Kaj
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Rönnqvist, Mikael
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Värbrand, Peter
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Ring network design by Lagrangean based column generation2002In: Telecommunications Systems, ISSN 1018-4864, E-ISSN 1572-9451, Vol. 21, no 2-4, p. 301-318Article in journal (Refereed)
    Abstract [en]

    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.

  • 28.
    Henningsson, Mathias
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Holmberg, Kaj
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Yuan, Di
    Linköping University, The Institute of Technology. Linköping University, Department of Science and Technology, Communications and Transport Systems.
    Ring Network Design2006In: Handbook of Optimization in Telecommunications / [ed] Mauricio G.C. Resende, Panos M. Pardalos, New York: Springer Science + Business Media , 2006, p. 291-312Chapter in book (Other academic)
    Abstract [en]

    "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 Technologies

    Telecommunications 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.

  • 29.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    A new method for optimal proportional representation2019Report (Other academic)
    Abstract [en]

    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.

    Download full text (pdf)
    A new method for optimal proportional representation
    Download (png)
    presentationsbild
  • 30.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Computational Results for Map Matching by Optimization2015Report (Other academic)
    Abstract [en]

    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.

    Download full text (pdf)
    Computational Results for Map Matching by Optimization
  • 31.
    Holmberg, Kaj
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Experiments with primal - dual decomposition and subgradient methods for the uncapacitatied facility location problem2001In: Optimization, ISSN 0233-1934, E-ISSN 1029-4945, Vol. 49, no 5-6, p. 495-516Article in journal (Refereed)
    Abstract [en]

    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

  • 32.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Formation of student groups with the help of optimisation2019In: Journal of the Operational Research Society, ISSN 0160-5682, E-ISSN 1476-9360, Vol. 70, no 9, p. 1538-1553Article in journal (Refereed)
    Abstract [en]

    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.

    Download full text (pdf)
    fulltext
  • 33.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Formation of Student Groups with the Help of Optimization2014Report (Other academic)
    Abstract [en]

    We study the problem of forming groups of students so that the groups are as even as possible with respect to certain aspects, 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.

    Download full text (pdf)
    Formation of Student Groups with the Help of Optimization
  • 34.
    Holmberg, Kaj
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Graph Optimization Approaches for Minimal Rerouting in Symmetric Three Stage Clos Networks2007Report (Other academic)
    Abstract [en]

    Considering routing in symmetrical three stage Clos networks, we search for the routing of an additional connection that requires the least rearrangements, i.e.\ the minimal number of changes of already routed connections. We describe polynomial methods, based on matchings and edge colorings. The basic idea is to swap colors along alternating paths. The paths need to be maximal, and the shortest of these maximal paths is chosen, since it minimizes the rerouting that needs to be done. Computational tests confirm the efficiency of the approach.

  • 35.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Graph optimization approaches for minimal rerouting in symmetric three stage Clos networks2009In: Journal of Mathematical Modelling and Algorithms, ISSN 1570-1166, Vol. 8, no 1, p. 81-100Article in journal (Refereed)
    Abstract [en]

    We consider routing in symmetrical three stage Clos networks. Especially we search for the routing of an additional connection that requires the least rearrangements, i.e. the minimal number of changes of already routed connections. We describe polynomial methods, based on matchings and edge colorings. The basic idea is to swap colors along alternating paths. The paths need to be maximal, and the shortest of these maximal paths is chosen, since it minimizes the rerouting that needs to be done. Computational tests confirm the efficiency of the approach.

    Download full text (pdf)
    FULLTEXT01
  • 36.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Heuristics for the rural postman problem2010In: Computers & Operations Research, ISSN 0305-0548, E-ISSN 1873-765X, Vol. 37, no 5, p. 981-990Article in journal (Refereed)
    Abstract [en]

    When addressing the problem of snow removal for secondary roads, a tool for solving the rural postman problem can be very useful. We present some ideas for heuristics for this problem. The heuristics are of the same type as the classical Frederickson heuristic. The ideas concern the order of the main steps in such a method, namely constructing a connected graph with all vertices having even degree, containing all the required edges. We also propose two postprocessing heuristics for improving the tours and removing unnecessary detours. The computational tests show that the ideas are interesting alternatives to the classical approach, and that running times are acceptable. We study problem characteristics that may indicate which method to choose.

  • 37.
    Holmberg, Kaj
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Heuristics for the Rural Postman Problem with Application to Snow Removal for Secondary Roads2008Report (Other academic)
  • 38.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Heuristics for the weighted k-Chinese/rural postman problem with a hint of fixed costs with applications to urban snow removal2015Report (Other academic)
    Abstract [en]

    We describe a weighted version of the k-Chinese or k-rural postman problem that occurs in the context of snow removal. The problem concerns the questions of which vehicle shall do each task and how the vehicles shall travel between tasks. We also consider different numbers of vehicles, in view of a fixed cost for each vehicle. We describe and discuss heuristic solution approaches, based on usable substructures, such as Chinese/rural postman problems, meta-heuristics, k-means clustering and local search improvements by moving cycles. The methods have been implemented and tested on real life examples.

    Download full text (pdf)
    Heuristics for the weighted k-Chinese/rural postman problem with a hint of fixed costs with applications to urban snow removal
  • 39.
    Holmberg, Kaj
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Kombinatorisk optimering med linjärprogrammering2003Other (Other (popular science, discussion, etc.))
  • 40.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Map Matching by Optimization2015Report (Other academic)
    Abstract [en]

    The problem of map matching appears when evaluating GPS-tracks recorded by service vehicles, and utilizing GPS-information in graphs suitable for route optimization. The task is to associate sequences of GPS-points to links in a graph, suitable for optimization, and thereby obtain paths or tours in the graph. Difficulties are errors in the GPS-coordinates and possible lack of GPS-points on short street segments. We apply mathematical modeling to the problem, in the form of integer programming, and do computational tests of the solvability of the models. In addition to integer programming, we develop several heuristic methods for off-line solution of this problem, based on heuristics, shortest paths and rural postman problems. All methods are computationally tested, and summarized results are reported.

    Download full text (pdf)
    Map Matching by Optimization
  • 41.
    Holmberg, Kaj
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Mean Value Cross Decomposition Based Branch-and-Bound for Mixed Integer Programming Problems2004Report (Other academic)
  • 42.
    Holmberg, Kaj
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Mean Value Cross Decomposition for Nonlinear Convex Problems2003In: 18th International Symposium on Mathematical Programming,2003, 2003Conference paper (Other academic)
  • 43.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    On Using OpenStreetMap and GPS for Optimization2015Report (Other academic)
    Abstract [en]

    Data from OpenStreetMap can be a valuable tool in route optimization of many kinds. With GPS data, analyses of trips can be made. In this paper, we discuss how to extract such data and transform it into forms that are useful for optimization purposes. We also discuss obtaining coordinates from such data. Sets of test problems, for future use, are presented and extracted.

    Download full text (pdf)
    On Using OpenStreetMap and GPS for Optimization
  • 44.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Optimal proportional representation2020Report (Other academic)
    Abstract [en]

    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 the feasible solution that has the minimal disproportionality (with the measure chosen), even in the presence of a parliament threshold, which is not always the case for the practical 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 modified Sainte-Laguë method, 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. The numbers of mandates for the constituencies are based on the number of votes given, not on estimated numbers of inhabitants entitled to vote. This removes the need for compensatory mandates, and makes the question about sizes of the constituencies less important.

    Download full text (pdf)
    fulltext
  • 45.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Optimering2010Book (Refereed)
    Abstract [sv]

    Optimering är en komplett grundbok i optimeringslära som passar för både enklare och mer avancerade kurser på universitetsnivå. Läsaren får en mångsidig verktygslåda för att lösa praktiska optimeringsproblem. Fokus ligger på användbara metoder snarare än teori.Läs merAndra utmärkande drag:? Täcker alla delar av optimeringens grunder? Är ovanligt grundlig i behandlingen av kombinatoriskoptimering och optimering av grafer? Innehåller en stor mängd övningsuppgifter, tillräckligt förbåde lärarledda lektioner och hemuppgifterSpråket är enkelt och beskrivningarna inleds genomgående med exempel där författaren konkret förklarar när och hur metoderna kan användas.

  • 46.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Optimization of OSPF Routing in IP Networks2010In: Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless and Ad Hoc Networks / [ed] A. Koster and X. Munoz, Springer Berlin/Heidelberg, 2010Chapter in book (Refereed)
    Abstract [en]

    Algorithmic discrete mathematics plays a key role in the development of information and communication technologies, and methods that arise in computer science, mathematics and operations research – in particular in algorithms, computational complexity, distributed computing and optimization – are vital to modern services such as mobile telephony, online banking and VoIP. This book examines communication networking from a mathematical viewpoint. The contributing authors took part in the European COST action 293 – a four-year program of multidisciplinary research on this subject. In this book they offer introductory overviews and state-of-the-art assessments of current and future research in the fields of broadband, optical, wireless and ad hoc networks. Particular topics of interest are design, optimization, robustness and energy consumption. The book will be of interest to graduate students, researchers and practitioners in the areas of networking, theoretical computer science, operations research, distributed computing and mathematics.

  • 47.
    Holmberg, Kaj
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Optmization Models for Routing in Switching Networks of Clos Type with many Stages2008In: Advanced modeling and optimization, ISSN 1841-4311, Vol. 10, no 1Article in journal (Refereed)
  • 48.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Prepared Test Instances Extracted from OpenStreetMapData Using Different Network Reductions2018Report (Other academic)
    Abstract [en]

    We investigate the effect of different reductions when importing networksfrom OpenStreetMap data. We describe the network reductions and report computationaltests for doing the network extraction and reduction. We also show the effect ofthe reductions by solving a few standard optimization problems in the resulting networks.Computational tests show that the reductions have a dramatic effect on thenetwork size and the time needed for solving the optimization problems. In many cases,the reductions are necessary in order to be able to solve the optimization problem inreasonable time. A practical result of this work is a set of networks that will be usedas benchmarks in future research, and are publically available for other researchers.

    Download full text (pdf)
    fulltext
  • 49.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Projecting points on the convex hull2016Report (Other academic)
    Abstract [en]

    We discuss the problem of projecting points on their convex hull. Points in the interior of the convex hull are moved outwards to the boundary of the convex hull. While finding the convex hull is a well treated problem, projecting each interior point on the convex hull is not. It is a harder problem, since each point has to be treated. We first discuss a solution approach in two dimensions, and then generalize it to three dimensions. After some significant improvements and changes, we arrive at efficient solutions method for the three dimensional case, using various column and/or constraint generation techniques.

    Download full text (pdf)
    Projecting points on the convex hull
  • 50.
    Holmberg, Kaj
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    The (Over) Zealous Snow Remover Problem2016Report (Other academic)
    Abstract [en]

    Planning snow removal is a difficult, infrequently occurring optimization problem, concerning complicated routing of vehicles. Clearing a street includes several different activities, and the tours must be allowed to contain subtours. The streets are classified into different types, each type requiring different activities. We address the problem facing a single vehicle, including details such as precedence requirements and turning penalties. We describe a solution approach based on a reformulation to an asymmetric traveling salesman problem in an extended graph, plus a heuristic for finding feasible solutions. The method have been implemented and tested on real life examples, and the solution times are short enough to allow online usage. We compare two different principles for the number of sweeps on a normal street, encountered in discussions with snow removal contractors. A principle using a first sweep in the middle of the street around the block, in order to quickly allow usage of the streets, is found to yield interesting theoretical and practical difficulties.

    Download full text (pdf)
    The (Over) Zealous Snow Remover Problem
12 1 - 50 of 72
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf