Search Advanced

Networks and Heterogeneous Media

2010, Volume 5, Issue 1: 143-162. doi: 10.3934/nhm.2010.5.143
Previous Article Next Article

The coolest path problem

  • 1.
    Rheinisch-Westfälische Technische Hochschule Aachen, Department of Mathematics & Center for Computational Engineering Science, Schinkelstraße 2, 52056 Aachen
  • 2.
    Konrad-Zuse-Zentrum für Informationstechnik (ZIB), Department of Optimization, Takustraße 7, 14195 Berlin
  • 3.
    Rheinisch-Westfälische Technische Hochschule Aachen, Department of Mathematics, Templergraben 55, 52056 Aachen
  • 4.
    Technische Universität Darmstadt, Department of Mathematics, Dolivostraße 15, 64293 Darmstadt
  • Received: 01 March 2009 Revised: 01 December 2009

  • Primary: 35K05, 90C10; Secondary: 90B10.

  • We introduce the coolest path problem, which is a mixture of two well-known problems from distinct mathematical fields. One of them is the shortest path problem from combinatorial optimization. The other is the heat conduction problem from the field of partial differential equations. Together, they make up a control problem, where some geometrical object traverses a digraph in an optimal way, with constraints on intermediate or the final state. We discuss some properties of the problem and present numerical solution techniques. We demonstrate that the problem can be formulated as a linear mixed-integer program. Numerical solutions can thus be achieved within one hour for instances with up to 70 nodes in the graph.

    Citation: Martin Frank, Armin Fügenschuh, Michael Herty, Lars Schewe. The coolest path problem[J]. Networks and Heterogeneous Media, 2010, 5(1): 143-162. doi: 10.3934/nhm.2010.5.143

    Related Papers:

    [1] Martin Frank, Armin Fügenschuh, Michael Herty, Lars Schewe . The coolest path problem. Networks and Heterogeneous Media, 2010, 5(1): 143-162. doi: 10.3934/nhm.2010.5.143
    [2] Simone Göttlich, Camill Harter . A weakly coupled model of differential equations for thief tracking. Networks and Heterogeneous Media, 2016, 11(3): 447-469. doi: 10.3934/nhm.2016004
    [3] Maya Briani, Emiliano Cristiani . An easy-to-use algorithm for simulating traffic flow on networks: Theoretical study. Networks and Heterogeneous Media, 2014, 9(3): 519-552. doi: 10.3934/nhm.2014.9.519
    [4] Samitha Samaranayake, Axel Parmentier, Ethan Xuan, Alexandre Bayen . A mathematical framework for delay analysis in single source networks. Networks and Heterogeneous Media, 2017, 12(1): 113-145. doi: 10.3934/nhm.2017005
    [5] Qinglan Xia, Shaofeng Xu . On the ramified optimal allocation problem. Networks and Heterogeneous Media, 2013, 8(2): 591-624. doi: 10.3934/nhm.2013.8.591
    [6] Massimiliano Caramia, Giovanni Storchi . Evaluating the effects of parking price and location in multi-modal transportation networks. Networks and Heterogeneous Media, 2006, 1(3): 441-465. doi: 10.3934/nhm.2006.1.441
    [7] Santiago Moral, Victor Chapela, Regino Criado, Ángel Pérez, Miguel Romance . Efficient algorithms for estimating loss of information in a complex network: Applications to intentional risk analysis. Networks and Heterogeneous Media, 2015, 10(1): 195-208. doi: 10.3934/nhm.2015.10.195
    [8] Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel . Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks and Heterogeneous Media, 2013, 8(3): 783-802. doi: 10.3934/nhm.2013.8.783
    [9] Delio Mugnolo . Gaussian estimates for a heat equation on a network. Networks and Heterogeneous Media, 2007, 2(1): 55-79. doi: 10.3934/nhm.2007.2.55
    [10] Serge Nicaise, Cristina Pignotti . Asymptotic analysis of a simple model of fluid-structure interaction. Networks and Heterogeneous Media, 2008, 3(4): 787-813. doi: 10.3934/nhm.2008.3.787
  • We introduce the coolest path problem, which is a mixture of two well-known problems from distinct mathematical fields. One of them is the shortest path problem from combinatorial optimization. The other is the heat conduction problem from the field of partial differential equations. Together, they make up a control problem, where some geometrical object traverses a digraph in an optimal way, with constraints on intermediate or the final state. We discuss some properties of the problem and present numerical solution techniques. We demonstrate that the problem can be formulated as a linear mixed-integer program. Numerical solutions can thus be achieved within one hour for instances with up to 70 nodes in the graph.


  • This article has been cited by:

    1. Armin Fügenschuh, Markus Bambach, Johannes Buhl, 2019, Chapter 41, 978-3-030-18499-5, 331, 10.1007/978-3-030-18500-8_41
    2. Fabian Gnegel, Michael Dudzinski, Armin Fügenschuh, Markus Stiemer, 2018, Chapter 64, 978-3-319-89919-0, 483, 10.1007/978-3-319-89920-6_64
    3. Markus Bambach, Armin Fügenschuh, Johannes Buhl, Felix Jensch, Johannes Schmidt, Mathematical Modeling and Optimization for Powder-Based Additive Manufacturing, 2020, 47, 23519789, 1159, 10.1016/j.promfg.2020.04.158
    4. Donatella Granata, Luca Lorenzi, An Evaluation of Propagation of the HIV-Infected Cells via Optimization Problem, 2022, 10, 2227-7390, 2021, 10.3390/math10122021
    5. Fabian Gnegel, Armin Fügenschuh, Michael Hagel, Sven Leyffer, Marcus Stiemer, A solution framework for linear PDE-constrained mixed-integer problems, 2021, 188, 0025-5610, 695, 10.1007/s10107-021-01626-1
    6. Jesse Beisegel, Johannes Buhl, Rameez Israr, Johannes Schmidt, Markus Bambach, Armin Fügenschuh, 2023, Chapter 5, 978-981-99-0775-5, 121, 10.1007/978-981-99-0776-2_5
  • Reader Comments
  • © 2010 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
Networks and Heterogeneous Media
1.3 1.9

Metrics

Article views(4358) PDF downloads(245) Cited by(6)

Preview PDF
Download XML
Export Citation
Article outline
Abstract

Other Articles By Authors

Related pages

Tools

Copyright © AIMS Press

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog