The coolest path problem

Martin Frank; Armin Fügenschuh; Michael Herty; Lars Schewe; Martin Frank; Armin Fügenschuh; Michael Herty; Lars Schewe

doi:10.3934/nhm.2010.5.143

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.
- Heat Equation,
- Integer Programming,
- Shortest Path
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:
Abstract

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.
Reader Comments

Your name:*

Email:*
© 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)