search

takemaru / graphillion

Fast, lightweight graphset operation library
Other
466 stars 40 forks source link

Reproducing Paper Results #67

Open seanlaw opened 9 months ago

seanlaw commented 9 months ago

In this recent paper published by Prof. Minato titled, "Interval-Memoized Backtracking on ZDDs for Fast Enumeration of All Lower Cost Solutions", it is mentioned that Graphillion was used. Are you able to give any advice/suggestions on how to use Graphillion to reproduce their results and implement their published algorithms?

takemaru commented 9 months ago

Why don't you ask Prof Minato? I'm not a co-author of the paper.

seanlaw commented 8 months ago

Thank you @takemaru. I had already reached out to both Prof Minato and Prof Kawahara and received the following response:

The code has already been implemented in the BDDCT class in SAPPOROBDD package, and will be implemented in graphillion soon.

Since I am not familiar with the C programming language and, without proper documentation, it is not clear how to use SAPPOROBDD. Thus, I was hoping that I could use/construct ZDDs through Graphillion's extension into SAPPOROBDD. However, I am confused since BDD/ZDD directed acyclic graphs (DAG) but, in the Graphillion documentation it states that:

Graphillion supports undirected graphs only

If Graphillion uses ZDDs, which are DAGs, then are you able to help me better understand why Graphillion only supports undirected graphs (even though it uses ZDD DAGs)? This is not so clear to me.

Or to ask my question differently, is it possible to use Graphillion's Python interface to create a ZDD that can then be used to solve a knapsack problem?

Thank you for your time and patience!

takemaru commented 8 months ago

Since Graphillion is designed for graph problems, it is not suitable for knapsack problems. If you want a Python-based ZDD library, please try https://github.com/tulip-control/dd

seanlaw commented 7 months ago

After exchanging a few emails with @junkawahara, the methods proposed in the paper have been implemented in v1.7rc and a simple reproducible example was kindly provided:

For the knapsack problem, it is suitable to use "setset" class, which is similar to GraphSet but represents sets of sets.

The following is a piece of sample code.


from graphillion import setset

items = [1, 2, 3, 4, 5] # item id (arbitrary) weights = [3, 2, 7, 5, 1] # item weights cost_bound = 6 # capacity of the bin

cost_dic = {} # dictionary whose key is an item and whose value is item's weight for i in range(len(items)): cost_dic[items[i]] = weights[i]

setset.set_universe(items) # must be called

power_set = setset({}) # power set (all the combinations of the items)

sets_le_6 = power_set.cost_le(weights, cost_bound) # sets_le_6 is an object of setset class.



Thank you @junkawahara and @takemaru for your help, time, and patience. Please let me know if this example would be worth adding to the Wiki and I can submit a PR when the release candidate is merged.