DROPS

Document

DOI: 10.4230/LIPIcs.CP.2023.18

Preprocessing in SAT-Based Multi-Objective Combinatorial Optimization

Authors: Christoph Jabs, Jeremias Berg, Hannes Ihalainen, and Matti Järvisalo

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract

Building on Boolean satisfiability (SAT) and maximum satisfiability (MaxSAT) solving algorithms, several approaches to computing Pareto-optimal MaxSAT solutions under multiple objectives have been recently proposed. However, preprocessing in (Max)SAT-based multi-objective optimization remains so-far unexplored. Generalizing clause redundancy to the multi-objective setting, we establish provably-correct liftings of MaxSAT preprocessing techniques for multi-objective MaxSAT in terms of computing Pareto-optimal solutions. We also establish preservation of Pareto-MCSes - the multi-objective lifting of minimal correction sets tightly connected to optimal MaxSAT solutions - as a distinguishing feature between different redundancy notions in the multi-objective setting. Furthermore, we provide a first empirical evaluation of the effect of preprocessing on instance sizes and multi-objective MaxSAT solvers.

Cite as

Christoph Jabs, Jeremias Berg, Hannes Ihalainen, and Matti Järvisalo. Preprocessing in SAT-Based Multi-Objective Combinatorial Optimization. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jabs_et_al:LIPIcs.CP.2023.18,
  author =	{Jabs, Christoph and Berg, Jeremias and Ihalainen, Hannes and J\"{a}rvisalo, Matti},
  title =	{{Preprocessing in SAT-Based Multi-Objective Combinatorial Optimization}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.18},
  URN =		{urn:nbn:de:0030-drops-190553},
  doi =		{10.4230/LIPIcs.CP.2023.18},
  annote =	{Keywords: maximum satisfiability, multi-objective combinatorial optimization, preprocessing, redundancy}
}

Document

DOI: 10.4230/LIPIcs.CP.2021.28

Refined Core Relaxation for Core-Guided MaxSAT Solving

Authors: Hannes Ihalainen, Jeremias Berg, and Matti Järvisalo

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract

Maximum satisfiability (MaxSAT) is a viable approach to solving NP-hard optimization problems. In the realm of core-guided MaxSAT solving - one of the most effective MaxSAT solving paradigms today - algorithmic variants employing so-called soft cardinality constraints have proven very effective. In this work, we propose to combine weight-aware core extraction (WCE) - a recently proposed approach that enables relaxing multiple cores instead of a single one during iterations of core-guided search - with a novel form of structure sharing in the cardinality-based core relaxation steps performed in core-guided MaxSAT solvers. In particular, the proposed form of structure sharing is enabled by WCE, which has so-far not been widely integrated to MaxSAT solvers, and allows for introducing fewer variables and clauses during the MaxSAT solving process. Our results show that the proposed techniques allow for avoiding potential overheads in the context of soft cardinality constraint based core-guided MaxSAT solving both in theory and in practice. In particular, the combination of WCE and structure sharing improves the runtime performance of a state-of-the-art core-guided MaxSAT solver implementing the central OLL algorithm.

Cite as

Hannes Ihalainen, Jeremias Berg, and Matti Järvisalo. Refined Core Relaxation for Core-Guided MaxSAT Solving. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 28:1-28:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ihalainen_et_al:LIPIcs.CP.2021.28,
  author =	{Ihalainen, Hannes and Berg, Jeremias and J\"{a}rvisalo, Matti},
  title =	{{Refined Core Relaxation for Core-Guided MaxSAT Solving}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{28:1--28:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.28},
  URN =		{urn:nbn:de:0030-drops-153197},
  doi =		{10.4230/LIPIcs.CP.2021.28},
  annote =	{Keywords: maximum satisfiability, MaxSAT, core-guided MaxSAT solving}
}

Search Results

Documents authored by Ihalainen, Hannes

Preprocessing in SAT-Based Multi-Objective Combinatorial Optimization

Abstract

Cite as

Refined Core Relaxation for Core-Guided MaxSAT Solving

Abstract

Cite as

Thanks for your feedback!

Could not send message