About: Abstract Cores in Implicit Hitting Set MaxSat Solving

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Abstract Cores in Implicit Hitting Set MaxSat Solving Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : wasabi.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
has title	Abstract Cores in Implicit Hitting Set MaxSat Solving
Creator	Berg, Jeremias Fahiem Bacchus, Poole, Alex
Source	PMC
abstract	Maximum Satisfiability (MaxSat) solving is an active area of research motivated by numerous successful applications to solving NP-hard combinatorial optimization problems. One of the most successful approaches to solving MaxSat instances arising from real world applications is the Implicit Hitting Set (IHS) approach. IHS solvers are complete MaxSat solvers that harness the strengths of both Boolean Satisfiability (SAT) and Integer Linear Programming (IP) solvers by decoupling core-extraction and optimization. While such solvers show state-of-the-art performance on many instances, it is known that there exist MaxSat instances on which IHS solvers need to extract an exponential number of cores before terminating. Motivated by the structure of the simplest of these problematic instances, we propose a technique we call abstract cores that provides a compact representation for a potentially exponential number of regular cores. We demonstrate how to incorporate abstract core reasoning into the IHS algorithm and report on an empirical evaluation demonstrating that including abstract cores into a state-of-the-art IHS solver improves its performance enough to surpass the best performing solvers of the most recent 2019 MaxSat Evaluation.
has issue date	2020-06-26(xsd:dateTime)
bibo:doi	10.1007/978-3-030-51825-7_20
has license	no-cc
sha1sum (hex)	fc1791b85d290a46bdeef940b88dacafae137000
schema:url	https://doi.org/10.1007/978-3-030-51825-7_20
resource representing a document's title	Abstract Cores in Implicit Hitting Set MaxSat Solving
has PubMed Central identifier	PMC7326551
schema:publication	Theory and Applications of Satisfiability Testing - SAT 2020
resource representing a document's body	covid:fc1791b85d290a46bdeef940b88dacafae137000#body_text
is schema:about of	named entity 'NUMBER OF' named entity 'EMPIRICAL EVALUATION' named entity 'REAL' named entity 'optimization' named entity 'MaxSat' named entity 'SAT' named entity 'algorithm' named entity 'optimal solution' named entity 'algorithm' named entity 'subroutine' named entity 'cardinality constraints' named entity 'lower bound' named entity 'SAT solver' named entity 'MaxSat' named entity 'hitting set' named entity 'SAT solver' named entity 'MaxSat' named entity 'SAT solver' named entity 'hitting set' named entity 'SAT' named entity 'Algorithm' named entity 'Integer Linear Programming' named entity 'Algorithm' named entity 'unsatisfiable' named entity 'disjunction' named entity 'computationally hard' named entity 'SAT' named entity 'SAT solver' named entity 'SAT' named entity 'upper bound' named entity 'MaxSat' named entity 'algorithm' named entity 'satisfiable' named entity 'exchangeability' named entity 'optimal solution' named entity 'compact representation' named entity 'UWr' named entity 'heuristic' named entity 'cnf' named entity 'SAT solver' named entity 'Optimization Problem' named entity 'MaxSat' named entity 'MaxSat' named entity 'optimal solution' named entity 'large number of cores' named entity 'lower bound' named entity 'SAT solver' named entity 'compact representation' named entity 'computing' named entity 'MaxSat' named entity 'inference' named entity 'Algorithm' named entity 'Algorithm' named entity 'SAT solver' named entity 'satisfiable' named entity 'MaxSat' named entity 'Algorithm' named entity 'optimal solution' named entity 'Algorithm' named entity 'MaxSat' named entity 'cardinality constraints' named entity 'hierarchical clusters' named entity 'integer' named entity 'UWr' named entity 'exchangeability' named entity 'Computing' named entity 'optimal solution' named entity 'algorithm' named entity 'lower bound' named entity 'optimization problem' named entity 'hitting set' named entity 'lower bound' named entity 'algorithm' named entity 'lower bound' named entity 'SAT solver' named entity 'Boolean Satisfiability' named entity 'cnf' named entity 'MaxSat' named entity 'line 7' named entity 'compact representation' named entity 'MaxSat'

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software