Is the separator defined in current DPOP algo the same as in MB-DPOP?

[luptior]

I'm trying to see if I can implement MB-DPOP https://infoscience.epfl.ch/record/98347 And I find that the _on_value_message() function in dpop.py's class DpopAlgo() does have some code related to separator.

Kind of confused, does the DPOP algorithm currently have MB-DPOP built-in or just use the separator for implementation need?

[luptior]

Also the comments says "Pseudo parent are not given explicitly but can be deduced from the relation set with add_relation." How should I property do this?

[PierreRustOrange]

Hi,

I'm glad you're working on MB-DPOP, this would be a very good addition to the set of algorithms available in pyDCOP. I advise you to implement it as a new file mbdpop.py in the algorithms directory. Note that if you already have some code, you can create a pull request with it so that we can see the same code and anybody could comment / contribute on it. I'll merge it once it's ready and working.

About the separator: The current DPOP implementation does not have MB-DPOP built-in, but simply the orginal DPOP. In DPOP, altough it's not written as such in the original paper, the util messages indeed contain a value for each node in the separator. In Petcu's thesis however, this message is defined based on the separator (p53, def 14). The definitions from the article and the thesis are actually equivalent.

Definition 14 (UTIL message) UTIL^j_i , the UTIL message sent by agent Xi to agent Xj is a multi- dimensional matrix, with one dimension for each variable present in Sepi. dim(U T ILji ) is the set of individual variables in the message. Note that always Xj ∈ dim(U T ILji ).

BTW, the comment of the DpopAlgo class states this :

• VALUE messages : contains the value of the parent of the node and the values of all variables that were present in our UTIl message to our parent (that is to say, our separator) .

About Pseudo-parent You're right, there's something wrong here, I think the comment is outdated and describes a previous version of the implementation. I'll have a look at this and get back to you shortly.

[PierreRustOrange]

I've updated and done some cleanup in the dpop implementation, let me know if you still have any questions