8 Pages
English

On Learning Constraint Problems Arnaud Lallouet

-

Gain access to the library to view online
Learn more

Description

Niveau: Supérieur, Doctorat, Bac+8
On Learning Constraint Problems Arnaud Lallouet GREYC, University of Caen Caen, France EMail: Matthieu Lopez, Lionel Martin, Christel Vrain LIFO, University of Orleans Orleans, France EMail: Abstract— It is well known that modeling with constraints networks require a fair expertise. Thus tools able to automatically generate such networks have gained a major interest. The major contribution of this paper is to set a new framework based on Inductive Logic Programming able to build a constraint model from solutions and non-solutions of related problems. The model is expressed in a middle-level modeling language. On this particular relational learning problem, traditional top-down search falls into blind search and bottom-up search produces too expensive coverage tests. Recent works in Inductive Logic Programming about phase transition and crossing plateau show that no general solution can face all these difficulties. In this context, we have designed an algorithm combining the major qualities of these two types of search techniques. We present experimental results on some benchmarks ranging from puzzles to scheduling problems. I. INTRODUCTION Constraint Programming (CP) is a very successful for- malism to model and solve a wide range of decision prob- lems, from arithmetic puzzles to timetabling and industrial scheduling problems. However, it has been recognized by the community [1] that modeling in CP requires expert knowledge to be achieved successfully.

  • covers all

  • rules can

  • counter-examples only

  • l2 ?

  • algorithms like

  • modeling language

  • cps

  • learning

  • caen caen

  • cs such


Subjects

Informations

Published by
Reads 44
Language English

OnLearningConstraintProblems

ArnaudLallouetMatthieuLopez,LionelMartin,ChristelVrain
GREYC,UniversityofCaenLIFO,UniversityofOrle´ans
Caen,FranceOrle´ans,France
EMail:arnaud.lallouet@info.unicaen.frEMail:firstname.name@univ-orleans.fr

Abstract
—Itiswellknownthatmodelingwithconstraints
networksrequireafairexpertise.Thustoolsabletoautomatically
generatesuchnetworkshavegainedamajorinterest.Themajor
contributionofthispaperistosetanewframeworkbased
onInductiveLogicProgrammingabletobuildaconstraint
modelfromsolutionsandnon-solutionsofrelatedproblems.
Themodelisexpressedinamiddle-levelmodelinglanguage.On
thisparticularrelationallearningproblem,traditionaltop-down
searchfallsintoblindsearchandbottom-upsearchproduces
tooexpensivecoveragetests.RecentworksinInductiveLogic
Programmingaboutphasetransitionandcrossingplateaushow
thatnogeneralsolutioncanfaceallthesedifficulties.Inthis
context,wehavedesignedanalgorithmcombiningthemajor
qualitiesofthesetwotypesofsearchtechniques.Wepresent
experimentalresultsonsomebenchmarksrangingfrompuzzles
toschedulingproblems.
I.I
NTRODUCTION
ConstraintProgramming(CP)isaverysuccessfulfor-
malismtomodelandsolveawiderangeofdecisionprob-
lems,fromarithmeticpuzzlestotimetablingandindustrial
schedulingproblems.However,ithasbeenrecognizedbythe
community[1]thatmodelinginCPrequiresexpertknowledge
tobeachievedsuccessfully.Amajorproblemencounteredby
noviceusersisthattheyhaveaverylimitedknowledgeon
howtochoosethevariables,howtofindtheconstraintsand
howtoimprovetheirmodelinordertomakeitefficient.In
thisprocess,theactivityoffindingtheconstraintstobestated
isacrucialpartandalotofworkhasbeenspentonthe
understanding[2]andautomation[3]ofmodelingtasks.
Theproblemweaddressinthispaperistheautomatic
acquisitionofaconstraintmodelfromexamplesandcounter-
examplesofrelatedproblems.Toourbestknowledge,learning
aconstraintnetworkhasonlybeenaddressedbythesystem
CONACQin[4]andsubsequentpapers[3],[5]withaversion-
spacealgorithm.However,whileefficient,amajorlimitation
ofthisapproachisthattheuserhastoprovidetheexact
setofvariablesaswellassolutionsandnon-solutionsfor
herveryproblem.Itisquestionablethattheuserstillwants
tobuildamodelafterhavingfoundsomeofitssolutions.
Incontrast,andfromacognitivepointofview,itismore
likelythattheuserwantstomodelanewproblem,having
ontheshelfasetofexamplesandcounter-examplesonlyfor
somerelatedproblems.Toillustratethem,wecanconsider
thattheuserwantstomodelschooltimetablingproblem,
onlyhavingsolutionsandnon-solutionsgeneratedbyhand
tosomehistoricalinstancesfromthepastfewyears.These

problemsarealmostthesamebutthenumberofteachers,
groups,roomsmaybedifferent.Despitethegeneralization
toanactivelearningframework[5],itisstillrequiredwith
CONACQtoprovidejudgementsonpotentialsolutionsofthe
actualproblem.
SomemodelinglanguageslikeOPL[6],Essence’[7]or
MiniZinc[8]provideanactualframeworkformodeling
constraintproblemsatmiddle-levelofabstraction.Theuser
providesrulesandparameterswhicharecombinedina
rewritingprocesstogenerateaConstraintSatisfactionProblem
(CSP)adaptedtotheveryproblemtosolve.Learningsucha
specificationfromalreadysolvedproblems(historicaldata)
wouldprovideamodelthatcouldbereusedinanewcontext
withdifferentparameters.Forexample,afterthegeneration
oftheschooltimetablingproblem,themodelcanbefedwith
currentparameterdatalikethenumberofclasses,thenumber
ofteachers,newavailableclassrooms,etc.
Inthispaper,wepresentawayofacquiringsuchacon-
straintspecificationusingInductiveLogicProgramming(ILP).
Theexamplesandcounter-examplesfortheconcepttobe
learnedaredefinedasinterpretationsinalogiclanguagewe
callthe
descriptionlanguage
andtheoutputCSPisexpressed
byconstraintsina
constraintlanguage
.Thespecificationis
expressedbyfirst-orderruleswhichassociatetoasetof
predicatesinthedescriptionlanguage(bodyofarule)asetof
constraintsoftheconstraintlanguage(headofarule).Wedo
notusedirectlyamodelinglanguagelikeEssenceorZincto
stayclosertoarulesystembuttheruleswelearnareatthe
same
levelofabstractionastheonesofintermediatemodeling
languageslikeEssence’,MinizincorOPL.Inparticular,they
allowtheuseofarithmeticsandparametersandtheycanbe
rewrittentogenerateconstraintproblemsofdifferentsize.It
happensthatfindingsuchrulesisagenuinechallengeforILP
techniquessincethediscoveryprocessfallsalmosteverytime
intoILPpathologicalcasesofblindplateausearchatphase
transition[9].
Thecontributionsofthispaperarefirstsettingtheframe-
workoflearningCSPspecifications,thenthechoiceofthe
rulelanguageanditsrewritingintoaCSPandthelearning
algorithmwhichallowstoguidesearchwhentraditional
methodsfail.Thelearningalgorithmisaslightlyimproved
versionoftheonepresentedin[19].
Thepaperisorganizedasfollow.Wefirstgiveaninformal
overviewoftheframework(sectionII),introducetherule
language(sectionIII),thenwepresentthelearningframework

