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

Authors

  • Naina Razakarison ENS Cachan
  • Mats Carlsson Swedish Institute of Computer Science
  • Nicolas Beldiceanu Mines de Nantes
  • Helmut Simonis 4C, University College Cork

DOI:

https://doi.org/10.1609/socs.v4i1.18280

Keywords:

Constraints, Learning, Filtering Algorithms

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.

Downloads

Published

2021-08-20