Library for tree search for combinatorial optimization problems

Question

I notice that some of the "hard" combinatorial problems I come across can be cast in terms of some type of tree search like alpha-beta pruning, or beam search, or a similar algorithm. However, programming them seems like repetitively coding the same things and it is also pretty easy to make mistakes. It seems to me there should be a library that implements these algorithms, and all I should be asked to write is

1. a coding for the solution, i.e., how to get a more specific solution from an incomplete solution. This will give the tree/graph structure.
2. Given a partial solution, how to get the maximum/minimum cost, and perhaps an estimate of the cost.
3. An Initial solution/partial solution.
4. Maybe some sort of a verification solution.

I am sorry I haven't given any specific code, but I think I have explained the problem. If I can write code for the functions described above, shouldn't I be able to run a number of tree/graph search algorithms easily? Is there any user friendly library/framework that supports this easily? I'd love it to be in Python or C/C++, but would be interested to hear any suggestions.

Edit: To be more precise, I am talking about informed tree search algorithms.

Thornie

Answer 1

Fuego is an open-source monte-carlo tree search (as opposed to alpha-beta tree search) platform that can target 2-player full-information games (originally created to target Go). It may even be more general than that.

http://fuego.sourceforge.net/

Edit: I just learned that it also features an alpha-beta searcher. Here is a recent paper: http://webdocs.cs.ualberta.ca/~mmueller/ps/fuego-TCIAIG.pdf

Thalamencephalon

Answer 2

Expressing a problem without specifying the specific steps is a kind of declarative programming.

You talk about 'partial solutions'. Does this mean that the kind of problems you are considering have overlapping subproblems? If so, then it sounds like you're asking for a way to do general dynamic programming. All that really means is building a function through successive steps, solving simpler versions of the problem and then iterating. There are some nice examples in this Mathematica journal article.

Have you considered Prolog? It's not a framework, but the search algorithm, if you like, is built into the language. It's possible to write very general constraint programming solutions using something like Prolog as the basis. In Python there is the python-constraint library, which is pretty nice - I've used it in the past.

Mascarenas

Declarative Programming and dynamic programming don't really do informed tree searches, unless I am missing something. – Thornie

@Thornie - Could you define what you mean by 'informed tree search'? – Mascarenas

Sure, cs.umd.edu/~nau/cmsc421/chapter04a.pdf and Peter Norvigs book have good sections on informed search. Basically, if you know every vertex in a tree represents a solution, and related solutions are its children, can you use the current solutions to search for better solutions. A* and branch and bound algorithms come to mind. – Thornie

+1 for useful information. Does declarative programming specify the search algorithm? – Thornie

Answer 3

QuickGraph

For anyone willing to go .Net, take a look at the open source QuickGraph library for all your graph/tree based processing. It neatly seperates all concepts related to graph-representation, -algorithms, -mutations and -presentation. It has lots of extension points so it should be able to support most graph-castable problems.

[EDIT] The set of algorithms supplied with QuickGraph does not include alpha-beta pruning or beam search at this moment, although its 'search' algorithm section includes 11 other methods that provide ample guidance for implementing your favorite traversal algorithm, and in time I would imagine it will support alpha-beta and beam.

ad. 1 It does satisfy your first criterion though, in that it is possible to insert a delegate function that returns several more specific solutions (i.e. neighboring nodes) based on an incomplete solution (i.e. current node). This is handled by DelegateImplicitGraph (and variations) and is supposed to be memory efficient because it prevents having the whole search space in memory at once. ad. 2 Furthermore, the algorithms may take custom delegates such as max/min/expected cost hueristics (see AStarShortestPathAlgorithm). This satisfies your second criterion.

In summary, QuickGraph helps you structure your problem, provides drop-in algorithms for various types of problems, and allows you to improve on it by supplying new algorithms.

Sham

Like BGL, I don't see any options to use it to search a solution space, this is more like graph traversal or already known graphs. Though I understand one can build on this, like one can on BGL or networkx. – Thornie

Answer 4

Boost has the Boost Graph Libary (BGL). The Boost Graph Library User's Guide has an example on the Knight's tour problem using implicit graphs.

Atomic

BGL seems to have algorithms for traversing known graphs, not to search game trees or optimization decisions. – Thornie

I just found BGL also has some support for implicit graphs and a-star. – Thornie

Answer 5

I found Peter Norvig's Python code for informed and uninformed search online. It has support for A-star search, and can be used to program for generic problems from what I can see. I wonder if it is fast enough or can be extended to beam search, branch and bound etc.

Thornie