On Irrelevant Literals in Pseudo-Boolean Constraint Learning

• URL: http://arxiv.org/abs/2012.04424v1
• Date: Tue, 8 Dec 2020 13:52:09 GMT
• Title: On Irrelevant Literals in Pseudo-Boolean Constraint Learning
• Authors: Danel Le Berre, Pierre Marquis, Stefan Mengel, Romain Wallon
• Abstract summary: We show that emphirrelevant literals may lead to infer constraints that are weaker than they should be. This suggests that current implementations of PB solvers based on cutting planes should be reconsidered to prevent the generation of irrelevant literals.
• Score: 21.506382989223784
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning pseudo-Boolean (PB) constraints in PB solvers exploiting cutting planes based inference is not as well understood as clause learning in conflict-driven clause learning solvers. In this paper, we show that PB constraints derived using cutting planes may contain \emph{irrelevant literals}, i.e., literals whose assigned values (whatever they are) never change the truth value of the constraint. Such literals may lead to infer constraints that are weaker than they should be, impacting the size of the proof built by the solver, and thus also affecting its performance. This suggests that current implementations of PB solvers based on cutting planes should be reconsidered to prevent the generation of irrelevant literals. Indeed, detecting and removing irrelevant literals is too expensive in practice to be considered as an option (the associated problem is NP-hard.

Related papers

• Learning General Continuous Constraint from Demonstrations via Positive-Unlabeled Learning [8.361428709513476]
  This paper presents a positive-unlabeled (PU) learning approach to infer a continuous, arbitrary and possibly nonlinear, constraint from demonstration. The effectiveness of the proposed method is validated in two Mujoco environments.
  arXiv  Detail & Related papers  (2024-07-23T14:00:18Z)
• On the Correspondence of Non-flat Assumption-based Argumentation and Logic Programming with Negation as Failure in the Head [20.981256612743145]
  We show a correspondence between non-flat ABA and LPs with negation as failure in their head. We then extend this result to so-called set-stable ABA semantics, originally defined for the fragment of non-flat ABA called bipolar ABA. We showcase how to define set-stable semantics for LPs with negation as failure in their head and show the correspondence to set-stable ABA semantics.
  arXiv  Detail & Related papers  (2024-05-15T15:10:03Z)
• ConstraintChecker: A Plugin for Large Language Models to Reason on Commonsense Knowledge Bases [53.29427395419317]
  Reasoning over Commonsense Knowledge Bases (CSKB) has been explored as a way to acquire new commonsense knowledge. We propose **ConstraintChecker**, a plugin over prompting techniques to provide and check explicit constraints.
  arXiv  Detail & Related papers  (2024-01-25T08:03:38Z)
• Using Integer Constraint Solving in Reuse Based Requirements Engineering [0.0]
  Product Lines (PL) have proved an effective approach to reuse-based configurations. It is now widely acknowledged that a product can be considered as a constraint satisfaction problem. It is natural to consider constraint programming as a first choice candidate to specify constraints on PL. This paper proposes to further explore the use of integer constraint programming to specify PL constraints.
  arXiv  Detail & Related papers  (2023-09-28T09:20:07Z)
• Interpretability at Scale: Identifying Causal Mechanisms in Alpaca [62.65877150123775]
  We use Boundless DAS to efficiently search for interpretable causal structure in large language models while they follow instructions. Our findings mark a first step toward faithfully understanding the inner-workings of our ever-growing and most widely deployed language models.
  arXiv  Detail & Related papers  (2023-05-15T17:15:40Z)
• APOLLO: A Simple Approach for Adaptive Pretraining of Language Models for Logical Reasoning [73.3035118224719]
  We propose APOLLO, an adaptively pretrained language model that has improved logical reasoning abilities. APOLLO performs comparably on ReClor and outperforms baselines on LogiQA.
  arXiv  Detail & Related papers  (2022-12-19T07:40:02Z)
• Online Selective Classification with Limited Feedback [82.68009460301585]
  We study selective classification in the online learning model, wherein a predictor may abstain from classifying an instance. Two salient aspects of the setting we consider are that the data may be non-realisable, due to which abstention may be a valid long-term action. We construct simple versioning-based schemes for any $mu in (0,1],$ that make most $Tmu$ mistakes while incurring smash$tildeO(T1-mu)$ excess abstention against adaptive adversaries.
  arXiv  Detail & Related papers  (2021-10-27T08:00:53Z)
• Sufficient reasons for classifier decisions in the presence of constraints [9.525900373779395]
  Recent work has unveiled a theory for reasoning about the decisions made by binary classifiers. We propose a more general theory, tailored to taking constraints into account. We prove that this simple idea results in reasons that are no less (and sometimes more) succinct.
  arXiv  Detail & Related papers  (2021-05-12T23:36:12Z)
• Please Mind the Root: Decoding Arborescences for Dependency Parsing [67.71280539312536]
  We analyze the output of state-of-the-arts on many languages from the Universal Dependency Treebank. The worst constraint-violation rate we observe is 24%.
  arXiv  Detail & Related papers  (2020-10-06T08:31:14Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)
• On Weakening Strategies for PB Solvers [19.78156213005998]
  Current pseudo-Boolean solvers implement different variants of the cutting planes proof system to infer new constraints during conflict analysis. One of these variants is generalized resolution, which allows to infer strong constraints, but suffers from the growth of coefficients it generates. Another variant consists in using weakening and division, which is more efficient in practice but may infer weaker constraints.
  arXiv  Detail & Related papers  (2020-05-09T15:40:55Z)

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.