Least Cost Branch and Bound with Scala

By Michal Lacko

In this article I would like to introduce you to an algorithm I learned some time ago. While it blew my mind I used it only maybe twice in my life. Still learning it felt like gaining a super power. So if you by any chance know and enjoy algorithms like mini-max or A* you may also enjoy this one (if you don’t know these algorithms it's fine). 

I will use my favorite and best language in the world for this, which is Scala. Still the language won't matter too much.

Alright, so maybe you know the standard hard problem of the traveling salesman who needs to visit any city but also only once. Typically every city is connected by some road of some distance. The goal is to find the shortest path. The catch is it's a really hard problem, some say it’s an NP-hard problem. This means there is probably no algorithm which could find the shortest path in some polynomial time.

Let's start with some example, we define the cities and distances with some table.

Or graph.

So with 4 cities it's a simple problem we could try any path and find the shortest path eventually, sadly we technically do need to check every possible path (or do we ?!).

To be fair there is a nice greedy solution which solves this problem in O(n log n) time but the result may not be the shortest path. The greedy solution basically sorts all edges/roads and takes the shortest roads which connect cities which are not yet connected.

Now let's actually start with the main algorithm Least cost, branch and bound. First we draw some solution tree.

I draw this in excalidraw.com (and the graph is obviously unfinished), as you can see we start with no solution and by adding cities (by going some path down in the tree) we eventually end up with some solution.

This also demonstrates why (if we need to check every path) it is indeed a hard problem. With 4 cities there are 4x3x2x1 solutions so 4! which is 24, by adding one more city it becomes 5! so 120 and so one. Now what if you have a lot more cities ?! Also note with 4 cities and 24 solutions to the problem there are 4+12+24+24 edges in the graph.

The point of the LCBB algorithm is that maybe you don't need to check every path.

Imagine you are halfway through with finding the best solution and you already found some good solution (or even a solution with a greedy algorithm) and now you are checking some random path which added a city with a long distance. You know you have a solution which is relatively short and which is shorter than the current unfinished path. Does it make sense to continue in the current path… no. Obviously you cut off some computation but it's unclear how much and what are the chances for a “cut”.

A cut can be relatively big if it happened early (high) in the tree and make a big difference since it's not just one path but all paths which started there!

Now what is the time complexity? Well it’s still O(n!) because there are no guarantees.

Think i promised some scala code so lets define some structures for starters

final case class City(name: String)


final case class CityMap(map: Map[Set[City], Int]):
 def distance(c1: City, c2: City): Int =
   map(Set(c1, c2))


// note not a set, order is important
final case class Path(cities: Seq[City]):
 def distance(cm: CityMap): Int =
   (cities zip cities.tail)
     .map{
       case (c1, c2) => cm.distance(c1, c2)
     }.sum
  
 def addCity(city: City): Path =
   Path(cities :+ city)
  
object Path:
 val empty = Path(Seq.empty[City])
end Path

Nothing surprising I hope. The only important part is that the path has cities in some order.

Let's define the example problem.

val cityA = City("a")
val cityB = City("b")
val cityC = City("c")
val cityD = City("d")


val allCities = Set(cityA, cityB, cityC, cityD)


val cityMap = CityMap(
 Map(
   Set(cityA, cityB) -> 20,
   Set(cityA, cityC) -> 42,
   Set(cityA, cityD) -> 35,
   Set(cityB, cityC) -> 30,
   Set(cityB, cityD) -> 34,
   Set(cityC, cityD) -> 12,
 )
)

The values should be the same as in the first table/graph.

Let's start with a solution which evaluates every path.

var stepsTaken = 0
def fullSearch(cityMap: CityMap, cities: Set[City]): Path =
 def oneStepDeeper(currentPath: Path): Path =
   stepsTaken = stepsTaken + 1
   val canTravelTo = cities.filterNot(currentPath.cities.contains)
  
   if canTravelTo.isEmpty then
     currentPath
   else
     canTravelTo
       .map(currentPath.addCity)
       .map(oneStepDeeper)
       .minBy(_.distance(cityMap))
    
 oneStepDeeper(Path.empty)


val bestPath = fullSearch(cityMap, allCities)


println("Shortest path")
println(bestPath.cities.map(_.name).mkString("->"))
println(s"steps taken: $stepsTaken")

The outcome is:

Shortest path

a->b->c->d

steps taken: 65

Think it has 65 steps and not 64 because of the “root step”.

Alright lets cut some useless branches.

var stepsTaken = 0
def fullSearch(cityMap: CityMap, cities: Set[City]): Path =
 def oneStepDeeper(currentPath: Path, bestSoFar: Option[Path]): Path =
   stepsTaken = stepsTaken + 1
   lazy val canTravelTo = cities.filterNot(currentPath.cities.contains)
   lazy val currentDistance = currentPath.distance(cityMap)


   bestSoFar match
     case Some(best) if currentDistance >= best.distance(cityMap) =>
		// a cut!
       best
     case _ if canTravelTo.isEmpty => currentPath
     case _ =>
       var bestSoFar_ = bestSoFar
       canTravelTo.map{city =>
         val pathToEvaluate = currentPath.addCity(city)
         val bestLocal = oneStepDeeper(pathToEvaluate, bestSoFar_)
         bestSoFar_ = (Seq(bestLocal) ++ bestSoFar_.toSeq)
           .minByOption(_.distance(cityMap))


         bestLocal
       }
       .minBy(_.distance(cityMap))


 oneStepDeeper(Path.empty, None)


val bestPath = fullSearch(cityMap, allCities)

The outcome is:

Shortest path

a->b->c->d

steps taken: 55

55 steps, it's 10 less which does not seem like much but this cutting adds up in larger problems. Imagine cutting an edge close to the root, you didnt cut just one edge but rather the whole subtree under it.

The solution itself isn't too complicated, we are basically trying to remember the best solution we found so far and compare the current unfinished solution to it. If the unfinished solution has no chance of making a better full solution we give up on that branch (and just return the current best solution, so the nested function always returns something).

We can improve this in many ways, for example instead of taking the current path distance as it is we can add the minimal distance to make it “a full path”. Let's say we have currently only 2 cities connected. We know we still need 2 more, so 2 more roads. If the 2 shortest roads are 12 and 20, we can add these numbers before comparing the value to the best solution we found so far. With this we will cut quicker (higher in the tree). You need to be careful that the “minimal possible distance” is correct and can't be undercut, otherwise you may end up giving up on a better solition.

Note obviously there are no guarantees for improvements, and so its still an algorithm with O(n!), it's just that the average solution is much better and allows you to find the best solution in a much bigger input/graph.

We can still improve the algorithm with better data structures, in fact it's one of the few places where you should use mutable data structures (because of performance). We can also perhaps find a solution with a greedy algorithm so that we have a good solution from the start (and can cut quicker).

We can also stop the algorithm after a certain amount of steps have been taken if we truly don't need the best solution but a good solution will do.

Now I am writing here about the traveling salesman problem but LCBB can be used for all sorts of problems. Typically you need to be able to create some sort of tree with partial solutions to the problem. You need to be able to evaluate a full solution (a function which takes the solution and gives you some number) and to evaluate a partial solution to get the minimal possible outcome to compare.

Anyway, I hope you learned something interesting.

_

Thank you to Michal for contributing to Scala Matters.

To submit your blog, message Patrycja or email Patrycja@umatr.io