A Deep Dive into Conflict Generating Decisions
- URL: http://arxiv.org/abs/2105.04595v1
- Date: Mon, 10 May 2021 18:17:52 GMT
- Title: A Deep Dive into Conflict Generating Decisions
- Authors: Md Solimul Chowdhury, Martin M\"uller, Jia You
- Abstract summary: We use Conflict Driven Clause Learning to solve Satisfiability (SAT) problems.
We show that CDCL learns clauses from conflicts, a technique that allows a solver to prune its search space.
We develop Common Reason Variable Reduction (CRVR) as a new decision strategy that reduces the selection priority of some variables from the learned clauses of mc decisions.
- Score: 3.222802562733787
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Boolean Satisfiability (SAT) is a well-known NP-complete problem. Despite
this theoretical hardness, SAT solvers based on Conflict Driven Clause Learning
(CDCL) can solve large SAT instances from many important domains. CDCL learns
clauses from conflicts, a technique that allows a solver to prune its search
space. The selection heuristics in CDCL prioritize variables that are involved
in recent conflicts. While only a fraction of decisions generate any conflicts,
many generate multiple conflicts.
In this paper, we study conflict-generating decisions in CDCL in detail. We
investigate the impact of single conflict (sc) decisions, which generate only
one conflict, and multi-conflict (mc) decisions which generate two or more. We
empirically characterize these two types of decisions based on the quality of
the learned clauses produced by each type of decision. We also show an
important connection between consecutive clauses learned within the same mc
decision, where one learned clause triggers the learning of the next one
forming a chain of clauses. This leads to the consideration of similarity
between conflicts, for which we formulate the notion of conflictsproximity as a
similarity measure. We show that conflicts in mc decisions are more closely
related than consecutive conflicts generated from sc decisions. Finally, we
develop Common Reason Variable Reduction (CRVR) as a new decision strategy that
reduces the selection priority of some variables from the learned clauses of mc
decisions. Our empirical evaluation of CRVR implemented in three leading
solvers demonstrates performance gains in benchmarks from the main track of SAT
Competition-2020.
Related papers
- Configurable Mirror Descent: Towards a Unification of Decision Making [36.42770584314967]
Various methods are proposed to address the specific decision-making problems.
Despite the successes in specific categories, these methods typically evolve independently and cannot generalize to other categories.
This work presents a preliminary attempt to address the question with three main contributions.
arXiv Detail & Related papers (2024-05-20T03:10:22Z) - Selecting the Most Conflicting Pair of Candidates [6.838139628413773]
We study committee elections from a perspective of finding the most conflicting candidates, that is, candidates that imply the largest amount of conflict, as per voter preferences.
By proposing basic axioms to capture this objective, we show that none of the prominent multiwinner voting rules meet them.
A subsequent deepened analysis sheds more light on how they operate.
arXiv Detail & Related papers (2024-05-09T16:00:20Z) - Resolving Knowledge Conflicts in Large Language Models [48.92369530853202]
Large language models (LLMs) often encounter knowledge conflicts.
We ask what are the desiderata for LLMs when a knowledge conflict arises and whether existing LLMs fulfill them.
We introduce KNOWLEDGE CONFLICT, an evaluation framework for simulating contextual knowledge conflicts.
arXiv Detail & Related papers (2023-10-02T06:57:45Z) - Rehearsal: Simulating Conflict to Teach Conflict Resolution [54.32934135393982]
Rehearsal is a system that allows users to rehearse conflicts with a believable simulated interlocutor.
Users can utilize Rehearsal to practice handling a variety of predefined conflict scenarios.
Rehearsal uses IRP to generate utterances grounded in conflict resolution theory.
arXiv Detail & Related papers (2023-09-21T17:59:20Z) - SCREWS: A Modular Framework for Reasoning with Revisions [58.698199183147935]
We present SCREWS, a modular framework for reasoning with revisions.
We show that SCREWS unifies several previous approaches under a common framework.
We evaluate our framework with state-of-the-art LLMs on a diverse set of reasoning tasks.
arXiv Detail & Related papers (2023-09-20T15:59:54Z) - Causal Fairness Analysis [68.12191782657437]
We introduce a framework for understanding, modeling, and possibly solving issues of fairness in decision-making settings.
The main insight of our approach will be to link the quantification of the disparities present on the observed data with the underlying, and often unobserved, collection of causal mechanisms.
Our effort culminates in the Fairness Map, which is the first systematic attempt to organize and explain the relationship between different criteria found in the literature.
arXiv Detail & Related papers (2022-07-23T01:06:34Z) - On the Complexity of Adversarial Decision Making [101.14158787665252]
We show that the Decision-Estimation Coefficient is necessary and sufficient to obtain low regret for adversarial decision making.
We provide new structural results that connect the Decision-Estimation Coefficient to variants of other well-known complexity measures.
arXiv Detail & Related papers (2022-06-27T06:20:37Z) - Modularity in Reinforcement Learning via Algorithmic Independence in
Credit Assignment [79.5678820246642]
We show that certain action-value methods are more sample efficient than policy-gradient methods on transfer problems that require only sparse changes to a sequence of previously optimal decisions.
We generalize the recently proposed societal decision-making framework as a more granular formalism than the Markov decision process.
arXiv Detail & Related papers (2021-06-28T21:29:13Z) - Learning to Resolve Conflicts for Multi-Agent Path Finding with
Conflict-Based Search [35.71926950656326]
Conflict-Based Search (CBS) is a state-of-the-art algorithm for path finding.
We propose a machine-learning framework for conflict selection that observes the decisions made by the oracle.
Our method significantly improves the success rates, the search tree sizes and runtimes over the current state-of-the-art CBS solver.
arXiv Detail & Related papers (2020-12-10T22:44:35Z) - Entangled and correlated photon mixed strategy for social decision
making [0.0]
We show that an optimal mixture of entangled- and correlated-photon-based strategies exists depending on the dynamics of the reward environment.
This study paves the way for utilizing both quantum and classical aspects of photons in a mixed manner for decision making.
arXiv Detail & Related papers (2020-10-25T10:57:50Z) - Resolving Head-On Conflicts for Multi-Agent Path Finding with
Conflict-Based Search [0.0]
Conflict-Based Search (CBS) is a popular framework for solving the Multi-Agent Path Finding problem.
This paper introduces a new technique, namely the head-on technique that finds out such conflicts.
Experimental results show that the head-on technique improves the state-of-the-art MAPF solver CBSH.
arXiv Detail & Related papers (2020-07-07T15:52:45Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.