How to implement a branch-and-bound in a functional programming language

functional programminglisp

I am trying to write a branch and bound search on the set of all functions f: D -> R, where the domain size is small (|D| ~ 20) and the range is much bigger (|R| ~ 2^20). Initially, I came up with the following solution.

(builder (domain range condlist partial-map)
            (let ((passed? (check condlist partial-map)))
              (cond
               ((not passed?) nil)
               (domain (recur-on-first domain range condlist partial-map '()))
               (t partial-map))))
(recur-on-first (domain range condlist partial-map ignored)
                   (cond
                    ((null range) nil)
                    (t (let ((first-to-first
                              (builder (cdr domain)
                                       (append ignored (cdr range))
                                       condlist
                                       (cons (cons (car domain) (car range)) partial-map))))
                         (or first-to-first
                             (recur-on-first domain
                                             (cdr range)
                                             condlist
                                             partial-map
                                             (cons (car range) ignored))))))))

Here the parameter condlist to the function builder is a list of conditions that should be satisfied by a solution. The function check returns nil iff any element in the list of conditions is violated by the partial-map. The function recur-on-first assigns the first element in the domain to the first element in the range and tries to build a solution from there. Failing this recur-on-first invokes itself to try and construct a solution that assigns the first element in the domain to some element other than the first one in the range. However, it has to maintain a list ignored that stores these discarded elements (like the first element in the range) as they could be images of some other elements in the domain.

There are two problems that I can see with this solution. The first one is that the lists ignored and range in the function recur-on-first are quite large and appending them is an expensive operation. The second problem is that the recursion depth of the solution depends on the size of the range.

So I came up with the following solution that uses doubly linked lists to store the elements in the range. The functions start, next and end provide facilities to iterate over the doubly linked list.

(builder (domain range condlist &optional (partial-map nil))
            (block builder
                   (let ((passed? (check condlist partial-map)))
                     (cond
                       ((not passed?) nil)
                       (domain (let* ((cur (start range))
                                      (prev (dbl-node-prev cur)))
                                 (loop
                                   (if (not (end cur))
                                     (progn
                                       (splice-out range cur)
                                       (let ((sol (builder (cdr domain)
                                                           range
                                                           condlist
                                                           (cons (cons (car domain) (data cur)) partial-map))))
                                         (splice-in range prev cur)
                                         (if sol (return-from builder sol)))
                                       (setq prev cur)
                                       (setq cur (next cur)))
                                     (return-from builder nil)))))
                       (t partial-map))))))

The runtime of the second solution is much better than the runtime of the first solution. The append operation in the first solution is replaced by splicing elements in and out of a doubly linked list (these operations are constant time) and the recursion depth only depends on the size of the domain. But my problem with this solution is that it uses C style code. So my question is this.

Is there a solution that is as efficient as the second solution but does not use setfs and mutable data structures? In other words, is there an efficient functional programming solution to this problem?

Best Answer

First idea that comes to mind: use the same general approach, but replace the loop with a tail-recursive call whose parameter is the spliced list for the next stage of the computation? You never have to modify the spliced list, just generate a new list at each stage. This admittedly is not constant-time, but you need to walk the list to find where to splice anyway. It might even be able to re-use most of the nodes, especially if you can use a singly-linked list.

Related Topic