GAC for a Linear Inequality and an Atleast Constraint with an Application to Learning Simple Polynomials

Proceedings of the International Symposium on Combinatorial Search, 6

Volume

Vol. 6 No. 1 (2013): Sixth Annual Symposium on Combinatorial Search

Full Papers

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 enforcesb variables out of x(0), x(1), ..., x(n-1) to be assigned to avalue in the set V. This work was motivated by learning simplepolynomials, i.e. finding the coefficients of polynomialsin several variables from example parameter and function values.We additionally require that coefficients be integers, andthat most coefficients be assigned to zero or integers close to0. These problems occur in the context of learning constraintmodels from sample solutions of different sizes. Experimentswith this more global filtering show an improvement by severalorders of magnitude compared to handling the constraintsin isolation or with cost gcc, while also out-performing a0/1 MIP model of the problem.

10.1609/socs.v4i1.18280