Modular Constraint Solver Cooperation via Abstract Interpretation

• URL: http://arxiv.org/abs/2008.01415v2
• Date: Mon, 14 Sep 2020 10:01:14 GMT
• Title: Modular Constraint Solver Cooperation via Abstract Interpretation
• Authors: Pierre Talbot, \'Eric Monfroy and Charlotte Truchet
• Abstract summary: We propose a modular framework in which solvers and cooperation schemes can be seamlessly added and combined. We contribute to two new cooperation schemes: (i) interval propagators that allows abstract domains to exchange bound constraints, and (ii) delayed product which exchanges over-approximations of constraints between two abstract domains.
• Score: 1.160208922584163
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cooperation among constraint solvers is difficult because different solving paradigms have different theoretical foundations. Recent works have shown that abstract interpretation can provide a unifying theory for various constraint solvers. In particular, it relies on abstract domains which capture constraint languages as ordered structures. The key insight of this paper is viewing cooperation schemes as abstract domains combinations. We propose a modular framework in which solvers and cooperation schemes can be seamlessly added and combined. This differs from existing approaches such as SMT where the cooperation scheme is usually fixed (e.g., Nelson-Oppen). We contribute to two new cooperation schemes: (i) interval propagators completion that allows abstract domains to exchange bound constraints, and (ii) delayed product which exchanges over-approximations of constraints between two abstract domains. Moreover, the delayed product is based on delayed goal of logic programming, and it shows that abstract domains can also capture control aspects of constraint solving. Finally, to achieve modularity, we propose the shared product to combine abstract domains and cooperation schemes. Our approach has been fully implemented, and we provide various examples on the flexible job shop scheduling problem. Under consideration for acceptance in TPLP.

Related papers

• Domain Expansion: A Latent Space Construction Framework for Multi-Task Learning [26.322513515274764]
  Training a single network with multiple objectives often leads to conflicting gradients that degrade shared representations.<n>We introduce Domain Expansion, a framework that prevents these conflicts by restructuring the latent space itself.
  arXiv  Detail & Related papers  (2026-01-27T21:30:21Z)
• Multi-Agent Constraint Factorization Reveals Latent Invariant Solution Structure [0.0]
  Multi-agent systems (MAS) composed of large language models often exhibit improved problem-solving performance despite operating on identical information.<n>We model each agent as enforcing a distinct family of validity constraints on a shared solution state, and show that a MAS implements a factorized composition of constraint-enforcement operators.<n>We extend this result from exact constraint enforcement to soft constraints via proximal operators, and apply the formalism to contemporary text-based dialog systems.
  arXiv  Detail & Related papers  (2026-01-21T15:23:04Z)
• Decoupling Constraint from Two Direction in Evolutionary Constrained Multi-objective Optimization [26.967831462095067]
  We propose a novel algorithm named Decoupling Constraint from Two Directions (DCF2D)<n>It periodically detects constraint couplings and spawns an auxiliary population for each relevant constraint with an appropriate search direction.<n>Experiments on seven challenging CMOP benchmark suites and on a collection of real-world CMOPs demonstrate that DCF2D outperforms five state-of-the-art CMOEAs.
  arXiv  Detail & Related papers  (2025-12-30T02:22:32Z)
• Synergy over Discrepancy: A Partition-Based Approach to Multi-Domain LLM Fine-Tuning [9.97195966127976]
  Large language models (LLMs) demonstrate impressive generalization abilities, yet adapting them effectively across multiple heterogeneous domains remains challenging.<n>We propose a partition-based multi-stage fine-tuning framework designed to exploit inter-domain synergies while minimizing negative transfer.<n>Our approach strategically partitions domains into subsets (stages) by balancing domain discrepancy, synergy, and model capacity constraints.
  arXiv  Detail & Related papers  (2025-11-10T15:27:26Z)
• LLM4CMO: Large Language Model-aided Algorithm Design for Constrained Multiobjective Optimization [54.35609820607923]
  Large language models (LLMs) offer new opportunities for assisting with algorithm design.<n>We propose LLM4CMO, a novel CMOEA based on a dual-population, two-stage framework.<n>LLMs can serve as efficient co-designers in the development of complex evolutionary optimization algorithms.
  arXiv  Detail & Related papers  (2025-08-16T02:00:57Z)
• Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
  Chain-of-Thought (CoT) prompting enhances the reasoning of large language models (LLMs) by decomposing problems into sequential steps. We propose Syzygy of Thoughts (SoT)-a novel framework that extends CoT by introducing auxiliary, interrelated reasoning paths. SoT captures deeper logical dependencies, enabling more robust and structured problem-solving.
  arXiv  Detail & Related papers  (2025-04-13T13:35:41Z)
• Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
  We propose SEQUOIA, an RL algorithm that directly optimize for long-term reward over the feasible action space. We empirically validate SEQUOIA on four novel restless bandit problems with constraints: multiple interventions, path constraints, bipartite matching, and capacity constraints.
  arXiv  Detail & Related papers  (2025-03-01T21:25:21Z)
