An efficient heuristic approach combining maximal itemsets and area measure for compressing voluminous table constraints

• URL: http://arxiv.org/abs/2203.11208v1
• Date: Mon, 21 Mar 2022 08:41:15 GMT
• Title: An efficient heuristic approach combining maximal itemsets and area measure for compressing voluminous table constraints
• Authors: Soufia Bennai, Kamala Amroun, Samir Loudni and Abdelkader Ouali
• Abstract summary: The table constraint is perhaps the most significant-being the most well-studied-and has the ability to encode any other constraints defined on finite variables. To reduce space and the time complexity, researchers have focused on various forms of compression. We propose a new approach based on maximal frequent itemsets technique and area measure for enumerating the maximal frequent itemsets relevant for compressing table constraints.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Constraint Programming is a powerful paradigm to model and solve combinatorial problems. While there are many kinds of constraints, the table constraint is perhaps the most significant-being the most well-studied and has the ability to encode any other constraints defined on finite variables. However, constraints can be very voluminous and their size can grow exponentially with their arity. To reduce space and the time complexity, researchers have focused on various forms of compression. In this paper we propose a new approach based on maximal frequent itemsets technique and area measure for enumerating the maximal frequent itemsets relevant for compressing table constraints. Our experimental results show the effectiveness and efficiency of this approach on compression and on solving compressed table constraints.

Related papers

• Submodular Maximization under the Intersection of Matroid and Knapsack Constraints [23.0838604893412]
  We consider the problem of submodular operations under the intersection of two commonly used constraints, i.e., $k$matroid constraint and $m$-knapsack constraint. We prove that SPROUTOUT can achieve a SPR-time approximation guarantee better than incorporating state-of-the-art algorithms. Experiments on the applications of movie recommendation and weighted max-cut demonstrate the superiority of SPROUT++ in practice.
  arXiv  Detail & Related papers  (2023-07-18T02:37:14Z)
• Neural Fields with Hard Constraints of Arbitrary Differential Order [61.49418682745144]
  We develop a series of approaches for enforcing hard constraints on neural fields. The constraints can be specified as a linear operator applied to the neural field and its derivatives. Our approaches are demonstrated in a wide range of real-world applications.
  arXiv  Detail & Related papers  (2023-06-15T08:33:52Z)
• Hybrid Quantum Algorithms integrating QAOA, Penalty Dephasing and Zeno Effect for Solving Binary Optimization Problems with Multiple Constraints [5.259170150405252]
  This paper presents a hybrid framework that combines the use of standard Ising Hamiltonians to solve a subset of the constraints. The resolution of these non-Ising constraints is achieved through either penalty dephasing or the quantum Zeno effect.
  arXiv  Detail & Related papers  (2023-05-14T03:49:10Z)
• Solving Quantum-Inspired Perfect Matching Problems via Tutte's Theorem-Based Hybrid Boolean Constraints [39.96302127802424]
  We study a new application of hybrid Boolean constraints, which arises in quantum computing. The problem relates to constrained perfect matching in edge-colored graphs. We show that direct encodings of the constrained-matching problem as hybrid constraints scale poorly and special techniques are still needed.
  arXiv  Detail & Related papers  (2023-01-24T06:14:24Z)
• 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)
• Learning, compression, and leakage: Minimising classification error via meta-universal compression principles [87.054014983402]
  A promising group of compression techniques for learning scenarios is normalised maximum likelihood (NML) coding. Here we consider a NML-based decision strategy for supervised classification problems, and show that it attains PAC learning when applied to a wide variety of models. We show that the misclassification rate of our method is upper bounded by the maximal leakage, a recently proposed metric to quantify the potential of data leakage in privacy-sensitive scenarios.
  arXiv  Detail & Related papers  (2020-10-14T20:03:58Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)
• 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)
• Constrained episodic reinforcement learning in concave-convex and knapsack settings [81.08055425644037]
  We provide a modular analysis with strong theoretical guarantees for settings with concave rewards and convex constraints. Our experiments demonstrate that the proposed algorithm significantly outperforms these approaches in existing constrained episodic environments.
  arXiv  Detail & Related papers  (2020-06-09T05:02:44Z)
• Submodular Bandit Problem Under Multiple Constraints [8.100450025624443]
  We introduce a submodular bandit problem under the intersection of $l$ knapsacks and a $k$-system constraint. To solve this problem, we propose a non-greedy algorithm that adaptively focuses on a standard or modified upper-confidence bound. We provide a high-probability upper bound of an approximation regret, where the approximation ratio matches that of a fast algorithm.
  arXiv  Detail & Related papers  (2020-06-01T01:28:44Z)

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.