Tours with Turn Costs
The Traveling Salesman Problem is one of the most important and well researched problems in combinatorial optimization. It tries to find a tours that visits all points/configurations/etc. while minimizing the overall cost of the transitions. However, in practice the transition cost is often more complicated than modelled in the classical problem formulation: The cost does not only depend on the current state but also on the previous state. You can easily mow a straight line with a lawnmower but doing a zigzag pattern will cost you a tremendous effort.
The following video gives a good introduction:
- Algorithmic methods for complex dynamic sweeping problems (Master Thesis)
- Covering Tours with Turn Cost: Variants, Approximation and Practical Solution
- Further to come…
Hardness, Approximation, Integer Programming, Heuristics, Algorithm Engineering
Boundary minimal non-simple polygons
Consider a set of points in the plane. If you find a tour of minimum length (Traveling Salesman Problem), you obtain a simple polygon with minimal boundary since any line intersection could be replaced by two shorter non-intersecting lines. Now consider the problem of not calculating a simple polygon with minimum boundary but any polygon with minimum boundary on this set of points. Subtours (holes) are now allowed but only on the first level, there cannot be holes in holes. Finding a set of subtours of minimum length can efficiently be solved but limiting it to non-recursive holes makes the problem much more complicated again.
See our paper Computing Nonsimple Polygons of Minimum Perimeter.
My part: Integer programming.