Fig.1.ConstraintProblemLearningworkflow

andgivekeystounderstandandtoimplementouralgorithm
anddescribehowtherulescanberewritteninaCSP.We
presenttheresultsofdifferentexperimentationsonclassical
constraintproblemsliketimetabling,job-shopschedulingand
theclassical
n
-queens.
II.G
ENERALPRESENTATIONOFTHEFRAMEWORK
Inordertobridgethegapbetweenconstraintprogramming
Fig.2.(g1)wrongcoloration,(g2)goodcoloration,(g3)tobecolored
modelinglanguageandILP,weusearathercomplexframe-
work.Inthissection,weprovideaquickoverviewoftheCSPforcoloringaspecificgraph,likethegraph
g
3
ofFigure
framework,aswellassomejustificationsofourchoicesas1.Weassumethattheuserprovidesadescriptionofthegraph
depictedintheworkflowofFigure1.Toillustratetheconcepts,shewantsacolorationof,bygivingasimilarbutincomplete
weusetheverysimpleexampleofgraphcoloring.descriptionofthegraph:
{
wc(g3),n(g3,a),n(g3,b),
First,examplesandcounter-examplesareeachdefined
n(g3,c),n(g3,d),n(g3,e),col(g3,a,ColA),col(g3,b,ColB),
byalogicalinterpretation,whichcanbeseenasaset
col(g3,c,ColC),col(g3,d,ColD),col(g3,e,ColE),adj(a,b),
ofgroundlitterals.Forthegraphcoloringexample,two
adj(a,c),adj(a,e),adj(b,d),adj(b,e),adj(c,e),a
6
=
b,...,red
graphsaredepictedinFigure2onewithawrongcol-
6
=
blue,...
}
.Thentheleft-handsideoftheruleismatched
orationcalled
g
1
andonewithagoodonecalled
g
2
.Foragainstthespecificationandallpossiblesubstitutionsare
thefirstgraph
g1
,itslogicaldescriptionisgivenbythecomputed.Forexample,withthesubstitution
{
G/g3,X/ColA,
interpretation
{
nwc(g1),n(g1,a),n(g1,b),n(g1,c),n(g1,d),Y/ColB
}
,weareabletosettheconstraint
ColA
6
=
ColB
of
adj(g1,a,b),adj(g1,a,d),adj(g1,b,c),adj(g1,b,d),adj(g1,c,d),
theCSPfromtheright-handsideoftherule.Byconsidering
col(g1,a,blue),col(g1,b,green),col(g1,c,green),col(g1,d,red),
allpossiblesubstitutionsallowedbythevariabletypes,we
a
6
=
b,...,red
6
=
blue,...
}
wherethepredicates
nwc
standobtaintheCSPof
g
3
’scolorability.
fornon-wellcolored,
n
fornode,
adj
foradjacentand
col
forExpressedasaclause,theaboverulegives:
color.Weassumethatallthepointwisedifferenceconstraints
betweenconstants(
a
6
=
b
,...)arepresentinthedescription.
¬
col
(
X,A
)
∨¬
col
(
Y,B
)
∨¬
adj
(
X,Y
)

A
6
=
B
Wecangiveasimilardescriptionofthewell-coloredgraph
g
2
withapredicate
wc
.Notethattheexamplesandcounter-Aspecificationiscomposedofaconjunctionofclauseslike
examplesmayrangeondifferentsetsofvariables.Thisgivesthisone.IthappensthatmostILPsystemsratherlearnDNF
ourframeworkanincreasedflexibilityoverthepreviousstate-insteadofCNF.Thenwesimplyconsiderthenegationof
of-the-artsystemCONACQ[4].TobeabletoinferaCSPtherulestobelearned,andexchangeexamplesandcounter-
fromaproblem,allvariablesandconstantshavetypes.Theexamples.Theconjunctiontobelearnedisasfollowsand
ruleweaimtolearnforgraphcoloringis:describesawrongcoloration:
col
(
G,X,A
)

col
(
G,Y,B
)

adj
(
G,X,Y
)

A
6
=
Bcol
(
X,A
)

col
(
Y,B
)

adj
(
X,Y
)

A
=
B
Thisruledescribe
colorability
ofagraphindependentlyoftheIntheory,wecouldsimplygivethisproblematthissteptoa
actualgraphtobecolored.Weassumethateachvariableisrelationallearningtool[13],[14],[20],[15],[16],[17]butin
universallyquantified.Wecanfurtherusethisruletobuildapractice,allofthemfailbecauseofatoolargeorunstructured

