Extending Max-Sum

[lcpz]

Hi Pierre, thanks for this project.

I am trying to figure out how can I implement two variants of Max-Sum I am interested in: Max-Sum_ADVP and ICG-Max-Sum. Max-Sum_ADVP defines an order in which the beliefs will propagate (basically, it generates a DAG). ICG-Max-Sum cyclically applies two Max-Sum in sequence through a column generation technique, and defines probabilistic functions in the factor nodes.

I would like to ask you what could be the best way to do it. Should I do everything inside the algorithms, or should I extend computations_graph/factor_graph as well?

More generally, what is the best practice for implementing algorithms that pre-process the computation graph?

---

Also, in algorithms.maxsum, I understand that the query message from variable to factor (q) is costs_for_factor, the response message from factor node to variable node (r) is factor_costs_for_var, and the marginal function (z) is select_value. Maybe you could add some comments in which you map this terminology to the original one for more clarity.

[PierreRustOrange]

Hi,

I'm very glad that you want to implement these algorithms in pyDCOP, as I would really like pyDCOP to provide many more DCOP algorithms implementations and I was planning to implement some of these myself (and a fast-maxsum implementation is under way from another pyDCOP's user) . I'm willing to help you as much as i can for this work. For educational and completeness purposes, I think I would be great to first implement MaxSum_AD, and then MaxSum_ADVP. I'm not really familiar with ICG_MaxSum so I'll have to study it a bit before giving you any relevant direction on it.

Regarding MaxSum_AD / ADVP, the major point is indeed the DAG generation:

• If the DAG generation must be implemented as part of a pre-processing phase, it should go in the computation graph generation, i.e. in computations_graph/factor_graph or preferably, in another computation_graph_type like for example computations_graph/fg_dag (which would of course reuse code from factor_graph).
• However, if it can be done distributively (I'm note sure it's the case) it would be nice to do it entirely in the algorithm it self.

Other points that come to mind are:

• The base algorithms described in the paper are designed for binary DCOPs, while our current MaxSum implementation supports n-ary constraints. If the implementation only supports binary constraint, it must raises an exception in case n-ary constraints are used. Ideally n-ary constraints should be supported, a potential approach is given in the paper.
• pyDCOP support asynchronous and synchrounous MaxSum, here of course only the synchronous version applies.

I'll see what I can do for the comment.

Let me know if you have any other question and please submit a Pull Request when you have some code (even incomplete) so we can discuss directly on the implementation.