XCSP3: An Integrated Format for Benchmarking Combinatorial Constrained Problems

• URL: http://arxiv.org/abs/1611.03398v5
• Date: Thu, 29 Aug 2024 09:26:01 GMT
• Title: XCSP3: An Integrated Format for Benchmarking Combinatorial Constrained Problems
• Authors: Frederic Boussemart, Christophe Lecoutre, Gilles Audemard, Cédric Piette,
• Abstract summary: The new format is made compact, highly readable, and rather easy to parse. XCSP3 encompasses practically all constraints that can be found in major constraint solvers. The user can make sophisticated queries for selecting instances from very precise criteria.
• Score: 3.149883354098941
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We propose a major revision of the format XCSP 2.1, called XCSP3, to build integrated representations of combinatorial constrained problems. This new format is able to deal with mono/multi optimization, many types of variables, cost functions, reification, views, annotations, variable quantification, distributed, probabilistic and qualitative reasoning. The new format is made compact, highly readable, and rather easy to parse. Interestingly, it captures the structure of the problem models, through the possibilities of declaring arrays of variables, and identifying syntactic and semantic groups of constraints. The number of constraints is kept under control by introducing a limited set of basic constraint forms, and producing almost automatically some of their variations through lifting, restriction, sliding, logical combination and relaxation mechanisms. As a result, XCSP3 encompasses practically all constraints that can be found in major constraint solvers developed by the CP community. A website, which is developed conjointly with the format, contains many models and series of instances. The user can make sophisticated queries for selecting instances from very precise criteria. The objective of XCSP3 is to ease the effort required to test and compare different algorithms by providing a common test-bed of combinatorial constrained instances.

Related papers

• Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity [59.57065228857247]
  Retrieval-augmented Large Language Models (LLMs) have emerged as a promising approach to enhancing response accuracy in several tasks, such as Question-Answering (QA) We propose a novel adaptive QA framework, that can dynamically select the most suitable strategy for (retrieval-augmented) LLMs based on the query complexity. We validate our model on a set of open-domain QA datasets, covering multiple query complexities, and show that ours enhances the overall efficiency and accuracy of QA systems.
  arXiv  Detail & Related papers  (2024-03-21T13:52:30Z)
• Toward Unified Controllable Text Generation via Regular Expression Instruction [56.68753672187368]
  Our paper introduces Regular Expression Instruction (REI), which utilizes an instruction-based mechanism to fully exploit regular expressions' advantages to uniformly model diverse constraints. Our method only requires fine-tuning on medium-scale language models or few-shot, in-context learning on large language models, and requires no further adjustment when applied to various constraint combinations.
  arXiv  Detail & Related papers  (2023-09-19T09:05:14Z)
• ACE, a generic constraint solver [1.550120821358415]
  Constraint Programming (CP) is a useful technology for modeling and solving constrained problems. This paper presents ACE, an open-source constraint solver developed in Java.
  arXiv  Detail & Related papers  (2023-01-06T12:15:18Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Personalized Federated Learning via Convex Clustering [72.15857783681658]
  We propose a family of algorithms for personalized federated learning with locally convex user costs. The proposed framework is based on a generalization of convex clustering in which the differences between different users' models are penalized.
  arXiv  Detail & Related papers  (2022-02-01T19:25:31Z)
• Lifting Symmetry Breaking Constraints with Inductive Logic Programming [2.036811219647753]
  We introduce a new model-oriented approach for Answer Set Programming that lifts the Symmetry Breaking Constraints into a set of interpretable first-order constraints. Experiments demonstrate the ability of our framework to learn general constraints from instance-specific SBCs.
  arXiv  Detail & Related papers  (2021-12-22T11:27:48Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classes is a new structural framework which permits generalization in reinforcement learning. The framework incorporates nearly all existing models in which a sample complexity is achievable. Our main result provides an RL algorithm which has sample complexity for Bilinear Classes.
  arXiv  Detail & Related papers  (2021-03-19T16:34:20Z)
• Handling Hard Affine SDP Shape Constraints in RKHSs [3.8073142980733]
  We propose a unified and modular convex optimization framework to encode hard affine SDP constraints on function derivatives. We prove the consistency of the proposed scheme and that of its adaptive variant, leveraging geometric properties of vRKHSs.
  arXiv  Detail & Related papers  (2021-01-05T14:08:58Z)
• XCSP3-core: A Format for Representing Constraint Satisfaction/Optimization Problems [3.149883354098941]
  XCSP3-core is a subset of XCSP3 that allows us to represent constraint satisfaction/optimization problems. XCSP3-core callbacks written in Java and C++ (using functions) defining a core format for comparisons (competitions) of constraint solvers.
  arXiv  Detail & Related papers  (2020-09-01T15:24:49Z)
• 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)
• An ASP semantics for Constraints involving Conditional Aggregates [9.289905977910378]
  We elaborate upon the formal foundations of hybrid Answer Set Programming (ASP) We extend its underlying logical framework with aggregate functions over constraint values and variables. We put some emphasis on logic programs with linear constraints and show how common ASP aggregates can be regarded as particular cases of so-called conditional linear constraints.
  arXiv  Detail & Related papers  (2020-02-17T12:25:01Z)

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.