searchspace:eitheratop-downsearchfallsintorandom
plateausearchorabottom-upsearchfacestooexpensive
coveragetests.Tostayinformalinthissection,wecansaythat
ourlearningalgorithmisbasedonaspecificruleconstruction
inwhichthesearchspaceistop-downrecursivelydividedinto
zones.Eachzoneisthenexploredbottomupuntilaruleis
found.Then,followingaseparate-and-conquertechnique,the
examplescoveredbytherulesarediscardedandthesearch
foranewruleislauncheduntilallexamplesarecovered.
III.M
ODELINGLANGUAGE
Let
V
beasetofvariablesand
D
=(
D
X
)
X

V
theirdo-
mains.A
constraint
isarelation
c
onasubsetofthevariables.
Wedenoteby
var
(
c
)
thevariablesonwhich
c
isdefinedand
by
sol
(
c
)

D
var
(
c
)
thesetoftuplesdefining
c
.ACSPis
atriple
(
V,D,C
)
inwhich
V
and
D
aredefinedasabove
and
C
isasetofconstraints.Amodelinglanguageprovidesa
waytospecifyaCSPinanabstractmanner.Alotofexisting
modelinglanguagesallowtheuseofhighlevelvariableslike
sets,functions,arithmeticoperators,universalandexistential
quantifiersorargumentstoparameterizetheirmodels[7],[10].
Inpractice,theparametersareusuallyprovidedinaseparate
fileandmixedwiththemodeltoproduceaCSP.Asdescribed
previously,weaimatlearningsuchanabstractmodelofthe
targetproblem.However,evenifwewouldliketolearna
specificationinsuchalanguage,wefoundthatdealingdirectly
withthemistoohardduetotheirexcessofexpressivity.In
thispaper,weproposetofocusonasimplerlanguagebutstill
allowingtoexpressalargenumberofproblems.Wechoose
afirst-orderlogiclanguageretainingthenotionofparameter.
Wehavediscardedfeatureslikefunctionscommonlyfound
inhuman-targetedmodelinglanguagesbutkeptthecrucial
abilitytobeabletogenerateCSPforasetofinstancesofthe
problem.
Asidecontributionofthispaperistoproposearule-based
intermediatemodelinglanguagesuitedforMachineLearning
purpose.AConstraintProblemSpecification(orCPS)inthis
languageconsistsinasetofrulesdescribingwhenaconstraint
shouldbepostedintheCSPinstance.Let
T
beasetoftypes.
Let
V
=(
V
t
)
t

T
and
(
Const
t
)
t

T
berespectivelyasetof
typedvariablesandconstants.Atermiseitheravariableor
aconstant.Predicatesalsohavetypesandaredividedinto
twodisjointsets
P
D
and
P
C
correspondingrespectivelyto
thebodyandtheheadofarule.Bodypredicatesformthe
descriptionlanguage
.Theyareusedtoexpressexamplesand
counter-examplesandtointroducethevariablesoftherules.
Theyalsohavemodedeclaration:eachargumenthasamode
describingiftheargumentisusedasinputoroutput.Input
modeisdenotedby
+
whileoutputmodeisdenotedby

.
Forexample,thepredicate
sum(X,Y,Z)
withsemantics
X
+
Y
=
Z
andmode
sum(+,+,-)
definesthelastargumentto
bethecomputationofthesumofthetwofirstgivenones.
Headpredicatesformthe
constraintlanguage
andareusedto
definetheconstraintswhichholdwhenbodypredicatesare
true.Thesepredicatesareprecursorsofconstraintsandwill
beturnedintoconstraintsintherewritingphase(seeFigure1

andsectionV).An
atom
isanexpression
P
(
t
1
,...,t
k
)
,where
P
isa
k
-arypredicateand
t
1
,...,t
k
areterms.
Thesyntaxofourrulesis:
rule
::=

variables
:
body

head
variables
::=
vs

TYPE
|
variables
,
variables
vs
::=
VARIABLE
|
vs
,
vs
body
::=
BODY_ATOM
|
body

body
head
::=
HEAD_ATOM

HEAD_ATOM
|
head

head
Figure3presentssomeexamplesofproblemsspecified
inourlanguage.Duetothelackofspace,theuniversal
quantificationofthevariablesisomitted.
Thefirstexamplecorrespondstothewell-knowngraph
coloringproblemwheretwoneighborsmusthavedifferent
colors.Thesecondoneisasimplifiedschooltimetabling
problemwhere
timetable
(
L,T,R,S
)
meansthatalesson
L
istaughtbyateacher
T
intheroom
R
attimeslot
S
.Thefirst
ruleimposestwolessonsnottobeduringthesametimeslotif
theyareinthesameroom.Thesecondrulesensuresthatone
teacherdoesnotgivetwolessonsduringthesametimeslot.
Finally,thelastexample,usedinexperiments,isasimplified
job-shopproblemwhere
schedule
(
J,T,B,E,M
)
meansthat
ajob
J
oftype
T
isprocessedbymachine
M
betweenthe
timepoints
B
and
E
.Thefirstrulespecifiesthatthebeginning
ofajobmustbebeforeitsend;thesecondonethattwojobs
cannotbeperformedatthesametime;thelastonedescribes
thatsomejobsmustbedonebeforeothersaccordingtotheir
types(
prev
depictstheorderonjobtypes).
Incontrastwithclassicalintermediatemodelinglanguages,
thepresenceofdisjunctionsmakesitmoredifficulttobeun-
derstoodbyahumanuser.However,amodelinthislanguage
issupposedtobeautomaticallycompiledintoaCSPandinthe
simplifiedexpressions,mostdisjunctionsusuallydisappear.
IV.L
EARNINGPROCESS
ThefirststepofourframeworkconsistsinlearningaCPS
describingthetargetproblem.Inthissection,westartby
presentingtheInductiveLogicProgrammingframeworkand
itsapplicationtoourlearningproblem.Then,wefocusour
presentationonthemainpartofthelearningalgorithmthe
learningofonerule.Weexplainthedifferentstrategieswe
haveconsideredandshowresultsobtainedfromtheexperi-
ments.
A.LearningaCPSasanILPproblem
First,wepresentwhatthelearningprocessneedsasinputs.
IfwerefertoFigure1,thelearningphaseneedsasetof
solutions,forinstanceexamplesofcorrecttimetable,anda
setofnon-solutions,likeexamplesofincorrecttimetables,
andabackgroundknowledge.Thisonecontainsadefinition
ofeachconstraintpredicategiveneitherinextensionorby
Hornclauses.Inaddition,modedeclarationsareputintothe
backgroundknowledge.
Thegoalistolearninourrulelanguageadefinitionof
aCPS,denotedby
CS
,thatcorrectlydiscriminatespositive