• When Disagreements Elicit Robustness: Investigating Self-Repair Capabilities under LLM Multi-Agent Disagreements [56.29265568399648]
  We argue that disagreements prevent premature consensus and expand the explored solution space.<n>Disagreements on task-critical steps can derail collaboration depending on the topology of solution paths.
  arXiv  Detail & Related papers  (2025-02-21T02:24:43Z)
• Mitigating Hallucinations in Multimodal Spatial Relations through Constraint-Aware Prompting [7.962140902232628]
  Spatial relation hallucinations pose a persistent challenge in large vision-language models (LVLMs) We propose a constraint-aware prompting framework designed to reduce spatial relation hallucinations.
  arXiv  Detail & Related papers  (2025-02-12T11:32:19Z)
• Athanor: Local Search over Abstract Constraint Specifications [2.3383199519492455]
  We focus on general-purpose local search solvers that accept as input a constraint model. The Athanor solver we describe herein differs in that it begins from a specification of a problem in the abstract constraint specification language Essence.
  arXiv  Detail & Related papers  (2024-10-08T11:41:38Z)
• Composable Part-Based Manipulation [61.48634521323737]
  We propose composable part-based manipulation (CPM) to improve learning and generalization of robotic manipulation skills. CPM comprises a collection of composable diffusion models, where each model captures a different inter-object correspondence. We validate our approach in both simulated and real-world scenarios, demonstrating its effectiveness in achieving robust and generalized manipulation capabilities.
  arXiv  Detail & Related papers  (2024-05-09T16:04:14Z)
• Compositional Diffusion-Based Continuous Constraint Solvers [98.1702285470628]
  This paper introduces an approach for learning to solve continuous constraint satisfaction problems (CCSP) in robotic reasoning and planning. By contrast, our model, the compositional diffusion continuous constraint solver (Diffusion-CCSP), derives global solutions to CCSPs.
  arXiv  Detail & Related papers  (2023-09-02T15:20:36Z)
• Multi-Grained Multimodal Interaction Network for Entity Linking [65.30260033700338]
  Multimodal entity linking task aims at resolving ambiguous mentions to a multimodal knowledge graph. We propose a novel Multi-GraIned Multimodal InteraCtion Network $textbf(MIMIC)$ framework for solving the MEL task.
  arXiv  Detail & Related papers  (2023-07-19T02:11:19Z)
• Recursion of Thought: A Divide-and-Conquer Approach to Multi-Context Reasoning with Language Models [58.41943058963672]
  We propose a new inference framework called Recursion of Thought (RoT) RoT introduces several special tokens that the models can output to trigger context-related operations. Experiments with multiple architectures including GPT-3 show that RoT dramatically improves LMs' inference capability to solve problems.
  arXiv  Detail & Related papers  (2023-06-12T06:34:16Z)
• Multipartite entanglement theory with entanglement-nonincreasing operations [91.3755431537592]
  We extend the resource theory of entanglement for multipartite systems beyond the standard framework of local operations and classical communication. We demonstrate that in this adjusted framework, the transformation rates between multipartite states are fundamentally dictated by the bipartite entanglement entropies of the respective quantum states.
  arXiv  Detail & Related papers  (2023-05-30T12:53:56Z)
• Optimal Control of Logically Constrained Partially Observable and Multi-Agent Markov Decision Processes [5.471640959988549]
  We first introduce an optimal control theory for partially observable Markov decision processes. We provide a structured methodology for synthesizing policies that maximize a cumulative reward. We then build on this approach to design an optimal control framework for logically constrained multi-agent settings.
  arXiv  Detail & Related papers  (2023-05-24T05:15:36Z)
• Jointly Learning Consistent Causal Abstractions Over Multiple Interventional Distributions [8.767175335575386]
  An abstraction can be used to relate two structural causal models representing the same system at different levels of resolution. We introduce a first framework for causal abstraction learning between SCMs based on the formalization of abstraction recently proposed by Rischel.
  arXiv  Detail & Related papers  (2023-01-14T11:22:16Z)
• UNIFY: a Unified Policy Designing Framework for Solving Constrained Optimization Problems with Machine Learning [18.183339583346005]
  We propose a unified framework to design a solution policy for complex decision-making problems. Our approach relies on a clever decomposition of the policy in two stages, namely an unconstrained ML model and a CO problem. We demonstrate the method effectiveness on two practical problems, namely an Energy Management System and the Set Multi-cover with coverage requirements.
  arXiv  Detail & Related papers  (2022-10-25T14:09:24Z)
• Constraint Answer Set Programming: Integrational and Translational (or SMT-based) Approaches [2.0559497209595814]
  Constraint answer set programming or CASP, for short, is a hybrid approach in automated reasoning. It puts together the advances of distinct research areas such as answer set programming, constraint processing, and satisfiability modulo theories. It opens new horizons for declarative programming applications such as solving complex train scheduling problems.
  arXiv  Detail & Related papers  (2021-07-17T14:58:57Z)
• 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)

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.