On Learning Constraint Problems Arnaud Lallouet

Arnaud Lallouet

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

Sujets

• Martin
• Modeling language
• Learning

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 44
• Langue: English

Extrait

OnLearningConstraintProblems

ArnaudLallouetMatthieuLopez,LionelMartin,ChristelVrain
GREYC,UniversityofCaenLIFO,UniversityofOrle´ans
Caen,FranceOrle´ans,France
EMail:[e-mail]:fi[e-mail]

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
examp