American Institute of Mathematical Sciences

Advanced
March  2010, 5(1): 143-162. doi: 10.3934/nhm.2010.5.143

The coolest path problem

Martin Frank 1, , Armin Fügenschuh 2, , Michael Herty 3, and  Lars Schewe 4,

1. 

Rheinisch-Westfälische Technische Hochschule Aachen, Department of Mathematics & Center for Computational Engineering Science, Schinkelstraße 2, 52056 Aachen, Germany
2. 

Konrad-Zuse-Zentrum für Informationstechnik (ZIB), Department of Optimization, Takustraße 7, 14195 Berlin, Germany
3. 

Rheinisch-Westfälische Technische Hochschule Aachen, Department of Mathematics, Templergraben 55, 52056 Aachen, Germany
4. 

Technische Universität Darmstadt, Department of Mathematics, Dolivostraße 15, 64293 Darmstadt, Germany

Received  March 2009 Revised  December 2009 Published  February 2010

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.
Keywords: Shortest Path., Integer Programming, Heat Equation.
Mathematics Subject Classification: Primary: 35K05, 90C10; Secondary: 90B1.
Citation: Martin Frank, Armin Fügenschuh, Michael Herty, Lars Schewe. The coolest path problem. Networks & Heterogeneous Media, 2010, 5 (1) : 143-162. doi: 10.3934/nhm.2010.5.143
[1]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557
[2]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[3]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353
[4]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027
[5]

Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213
[6]

Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67
[7]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[8]

Mohamed A. Tawhid, Ahmed F. Ali. A simplex grey wolf optimizer for solving integer programming and minimax problems. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 301-323. doi: 10.3934/naco.2017020
[9]

Liming Sun, Li-Zhi Liao. An interior point continuous path-following trajectory for linear programming. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1517-1534. doi: 10.3934/jimo.2018107
[10]

Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete & Continuous Dynamical Systems, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653
[11]

Mahmoud Ameri, Armin Jarrahi. An executive model for network-level pavement maintenance and rehabilitation planning based on linear integer programming. Journal of Industrial & Management Optimization, 2020, 16 (2) : 795-811. doi: 10.3934/jimo.2018179
[12]

René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363
[13]

Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115
[14]

Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009
[15]

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 & Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783
[16]

Mahdi Roozbeh, Saman Babaie–Kafaki, Zohre Aminifard. Two penalized mixed–integer nonlinear programming approaches to tackle multicollinearity and outliers effects in linear regression models. Journal of Industrial & Management Optimization, 2021, 17 (6) : 3475-3491. doi: 10.3934/jimo.2020128
[17]

Hassan Emamirad, Arnaud Rougirel. Feynman path formula for the time fractional Schrödinger equation. Discrete & Continuous Dynamical Systems - S, 2020, 13 (12) : 3391-3400. doi: 10.3934/dcdss.2020246
[18]

Fanwen Meng, Kiok Liang Teow, Kelvin Wee Sheng Teo, Chee Kheong Ooi, Seow Yian Tay. Predicting 72-hour reattendance in emergency departments using discriminant analysis via mixed integer programming with electronic medical records. Journal of Industrial & Management Optimization, 2019, 15 (2) : 947-962. doi: 10.3934/jimo.2018079
[19]

Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial & Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431
[20]

C. Brändle, E. Chasseigne, Raúl Ferreira. Unbounded solutions of the nonlocal heat equation. Communications on Pure & Applied Analysis, 2011, 10 (6) : 1663-1686. doi: 10.3934/cpaa.2011.10.1663

2020 Impact Factor: 1.213

Tools

Metrics

  • PDF downloads (151)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences