Dear Thomas,
nothing about FRODO in particularly, but about DCOP in generally. :-)
Maybe you want to share your point of view? There a lot of problems in the real world, which we transfer to DCOP "compatibles" problems, like Graph-Coloring, Time Scheduling, Sensor Network, ... problems.
But it seems to me hard to choose the "best" algorithm for a specific problem. What would you advice? Is there a kind of best practise way? So far, i think it depends on hard/soft constraints respectively if the algorithm allows to violate constraints or not.
I talked to someone who did research in optimizing (not linear optimizing) and he thought that it is more a kind of try out. But i'm thinking, it would be a waste of time an computer power, to try out the different algorithms on a complex problem, until you find a good one and start then with the detail tests.
Would you share your thoughts?
Best,
Teo
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I would tend to agree with your colleague: one empirical way to choose the best algorithm for a class of problems is to try out a few algorithms on some sample problem instances that are as representative as possible of your problem class. In fact, some of the philosophy behind making the FRODO platform open source is precisely to make it easier for people to try out various algorithms on given problem instances without having to first implement each algorithm, or having to adapt the representations of the problem instances to the various, inconsistent algorithm implementations that may be available out there.
That said, there are a few characteristics of problem classes and/or problem instances that you can look into and that should give you an idea of which algorithm(s) might be able to perform best. Here is a non-exhaustive list of such characteristics that come to my mind (omitting literature references for now; if you are interested, I can also provide you pointers).
Are you minimizing non-negative costs?
Some algorithms assume that the problem is a minimization problem, and that all costs are non-negative. If they find a solution of cost zero, they are then able to terminate earlier, since they know that no strictly better solution can exist. Examples of such algorithms are SynchBB and AFB. A counter-example is DPOP.
Do your problem instances have low tree width?
One interesting, quite unique property of the DPOP algorithm is that its complexity is exponential in the tree width. This means that your problem might be very large, but as long as the tree width is low, DPOP might perform remarkably well, while other complete algorithms might just time out.
Do you have loose constraints?
Algorithms that perform search (such as SynchBB, AFB, ADOPT...) are more likely to outperform algorithms based on dynamic programming (DPOP and its variants) when the constraint tightness is low, while DPOP is more likely to win on problems with very tight constraints.
Do you have very large problem instances?
Unless your problem class has some special topology (such as low tree width), you will find that complete algorithms (such as all the algorithms I mentioned so far) fail to scale to large problems. You will then have to resort to incomplete algorithms, which scale better but are no longer guaranteed to return an optimal (or even feasible) solution. Examples of such incomplete algorithms are DSA, MGM, or MaxSum.
Do you only have hard constraints?
If you are not maximizing utility or minimizing cost, but rather trying to find a feasible solution to a problem that involves only hard constraints, then it might be the case that pure DisCSP algorithm could perform better than DCOP algorithms running on a Max-DisCSP reformulation of the problem. Notice however that, with the exotic exception of the MPC-DisCSP4 algorithm, no pure DisCSP algorithm has been implemented in FRODO yet. Furthermore, I suspect there is not much literature out there reporting experimental results about the performance of DisCSP vs. DCOP algorithms on DisCSP problem classes.
I hope this helps; let me know if you would like me to go into more details on one or several of the points I briefly mentioned above.
Best,
Thomas
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
thank you very much for sharing your thoughts! This question came up for me while I examined the various algorithms, mainly because we transferred so the "typical" problems in the real world on a small number of "typical" DCO problems. And as the complexity is quite high, this seems to be a very interesting point.
I was looking for scientific papers - and honestly i must admit - i was expecting to find a few of them. Anyway - thank you for your assessment!
Best,
Teo
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Dear Thomas,
nothing about FRODO in particularly, but about DCOP in generally. :-)
Maybe you want to share your point of view? There a lot of problems in the real world, which we transfer to DCOP "compatibles" problems, like Graph-Coloring, Time Scheduling, Sensor Network, ... problems.
But it seems to me hard to choose the "best" algorithm for a specific problem. What would you advice? Is there a kind of best practise way? So far, i think it depends on hard/soft constraints respectively if the algorithm allows to violate constraints or not.
I talked to someone who did research in optimizing (not linear optimizing) and he thought that it is more a kind of try out. But i'm thinking, it would be a waste of time an computer power, to try out the different algorithms on a complex problem, until you find a good one and start then with the detail tests.
Would you share your thoughts?
Best,
Teo
Dear Teo,
I would tend to agree with your colleague: one empirical way to choose the best algorithm for a class of problems is to try out a few algorithms on some sample problem instances that are as representative as possible of your problem class. In fact, some of the philosophy behind making the FRODO platform open source is precisely to make it easier for people to try out various algorithms on given problem instances without having to first implement each algorithm, or having to adapt the representations of the problem instances to the various, inconsistent algorithm implementations that may be available out there.
That said, there are a few characteristics of problem classes and/or problem instances that you can look into and that should give you an idea of which algorithm(s) might be able to perform best. Here is a non-exhaustive list of such characteristics that come to my mind (omitting literature references for now; if you are interested, I can also provide you pointers).
Are you minimizing non-negative costs?
Some algorithms assume that the problem is a minimization problem, and that all costs are non-negative. If they find a solution of cost zero, they are then able to terminate earlier, since they know that no strictly better solution can exist. Examples of such algorithms are SynchBB and AFB. A counter-example is DPOP.
Do your problem instances have low tree width?
One interesting, quite unique property of the DPOP algorithm is that its complexity is exponential in the tree width. This means that your problem might be very large, but as long as the tree width is low, DPOP might perform remarkably well, while other complete algorithms might just time out.
Do you have loose constraints?
Algorithms that perform search (such as SynchBB, AFB, ADOPT...) are more likely to outperform algorithms based on dynamic programming (DPOP and its variants) when the constraint tightness is low, while DPOP is more likely to win on problems with very tight constraints.
Do you have very large problem instances?
Unless your problem class has some special topology (such as low tree width), you will find that complete algorithms (such as all the algorithms I mentioned so far) fail to scale to large problems. You will then have to resort to incomplete algorithms, which scale better but are no longer guaranteed to return an optimal (or even feasible) solution. Examples of such incomplete algorithms are DSA, MGM, or MaxSum.
Do you only have hard constraints?
If you are not maximizing utility or minimizing cost, but rather trying to find a feasible solution to a problem that involves only hard constraints, then it might be the case that pure DisCSP algorithm could perform better than DCOP algorithms running on a Max-DisCSP reformulation of the problem. Notice however that, with the exotic exception of the MPC-DisCSP4 algorithm, no pure DisCSP algorithm has been implemented in FRODO yet. Furthermore, I suspect there is not much literature out there reporting experimental results about the performance of DisCSP vs. DCOP algorithms on DisCSP problem classes.
I hope this helps; let me know if you would like me to go into more details on one or several of the points I briefly mentioned above.
Best,
Thomas
Dear Thomas,
thank you very much for sharing your thoughts! This question came up for me while I examined the various algorithms, mainly because we transferred so the "typical" problems in the real world on a small number of "typical" DCO problems. And as the complexity is quite high, this seems to be a very interesting point.
I was looking for scientific papers - and honestly i must admit - i was expecting to find a few of them. Anyway - thank you for your assessment!
Best,
Teo