搜索
1ConstraintLogicProgrammingandIntegerProgrammingapproachesandtheircollaborationinsolvinganassignmentschedulingproblemKenDarby-Dowman(1)JamesLittle(1)GautamMitra(1)MarcoZaffalon(2)(1)DepartmentofMathematicsandStatistics,BrunelUniversity,Uxbridge,Middlesex,UK,UB83PH(2)UniversitàdegliStudidiMilanoDip.diMatematica,ViaCicognara720129,Milan,Italy7thSeptember1996AnearlierversionofthispaperwasfirstpresentedattheThirdInternationalConferenceonAppliedMathematicalProgrammingandModelling(APMOD’95),heldatBrunelUniversity,3-5April,1995.2AbstractGeneralisedAssignmentProblems(GAP),traditionallysolvedbyIntegerProgrammingtechniques,areaddressedinthelightofcurrentConstraintProgrammingmethods.Aschedulingapplicationfrommanufacturing,basedonamodifiedGAP,isusedtoexaminetheperformanceofeachtechniqueunderavarietyofproblemcharacteristics.Experimentalevidenceshowedthat,forasetofassignmentproblems,ConstraintLogicProgramming(CLP)performedconsistentlybetterthanIntegerProgramming(IP).AnalysisoftheCLPandIPprocessesidentifiedwaysinwhichthesearchwaseffective.TheinsightgainedfromtheanalysisledtoanIntegerProgrammingapproachwithsignificantlyimprovedperformance.Finally,theissueofcollaborationbetweenthetwocontrastingapproachesisexaminedwithrespecttowaysinwhichthesolverscanbecombinedinaneffectivemanner.KeywordsConstraintLogicProgramming,IntegerProgramming,GeneralisedAssignmentProblem,Optimisation1.IntroductionTheanalysisofcomplexdecisionproblems,oncethepreserveofOperationsResearch(OR),hasinrecentyearsattractedtheattentionofanalystsfromotherdisciplines.Inparticular,ArtificialIntelligence(AI)intheformofConstraintLogicProgramming(CLP)isnowtacklingseriousdecisionproblemsintheareasofscheduling[Duncan(1994)],resourceallocation[DincbasandSimonis(1991)]andplanning[Belloneetal.(1992)].Theseapplicationsgenerallyinvolvesomeformofcombinatorialsearchandpresentchallengesinbothmodellinganddevelopingefficientsearchstrategies.CombinatorialoptimisationproblemsareoftenNP-hardand,assuch,allknownexactalgorithmshaveanexponentialworstcasecomplexity.Thisisnottosaythatsuchproblemsarenecessarilyunsolvableevenwhenlargescale.However,mostapproachestosolvinglargescalecombinatorialoptimisationproblemsuse,atsomestageinthesolutionprocess,atreesearch.Thekeytoasuccessfulapproachistoadopta‘good’branchingstrategywherebythetreesearchcanbecompletedrelativelyquickly.Integerprogramming(IP)andConstraintLogicProgramming(CLP)aretwoalternativeapproachestomodellingandsolvingcombinatorialoptimisationproblems.IntegerProgrammingisanestablishedapproachwithinOperationsResearchandmodern3softwareallowssubstantialusercontroloverthebranchingstrategy.Essentiallythesearchisguidedbyfactorssuchasthemathematicalstructureoftheintegerpolytope,theextentofthefractionalityofthecurrentsolutionortheprioritiesallocatedexternallytovarioussubsetsofvariables.ConstraintLogicProgramminghasanimportantrolewithintheArtificialIntelligenceapproachtoproblemsolving.Hereagain,thekeytosuccessliesindirectingthesearchwherebytheanalystcanexploitproblemspecificfeaturesindeterminingsearchstrategies,complementingtheunderlyingconstraintsolvers’ownsearchtechniques.AfulldescriptionoftheCLPparadigmispresentedinLittleandDarby-Dowman(1995).DuringtheevolutionofCLP,severalauthorshavecomparedittothetechniqueofIP.AnearlyexampleispresentedbyVanHentenryckandCarillon(1988)whocomparedCLPandIPappliedtoasimplewarehouselocationproblem.Thecomparisonwasbasedmainlyontheirdifferentmodellingcapabilities.AsCLPhasdeveloped,thesizeofproblemcapableofbeingtackledhasgrown.Smithetal.(1995),El-Sakkout(1995)andHajianetal.(1995)havealltackledlarge-scaleproblemswith‘stateoftheart’solversandhighdegreesofexpertise.Thefirstpaperdescribesaproblemoffindingaconstrainedsetofpermutationsof‘guests’visiting‘hosts’overseveraldiscretetimeperiods.Apropertyofthisparticularproblemisthatanyfeasiblesolutionisnecessarilyoptimal.Thusthesearchcanbeterminatedassoonasafeasiblesolutionisobtainedirrespectiveofwhetherornotthesearchtreehasbeenfullyfathomed.TheconclusionwasthatConstraintProgramminggavebettersolutionsthanIntegerProgrammingduetothecompactnessoftheproblemrepresentationandtheeffectivenessoftheconstraintsinreducingthesearchspace.Thesolutionsrequiredmanualamendment,butonlyafterCPhadprovidedagoodstartingpoint.Bothsolverswereusedwithahighdegreeofsophistication.Thesecondandthirdpapersarebothconcernedwiththeassignmentofaircrafttoflightsunderasetofoperationalconstraints.El-SakkoutshowedthatanoptimalsolutionwasobtainedonlyfromIP,butagood(sub-optimal)solutionwasproducedquicklybyCLP.Ananalysisofwhytheapproachesdifferedintermsofperformancewasnotfullyexplored.However,Hajianetal.observedthat,fortheproblemstheyconsidered,theCLPapproachwasabletoproduceafeasiblesolutionquicklywhereasIPwasgoodatprovingoptimality.Bycombiningbothapproaches,a‘loose-coupled’hybridsolverwasabletoachieveimprovedperformanceoverthatofeachindividualapproach.4Duetothehighlevelsofexpertiseneededforbothsolvers,researchintheareaofsolvercomparisonhasbeenrelativelyunexploredtodate.Itisonlybyunderstandingthereasonsforsolverperfo