Graphcoloringproblem
n
(
X
)

n
(
Y
)

col
(
X,A
)

col
(
Y,B
)

A
6
=
B
∨¬
adj
(
X,Y
)
Simplifiedjo
s
b
c
s
h
h
e
o
d
p
ule
(
J,T,B,E,M
)

B<E
∧Simp
t
l
i
ifi
m
e
e
d
ta
s
b
c
l
h
e
o
(
o
L
l
1
t
,
i
T
m
1
e
,
t
R
a
1
b
,
le
S
1
)

timetable
(
L
2
,T
2
,R
2
,S
2
)
sched

ulJe
(
1
J
=
1
,JT
21
,

B
1
,ME
11
6
,
=
MM
1
)
2
∧∨
schBe
1
du>leE
(
2
J
2
,

T
2
,E
1
B
2
<,EB
22
,M
2
)

L
1
=
L
2

R
1
6
=
R
2

S
1
6
=
S
2

timetable
(
L
1
,T
1
,R
1
,S
1
)
∧∧
timetable
(
L
2
,T
2
,R
2
,S
2
)
schedule
(
J

1
,JT
11
,
=
B
1
J,
2
E
1

,ME
11
)
<

Bsc
2
he

duplre
(
eJv
2
(
,TT
1
,
2
,T
2
B
)
2
,E
2
,M
2
)

T
1
6
=
T
2

L
1
=
L
2

S
1
6
=
S
2

N-queensproblem

position
(
Q
1
,L
1
,C
1
)

position
(
Q
2
,L
2
,C
2
)

Q
1
=
Q
2

L
1
6
=
L
2
position
(
Q
1
,L
1
,C
1
)

position
(
Q
2
,L
2
,C
2
)

Q
1
=
Q
2

C
1
6
=
C
2
position
(
Q
1
,L
1
,C
1
)

position
(
Q
2
,L
2
,C
2
)

gap
(
L
1
,L
2
,I
1
)

gap
(
C
1
,C
2
,I
2
)

Q
1
=
Q
2

I
1
6
=
I
2

Fig.3.SomeCPSexamples:allvariablesareuniversallyquantified

(solutions)fromnegativeexamples(non-solutions).Thedis-section3.4.3)consistinginsearchingadefinitionforthe
criminativepowerofaruleiscomputedw.r.t.acoveringnegationofthetargetconcept.
relation:informally,adefinition
C
coversanexample
e
withConsideringthetimetableexample,theCNFcorresponding
respecttoabackgroundknowledge
B
if
e
canbededucedfromtotheCPSfromfig.3is:
B
and
C
.Ontheotherhand,anexampleisrejectedwhenitis

L
1
,L
2

Lessons,T
1
,T
2

Teachers,...
:
notcovered.Thedefinition
C
issaidtobe
complete
ifitcovers
¬
timetable
(
L
1
,T
1
,R
1
,S
1
)
∨¬
timetable
(
L
2
,T
2
,R
2
,S
2
)
allpositiveexamplesand
consistent
ifitrejectsallnegative

L
1
=
L
2

R
1
6
=
R
2

S
1
6
=
S
2
ones.Tosumup,wecanformalizeourlearningproblemas
V
follow:giventwosetsofexamples
E
+
,
E

,andabackground

L
1
,L
2
,...
:
knowledge
B
,findadefinition
CS
suchthat:
¬
timetable
(
L
1
,T
1
,R
1
,S
1
)
∨¬
timetable
(
L
2
,T
2
,R
2
,S
2
)
+++•

e

E
:
e
iscoveredby
CS

T
1
6
=
T
2

L
1
=
L
2

S
1
6
=
S
2


e


E

:
e

isrejectedby
CS
Toillustratethelearningproblem,weusetheexampleofThenegationproducestheDNF:
schooltimetablingproblem.Letusnoticethatonexamplein

L
1
,L
2

Lessons,T
1
,T
2

Teachers,...
:
theFigure1,isusuallycomposedofoneormoretables(e.g.
timetable
(
L
1
,T
1
,R
1
,S
1
)

timetable
(
L
2
,T
2
,R
2
,S
2
)
forgraphcoloring,therearetwotables:oneforcolorand

L
1
6
=
L
2

R
1
=
R
2
W

S
1
=
S
2
anotherforadjacent).Fortimetabling,weonlyneedonetable
givingthefeaturesofeachlesson.Thistablecanbeviewed

L
1
,L
2
,...
:
asthe4-aryrelation
timetable
,theargumentsofwhichare
timetable
(
L
1
,T
1
,R
1
,S
1
)

timetable
(
L
2
,T
2
,R
2
,S
2
)
thelessonname,theteacher,theroomandthetimeslot.A

T
1
=
T
2

L
1
6
=
L
2

S
1
=
S
2
positiveexampleofasimpletimetablecouldbe:Tolearnthisconcept,thesetsofpositiveandnegativeexam-
e
+
:
{
timetable
(
CS,MrsBlue,s
203
,A
)
,
plesmustbeinverted.Positiveexamplesbecomenegativeand
timetable
(
Maths,MrsBrown,s
106
,C
)
viceversa.Inthesequelofthissection,weonlyfocuson
timetable
(
Biology,MrsWhite,s
308
,A
)
,
learningDNF.
timetable
(
Maths,MrsBrown,s
106
,B
)
}
whereasanegativeexamplecouldbe:
B.BackgroundinILP
e

:
{
timetable
(
CS,MrsBlue,s
203
,A
)
,
Thestate-of-the-artframeworkofILPconsistsinlearning
timetable
(
Maths,MrsBrown,s
106
,C
)
adefinitioncomposedofrules.Separate-and-conquerisa
timetable
(
Biology,MrsWhite,s
203
,A
)
,
heavilyusedfamilyofalgorithmsinILP(theinterestedreader
timetable
(
Maths,MrsBrown,s
105
,C
)
}
canreferto[12]foracompletestate-of-the-art).Thealgorithm
Notethatthecounter-example
e

