Search algorithms for combinatorial optimization: a guided tour
Search has been used for a long time and is present in multiple tools, including constraint programming, mixed integer programming, AI planning, branch-and-bounds of all sorts, and even shortest path algorithms.
While each tool has its own way of conceptualizing search, they also share many similar components. The goal of this lecture is to identify these similar components, and present how they can be combined with each other.
We will start with some simple examples (shortest path algorithms), then move on to some combinatorial optimization problems (a vehicle routing problem, a scheduling problem, and a 2D rectangle packing problem). For each of them, we will combine several search components and obtain state-of-the-art algorithms, showcasing how search can be used effectively.