This paper introduces a new hybrid method for efficiently integrating Pseudo-Boolean (PB) constraints into generic SAT solvers in order to solve PB satisfiability and optimization problems. To achieve this, we adopt the cutting-plane technique to draw inferences among PB constraints and combine it with generic implication graph analysis for conflict-induced learning. Novel features of our approach include a light-weight and efficient hybrid learning and backjumping strategy for analyzing PB constraints and CNF clauses in order to simultaneously learn both a CNF clause and a PB constraint with minimum overhead and use both to determine the backtrack level. Several techniques for handling the original and learned PB constraints are introduced. Overall, our method benefits significantly from the pruning power of the learned PB constraints, while keeping the overhead of adding them into the problem low. In this paper, we also address two other methods for solving PB problems, namely integer linear programming and pre-processing to CNF SAT, and present a thorough comparison between them and our hybrid method. Experimental comparison of our method against other hybrid approaches is also demonstrated. Additionally, we provide details of the MiniSAT-based implementation of our solver Pueblo to enable the reader to construct a similar one.

References in zbMATH (referenced in 28 articles , 1 standard article )

Showing results 1 to 20 of 28.
Sorted by year (citations)

1 2 next

  1. Morgado, Antonio; Heras, Federico; Liffiton, Mark; Planes, Jordi; Marques-Silva, Joao: Iterative and core-guided maxsat solving: a survey and assessment (2013)
  2. Qi, Guilin; Du, Jianfeng: Reasoning with uncertain and inconsistent OWL ontologies (2012)
  3. Graça, Ana; Marques-Silva, João; Lynce, In^es; Oliveira, Arlindo L.: Haplotype inference with pseudo-Boolean optimization (2011)
  4. Tate, Ross; Stepp, Michael; Tatlock, Zachary; Lerner, Sorin: Equality saturation: a new approach to optimization (2011)
  5. Di Rosa, Emanuele; Giunchiglia, Enrico; Maratea, Marco: Solving satisfiability problems with preferences (2010)
  6. Manquinho, Vasco; Martins, Ruben; Lynce, In^es: Improving unsatisfiability-based algorithms for Boolean optimization (2010)
  7. Morgado, António; Marques-Silva, Joao: Combinatorial optimization solutions for the maximum quartet consistency problem (2010)
  8. Bailleux, Olivier; Boufkhad, Yacine; Roussel, Olivier: New encodings of pseudo-Boolean constraints into CNF (2009)
  9. Binshtok, M.; Brafman, R.I.; Domshlak, C.; Shiomony, S.E.: Generic preferences over subsets of structured objects (2009)
  10. Buchheim, Christoph; Rinaldi, Giovanni: Terse integer linear programs for Boolean optimization (2009)
  11. Gebser, Martin; Kaminski, Roland; Kaufmann, Benjamin; Schaub, Torsten: On the implementation of weight constraint rules in conflict-driven ASP solvers (2009)
  12. Kovalev, Roman; Lysikov, Nikolay; Mikheev, Gennady; Pogorelov, Dmitry; Simonov, Vitaly; Yazykov, Vladislav; Zakharov, Sergey; Zharov, Ilya; Goryacheva, Irina; Soshenkov, Sergey; Torskaya, Elena: Freight car models and their computer-aided dynamic analysis (2009)
  13. Manquinho, Vasco; Marques-Silva, Joao; Planes, Jordi: Algorithms for weighted Boolean optimization (2009)
  14. Heras, Federico; Larrosa, Javier; de Givry, Simon; Schiex, Thomas: 2006 and 2007 Max-SAT evaluations: contributed instances (2008)
  15. Heras, F.; Larrosa, J.; Oliveras, A.: Minimaxsat: an efficient weighted Max-SAT solver (2008)
  16. Larrosa, Javier; Heras, Federico; de Givry, Simon: A logical approach to efficient Max-SAT solving (2008)
  17. Sanchez, Marti; de Givry, Simon; Schiex, Thomas: Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques (2008)
  18. Sun, Y.Q.; Cole, C.: Vertical dynamic behavior of three-piece bogie suspensions with two types of friction wedge (2008)
  19. Fuhs, Carsten; Giesl, Jürgen; Middeldorp, Aart; Schneider-Kamp, Peter; Thiemann, René; Zankl, Harald: SAT solving for termination analysis with polynomial interpretations (2007)
  20. Gosavi, Abhijit; Ozkaya, Emrah; Kahraman, Aykut F.: Simulation optimization for revenue management of airlines with cancellations and overbooking (2007)

1 2 next