Solving the routing and wavelength assignment problem with conflict-driven ASP solvers
MetadataShow full item record
The Routing and Wavelength Assignment (RWA) problem is an optical networking problem that aims to improve data transmission by eliminating optoelectronic conversions through the network. The RWA problem is in the set of NP-complete problems and thus, it is also an interesting problem from a computational point of view. It can be solved in different flavors, being the Static Lightpath Establishment (SLE) the one studied in this work. In this work we define different Answer Set Programming (ASP) encodings for the RWA-SLE problem and study their performance when solving the problem with a state-of-the-art conflict-driven ASP solver: clasp. We investigate the relation between the performance of the ASP encodings and two different characteristics of the encodings: the number of nogoods and loop nogoods generated during search and a new measure for their tightness that we introduce. We also compare the performance of our ASP encodings with the best performing pseudo-Boolean encoding that we presented in a previous work.
Is part ofAi Communications, 2015, vol.28, núm. 1, p. 21-34
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 (Springer, 2008)Recently, edge matching puzzles, an NP-complete problem, have rececived, thanks to money-prized contests, considerable attention from wide audiences. We consider these competitions not only a challenge for SAT/CSP solving ...
Béjar Torres, Ramón; Manyà Serres, Felip; Cabiscol i Teixidó, Alba; Fernàndez Camon, César; Gomes, Carla (Elsevier, 2007)Regular-SAT is a constraint programming language between CSP and SAT that—by combining many of the good properties of each paradigm—offers a good compromise between performance and expressive power. Its similarity to SAT ...