Font Size:

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

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.

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.

#### Keywords

Constraints; Learning; Filtering Algorithms

Full Text:
PDF