Jovial Cheukam Ngouonou, Ramiz Gindullin, Claude-Guy Quimper et al.
We present an improved incremental selection algorithm of the selection algorithm presented in [1] and prove all the selected conjectures.
Jovial Cheukam-Ngouonou, Ramiz Gindullin, Nicolas Beldiceanu et al.
We present the proofs of the conjectures mentioned in the paper published in the proceedings of the 2024 AAAI conference [1], and discovered by the decomposition methods presented in the same paper.
Christian Bessiere, Clement Carbonnel, Anton Dries et al.
Learning constraint networks is known to require a number of membership queries exponential in the number of variables. In this paper, we learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm, called QUACQ, that, given a negative example, focuses onto a constraint of the target network in a number of queries logarithmic in the size of the example. The whole constraint network can then be learned with a polynomial number of partial queries. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases.
Nicolas Beldiceanu, Mats Carlsson, Claude-Guy Quimper et al.
Given, a sequence $\mathcal{X}$ of $n$ variables, a time-series constraint ctr using the Sum aggregator, and a sliding time-series constraint enforcing the constraint ctr on each sliding window of $\mathcal{X}$ of $m$ consecutive variables, we describe a $Θ(n)$ time complexity checker, as well as a $Θ(n)$ space complexity reformulation for such sliding constraint.
Gilles Pesant, Claude-Guy Quimper, Alessandro Zanarini
Designing a search heuristic for constraint programming that is reliable across problem domains has been an important research topic in recent years. This paper concentrates on one family of candidates: counting-based search. Such heuristics seek to make branching decisions that preserve most of the solutions by determining what proportion of solutions to each individual constraint agree with that decision. Whereas most generic search heuristics in constraint programming rely on local information at the level of the individual variable, our search heuristics are based on more global information at the constraint level. We design several algorithms that are used to count the number of solutions to specific families of constraints and propose some search heuristics exploiting such information. The experimental part of the paper considers eight problem domains ranging from well-established benchmark puzzles to rostering and sport scheduling. An initial empirical analysis identifies heuristic maxSD as a robust candidate among our proposals.eWe then evaluate the latter against the state of the art, including the latest generic search heuristics, restarts, and discrepancy-based tree traversals. Experimental results show that counting-based search generally outperforms other generic heuristics.