containstwoerrors.Back-iteratesasinglerulelearningalgorithmuntilpositiveexamples
groundknowledgecontainsusefulpredicateslikeequalitiestoarecorrectlydiscriminatedfromallnegativeones.Sincewe
comparelessons,teachers,roomsandtimeslots.useseparate-and-conquer,thissectiononlyfocusesonthe
AsetofrulesdefiningaCPSisequivalenttoaConjunctivesinglerulelearningstep.
NormalForm(CNF).However,themajorityofexistingILPFirst,weintroducethesearchspaceofILP.A
searchstate
systemshandleDisjunctiveNormalForm(DNF)orequivalent.isrepresentedbyaconjunctionofliteralsrepresentingarule
PassingfromCNFtoDNFisasimpleoperation(see[11],withrespecttobackgroundknowledge.Toevaluatetheinterest

ofastate,wecanconsiderdifferentcriteriasuchasthelength
oftheruleoritscoveragescoreoverpositiveandnegative
examples.Anexample
e
is
covered
byarule
r
ifthereexists
asubstitution
σ
suchthat
σ
(
r
)

e
.
Thesearchspacecanbeorganizedasalattice.Inthispaper,
weconsiderthefollowingsearchlatticeboundedbytworules
denoted
>
(top)and

(bottom)andorderedbytheinclusion
relation.Aclause
c
1
isincludedinanotherone
c
2
ifallthe
literalsof
c
1
appearin
c
2
,uptovariablerenaming.Inthis
case,wesaythat
c
1
is
moregeneral
than
c
2
and,similarly,
that
c
2
is
morespecific
than
c
1
.
The
>
clauseisthemostgeneralclauseofthelattice.
Itcoversthemaximumnumberof(positiveandnegative)
examples.Theemptyclausewhichcoversalltheexamples
andcounter-examplescanbeconsideredasa
>
clause.Butin
ordertoreducethesearchspace,manyalgorithmschooseas
>
clauseamorespecializedone.
Thebottomclauseisthemostspecificoneandshouldreject
mostexamples.IncertainalgorithmslikeFOIL[13],this
boundistheoreticalsince

isaninfiniteclause(andtherefore
wehaveaninfinitesearchspace)becausenewvariablescan
beintroducedateachstep.Thisiswhyabottomlimitis
chosenbysaturationofanexamplecalleda
seed
(see[14]
forcompleteexplanation).Givenapositiveseedexample
s
,
itssaturation
sat
(
s
)
consistsin
s
augmentedofallentailed
backgroundknowledgeliterals.Toobtainthislimit,modesare
usedandnewvariablescorrespondingtooutputmodesmay
beintroduced.Thissetcanbeparameterizedbyacertainlimit
toobtainafinitesetandsoafinitesearchspace.Typically,
wecanlimitthenumberofnewvariablesintroducedundera
limit
k
.
Toexplorethesearchspace,thereexistsdifferentstrategies
like
top-down
(SeeFigure4),whichstartsfromthehypothesis
>
andprogressivelyspecializesthehypothesisbyaddingnew
literals,or
bottom-up
,whichstartsfrom

andgeneralizes
thehypothesisbyremovingsomeliterals.Thesetwostrategies
consistinasequenceofoperations,called
refinements
,thegoal
ofwhichistospecializeorgeneralizethecurrenthypothesis.
Eachrefinementproducesanewhypothesis.Forahypothesis,
thereexistsgenerallyseveralpossiblerefinementsduetothe
latticestructure.Tochoosethebestone,algorithmsusea
heuristicfunction
basedonacoveragescoreand/orthelength
oftherule.
Letusillustratethiswithanexample.Averysimple
refinementoperator,inatop-downsearch,couldbeanop-
erationselectingaliteralinthe

clauseandaddingittothe
hypothesis.Then,thenumberofpossiblerefinementswould
beequaltothelengthof

.Toselectaliteral,wecanchoose
ponewiththebest
purity
heuristicvaluedefinedby
p
+
n
where
p
and
n
correspondtothecoveragescoreoverpositiveand
negativeexamples.
Wehavepresentedtherulelearningprocesswithahill-
climbingstrategybutmanyversionsexistwith,forinstance,
beamsearchor
A

methods.
Top-down
areillustratedby
algorithmslikeFOIL[13],Progol[14],ICL[15],Beth[16]
andPropal[17].ButthesealgorithmsfailonourCSPbench-

marks(seesectionIV-D).Recentworksonphasetransition
problemsinILP[18]andblindsearchorcrossing”plateau”
[9]indicatethatsearchingasolutionmayfallintoavery
difficultzoneandCPSlearningclearlybelongstothiskind
ofproblems.
Bottom-up
approachesarenotadaptedbecause
oftheexpensivecostofcoveragetestatthebeginningof
thesearch.TotakeadvantagesofthestructureofCPS,we
havedevelopedanewalgorithm[19]basedonabidirectional
search.Wedescribeitinthenextsection.
C.Bidirectionalsearch
Wehavedesignedanewalgorithmtakingadvantagesof
top-downandbottom-upapproaches.Ouralgorithmisabidi-
rectionalsearchwhereeachrefinementstepischaracterized
byacoupleofhypothesis
(
H
i
>
,H
i

)
Inthiscouple,
(
H
i
>
and
H
i

)
aretworuleswhere
H
i
>
isaspecializationof
>
and
H
i

ageneralizationof

(seefig.4).
Thesearchstartswith
H
>
0
reducedtoanemptyrule,and
H

0
obtainedbysaturationofapositiveuncoveredexample.
Themaincharacteristicsoftheapproachare:

H
i
>
+1
isobtainedfrom
H
i
>
byaddingasetofliterals.The
candidatesetsareselectedfrom
H
i

w.r.t.theanalysisof
layersintheinitialsaturation
H

0
.Westartbysearching
singletonsandthesizeofcandidatesetsisincreaseduntil
asatisfyingcandidateisfound.Eachcandidateset
S
is
associatedtoacandidateclauseobtainedbyadding
S
to
thebodyof
H
i
>
.

Candidateclausesarenotevaluatedw.r.t.theirdiscrimi-
natingpowerbutw.r.t.thediscriminatingpoweroftheir
saturation.Thischoicereducesthephenomenonofblind
search.

Werestrictthesearchtocandidatesetssothatif
H

0
containsadiscriminatingclause,thenthisclausecanbe
foundbyourbidirectionalsearch.

Onceacandidateclause
H
i
>
+1
isselected,
H
i

+1
is
obtainedbyasaturationof
H
i
>
+1
whereonlyliteralsfrom
H

0
areadded.
Thisprocessisrepeateduntil
H
i
>
=
H
i

.Eachstepproduces
arefinementoftheprevioustopclause,butcoveragetests
arelessexpensivethaninusualbottom-upsearch.Atthe
sametime,itproducesageneralizationofthebottomclause
whichbothallowstoreducethesearchspaceandisused
forevaluatingandchoosingamongrefinements(tobemore
accuratethantop-downsearches).Wehaveobtainedwiththis
techniqueveryinterestingandencouragingresultscompared
toothertestedapproaches.Thedetailofthealgorithmcanbe
foundin[19].
D.Experimentsanddiscussion
Toevaluatedifferentexistingstrategies,wehavegenerated
severalbenchmarksfortheexamplesspecifiedinFigure3.
Indoingso,wehavegeneratedasetofsolutionsandnon-
solutions.Toproducesolutions,wehavechosenarandom
sizeforeachproblem(
e.g.
forthegraphcoloringproblem,
thenumberofverticesandcolors),andthensolvedtheCSP.
Fornegativeones,wehaveproceededinasimilarwaybut

>

...R

⊥Top-downsearch

>

R...

⊥Bottom-upsearch
Fig.4.Searchstrategies

>

...R...

⊥Bidirectionalsearch

constraintshavebeenrelaxedandwehavecheckedthattheresendingamailtotheauthors.Thismethod,builtasshownin
isatleastoneunsatisfiedconstraint.[19],worksveryefficientlywithCSPbenchmark.Itreliesona
WehavetestedmostusualILPalgorithms.Resultsofstratifiedrepresentationoftheexamples,whichunfortunately
experimentsaredetailedinFigure5.Tocomputetheaccu-isnotsatisfiedonallkindoflearningproblems.
racyofalearnedCPS(thirdcolumn),wehavegenerated
newexamplesandcomputedtheratioofexamplescorrectlyV.T
RANSLATIONOF
CPS
TO
CSP
discriminatedbythelearnedrules(coveredforsolutionsandLetusconsiderasexampletheschooltimetablingproblem.
rejectedfornon-solutions).WehaveconcentratedoureffortonWeassumetheuserhasobtainedaCPSduringthelearning
recognizedtop-downapproaches.Bottom-upapproacheshavephase.ToproduceanactualCSP,sheneedstoprovidea
beentotallyineffectiveduetothelargesizeof

rulesandpartiallycompletedtablerepresentingthepredicate
timetable
theexpensivecoveragetest.Fortop-downsearches,resultsare(fig.1).Ingeneral,theremaybeseveraltables,called
partial
moreinterestingbutnotenoughtobeacceptable.Onlythree
extension
.TheysettheparametersoftheCPS.Theobjective,
top-downapproacheshavegiveninterestingresults:Propalandfortheuser,istoobtainaCSPwhichisable,oncesolved,
twoconfigurationsofAleph[20]
1
.Propalisbasedonthedatatocompletepartialextensions.InFigure1,theproblemisto
drivenstrategy(awaytorejectcertainrefinements).Thefirstdetermineroomsandtimeslotswhereteacherscoulddotheir
configurationforAleph,calledAleph1,isabreadthfirstsearchlessons.Theusermustgivedomainscorrespondingtorooms
withamaximumof200000visitedsearchstatesandaninfiniteandtimeslotsinordertoobtaintheCSPmodelcorresponding
openlist.Thesecond,namedAleph2,onlydiffersfromthetoherproblem.Inparticular,theremaybenewteachers,a
firstonebythesearchstrategyinwhichthebreath-firstsearchdifferentnumberofgroups.Thesedataareverynaturalto
hasbeenreplacedbyaheuristicsearch.Themorecomplextheprovidegivenanactualproblemtosolve.
targetconceptis,themorePropalandAleph2findanincorrectA
partialextension
ofapredicate
p
isapair
(
p,E
)
,where
theory.Forthe
n
-queensproblem,Propalhasbeenstopped
E
isasetoftuples
h
x
1
,x
2
,...,x
k
i
definingthispredicate,
aftertenhours.Theseresultsshowthemainlimitationof
top-
and
x
i
iseitheraconstantor
?
,thelattermeaningthattheuser
down
approacheswhentheyfacetoplateauphenomena[9].doesnotknowthevalueoftheattribute.Wedenoteby
ext
Aleph1correspondstoaquasicompletesearchwhichmaythesetofpartialextensionsgivenbytheuser.Thetranslation
succeedsbutwithanimportantcomputationtime(dependingfromCPStoCSPiscomposedoftwosteps.First,partial
ontheproblems).extensionsarecompletedwithCSPvariableswhichareset
Incontrast,ourbidirectionalmethodhassucceededwithalltothecorrespondingdomains.Second,foreachruleofthe
benchmarks:itfindsaccuratedefinitioninashortamountofCPS,allpossiblesubstitutionsofthebodyareproducedand
time.Butevenifthemeaningisidentical,thelearnedrulesarethecorrespondingconstraints(theheadoftherule)areposted.
notalwaystheexpectedones.Forexample,for
n
-queens,theAlgorithmVcomputesthesetwosteps.
learnedconstraintforcolumnis(
gap
isapredicateexpressingThefirststep(line3)consistsincompleting
ext
,replacing
thedifferenceoftwointegers):all
?
byCSPvariableswiththerightdomain(givenbythe
position
(
Q
1
,X
1
,Y
1)

position
(
Q
2
,X
2
,Y
2)
user).Thesecondstepconsistsinproducingconstraintsfrom

gap
(
Y
1
,Y
2
,V
1)

gap
(
Y
2
,Y
2
,V
2)
CPSruleswithrespecttotheuserinstance.Indoingso,we

Q
1=
Q
2

V
2
6
=
V
1
generateallpossiblesubstitutionsofthebody
G
allowing
tosatisfytheebody.Givenasubstitution
σ
,thebodyis
Ourprototype,aswellasthebenchmarks,canbeobtainedbysatisfiedifeachatom
p
(
t
1
,...,t
k
)
of
G
issatisfiedwith
σ
.
1
AlephisageneralsystemallowingtheemulationofseveralotherILP
Anatom
p
(
t
1
,...,t
k
)
issatisfiedif
σ
(
p
(
t
1
,...,t
k
))
hasa
systems
supportin
ext
or,inthecasewhere
p
isintensionallydefined,

Propalalgorithmfrom[19]
benchmark#learnedrulestime(s)acc.#learnedrulestime(s)acc.
Graphcoloring10100%10.17100%
Schooltimetable31198,33%20.69100%
Job-shop610387,78%57.37100%
N-queens---329.11100%
Aleph1Aleph2
Graphcoloring10.24100%10.14100%
Schooltimetable11.24100%10.31100%
JNo-bq-useheonps331408591..4093110000%%3641518330..8848619.667%%
Fig.5.Experimentswithdifferentlearningstrategies

if
σ
(
p
(
t
1
,...,t
k
))
isvalidwithrespecttothedefinition.A
Algorithm:
T
RANSLATE
(
CS,ext,domains
)
problemexistswhen
p
isintensional.WhenthereareCSP
1.//Completethepartialextension
variablesamongpositionswithinputmodeof
p
,wegenerate
2.//withCSPvariableswithdomains
auxiliaryCSPvariablesfortheoutput.Forinstance,consid-
3.
ext

C
OMPLETE
(
ext,domains
)
eringthefollowingatom
sum
(
X,Y,Z
)
andthesubstitution
4.//Initializethevariablesset
{
X/
2
,Y/v
1
,Z/
?
}
wherethedomainof
v
1
is
[2
..
6]
.Thesub-
5.//withtheseinext
stitutioniscompletedwith
Z/v
2
andthedomainof
v
2
is
[4
..
8]
.
6.
vars

G
ET
V
AR
(
ext
)
Whenallthesubstitutionsarecomputed,thealgorithmsubsti-
7.
constraints
←∅
tutestheheadoftheruletoproducetheconstraints(line21).
8.
foreach
G

C

CS
Theseconstraintsaredisjunctionsofconstraints.However,if
9.//Generateallsubstitutionofthe
weconsidertheexampleofschooltimetablingproblem,many
body
variablesoftheconstraintshavealreadyavalueallowingto
10.
subst

G
ENERATE
A
LL
S
UBST
(
G,ext
)
simplifytheconstraint.Forinstance,considerthesubstitution
11.
foreach
σ

subst
{
L
1
/Latin,T
1
/MrsGreen,R
1
/v
1
,S
1
/v
2
,L
2
/English,
12.//Ifthereareatomswithnomatching
T
2
/MrsGreen,R
2
/v
3
,S
2
/v
4
}
ofthesecondrule.The
13.//inext,itaddsaux.variables
computedconstraintwillbe
MrGreen
6
=
MrsGreen

14.//andtheconstraint
Latin
=
English

v
2
6
=
v
4
.Itcanbesimplifiedin
v
2
6
=
v
4
.
15.
foreach
atomsp
(
t
1
,...,t
k
)

G
Constraintcannotalwaysbesimplified;forinstance,ifthe
16.
suchthat
(
p,
)

/ext
substitutionisappliedtothefirstrule,thedisjunctionremains.
17.
vars.add
(
G
ET
V
AR
(
σ
(
p
(
t
1
,...,t
k
))))
VI.C
ONCLUSION
18.
constraints.add
(
σ
(
p
(
t
1
,...,t
k
)))
19.//Itaddstheconstraint
Themotivationofourworkistoavoidsomeofthe
20.//correspondingtothehead
limitationsencounteredwithsystemslikeCONACQ[3].Toour
21.
constraint.add
(
σ
(
C
))
bestknowledge,CONACQandoursystemaretheonlyworks
22.//Finally,itreturnstheCSP
concerningtheacquisitionofCSP.In[21],Bessie`reetal.
23.
return
CSP
(
vars,domains,constraints
)
proposeamethodtoautomaticallygenerateviewpointsfrom
examples.However,nomethodisgiventogenerateconstraints
Fig.6.TranslationofaCPSinCSP
onthesevariables.Moregenerally,severalworksexistabout
reformulationofmodels,includingthediscoveryofimplied
orredundantconstraints[22],[23].Inthiscase,thelearninglearningproblemhasprovedtobeverydifficult.Itfallsinto
taskconsistsinlearningonlyfrompositiveexamplessincethewellknownlimitationsofILP:blindsearchwithplateau
discriminationofsolutionsandnon-solutionsarealreadymadephenomenafortop-downsearchesandtooexpensivetestsfor
bythesimplemodel.Thisiscomplementarytoourapproachbottom-upsearch.Inordertosucceedinourlearningtask,
sinceourlearnedmodelswouldgaintobereformulatedintowehavedesignedanewalgorithmtakingadvantagesofthese
moreefficientones.twostrategies.Thisalgorithmpresentaverygoodbehavior
Inthispaper,wehavepresentedaframeworktoobtainonCSPbenchmarks.Thefinalstepofourframeworkconsists
automaticallyanabstractmodelofaCSP.Ourapproach,inatranslationoftheCPSandthedataoftheuser’svery
basedonInductiveLogicProgramming,receivedexamplesproblemintoaCSP.Thisworkconstitutesanencouraging
ofwhattheuserconsidersassolutionsandnon-solutionssteptowardstheautomaticacquisitionofaCSP.Obviously,
of
related
problems.Then,shegetsaspecification(aCPS)theCPSlanguagehastobeimprovedtohandlelargerCSP
whichcanbefurthertranslatedintoaCSPbyaddingdataproblemclasses.Aneasywaywouldbetoadd,similarlytothe
fromherveryproblem.Evenwithaspecificationexpressed”forall”blockpresentedinthispaper,anexistentialblock.The
infirstorderlogic,andwhichcanpotentiallytakeadvantagemethodshouldbethesame.Butanimportantimprovement
ofalotofsystemsdesignedtolearnsuchdefinitions,thiswouldbetheadditionofaggregates(e.g.thesumofalistof

variables).However,eachimprovementhasacostwhichneeds
tobetakeninaccounttopreservethesystemefficiency.
R
EFERENCES
[1]J.-F.Puget,“Constraintprogrammingnextchallenge:Simplicityofuse,”
in
InternationalConferenceonConstraintProgramming
,ser.LNCS,
M.Wallace,Ed.,vol.3258.Toronto,CA:Springer,2004,pp.5–8,
invitedpaper.
[2]B.M.Smith,“Modelling,”in
HandbookofConstraintProgramming
,
T.W.F.Rossi,P.vanBeek,Ed.Elsevier,2006,ch.11,pp.377–406.
[3]C.Bessie`re,R.Coletta,F.Koriche,andB.O’Sullivan,“Acquiring
constraintnetworksusingasat-basedversionspacealgorithm,”in
AAAI
.
AAAIPress,2006.
[4]R.Coletta,C.Bessie`re,B.O’Sullivan,E.C.Freuder,S.O’Connell,and
J.Quinqueton,“Semi-automaticmodelingbyconstraintacquisition,”in
CP
,ser.LectureNotesinComputerScience,F.Rossi,Ed.,vol.2833.
Springer,2003,pp.812–816.
[5]C.Bessie`re,R.Coletta,B.O’Sullivan,andM.Paulin,“Query-driven
constraintacquisition,”in
IJCAI
,M.M.Veloso,Ed.,2007,pp.50–55.
[6]P.V.Hentenryck,
TheOPLoptimizationprogramminglanguage
.Cam-
bridge,MA,USA:MITPress,1999.
[7]A.M.Frisch,M.Grum,C.Jefferson,B.M.Herna´ndez,andI.Miguel,
“Thedesignofessence:Aconstraintlanguageforspecifyingcombina-
torialproblems,”in
IJCAI
,M.M.Veloso,Ed.,2007,pp.80–87.
[8]N.Nethercote,P.J.Stuckey,R.Becket,S.Brand,G.J.Duck,and
G.Tack,“Minizinc:Towardsastandardcpmodellinglanguage,”in
CP
,
2007,pp.529–543.
[9]E´.AlphonseandA.Osmani,“Ontheconnectionbetweenthephase
transitionofthecoveringtestandthelearningsuccessrateinilp,”
MachineLearning
,vol.70,no.2-3,pp.135–150,2008.
[10]K.Marriott,N.Nethercote,R.Rafeh,P.J.Stuckey,M.G.dela
Banda,andM.Wallace,“Thedesignofthezincmodellinglanguage,”
Constraints
,vol.13,no.3,pp.229–267,2008.
[11]W.V.Laer,“Frompropositionaltofirstorderlogic
inmachinelearninganddatamining,”Ph.D.dissertation,
KatholiekeUniversiteitLeuven,June2002.[Online].Available:
http://www.cs.kuleuven.ac.be/wimv/PhD/
[12]J.Furnkranz,“Separate-and-conquerrulelearning,”
ArtificialIntelli-
genceReview
,vol.13,pp.3–54,1999.
[13]J.R.QuinlanandR.M.Cameron-Jones,“Foil:Amidtermreport.”in
ECML
,ser.LectureNotesinComputerScience,P.Brazdil,Ed.,vol.
667.Springer,1993,pp.3–20.
[14]S.Muggleton,“Inverseentailmentandprogol,”
NewGeneration
Computing,SpecialissueonInductiveLogicProgramming
,
vol.13,no.3-4,pp.245–286,1995.[Online].Available:
http://citeseer.ist.psu.edu/muggleton95inverse.html
[15]L.D.RaedtandW.V.Laer,“Inductiveconstraintlogic,”in
ALT
,1995,
pp.80–94.
[16]L.P.R.Tang,“Integratingtop-downandbottom-upapproachesinin-
ductivelogicprogramming:applicationsinnaturallanguageprocessing
andrelationaldatamining,”Ph.D.dissertation,DepartmentofComputer
Sciences,UniversityofTexas,2003,supervisor-Mooney,RaymondJ.
[17]E´.AlphonseandC.Rouveirol,“Extensionofthetop-downdata-driven
strategytoilp,”in
ILP
,ser.LectureNotesinComputerScience,
S.Muggleton,R.P.Otero,andA.Tamaddoni-Nezhad,Eds.,vol.4455.
Springer,2006,pp.49–63.
[18]A.Serra,A.Giordana,andL.Saitta,“Learningonthephasetransition
edge,”in
IJCAI
,2001,pp.921–926.
[19]M.Lopez,L.Martin,andC.Vrain,“Learningdiscriminantrulesasa
minimalsaturationsearch,”in
ILP
,2010.
[20]A.Srinivasan,
Alearningengineforproposinghypotheses(Aleph)
.
[21]C.Bessiere,J.Quinqueton,andG.Raymond,“Mininghistoricaldata
tobuildconstraintviewpoints,”in
ProceedingsCP’06Workshopon
ModellingandReformulation
,2006,pp.1–16.
[22]J.Charnley,S.Colton,andI.Miguel,“Automaticgenerationofimplied
constraints,”in
ECAI
,2006,pp.73–77.
[23]C.Bessie`re,R.Coletta,andT.Petit,“Learningimpliedglobalcon-
straints,”in
IJCAI
,2007,pp.44–49.
[24]M.M.Veloso,Ed.,
IJCAI2007,Proceedingsofthe20thInternational
JointConferenceonArtificialIntelligence,Hyderabad,India,January
6-12,2007
,2007.