AAAI Publications, Sixth Annual Symposium on Combinatorial Search

Font Size: 
GAC for a Linear Inequality and an Atleast Constraint with an Application to Learning Simple Polynomials
Naina Razakarison, Mats Carlsson, Nicolas Beldiceanu, Helmut Simonis

Last modified: 2013-06-19

Abstract


We provide a filtering algorithm achieving GAC for the conjunction of constraints atleast (b, [x(0),x(1),...,x(n-1)], V) and (a(0)*x(0) +...+ a(n-1)*x(n-1)) <= c,  where the atleast constraint enforces
b variables out of x(0), x(1), ..., x(n-1) to be assigned to a
value in the set V. This work was motivated by learning simple
polynomials, i.e. finding the coefficients of polynomials
in several variables from example parameter and function values.
We additionally require that coefficients be integers, and
that most coefficients be assigned to zero or integers close to
0. These problems occur in the context of learning constraint
models from sample solutions of different sizes. Experiments
with this more global filtering show an improvement by several
orders of magnitude compared to handling the constraints
in isolation or with cost gcc, while also out-performing a
0/1 MIP model of the problem.

Full Text: PDF