Statistical modelling of CSP solving algorithms performance
MetadataShow full item record
The goal of this work is to try to create a statistical model, based only on easily computable parameters from the CSP problem to predict runtime behaviour of the solving algorithms, and let us choose the best algorithm to solve the problem. Although it seems that the obvious choice should be MAC, experimental results obtained so far show, that with big numbers of variables, other algorithms perfom much better, specially for hard problems in the transition phase.
Is part ofLecture Notes in Computer Science, 2005, vol. 3709, p. 861-867
European research projects
Showing items related by title, author, creator and subject.
Argelich Romà, Josep; Béjar Torres, Ramón; Fernàndez Camon, César; Mateu Piñol, Carles; Planes Cid, Jordi (Springer International Publishing Switzerland, 2016-06-01)We analyze and compare two solvers for Boolean optimization problems: WMaxSatz, a solver for Partial MaxSAT, and MinSatz, a solver for Partial MinSAT. Both MaxSAT and MinSAT are similar, but previous results indicate that ...
Ansótegui Gil, Carlos José; Béjar Torres, Ramón; Fernàndez Camon, César; Mateu Piñol, Carles (Association for the Advancement of Artificial Intelligence, 2007)Tractable cases of the binary CSP are mainly divided in two classes: constraint language restrictions and constraint graph restrictions. To better understand and identify the hardest binary CSPs, in this work we propose ...
Ansótegui Gil, Carlos José; Béjar Torres, Ramón; Fernàndez Camon, César; Mateu Piñol, Carles (Association for the Advancement of Artificial Intelligence, 2008)In this paper we provide a new method to generate hard k-SAT instances. We incrementally construct a high girth bipartite incidence graph of the k-SAT instance. Having high girth assures high expansion for the graph, and ...