liu.seSök publikationer i DiVA
Ändra sökning
Avgränsa sökresultatet
1234567 151 - 200 av 367
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Träffar per sida
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sortering
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
  • 151.
    Gunnarsson, Helene
    et al.
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Rönnqvist, Mikael
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Solving a multi-period supply chain problem for a pulp industry using Lagrangian heuristics based on time periods2007Rapport (Övrigt vetenskapligt)
  • 152.
    Gunnarsson, Helene
    et al.
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Rönnqvist, Mikael
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Carlsson, Dick
    A combined terminal location and ship routing problem2004Rapport (Övrigt vetenskapligt)
  • 153.
    Gunnarsson, Helene
    et al.
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Rönnqvist, Mikael
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Carlsson, Dick
    Integrated production and distribution planning of the supply chain for Södra Cell AB2004Rapport (Övrigt vetenskapligt)
  • 154. Beställ onlineKöp publikationen >>
    Gunnarsson Lidestam, Helene
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Supply chain optimization in the forest industry2007Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
    Abstract [sv]

    Denna avhandling presenterar matematiska modeller och lösningsmetoder för optimering av olika logistikproblem inom skogsindustrin. Vi studerar försörjningskedjor för skogsbränsle och massaproduker, och beaktar den årliga planeringen i syfte att optimera flödet.

    Det första problemet behandlar skogsbränsle och är ett samarbete med Sydved Energileveranser AB. Råmaterial i form av grenar och toppar från avverkningsplatser ska flisas och transporteras till värmeverk, eventuellt via terminaler. Det finns möjlighet att flisa både i skogen och på terminaler. Biprodukter från sågverk kan också användas som råmaterial. Vid behov kan utbudet av råmaterial utökas genom att fler avverkningsplatser och sågverk kontrakteras. Värmeverken har en efterfrågan, angiven i kWh per månad, som ska uppfyllas. Exempel på beslut som ska tas är var flisning ska ske, om nya avverkningsplatser ska kontrakteras, var lagring ska ske, samt hur och när skogsbränslet ska transporteras.

    Nästföljande problem behandlar massaprodukter och är ett samarbete med Södra Cell AB. Olika sorters massaved från skogen och biprodukter från sågverk utgör råmaterial för produktion av massaprodukter. Råmaterialet transporteras till massabruk för tillverkning enligt specificerade recept. De färdiga produkterna transporteras sedan med fartyg till terminaler i Europa. Från terminalerna transporteras produkterna vidare till pappersbruk, vilka är företagets slutkunder. Massaprodukterna transporteras i vissa fall med lastbil eller tåg direkt från massabruken till kunderna. Efterfrågan är angiven inom vissa gränser i olika order. Vissa order är fasta, vilket innebär att dess efterfrågan måste uppfyllas, medan andra order är fria. Exempel på beslut som ska tas är vilka bruk olika produkter ska produceras på, hur många och vilka terminaler som ska användas, samt hur transporterna ska utföras för att ge bästa resultat.

    Utifrån ovanstående beskrivningar har matematiska modeller formulerats. Ge-nom att lösa dessa kan vi få svar på logistik- och transportfrågorna och ett optimalt flöde kan hittas. För att lösa modellerna har kommersiell programvara använts. Heuristiker och mer avancerade optimeringsmetoder har också utvecklats i syfte att producera bra lösningar snabbare.

    Delarbeten
    1. Supply chain modelling of forest fuel
    Öppna denna publikation i ny flik eller fönster >>Supply chain modelling of forest fuel
    2004 (Engelska)Ingår i: European Journal of Operational Research, ISSN 0377-2217, Vol. 158, nr 1, s. 103-123Artikel i tidskrift (Refereegranskat) Published
    Abstract [en]

    We study the problem of deciding when and where forest residues are to be converted into forest fuel, and how the residues are to be transported and stored in order to satisfy demand at heating plants. Decisions also include whether or not additional harvest areas and saw-mills are to be contracted. In addition, we consider the flow of products from saw-mills and import harbors, and address the question about which terminals to use. The planning horizon is one year and monthly time periods are considered. The supply chain problem is formulated as a large mixed integer linear programming model. In order to obtain solutions within reasonable time we have developed a heuristic solution approach. Computational results from a large Swedish supplying entrepreneur are reported.

    Nyckelord
    Supply chain management, Integer programming, Inventory, Transportation
    Nationell ämneskategori
    Matematik
    Identifikatorer
    urn:nbn:se:liu:diva-14461 (URN)10.1016/S0377-2217(03)00354-0 (DOI)
    Tillgänglig från: 2007-05-14 Skapad: 2007-05-14 Senast uppdaterad: 2013-11-07
    2. A combined terminal location and ship routing problem
    Öppna denna publikation i ny flik eller fönster >>A combined terminal location and ship routing problem
    2006 (Engelska)Ingår i: Journal of the Operational Research Society, ISSN 0160-5682, Vol. 57, nr 8, s. 928-938Artikel i tidskrift (Refereegranskat) Published
    Abstract [en]

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

    Nyckelord
    mixed integer programming, facility location, transportation, ship routing
    Nationell ämneskategori
    Matematik
    Identifikatorer
    urn:nbn:se:liu:diva-14462 (URN)10.1057/palgrave.jors.2602057 (DOI)
    Tillgänglig från: 2007-05-14 Skapad: 2007-05-14 Senast uppdaterad: 2013-11-07
    3. Integrated production and distribution planning for S¨odra Cell AB
    Öppna denna publikation i ny flik eller fönster >>Integrated production and distribution planning for S¨odra Cell AB
    2007 (Engelska)Ingår i: Journal of Mathematical Modelling and Algorithms, ISSN 1570-1166, Vol. 6, nr 1, s. 25-45Artikel i tidskrift (Refereegranskat) Published
    Abstract [en]

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

    Nyckelord
    supply chain management; production planning; modelling; transportation; distribution, integer programming
    Nationell ämneskategori
    Matematik
    Identifikatorer
    urn:nbn:se:liu:diva-14463 (URN)10.1007/s10852-006-9048-z (DOI)
    Tillgänglig från: 2007-05-14 Skapad: 2007-05-14
    4. Solving a multi-period supply chain problem for a pulp company using heuristics—An application to Södra Cell AB
    Öppna denna publikation i ny flik eller fönster >>Solving a multi-period supply chain problem for a pulp company using heuristics—An application to Södra Cell AB
    2008 (Engelska)Ingår i: International Journal of Production Economics, ISSN 0925-5273, E-ISSN 1873-7579, Vol. 116, nr 1, s. 75-94Artikel i tidskrift (Refereegranskat) Published
    Abstract [en]

    In this paper, the integrated planning of production and distribution for a pulp company is considered. The tactical decisions included regard transportation of raw materials from harvest areas to pulp mills; production mix and contents at pulp mills; inventory; distribution of pulp products from mills to customers and the selection of potential orders and their levels at customers. The planning period is one year and several time periods are included. As a solution approach we make use of two different heuristic approaches. The main reason to use heuristics is the need for quick solution times. The first heuristic is based on a rolling planning horizon where iteratively a fixed number of time periods is taken into consideration. The second heuristic is based on Lagrangian decomposition and subgradient optimization. This provides optimistic bounds of the optimal objective function value that are better than the LP relaxation value, which can be used as a measure of the heuristic (pessimistic) solution quality. In addition, we apply the proposed rolling horizon heuristic in each iteration of the subgradient optimization. A number of cases based on real data is analysed which shows that the proposed solution approach is simple and provides high quality solutions.

    Ort, förlag, år, upplaga, sidor
    Elsevier, 2008
    Nyckelord
    Supply chain modelling, Production planning, Heuristics, Lagrangian decomposition
    Nationell ämneskategori
    Samhällsvetenskap
    Identifikatorer
    urn:nbn:se:liu:diva-14850 (URN)10.1016/j.ijpe.2008.07.010 (DOI)000261007900006 ()
    Anmärkning

    Original publication: Helene Gunnarsson and Mikael Rönnqvist, Solving a multi-period supply chain problem for a pulp company using heuristics—An application to Södra Cell AB, 2008, International Journal of Production Economics. http://dx.doi.org/10.1016/j.ijpe.2008.07.010. Copyright: Elsevier B.V., http://www.elsevier.com/

    Tillgänglig från: 2008-09-26 Skapad: 2008-09-26 Senast uppdaterad: 2017-12-13Bibliografiskt granskad
    5. Solving a multi-period supply chain problem for a pulp industry using Lagrangian heuristics based on physical stages
    Öppna denna publikation i ny flik eller fönster >>Solving a multi-period supply chain problem for a pulp industry using Lagrangian heuristics based on physical stages
    Manuskript (Övrigt vetenskapligt)
    Identifikatorer
    urn:nbn:se:liu:diva-14465 (URN)
    Tillgänglig från: 2007-05-14 Skapad: 2007-05-14 Senast uppdaterad: 2010-01-13
    Ladda ner fulltext (pdf)
    FULLTEXT01
  • 155.
    Gunnarsson (Lidestam), Helene
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Lundgren, Jan
    Linköpings universitet, Institutionen för teknik och naturvetenskap. Linköpings universitet, Tekniska högskolan.
    Rönnqvist, Mikael
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Supply chain modelling of forest fuel2004Ingår i: European Journal of Operational Research, ISSN 0377-2217, Vol. 158, nr 1, s. 103-123Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We study the problem of deciding when and where forest residues are to be converted into forest fuel, and how the residues are to be transported and stored in order to satisfy demand at heating plants. Decisions also include whether or not additional harvest areas and saw-mills are to be contracted. In addition, we consider the flow of products from saw-mills and import harbors, and address the question about which terminals to use. The planning horizon is one year and monthly time periods are considered. The supply chain problem is formulated as a large mixed integer linear programming model. In order to obtain solutions within reasonable time we have developed a heuristic solution approach. Computational results from a large Swedish supplying entrepreneur are reported.

  • 156.
    Gunnarsson Lidestam, Helene
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Rönnqvist, Mikael
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Solving a multi-period supply chain problem for a pulp industry using Lagrangian heuristics based on time periodsManuskript (Övrig (populärvetenskap, debatt, mm))
  • 157.
    Gunnarsson (Lidestam), Helene
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Rönnqvist, Mikael
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Carlsson, Dick
    Södra Cell AB, Växjö, Sweden.
    A combined terminal location and ship routing problem2006Ingår i: Journal of the Operational Research Society, ISSN 0160-5682, Vol. 57, nr 8, s. 928-938Artikel i tidskrift (Refereegranskat)
    Abstract [en]

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

  • 158.
    Gunnarsson Lidestam, Helene
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Rönnqvist, Mikael
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Carlsson, Dick
    Södra Cell AB, Växjö, Sweden.
    Integrated production and distribution planning for S¨odra Cell AB2007Ingår i: Journal of Mathematical Modelling and Algorithms, ISSN 1570-1166, Vol. 6, nr 1, s. 25-45Artikel i tidskrift (Refereegranskat)
    Abstract [en]

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

  • 159.
    Gustafsson, Stig-Inge
    et al.
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för ekonomisk och industriell utveckling, Energisystem.
    Rönnqvist, Mikael
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Claesson, M
    Optimization models and solution methods for load management2004Ingår i: International journal of energy research (Print), ISSN 0363-907X, E-ISSN 1099-114X, Vol. 28, nr 4, s. 299-317Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    The electricity market in Sweden has changed during recent years. Electricity for industrial use can now be purchased from a number of competing electricity suppliers. Hence, the price for each kilowatt-hour is significantly lower than it was just two years ago and interest in electricity conservation measures has declined. However, part of the electricity tariff, i.e. the demand cost expressed in Swedish Kronor (SEK) for each kilowatt, is almost the same as before. Attention has thereby been drawn to load management measures in order to reduce this specific cost. Saving one kWh might lead to a monetary saving of between SEK 0.22 and SEK 914, this paper demonstrates how to eliminate only those kWh that actually save a significant amount of money. A load management system has been installed in a small carpentry factory that can turn off equipment based on a pre-set priority and number of minutes each hour. The question now is what level of the electricity load is optimal in a strictly mathematical sense, i.e. how many kW should be set in the load management computer in order to maximise profitability? In this paper, we develop a mathematical model that can be used as a tool both to find the most profitable subscription level and to control the choices to be made. Numerical results from a case study are presented. Copyright (C) 2004 John Wiley Sons, Ltd.

  • 160.
    Göthe-Lundgren, Maud
    et al.
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Frisk, Mikael
    Skogforsk.
    Rönnqvist, Mikael
    Norges handelshögskola.
    Jörnsten, Kurt
    Norges handelshögskola.
    Cost allocation in forestry operations2006Ingår i: 12th IFAC Symposium on Information Control Problems in Manufacturing,2006, Paris: Elsevier Science , 2006Konferensbidrag (Refereegranskat)
    Abstract [en]

        

  • 161.
    Göthe-Lundgren, Maud
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Lundgren, Jan T.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Persson, Jan A.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    An optimization model for refinery production scheduling2002Ingår i: International Journal of Production Economics, ISSN 0925-5273, E-ISSN 1873-7579, Vol. 78, nr 3, s. 255-270Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    In this paper we describe a production planning and scheduling problem in an oil refinery company. The problem concerns the planning and the utilization of a production process consisting of one distillation unit and two hydro-treatment units. In the process crude oil is transformed to bitumen and naphthenic special oils. The aim of the scheduling is to decide which mode of operation to use in each processing unit at each point in time, in order to satisfy the demand while minimizing the production cost and taking storage capacities into account. The production cost includes costs for changing mode and for holding inventory. We formulate a mixed integer linear programming model for the scheduling problem. The model can be regarded as a generalized lot-sizing problem, where inventory capacities are considered and more than one product is obtained for some modes of operation. A number of modifications and extensions of the model are also discussed. It is shown how the optimization model can be used as a viable tool for supporting production planning and scheduling at the refinery, and that it is possible to analyze scheduling scenarios of realistic sizes. It is also shown that the model can support shipment planning and strategic decisions concerning new products and investments in storage capacity. © 2002 Elsevier Science B.V. All rights reserved.

  • 162.
    Henningsson, Mathias
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Ring network design in telecommunications: optimization based solution approaches2003Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
    Abstract [en]

    When designing a telecommunication network, one often wish to include some kind of survivability requirement, for example that the network should be two-connected. A two-connected network fulfills the requirement that there should be at least two paths with no links in common between all pairs of nodes. One 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 given network, and compose them into a number of rings. A ring is reliable in the sense that there always exist two ways of sending traffic, clockwise or counter-clockwise, which means that a ring fulfills the two-connectivity requirement. There is often a number of requirements on a ring, such as a limited length and limited number of nodes connected to the ring. This means that a ring network will include a number of rings, and traffic between rings must be possible. The traffic between rings is usually made at certain nodes, called transit nodes. Therefore all rings should be connected to at least one of the transit nodes. We focus on the case where we have two transit nodes in the network.

    Each possible ring is associated with a certain fixed cost, and all links in a certain ring are given the same capacity. Reserve capacity is allocated according to certain principles. The number of possible rings in a network is an exponential function of the number of nodes in the network, so for larger networks is it impossible to a priori generate all possible rings.

    We describe the problem, and model it as a linear integer programming problem, where a set of rings are assumed to be known. The usage of rings, i.e., the allocation of demand to rings, is determined. In practice, too many rings can not be included in the model. Instead we must be able to generate useful rings. A Lagrangean relaxation of the model is formulated, and the dual solution is used in order to derive reduced costs which can be used to generate new better rings. The information generated describes only the physical structure of the ring, not the usage of it. The ring generation problem is a modified traveling salesman subtour problem, which is known to be difficult to solve. Therefore, we focus on heuristic solution methods for this problem.

    We also presents a column generation approach where the problem is modeled as a set covering problem. Here, a column describes both the topology of the ring and the exact usage of it. A similar ring generation problem appears as a subproblem, in order to generate new rings.

    All methods are computationally tested on both real life data and randomly generated data, similar to real life problems.

    Delarbeten
    1. A ring network design problem and heuristics for generating a set of feasible rings
    Öppna denna publikation i ny flik eller fönster >>A ring network design problem and heuristics for generating a set of feasible rings
    2003 (Engelska)Rapport (Övrigt vetenskapligt)
    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.

    Ort, förlag, år, upplaga, sidor
    Linköping: Linköpings universitet, 2003. s. 33
    Serie
    LiTH-MAT-R, ISSN 0348-2960 ; 16
    Nationell ämneskategori
    Matematik
    Identifikatorer
    urn:nbn:se:liu:diva-22367 (URN)1575 (Lokalt ID)1575 (Arkivnummer)1575 (OAI)
    Tillgänglig från: 2009-10-07 Skapad: 2009-10-07 Senast uppdaterad: 2013-08-29
    2. Lagrangean price directive ring generation for network design
    Öppna denna publikation i ny flik eller fönster >>Lagrangean price directive ring generation for network design
    2003 (Engelska)Rapport (Övrigt vetenskapligt)
    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.

    Ort, förlag, år, upplaga, sidor
    Linköping: Linköpings universitet, 2003. s. 19
    Serie
    LiTH-MAT-R, ISSN 0348-2960 ; 17
    Nyckelord
    network design, rings, column generation, Lagrange multipliers
    Nationell ämneskategori
    Matematik
    Identifikatorer
    urn:nbn:se:liu:diva-22370 (URN)1578 (Lokalt ID)1578 (Arkivnummer)1578 (OAI)
    Tillgänglig från: 2009-10-07 Skapad: 2009-10-07 Senast uppdaterad: 2013-08-29
    3. Calculating cost coefficients for generation of rings in network design
    Öppna denna publikation i ny flik eller fönster >>Calculating cost coefficients for generation of rings in network design
    2003 (Engelska)Rapport (Övrigt vetenskapligt)
    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.

    Ort, förlag, år, upplaga, sidor
    Linköping: Linköpings universitet, 2003. s. 27
    Serie
    LiTH-MAT-R, ISSN 0348-2960 ; 18
    Nyckelord
    network design, rings, integer programming, column generation, lagrangean relaxation
    Nationell ämneskategori
    Matematik
    Identifikatorer
    urn:nbn:se:liu:diva-22368 (URN)1576 (Lokalt ID)1576 (Arkivnummer)1576 (OAI)
    Tillgänglig från: 2009-10-07 Skapad: 2009-10-07 Senast uppdaterad: 2013-08-29
    4. A ring generation problem based on the traveling salesman subtour problem
    Öppna denna publikation i ny flik eller fönster >>A ring generation problem based on the traveling salesman subtour problem
    2003 (Engelska)Rapport (Övrigt vetenskapligt)
    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.

    Ort, förlag, år, upplaga, sidor
    Linköping: Linköpings universitet, 2003. s. 27
    Serie
    LiTH-MAT-R, ISSN 0348-2960 ; 19
    Nyckelord
    traveling salesman subtour problem, orienteering problem, prize collecting travelling salesman problem, ring generation
    Nationell ämneskategori
    Matematik
    Identifikatorer
    urn:nbn:se:liu:diva-22369 (URN)1577 (Lokalt ID)1577 (Arkivnummer)1577 (OAI)
    Tillgänglig från: 2009-10-07 Skapad: 2009-10-07 Senast uppdaterad: 2013-08-29
    5. A ring network design problem solved by a ring generation and allocation approach
    Öppna denna publikation i ny flik eller fönster >>A ring network design problem solved by a ring generation and allocation approach
    2003 (Engelska)Rapport (Övrigt vetenskapligt)
    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.

    Ort, förlag, år, upplaga, sidor
    Linköping: Linköpings universitet, 2003. s. 37
    Serie
    LiTH-MAT-R, ISSN 0348-2960 ; 20
    Nationell ämneskategori
    Matematik
    Identifikatorer
    urn:nbn:se:liu:diva-22366 (URN)1574 (Lokalt ID)1574 (Arkivnummer)1574 (OAI)
    Tillgänglig från: 2009-10-07 Skapad: 2009-10-07 Senast uppdaterad: 2013-08-29
    6. A column generation approach for a ring network design problem
    Öppna denna publikation i ny flik eller fönster >>A column generation approach for a ring network design problem
    2003 (Engelska)Rapport (Övrigt vetenskapligt)
    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.

    Förlag
    s. 26
    Serie
    LiTH-MAT-R, ISSN 0348-2960 ; 21
    Nationell ämneskategori
    Teknik och teknologier
    Identifikatorer
    urn:nbn:se:liu:diva-87193 (URN)
    Tillgänglig från: 2013-01-14 Skapad: 2013-01-14 Senast uppdaterad: 2013-08-29
  • 163.
    Henningsson, Mathias
    et al.
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Holmberg, Kaj
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Yuan, Di
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem.
    Ring Network Design2006Ingår i: Handbook of Optimization in Telecommunications / [ed] Mauricio G.C. Resende, Panos M. Pardalos, New York: Springer Science + Business Media , 2006, s. 291-312Kapitel i bok, del av antologi (Övrigt vetenskapligt)
    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.

  • 164.
    Henningsson, Mathias
    et al.
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Karlsson, Jenny
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Rönnqvist, Mikael
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Mixed Integer Programming models to support Tactical Forest Road Upgrade Planning2004Rapport (Övrigt vetenskapligt)
  • 165.
    Henningsson, Mathias
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Karlsson, Jenny
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Rönnqvist, Mikael
    Department of Finance and Management Science, Norwegian School of Economics and Business Administration, Bergen, Norway.
    Optimization models for forest road upgrade planning2007Ingår i: Journal of Mathematical Modelling and Algorithms, ISSN 1570-1166, E-ISSN 1572-9214, Vol. 6, nr 1, s. 3-23Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Road blocking due to thawing or heavy rains annually contribute to a considerable loss in Swedish forestry. Companies are forced to build up large stocks of raw material (saw and pulp logs) in order to secure a continuous supply when access to the road network is uncertain. Storage outdoors leads to quality deterioration and monetary losses. Other related costs due to road blocking are road damage and longer haulage distances. One approach to reduce the losses due to road blocks is to upgrade the road network to a standard that guarantees accessibility. We consider the road upgrade problem from the perspective of Swedish forest companies with a planning horizon of about one decade. The objective is to minimize the combined upgrade and transportation costs. We present two mixed integer programming models, which are uncapacitated fixed charge network flow problems including multiple assortments, several time periods and a set of road classes. One model is based on arc flows and one on route flows. For a typical planning instance, the models become large and we propose how to improve solution performance through model strengthening. The models are tested in a case study for a major Swedish forest company.

  • 166.
    Holm, Åsa
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    A Tailored Branch-and-Bound Method for Optimizing the Dwelling Time Pattern and Catheter Positioning in HDR Brachytherapy2013Rapport (Övrigt vetenskapligt)
    Abstract [en]

    High dose-rate (HDR) brachytherapy is one type of treatment for prostate cancer, in which a radioactive source is moved through catheters implanted into the prostate. For each patient, a unique treatment plan is constructed. This plan determines for example the catheter positioning and the dwelling time pattern, that is, where and for how long the source should stop.

    Mathematical optimization methods are frequently used to find high-quality dwelling time patterns. However, choosing the catheter positioning is usually done without any aid of mathematical optimization methods. Researchers have recently suggested some optimization models for catheter positioning, and also heuristics for solving them. However, there are no available methods for finding the optimal solution of these models within a clinically acceptable time frame.

    In this paper we present the foundation for a branch-and-bound method that has been tailored to the catheter positioning problem. Tests show that this tailored branch-and-bound method has some promising features, for example that the dual bound is improved faster than when using a standard branch-and-bound method. But the tests also show that further research is required to develop it into a method that can find the optimal solution fast enough.

    Ladda ner fulltext (pdf)
    A Tailored Branch-and-Bound Method for Optimizing the Dwelling Time Pattern and Catheter Positioning in HDR Brachytherapy
  • 167.
    Holm, Åsa
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Mathematical Optimization of HDR Brachytherapy2013Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
    Abstract [en]

    One out of eight deaths throughout the world is due to cancer. Developing new treatments and improving existing treatments is hence of major importance. In this thesis we have studied how mathematical optimization can be used to improve an existing treatment method: high-dose-rate (HDR) brachytherapy.

    HDR brachytherapy is a radiation modality used to treat tumours of for example the cervix, prostate, breasts, and skin. In HDR brachytherapy catheters are implanted into or close to the tumour volume. A radioactive source is moved through the catheters, and by adjusting where the catheters are placed, called catheter positioning, and how the source is moved through the catheters, called the dwelling time pattern, the dose distribution can be controlled.

    By constructing an individualized catheter positioning and dwelling time pattern, called dose plan, based on each patient's anatomy, it is possible to improve the treatment result. Mathematical optimization has during the last decade been used to aid in creating individualized dose plans. The dominating optimization model for this purpose is a linear penalty model. This model only considers the dwelling time pattern within already implanted catheters, and minimizes a weighted deviation from dose intervals prescribed by a physician.

    In this thesis we show that the distribution of the basic variables in the linear penalty model implies that only dwelling time patterns that have certain characteristics can be optimal. These characteristics cause troublesome inhomogeneities in the plans, and although various measures for mitigating these are already available, it is of fundamental interest to understand their cause.

    We have also shown that the relationship between the objective function of the linear penalty model and the measures commonly used for evaluating the quality of the dose distribution is weak. This implies that even if the model is solved to optimality there is no guarantee that the generated plan is optimal with respect to clinically relevant objectives, or even near-optimal. We have therefore constructed a new model for optimizing the dwelling time pattern. This model approximates the quality measures by the concept conditional value-at-risk, and we show that the relationship between our new model and the quality measures is strong. Furthermore, the new model generates dwelling time patterns that yield high-quality dose distributions.

    Combining optimization of the dwelling time pattern with optimization of the catheter positioning yields a problem for which it is rarely possible to find a proven optimal solution within a reasonable time frame. We have therefore developed a variable neighbourhood search heuristic that outperforms a state-of-the-art optimization software (CPLEX). We have also developed a tailored branch-and-bound algorithm that is better at improving the dual bound than a general branch-and-bound algorithm. This is a step towards the development of a method that can find proven optimal solutions to the combined problem within a reasonable time frame.

    Delarbeten
    1. Impact of Using Linear Optimization Models in Dose Planning for HDR Brachytherapy
    Öppna denna publikation i ny flik eller fönster >>Impact of Using Linear Optimization Models in Dose Planning for HDR Brachytherapy
    2012 (Engelska)Ingår i: Medical physics (Lancaster), ISSN 0094-2405, Vol. 39, nr 2, s. 1021-1028Artikel i tidskrift (Refereegranskat) Published
    Abstract [en]

    Purpose: Dose plans generated with optimization models hitherto used in HDR brachytherapy have shown a tendency to yield longer dwell times than manually optimized plans. Concern has been raised for the corresponding undesired hot spots and various methods to mitigate these have been developed. The hypotheses of this work are a) that one cause for the long dwell times is the use of objective functions comprising simple linear penalties and b) that alternative penalties, being piecewise linear, would lead to reduced length of individual dwell times.

    Methods: The characteristics of the linear penalties and the piecewise linear penalties are analysed mathematically. Experimental comparisons between the two types of penalties are carried out retrospectively for a set of prostate cancer patients.

    Results: While most dose-volume parameters do not differ significantly between the two types of penalties significant changes can be seen in the dwell times. On the average, total dwell times were reduced by 4.2%, with a reduction of maximum dwell times by 30%, using the alternative penalties.

    Conclusion: The use of linear penalties in optimization models for HDR brachytherapy is one cause for undesired longer dwell times appearing in mathematically optimized plans. By introducing alternative penalties significant reduction in dwell times can be achieved for HDR brachytherapy dose plans. Although various constraints as to reduce the long dwell times have been developed our finding is of fundamental interest in showing the shape of the objective function to be one reason for their appearance.

    Ort, förlag, år, upplaga, sidor
    American Association of Physicists in Medicine, 2012
    Nyckelord
    Brachytherapy, Optimization, Treatment planning, Linear programming, Piecewise linear functions
    Nationell ämneskategori
    Matematik
    Identifikatorer
    urn:nbn:se:liu:diva-67786 (URN)10.1118/1.3676179 (DOI)000300215800048 ()
    Tillgänglig från: 2011-04-26 Skapad: 2011-04-26 Senast uppdaterad: 2017-12-11Bibliografiskt granskad
    2. Study of the Relationship Between Dosimetric Indices and Linear Penalties in Dose Distribution Optimization for HDR Prostate Brachytherapy
    Öppna denna publikation i ny flik eller fönster >>Study of the Relationship Between Dosimetric Indices and Linear Penalties in Dose Distribution Optimization for HDR Prostate Brachytherapy
    2013 (Engelska)Manuskript (preprint) (Övrigt vetenskapligt)
    Abstract [en]

    Purpose: Most clinical software for optimizing dwelling time patterns is based on a linear penalty model. The quality of a dose distribution generated by the dwelling time pattern is, however, evaluated through a number of dosimetric indices. The purpose of this article is to investigate the relationship between the linear penalty model and the dosimetric indices.

    Method and Materials: Data sets from three patients, previously treated for prostate cancer with HDR brachytherapy as a boost to external beam therapy, were used for this study, and for each of them 300 random dwelling time patterns were generated. The relationship between the linear penalty model and the dosimetric indices were studied both by the Pearson’s product moment correlation coefficient between the objective function value of the linear penalty model and the values of the dosimetric indices, and by scatter-grams.

    Results: For one of the three patients we found a clear connection between the linear penalty model and the values of the dosimetric indices, but not for the other two. For the two patients without a clear connection there where some dosimetric indices that actually improved with deteriorating objective function value.

    Conclusion: The dwelling time pattern found by using the linear penalty model does not correspond to the optimal dose distribution with respect to dosimetric indices.

    Nyckelord
    Optimization, Linear penalty models, Correlation, HDR Brachytherapy
    Nationell ämneskategori
    Medicin och hälsovetenskap
    Identifikatorer
    urn:nbn:se:liu:diva-100388 (URN)
    Tillgänglig från: 2013-11-05 Skapad: 2013-11-05 Senast uppdaterad: 2013-11-05Bibliografiskt granskad
    3. A linear programming model for optimizing HDR brachytherapy dose distributions with respect to mean dose in the DVH-tail
    Öppna denna publikation i ny flik eller fönster >>A linear programming model for optimizing HDR brachytherapy dose distributions with respect to mean dose in the DVH-tail
    2013 (Engelska)Ingår i: Medical physics (Lancaster), ISSN 0094-2405, Vol. 40, nr 8Artikel i tidskrift (Refereegranskat) Published
    Abstract [en]

    Purpose: Recent research has shown that the optimization model hitherto used in high-dose-rate (HDR) brachytherapy corresponds weakly to the dosimetric indices used to evaluate the quality of a dose distribution. Although alternative models that explicitly include such dosimetric indices have been presented, the inclusion of the dosimetric indices explicitly yields intractable models. The purpose of this paper is to develop a model for optimizing dosimetric indices that is easier to solve than those proposed earlier. less thanbrgreater than less thanbrgreater thanMethods: In this paper, the authors present an alternative approach for optimizing dose distributions for HDR brachytherapy where dosimetric indices are taken into account through surrogates based on the conditional value-at-risk concept. This yields a linear optimization model that is easy to solve, and has the advantage that the constraints are easy to interpret and modify to obtain satisfactory dose distributions. less thanbrgreater than less thanbrgreater thanResults: The authors show by experimental comparisons, carried out retrospectively for a set of prostate cancer patients, that their proposed model corresponds well with constraining dosimetric indices. All modifications of the parameters in the authors model yield the expected result. The dose distributions generated are also comparable to those generated by the standard model with respect to the dosimetric indices that are used for evaluating quality. less thanbrgreater than less thanbrgreater thanConclusions: The authors new model is a viable surrogate to optimizing dosimetric indices and quickly and easily yields high quality dose distributions.

    Ort, förlag, år, upplaga, sidor
    American Association of Physicists in Medicine, 2013
    Nyckelord
    brachytherapy, optimization, treatment planning, dosimetric indices, conditional value-at-risk
    Nationell ämneskategori
    Medicin och hälsovetenskap
    Identifikatorer
    urn:nbn:se:liu:diva-97239 (URN)10.1118/1.4812677 (DOI)000322735900010 ()
    Anmärkning

    Funding Agencies|Swedish Cancer Society (Cancerfonden)|100512|

    Tillgänglig från: 2013-09-05 Skapad: 2013-09-05 Senast uppdaterad: 2017-12-06
    4. Heuristics for Integrated Optimization of Catheter Positioning and Dwell Time Distribution in Prostate HDR Brachytherapy
    Öppna denna publikation i ny flik eller fönster >>Heuristics for Integrated Optimization of Catheter Positioning and Dwell Time Distribution in Prostate HDR Brachytherapy
    2016 (Engelska)Ingår i: Annals of Operations Research, ISSN 0254-5330, E-ISSN 1572-9338, Vol. 236, nr 2, s. 319-339Artikel i tidskrift (Refereegranskat) Published
    Abstract [en]

    High dose-rate (HDR) brachytherapy is a kind of radiotherapy used to treat, among others, prostate cancer. When applied to prostate cancer a radioactive source is moved through catheters implanted into the prostate. For each patient a treatment plan is constructed that decide for example catheter placement and dwell time distribution, that is where to stop the radioactive source and for how long.

    Mathematical optimization methods has been used to find quality plans with respect to dwell time distribution, however few optimization approaches regarding catheter placement have been studied. In this article we present an integrated optimization model that optimize catheter placement and dwell time distribution simultaneously. Our results show that integrating the two decisions yields greatly improved plans, from 15% to 94% improvement.

    Since the presented model is computationally demanding to solve we also present three heuristics: tabu search, variable neighbourhood search and genetic algorithm. Of these variable neighbourhood search is clearly the best, outperforming a state-of-the-art optimization software (CPLEX) and the two other heuristics.

    Ort, förlag, år, upplaga, sidor
    Springer, 2016
    Nyckelord
    Brachytherapy, Dose planning, Catheter positioning, Mixed integer programming, Metaheuristics
    Nationell ämneskategori
    Matematik
    Identifikatorer
    urn:nbn:se:liu:diva-67788 (URN)10.1007/s10479-013-1448-7 (DOI)000368946400003 ()
    Tillgänglig från: 2011-04-26 Skapad: 2011-04-26 Senast uppdaterad: 2019-01-28Bibliografiskt granskad
    5. A Tailored Branch-and-Bound Method for Optimizing the Dwelling Time Pattern and Catheter Positioning in HDR Brachytherapy
    Öppna denna publikation i ny flik eller fönster >>A Tailored Branch-and-Bound Method for Optimizing the Dwelling Time Pattern and Catheter Positioning in HDR Brachytherapy
    2013 (Engelska)Rapport (Övrigt vetenskapligt)
    Abstract [en]

    High dose-rate (HDR) brachytherapy is one type of treatment for prostate cancer, in which a radioactive source is moved through catheters implanted into the prostate. For each patient, a unique treatment plan is constructed. This plan determines for example the catheter positioning and the dwelling time pattern, that is, where and for how long the source should stop.

    Mathematical optimization methods are frequently used to find high-quality dwelling time patterns. However, choosing the catheter positioning is usually done without any aid of mathematical optimization methods. Researchers have recently suggested some optimization models for catheter positioning, and also heuristics for solving them. However, there are no available methods for finding the optimal solution of these models within a clinically acceptable time frame.

    In this paper we present the foundation for a branch-and-bound method that has been tailored to the catheter positioning problem. Tests show that this tailored branch-and-bound method has some promising features, for example that the dual bound is improved faster than when using a standard branch-and-bound method. But the tests also show that further research is required to develop it into a method that can find the optimal solution fast enough.

    Ort, förlag, år, upplaga, sidor
    Linköping: Linköping University Electronic Press, 2013. s. 10
    Serie
    LiTH-MAT-R, ISSN 0348-2960 ; 2013:12
    Nyckelord
    Branch-and-Bound, Branching rules, Brachytherapy, Dose planning, Catheter positioning
    Nationell ämneskategori
    Annan matematik
    Identifikatorer
    urn:nbn:se:liu:diva-99784 (URN)LiTH-MAT-R– 2013/12–SE (ISRN)
    Tillgänglig från: 2013-10-21 Skapad: 2013-10-21 Senast uppdaterad: 2013-11-06Bibliografiskt granskad
    Ladda ner fulltext (pdf)
    Mathematical Optimization of HDR Brachytherapy
    Ladda ner (pdf)
    omslag
  • 168.
    Holm, Åsa
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Carlsson Tedgren, Åsa
    Linköpings universitet, Institutionen för medicin och hälsa, Avdelningen för radiologiska vetenskaper. Linköpings universitet, Medicinska fakulteten. Region Östergötland, Centrum för kirurgi, ortopedi och cancervård, Radiofysikavdelningen US.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Heuristics for Integrated Optimization of Catheter Positioning and Dwell Time Distribution in Prostate HDR Brachytherapy2016Ingår i: Annals of Operations Research, ISSN 0254-5330, E-ISSN 1572-9338, Vol. 236, nr 2, s. 319-339Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    High dose-rate (HDR) brachytherapy is a kind of radiotherapy used to treat, among others, prostate cancer. When applied to prostate cancer a radioactive source is moved through catheters implanted into the prostate. For each patient a treatment plan is constructed that decide for example catheter placement and dwell time distribution, that is where to stop the radioactive source and for how long.

    Mathematical optimization methods has been used to find quality plans with respect to dwell time distribution, however few optimization approaches regarding catheter placement have been studied. In this article we present an integrated optimization model that optimize catheter placement and dwell time distribution simultaneously. Our results show that integrating the two decisions yields greatly improved plans, from 15% to 94% improvement.

    Since the presented model is computationally demanding to solve we also present three heuristics: tabu search, variable neighbourhood search and genetic algorithm. Of these variable neighbourhood search is clearly the best, outperforming a state-of-the-art optimization software (CPLEX) and the two other heuristics.

  • 169.
    Holm, Åsa
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Carlsson Tedgren, Åsa
    Linköpings universitet, Institutionen för medicin och hälsa, Avdelningen för radiologiska vetenskaper. Linköpings universitet, Hälsouniversitetet. Östergötlands Läns Landsting, Centrum för kirurgi, ortopedi och cancervård, Radiofysikavdelningen US.
    A linear programming model for optimizing HDR brachytherapy dose distributions with respect to mean dose in the DVH-tail2013Ingår i: Medical physics (Lancaster), ISSN 0094-2405, Vol. 40, nr 8Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Purpose: Recent research has shown that the optimization model hitherto used in high-dose-rate (HDR) brachytherapy corresponds weakly to the dosimetric indices used to evaluate the quality of a dose distribution. Although alternative models that explicitly include such dosimetric indices have been presented, the inclusion of the dosimetric indices explicitly yields intractable models. The purpose of this paper is to develop a model for optimizing dosimetric indices that is easier to solve than those proposed earlier. less thanbrgreater than less thanbrgreater thanMethods: In this paper, the authors present an alternative approach for optimizing dose distributions for HDR brachytherapy where dosimetric indices are taken into account through surrogates based on the conditional value-at-risk concept. This yields a linear optimization model that is easy to solve, and has the advantage that the constraints are easy to interpret and modify to obtain satisfactory dose distributions. less thanbrgreater than less thanbrgreater thanResults: The authors show by experimental comparisons, carried out retrospectively for a set of prostate cancer patients, that their proposed model corresponds well with constraining dosimetric indices. All modifications of the parameters in the authors model yield the expected result. The dose distributions generated are also comparable to those generated by the standard model with respect to the dosimetric indices that are used for evaluating quality. less thanbrgreater than less thanbrgreater thanConclusions: The authors new model is a viable surrogate to optimizing dosimetric indices and quickly and easily yields high quality dose distributions.

  • 170.
    Holm, Åsa
    et al.
    Linköpings universitet, Matematiska institutionen. Linköpings universitet, Tekniska högskolan.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Carlsson Tedgren, Åsa
    Linköpings universitet, Institutionen för medicin och hälsa, Medicinsk radiofysik. Linköpings universitet, Hälsouniversitetet.
    Impact of Using Linear Optimization Models in Dose Planning for HDR Brachytherapy2012Ingår i: Medical physics (Lancaster), ISSN 0094-2405, Vol. 39, nr 2, s. 1021-1028Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Purpose: Dose plans generated with optimization models hitherto used in HDR brachytherapy have shown a tendency to yield longer dwell times than manually optimized plans. Concern has been raised for the corresponding undesired hot spots and various methods to mitigate these have been developed. The hypotheses of this work are a) that one cause for the long dwell times is the use of objective functions comprising simple linear penalties and b) that alternative penalties, being piecewise linear, would lead to reduced length of individual dwell times.

    Methods: The characteristics of the linear penalties and the piecewise linear penalties are analysed mathematically. Experimental comparisons between the two types of penalties are carried out retrospectively for a set of prostate cancer patients.

    Results: While most dose-volume parameters do not differ significantly between the two types of penalties significant changes can be seen in the dwell times. On the average, total dwell times were reduced by 4.2%, with a reduction of maximum dwell times by 30%, using the alternative penalties.

    Conclusion: The use of linear penalties in optimization models for HDR brachytherapy is one cause for undesired longer dwell times appearing in mathematically optimized plans. By introducing alternative penalties significant reduction in dwell times can be achieved for HDR brachytherapy dose plans. Although various constraints as to reduce the long dwell times have been developed our finding is of fundamental interest in showing the shape of the objective function to be one reason for their appearance.

    Ladda ner fulltext (pdf)
    fulltext
  • 171.
    Holm, Åsa
    et al.
    Linköpings universitet, Matematiska institutionen. Linköpings universitet, Tekniska högskolan.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Carlsson Tedgren, Åsa
    Linköpings universitet, Institutionen för medicin och hälsa, Medicinsk radiofysik. Linköpings universitet, Hälsouniversitetet. Östergötlands Läns Landsting, Centrum för kirurgi, ortopedi och cancervård, Radiofysikavdelningen US.
    On the Correlation Between DVH Parameters and Linear Penalties in Optimization of HDR Prostate Brachytherapy Dose PlansManuskript (preprint) (Övrigt vetenskapligt)
    Abstract [en]

    When optimizing dwell times for HDR brachytherapy it is common to use a model comprising an objective of linear penalties. However whether a planis considered good or not depends on other measures such as DVH-based parameters. We show through experiments that the correlation between the value of the objective function and the values of DVH-based parameters, such as D90, is weak in some cases. It seems that the objective function can only classify solutions into better or worse, however it can not distinguish the best with respect to DVH-based parameters.

  • 172.
    Holm, Åsa
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Carlsson Tedgren, Åsa
    Linköpings universitet, Institutionen för medicin och hälsa, Avdelningen för radiologiska vetenskaper. Linköpings universitet, Hälsouniversitetet. Östergötlands Läns Landsting, Centrum för kirurgi, ortopedi och cancervård, Radiofysikavdelningen US.
    Study of the Relationship Between Dosimetric Indices and Linear Penalties in Dose Distribution Optimization for HDR Prostate Brachytherapy2013Manuskript (preprint) (Övrigt vetenskapligt)
    Abstract [en]

    Purpose: Most clinical software for optimizing dwelling time patterns is based on a linear penalty model. The quality of a dose distribution generated by the dwelling time pattern is, however, evaluated through a number of dosimetric indices. The purpose of this article is to investigate the relationship between the linear penalty model and the dosimetric indices.

    Method and Materials: Data sets from three patients, previously treated for prostate cancer with HDR brachytherapy as a boost to external beam therapy, were used for this study, and for each of them 300 random dwelling time patterns were generated. The relationship between the linear penalty model and the dosimetric indices were studied both by the Pearson’s product moment correlation coefficient between the objective function value of the linear penalty model and the values of the dosimetric indices, and by scatter-grams.

    Results: For one of the three patients we found a clear connection between the linear penalty model and the values of the dosimetric indices, but not for the other two. For the two patients without a clear connection there where some dosimetric indices that actually improved with deteriorating objective function value.

    Conclusion: The dwelling time pattern found by using the linear penalty model does not correspond to the optimal dose distribution with respect to dosimetric indices.

  • 173.
    Holmberg, Kaj
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    A new method for optimal proportional representation2019Rapport (Övrigt vetenskapligt)
    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.

    Ladda ner fulltext (pdf)
    A new method for optimal proportional representation
    Ladda ner (png)
    presentationsbild
  • 174.
    Holmberg, Kaj
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Computational Results for Map Matching by Optimization2015Rapport (Övrigt vetenskapligt)
    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.

    Ladda ner fulltext (pdf)
    Computational Results for Map Matching by Optimization
  • 175.
    Holmberg, Kaj
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Formation of student groups with the help of optimisation2019Ingår i: Journal of the Operational Research Society, ISSN 0160-5682, E-ISSN 1476-9360, Vol. 70, nr 9, s. 1538-1553Artikel i tidskrift (Refereegranskat)
    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.

    Ladda ner fulltext (pdf)
    fulltext
  • 176.
    Holmberg, Kaj
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Formation of Student Groups with the Help of Optimization2014Rapport (Övrigt vetenskapligt)
    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.

    Ladda ner fulltext (pdf)
    Formation of Student Groups with the Help of Optimization
  • 177.
    Holmberg, Kaj
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Graph Optimization Approaches for Minimal Rerouting in Symmetric Three Stage Clos Networks2007Rapport (Övrigt vetenskapligt)
    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.

  • 178.
    Holmberg, Kaj
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Graph optimization approaches for minimal rerouting in symmetric three stage Clos networks2009Ingår i: Journal of Mathematical Modelling and Algorithms, ISSN 1570-1166, Vol. 8, nr 1, s. 81-100Artikel i tidskrift (Refereegranskat)
    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.

    Ladda ner fulltext (pdf)
    FULLTEXT01
  • 179.
    Holmberg, Kaj
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Heuristics for the rural postman problem2010Ingår i: Computers & Operations Research, ISSN 0305-0548, E-ISSN 1873-765X, Vol. 37, nr 5, s. 981-990Artikel i tidskrift (Refereegranskat)
    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.

  • 180.
    Holmberg, Kaj
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Heuristics for the Rural Postman Problem with Application to Snow Removal for Secondary Roads2008Rapport (Övrigt vetenskapligt)
  • 181.
    Holmberg, Kaj
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Heuristics for the weighted k-Chinese/rural postman problem with a hint of fixed costs with applications to urban snow removal2015Rapport (Övrigt vetenskapligt)
    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.

    Ladda ner fulltext (pdf)
    Heuristics for the weighted k-Chinese/rural postman problem with a hint of fixed costs with applications to urban snow removal
  • 182.
    Holmberg, Kaj
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Kombinatorisk optimering med linjärprogrammering2003Övrigt (Övrig (populärvetenskap, debatt, mm))
  • 183.
    Holmberg, Kaj
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Map Matching by Optimization2015Rapport (Övrigt vetenskapligt)
    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.

    Ladda ner fulltext (pdf)
    Map Matching by Optimization
  • 184.
    Holmberg, Kaj
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Mean Value Cross Decomposition Based Branch-and-Bound for Mixed Integer Programming Problems2004Rapport (Övrigt vetenskapligt)
  • 185.
    Holmberg, Kaj
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Mean Value Cross Decomposition for Nonlinear Convex Problems2003Ingår i: 18th International Symposium on Mathematical Programming,2003, 2003Konferensbidrag (Övrigt vetenskapligt)
  • 186.
    Holmberg, Kaj
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    On Using OpenStreetMap and GPS for Optimization2015Rapport (Övrigt vetenskapligt)
    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.

    Ladda ner fulltext (pdf)
    On Using OpenStreetMap and GPS for Optimization
  • 187.
    Holmberg, Kaj
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Optimal proportional representation2020Rapport (Övrigt vetenskapligt)
    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.

    Ladda ner fulltext (pdf)
    fulltext
  • 188.
    Holmberg, Kaj
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Optimering2010Bok (Refereegranskat)
    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.

  • 189.
    Holmberg, Kaj
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Optimization of OSPF Routing in IP Networks2010Ingår i: Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless and Ad Hoc Networks / [ed] A. Koster and X. Munoz, Springer Berlin/Heidelberg, 2010Kapitel i bok, del av antologi (Refereegranskat)
    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.

  • 190.
    Holmberg, Kaj
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Optmization Models for Routing in Switching Networks of Clos Type with many Stages2008Ingår i: Advanced modeling and optimization, ISSN 1841-4311, Vol. 10, nr 1Artikel i tidskrift (Refereegranskat)
  • 191.
    Holmberg, Kaj
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Prepared Test Instances Extracted from OpenStreetMapData Using Different Network Reductions2018Rapport (Övrigt vetenskapligt)
    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.

    Ladda ner fulltext (pdf)
    fulltext
  • 192.
    Holmberg, Kaj
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Projecting points on the convex hull2016Rapport (Övrigt vetenskapligt)
    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.

    Ladda ner fulltext (pdf)
    Projecting points on the convex hull
  • 193.
    Holmberg, Kaj
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    The (Over) Zealous Snow Remover Problem2016Rapport (Övrigt vetenskapligt)
    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.

    Ladda ner fulltext (pdf)
    The (Over) Zealous Snow Remover Problem
  • 194.
    Holmberg, Kaj
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    The (Over)zealous Snow Remover Problem2019Ingår i: Transportation Science, ISSN 0041-1655, E-ISSN 1526-5447, Vol. 53, nr 3, s. 867-881Artikel i tidskrift (Refereegranskat)
    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 and a reordering procedure. The method has been implemented and tested on real life examples, and the solution times are short enough to allow online usage. We compare the solutions to lower bounds obtained by solving a mixed integer programming model. We study 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.

  • 195.
    Holmberg, Kaj
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Urban Snow Removal:: Modeling and Relaxations2014Rapport (Övrigt vetenskapligt)
    Abstract [en]

    Snow removal is an important problem in certain countries. It is also difficult, especially in urban areas. The main questions are which vehicle shall do what task, when shall the tasks be done and how shall the vehicles travel. In this paper we describe the problem in detail and formulate a detailed mathematical time-indexed model that contains all practical  complications we have encountered, for example different vehicles and switching times  between tasks. We investigate the solvability of the model, and present a number of alternate formulations, relaxations and simplifications, yielding several different models of different sizes and different strength. We can either solve very small problems exactly or larger problems more approximately. Our main goal is to find good lower bounds on the optimal objective function value in a limited time, and we present extensive computational tests comparing the obtained bounds and the times needed for the different models. As a result we find some rather efficient models, in the sense that they yield rather good lower bounds in rather short time. With these models, we find lower bounds for several real life instances in the form of small local cities.

    Ladda ner fulltext (pdf)
    Urban Snow Removal: Modeling and Relaxations
  • 196.
    Holmberg, Kaj
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Broström, Peter
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Design of IP/OSPF Networks Using a Lagrangean Heuristic on an In-graph Based Model2005Ingår i: Proceedings of the International Network Optimization Conference, INOC 2005 / [ed] L. Gouveia and C. Mourao, Lisbon, Portugal: University of Lisbon , 2005, s. 702-Konferensbidrag (Refereegranskat)
    Abstract [en]

    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.

  • 197.
    Holmberg, Kaj
    et al.
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Broström, Peter
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Determining the Non-Existence of a Compatible OSPF Metric2005Ingår i: International Network Optimization Conference, INOC 2005,2005, Lisbon, Portugal: University of Lisbon, , 2005, s. 106-Konferensbidrag (Refereegranskat)
  • 198.
    Holmberg, Kaj
    et al.
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Broström, Peter
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Stronger Necessary Conditions for the Existence of a Compatible OSPF Metric2004Ingår i: Nordic MPS 04,2004, 2004Konferensbidrag (Övrigt vetenskapligt)
  • 199.
    Holmberg, Kaj
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Call, Mikael
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Complexity of Inverse Shortest Path Routing2011Ingår i: Network Optimization: 5th International Conference, INOC 2011 / [ed] J. Pahl, T. Reiners, and S. Voß, Springer Berlin/Heidelberg, 2011, s. 339-353Kapitel i bok, del av antologi (Refereegranskat)
    Abstract [en]

    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.

  • 200.
    Holmberg, Kaj
    et al.
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
    Joborn, Martin
    Carmen .
    Melin, Kennet
    Lagrangian Based Heuristics for the Multicommodity Network Flow Problem with Fixed Costs On Paths2004Rapport (Övrigt vetenskapligt)
1234567 151 - 200 av 367
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf