SODA

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

Razakarison, Naina and Beldiceanu, Nicolas and Carlsson, Mats and Simonis, Helmut (2013) GAC for a Linear Inequality and an Atleast Constraint with an Application to Learning Simple Polynomials. In: Symposium on Combinatorial Search, SOCS 2013, 11-13 July 2013, Leavenworth, WA, USA.

Full text not available from this repository.

Official URL: http://www.aaai.org/ocs/index.php/SOCS/SOCS13/pape...

Abstract

We provide a filtering algorithm achieving GAC for the conjunction of constraints AtLeast(b,[x[0],x[1],...,x[n-1]],V) /\ Sum(i in 0..n-1)(a[i] c[i]) <= c where the AtLeast constraint enforces at least b variables out of x[0], x[1], ..., x[n-1] to be assigned 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 CostGCC, while also out-performing a 0/1 MIP model of the problem.

Item Type:Conference or Workshop Item (Paper)
Uncontrolled Keywords:Constraints, Learning, Filtering Algorithms
ID Code:5688
Deposited By:Mats Carlsson
Deposited On:09 Jul 2014 14:16
Last Modified:09 Jul 2014 14:16

Repository Staff Only: item control page