Algorithms for hybrid MILPCP models for a class of

AlgorithmsforHybridMILP/CPModelsforaClassofOptimizationProblemsVipulJainIgnacioE.GrossmannDepartmentofChemicalEngineering,CarnegieMellonUniversity,Pittsburgh,Pennsylvania,15213,[e-mail]@cmu.eduThegoalofthispaperistodevelopmodelsandmethodsthatusecomple-mentarystrengthsofMixedIntegerLinearProgramming(MILP)andCon-straintProgramming(CP)techniquestosolveproblemsthatareotherwiseintractableifsolvedusingeitherofthetwomethods.Theclassofproblemsconsideredinthispaperhavethecharacteristicthatonlyasubsetofthebinaryvariableshavenon-zeroobjectivefunctioncoeÆcientsifmodeledasanMILP.ThisclassofproblemsisformulatedasahybridMILP/CPmodelthatinvolvessomeoftheMILPconstraints,areducedsetoftheCPcon-straints,andequivalencerelationsbetweentheMILPandtheCPvariables.AnMILP/CPbaseddecompositionmethodandanLP/CP-basedbranch-and-boundalgorithmareproposedtosolvethesehybridmodels.BoththesealgorithmsrelyonthesamerelaxedMILPandfeasibilityCPproblems.Anapplicationexampleisconsideredinwhichtheleast-costschedulehastobederivedforprocessingasetoforderswithreleaseandduedatesusingasetofdissimilarparallelmachines.ItisshownthatthisproblemcanbemodeledasanMILP,aCP,acombinedMILP-CPOPLmodel(VanHentenryck1999),andahybridMILP/CPmodel.ThecomputationalperformanceofthesemodelsforseveralsetsshowsthatthehybridMILP/CPmodelcanachievetwotothreeordersofmagnitudereductioninCPUtime.(IntegerProgramming;Benders-Decomposition;ConstraintProgramming;MILP/CPHybridAlgorithms;ParallelMachineScheduling)11.IntroductionRecently,therehasbeenasignicantinterestindevelopingmodelsandmeth-odsthatcombineMixedIntegerLinearProgramming(MILP)(NemhauserandWolsey1988)andConstraintProgramming(CP)(MarriotandStuckey1998)tosolvecombinatorialoptimizationproblems.Theprimaryreasonforthisinterestisthateventhoughthesemethodologiescansolvesimilarprob-lems,theyhaveprovedtobesuccessfulinsolvingcomplementaryclassesofproblems.MILPmethodshavebeensuccessfullyappliedtosolvediverseproblems,suchasnetworksynthesis,crewscheduling,planning,andcapitalbudgeting,thatcanbemodeledasoptimizationproblems.CPmethodshaveprovedtobesuccessfulinsolvinghighlyconstraineddiscreteoptimizationandfeasibilityproblemsforscheduling,conguration,andresourcealloca-tion.ThemainobjectiveofdevelopingintegratedmodelsandmethodsistousethecomplementarystrengthsofMILPandCPforsolvingproblemsthatareotherwiseintractableusingeitherofthesetwomethodsalone.InthispaperweproposealgorithmsthatusecomplementaryMILPandCPmodelstoachievethisgoalforacertainclassofoptimizationproblems.Thispaperisstructuredasfollows.Inthenextsection,wepresentabriefbackgroundonMILPandCPforsolvingoptimizationproblems.Itisfollowedbyaliteraturereviewonintegrationofthesetechniques.WethendescribeaclassofproblemsinwhichonlyasubsetofthebinaryvariablesappearsintheobjectivefunctionoftheMILPformulation.WeformulatethisclassofproblemsashybridMILP/CPmodelsthatinvolvesomeoftheMILPconstraints,areducedsetoftheCPconstraints,andtheequivalencerelationsbetweentheMILPandtheCPvariables.Wethenproposedecompositionandbranch-and-boundalgorithmstosolvethesehybridmodels.BothofthesealgorithmsrelyonrelaxedMILPandfeasibilityCPproblems.TheaimofthesemethodsistocombinethestrengthofMILPforprovingoptimalitybyusingtheLPrelaxations,andthepowerofCPforndingfeasiblesolutionsbyusingthespecializedpropagationalgorithms.Asanexample,weconsideraschedulingproblemthatinvolvesndingaleast-costscheduletoprocessasetofordersusingdissimilarparallelmachinessubjecttoreleaseanddue-dateconstraints.ItisshownthatthisproblemcanbemodeledasanMILP,CP,oracombinedMILP-CPOPLmodel(VanHentenryck1999).Wetheninvestigatethecomputationalperformanceofthesealternativemodelsforanumberofdatasetsandhighlighttheadvantagesanddisadvantagesofthese2approaches.ThisproblemisthenmodeledasahybridMILP/CPmodelandissolvedusingtheproposeddecompositionalgorithm.Computationalresultsarepresentedandnallysomeconclusionsaredrawn.2.BackgroundMILP-basedmethodsweredevelopedoverthelastfourdecadesbytheOper-ationsResearchcommunity(NemhauserandWolsey1988).CP-basedmeth-ods,ontheotherhand,aretheresultofresearchbytheArticialIntelligencecommunityintheareaofLogicProgrammingandConstraintSatisfaction(Colmerauer1985,VanHentenryck1989,Tsang1993).Boththeseframe-worksrelyonbranchingtoexplorethesearchspace.Theprimarydierenceliesinthewayinferenceisperformedateachnode.LinearProgramming(LP)-basedbranch-and-boundmethodsforMILPinvolvesolvingLPsub-problemsthataregeneratedbydroppingsomeoftheconstraints(integralityconstraints)toobtainboundsontheobjective-functionvaluesandtoprovethatasetofconstraintsisinconsistent.Anodeisfathomedeitherwhentheobjective-functionvalueoftheLPrelaxationisworsethanthebestintegersolutionobtainedsofar,ortheLPsubproblemisinfeasible.BranchingisperformedwheneverthesolutionobtainedbysolvingtheLPrelaxationdoesnotsatisfyalltheconstraintsintheoriginalproblem.Iftherelaxedsolutionsatisesalltheconstraintsintheoriginalproblemandisbetterthanthebestfeasiblesolutionfoundsofar,thenthebestfeasiblesolutionisupdated.Thesearchterminateswhenitisprovedthatnobettersoluti