MiniMaxSat: A New Weighted Max-SAT Solver. n this paper we introduce MiniMaxSat, a new Max-SAT solver that incorporates the best SAT and Max-SAT techniques. It can handle hard clauses (clauses of mandatory satisfaction as in SAT), soft clauses (clauses whose falsification is penalized by a cost as in Max-SAT) as well as pseudo-boolean objective functions and constraints. Its main features are: learning and backjumping on hard clauses; resolution-based and subtraction-based lower bounding; and lazy propagation with the two-watched literals scheme. Our empirical evaluation on a wide set of optimization benchmarks indicates that its performance is usually close to the best specialized alternative and, in some cases, even better.

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

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

1 2 next

  1. Marques-Silva, Joao; Malik, Sharad: Propositional SAT solving (2018)
  2. Ansótegui, Carlos; Gabàs, Joel: WPM3: an (in)complete algorithm for weighted partial MaxSAT (2017)
  3. Ansótegui, Carlos; Gabàs, Joel; Levy, Jordi: Exploiting subproblem optimization in SAT-based maxsat algorithms (2016)
  4. Ansótegui, Carlos; Gabàs, Joel; Malitsky, Yuri; Sellmann, Meinolf: MaxSAT by improved instance-specific algorithm configuration (2016)
  5. Cai, Shaowei; Luo, Chuan; Lin, Jinkun; Su, Kaile: New local search methods for partial MaxSAT (2016)
  6. Jamil, Noreen; Müller, Johannes; Naeem, M. Asif; Lutteroth, Christof; Weber, Gerald: Extending linear relaxation for non-square matrices and soft constraints (2016)
  7. Eberhard, Sebastian; Hetzl, Stefan: Inductive theorem proving based on tree grammars (2015)
  8. Achá, Roberto Asín; Nieuwenhuis, Robert: Curriculum-based course timetabling with SAT and MaxSAT (2014)
  9. Allouche, David; André, Isabelle; Barbe, Sophie; Davies, Jessica; de Givry, Simon; Katsirelos, George; O’Sullivan, Barry; Prestwich, Steve; Schiex, Thomas; Traoré, Seydou: Computational protein design as an optimization problem (2014)
  10. Davies, Jessica; Bacchus, Fahiem: Exploiting the power of MIP solvers in MAXSAT (2013)
  11. Heras, F.; Baneres, D.: Incomplete inference for graph problems (2013)
  12. Menai, Mohamed El Bachir; Al-Yahya, Tasniem Nasser: A taxonomy of exact methods for partial Max-SAT (2013)
  13. Morgado, Antonio; Heras, Federico; Liffiton, Mark; Planes, Jordi; Marques-Silva, Joao: Iterative and core-guided maxsat solving: a survey and assessment (2013)
  14. Maratea, Marco: Planning as satisfiability with IPC simple preferences and action costs (2012)
  15. Maratea, Marco; Pulina, Luca: Solving disjunctive temporal problems with preferences using maximum satisfiability (2012)
  16. Morgado, Antonio; Heras, Federico; Marques-Silva, Joao: Improvements to core-guided binary search for MaxSAT (2012)
  17. Abío, Ignasi; Deters, Morgan; Nieuwenhuis, Robert; Stuckey, Peter J.: Reducing chaos in SAT-like search: finding solutions close to a given one (2011)
  18. Arieli, Ofer; Zamansky, Anna: A framework for reasoning under uncertainty based on non-deterministic distance semantics (2011)
  19. Arieli, Ofer; Zamansky, Anna: Simplified forms of computerized reasoning with distance semantics (2011)
  20. Ibaraki, Toshihide; Imamichi, Takashi; Koga, Yuichi; Nagamochi, Hiroshi; Nonobe, Koji; Yagiura, Mutsunori: Efficient branch-and-bound algorithms for weighted MAX-2-SAT (2011)

1 2 next