In the context of solving large distributed constraint optimization problems, belief-propagation and incomplete inference algorithms are candidates of choice. However, in general, when the problem structure is very cyclic, these solution methods suffer from bad performance, due to non-convergence and many exchanged messages. As to improve performances of the MaxSum inference algorithm when solving cyclic constraint optimization problems, we propose here to take inspiration from the belief-propagation-guided decimation used to solve sparse random graphs. We propose the novel DeciMaxSum method, which (...) is parameterized in terms of policies to decide when to trigger decimation, which variables to decimate and which values to assign to decimated variables. Based on an empirical evaluation on a classical constraint optimization benchmarks, some of these combinations of policies, using periodic decimation, cycle detection-based decimation, parallel and non parallel decimation, random or deterministic variable selection and deterministic or random sampling for value selection, outperform state-of-the-art competitors in many settings. (shrink)

Révulsé par une société qu’il juge débile et décervelante, le personnage de ce livre assume sa réputation d’hurluberlu : « Comme le monde serait ennuyeux si on se contentait de le prendre au pied de la lettre! J’ai toujours pensé qu’il fallait dépayser les choses pour se dépayser soi-même. » Il le fait ardemment, avec la conscience ironique et aiguë d’être ce qu’il est, un rêveur philosophe en rupture avec les routines sociales. Pendant quelque temps, il vit sur le toit (...) d’un immeuble parisien où il installe un matelas mousse, un duvet, un réchaud à gaz et quelques livres dans une caisse en guise de bibliothèque. « Ma parole, je crus bien avoir trouvé ma vraie place dans cette vie. » Sa compagne Janina, son ami dadaïste Getty, le professeur Schuzmeyer directeur d’une clinique psychiatrique, et divers personnages de rencontre dont le pittoresque alimente sa bonne humeur, lui fournissent la clé de sa philosophie : « Un individu qui ne revendique pas sa nature profonde de clown est perdu pour moi. Car il y a pire que le clown, il y a l’homme sans lucidité intérieure ». (shrink)