Abstract | ||
---|---|---|
Solving combinatorial optimization problems by reducing them to MaxSAT has shown to be a competitive problem solving approach. Since a lot of optimization problems have many-valued variables, we propose to exploit the domain information of the many-valued variables to enhance MaxSAT-based problem solving: first, we define a new way of encoding weighted maximum constraint satisfaction problems to both Boolean MaxSAT and many-valued MaxSAT, and second, we define a variable selection heuristic that takes into account the domain information and allow us to easily implement a many-valued MaxSAT solver. Moreover, the empirical results provide evidence of the good performance of the new encodings and the new branching heuristic on a representative set of instances. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1109/ISMVL.2017.42 | 2017 IEEE 47th International Symposium on Multiple-Valued Logic (ISMVL) |
Keywords | Field | DocType |
MaxSAT,many-valued clausal forms,hybrid encodings | Maximum satisfiability problem,Mathematical optimization,Heuristic,Feature selection,Computer science,Exploit,Constraint satisfaction problem,Solver,Optimization problem,Encoding (memory) | Conference |
ISBN | Citations | PageRank |
978-1-5090-5497-8 | 0 | 0.34 |
References | Authors | |
13 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Josep Argelich | 1 | 190 | 18.95 |
Chu Min Li | 2 | 1194 | 85.65 |
Felip Manyà | 3 | 787 | 59.52 |