The coolest path problem

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. Continuous and discrete optimization are at present two distinct areas of math- ematics. From time to time, discrete optimizers stumble over a problem which has some intrinsic nonlinear continuous structure, sometimes modeled using partial dif- ferential equations. Then they most likely would try to get rid of these continuous parts, such that a pure combinatorial problem remains. Similarly, if a person with a background in continuous optimization gets involved with a problem that involves discrete decisions, he or she would most likely try to relax the discontinuities to some continuous constraints, in order to apply some well-understood methods of the field. For both of them it is true that if one only owns a hammer then every problem must be a nail. However it is also true that if one always stays within its own cosy corner of the world, nothing new can emerge from that. Our research is motivated by the fact that both worlds can inspire the respective other by sharing ideas and methods. So to start the discussion at some point we combine two problems into a new one that was not studied before (to the best of our knowledge). From the discrete world we consider the shortest path problem on a directed graph. The contribution from the continuous world is the heat conduction problem. Both problems are combined into a new optimization problem, which we suggest to coin the coolest path problem.