Encoding cardinality constraints using multiway merge selection networks

DOI10.1007/S10601-019-09302-0MaRDI QIDQ2009191zbMATH OpenOpenAlexFDO

Authors Michał Karpiński, Marek Piotrów

Publication date 27 November 2019

Published in Constraints (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10601-019-09302-0

zbMATH Keywords

SAT encodingcardinality constraintSAT-solverSAT translationselection network

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational aspects of satisfiability (68R07)

Recommendations

• Cardinality networks: a theoretical and empirical study
• Cardinality Networks and Their Applications
• A parametric approach for smaller and better encodings of cardinality constraints
• Encoding cardinality constraints using standard encoding of generalized selection networks preserves arc-consistency
• Towards an Optimal CNF Encoding of Boolean Cardinality Constraints

Cites work

• scientific article; zbMATH DE number 5139161 (Why is no real title available?)
• scientific article; zbMATH DE number 5139168 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• A linear-time transformation of linear inequalities into conjunctive normal form
• A parametric approach for smaller and better encodings of cardinality constraints
• Cardinality networks: a theoretical and empirical study
• Curriculum-based course timetabling with SAT and MaxSAT
• Encoding cardinality constraints using standard encoding of generalized selection networks preserves arc-consistency
• PBLib -- a library for encoding pseudo-Boolean constraints into CNF
• Pairwise cardinality networks
• Towards an Optimal CNF Encoding of Boolean Cardinality Constraints

Cited in

(9)

• Cardinality Networks and Their Applications
• Exact and approximate determination of the Pareto front using minimal correction subsets
• On the benefits of knowledge compilation for feature-model analyses
• Certified Core-Guided MaxSAT Solving
• Encoding cardinality constraints using standard encoding of generalized selection networks preserves arc-consistency
• Normalizing cardinality rules using merging and sorting constructions
• Pairwise cardinality networks
• Cardinality networks: a theoretical and empirical study
• New core-guided and hitting set algorithms for multi-objective combinatorial optimization

Describes a project that uses

Uses Software

• COMiniSatPS
• PBLib
• MiniSat

This page was built for publication: Encoding cardinality constraints using multiway merge selection networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2009191)