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

• ECon: On the Detection and Resolution of Evidence Conflicts [56.89209046429291]
  The rise of large language models (LLMs) has significantly influenced the quality of information in decision-making systems. This study introduces a method for generating diverse, validated evidence conflicts to simulate real-world misinformation scenarios.
  arXiv  Detail & Related papers  (2024-10-05T07:41:17Z)
• AdaCAD: Adaptively Decoding to Balance Conflicts between Contextual and Parametric Knowledge [57.66282463340297]
  Knowledge conflict arises from discrepancies between information in the context of a large language model (LLM) and the knowledge stored in its parameters. We propose a fine-grained, instance-level approach called AdaCAD, which dynamically infers the weight of adjustment based on the degree of conflict.
  arXiv  Detail & Related papers  (2024-09-11T16:35:18Z)
• ConflictBank: A Benchmark for Evaluating the Influence of Knowledge Conflicts in LLM [36.332500824079844]
  Large language models (LLMs) have achieved impressive advancements across numerous disciplines, yet the critical issue of knowledge conflicts has rarely been studied. We present ConflictBank, the first comprehensive benchmark developed to evaluate knowledge conflicts from three aspects. Our investigation delves into four model families and twelve LLM instances, meticulously analyzing conflicts stemming from misinformation, temporal discrepancies, and semantic divergences.
  arXiv  Detail & Related papers  (2024-08-22T02:33:13Z)
• Differentiating Choices via Commonality for Multiple-Choice Question Answering [54.04315943420376]
  Multiple-choice question answering can provide valuable clues for choosing the right answer. Existing models often rank each choice separately, overlooking the context provided by other choices. We propose a novel model by differentiating choices through identifying and eliminating their commonality, called DCQA.
  arXiv  Detail & Related papers  (2024-08-21T12:05:21Z)
• 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)
• 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)
• 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)
• 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.