k-Disjunctive cuts and a finite cutting plane algo

arXiv:0707.3945v1[math.OC]26Jul2007k-disjuntiveutsandaniteuttingplanealgorithmforgeneralmixedintegerlinearprogramsMarkusJrgTehnisheUniversittMnhen,ZentrumMathematikBoltzmannstrae3,85747GarhingbeiMnhen,Germanyjoergma.tum.deJuly26,2007Abstrat:InthispaperwegiveageneralizationofthewellknownsplitutsofCook,KannanandShrijver[5℄toutswhiharebasedonmulti-termdisjuntions.Theywillbealledk-disjuntiveuts.Thestartingpointisthequestionwhatkindofutsisneededforaniteuttingplanealgorithmforgeneralmixedintegerprograms.Wewilldealwiththisquestionindetailandderiveuttingplanesbasedonk-disjuntionsrelatedtoagivenutvetor.FinallywewillshowhowaniteuttingplanealgorithmanbeestablishedusingtheseutsinombinationwithGomorymixedintegeruts.1IntrodutionInthispaperwewilldealwithuttingplanesandrelatedalgorithmsforgeneralmixedintegerlinearprograms(MILP).Asmostoftheresultswillbederivedbygeometriargumentswefousonprogramsthataregivenbyinequalityonstraints,i.e.maxcx+hyAx+Gy≤bx∈Zp(1)wheretheinputdataarethematriesA∈Qm×p,G∈Qm×q,theolumnvetorb∈Qmandtherowvetorsc∈Qp,h∈Qq.MoreoverwedenotebythepolyhedraP={(x,y):Ax+Gy≤b}⊂Rp+qandPI=conv({(x,y)∈P:x∈Zp})⊂Rp+qthefeasibledomainsoftheLPrelaxationandthe(mixed)integerhullofagivenMILP,respetively.Weall1aMILPbounded,ifthepolyhedronPisbounded.WewillalsoneedtheprojetionprojX(P):={x∈Rp:∃y∈Rq:(x,y)∈P}ofthepolyhedronPonthespaeoftheintegervariables.ByauttingplaneforPweunderstandaninequalityαx+βy≤γwithrowvetorsα∈Qp,β∈QqwhihisvalidforPIbutnotforP.UsinguttingplanesgivesasimpleideaofhowtosolveageneralMILP:SolvetheLPrelaxationoftheMILP.Iftheoptimalsolutionisfeasible,i.e.satisestheintegralityonstraint,anoptimalsolutionisfound.Otherwisendavaliduttingplanethatutsotheurrentsolutionandrepeat.ButunlikethepureintegerasenoniteexatuttingplanealgorithmisknownforgeneralMILP.ThereforweremarkthatmostuttingplanesforgeneralMILPsuhase.g.Gomorymixedintegeruts[7℄ormixedintegerroundinguts[11℄arespeialasesoforequivalenttosplituts[5℄.Thisfatandmoredetailedrelationsbetweentheseandotherutsarestatedin[6℄.Hereasplitutisdenedasauttingplaneαx+βy≤γforPwiththeadditionalpropertythatthereexistsd∈Zp,δ∈Zsuhthatαx+βy≤γisvalidforall(x,y)∈Pwhihsatisfythesplitdisjuntiondx≤δordx≥δ+1.Sosplitutsaredenednotonstrutivelybutbyaproperty,only.Nowoneanseeinthefollowing’lassial’exampleofCook,KannanandShrijver[5℄thatsplitutsarenotsuientforsolvingageneralMILPinnitetime.Example1.TheMILPmaxy−x1+y≤0−x2+y≤0x1+x2+y≤2x1,x2∈Zhastheoptimalobjetivefuntionvalue0buttheproblemannotbesolvedbyanyalgo-rithmthatusessplituts,only.AproofofthisstatementinamoregeneralontextisgiveninLemma3.Ontheotherhand,aspositiveresultsintheontextofuttingplanealgorithmsforMILPweanonlygivethefollowingtwospeialases:Formixed0-1programssplitutsaresuientforgeneratingtheintegerhullPIofagivenpolyhedronP.Seee.g.[11℄intheontextofmixedintegerroundingutsor[3℄inthemorereentrepresentationoflift-and-projetuts.ForgeneralMILP,thereonlyexistsaniteapproximationalgorithmofOwenandMehrotra[12℄whihndsafeasibleǫ-optimalsolutionandusessimplesplituts,thatmeanssplitutstodisjuntionsxi≤δ∨xi≥δ+1.SoassplitutsfailinthedesignofaniteuttingplanealgorithmforgeneralMILPwewanttogeneralizethisapproahtoutsthatarebasedonmulti-termdisjuntions.Thereforwestartinsetion2withtheintrodutionofk-disjuntiveutsandsomeofitsbasiproperties.Afterwardswelookattheapproximationpropertiesofthek-disjuntivelosuresanddealwiththequestionwhatkindofutsisneededforanexatniteutting2planealgorithmbothingeneralandinspeialases.Finallywederiveak-disjuntiveutaordingtoagivenutvetor.Insetion3weturntoalgorithmiaspetsandgiveawayofhowaniteuttingplanealgorithmforgeneralMILPanbedesignedusingk-disjuntiveutsinonnetionwiththewellknownmixedintegerGomoryuts.Finallywewilldisussthealgorithmandgivesomeinterpretations.1.1PreliminariesHerewerepeattwobasiresultsthatwewillneedduringthispaper.TherstonedealswiththeomputationoftheprojetionprojX(P),theseondonewiththeonvergeneofthemixedintegerGomoryalgorithminaspeialase.Lemma1.LetapolyhedronP={(x,y):Ax+Gy≤b}begiven.ThenprojX(P)={x∈Rp:vrAx≤vrb,∀r∈R},where{vr}r∈RisthesetofextremeraysoftheoneQ:={v∈Rm:GTv=0,v≥0}.Proof.ThestatementfollowsbyapplyingtheFarkasLemma,seee.g.[10℄,I.4.4.NextwelookattheusualmixedintegerGomoryalgorithm[7℄.Althoughthealgorithmdoesingeneralnotevenonvergetotheoptimum,thespeialaseinwhihtheoptimalobjetivefuntionvalueanbeassumedtobeinteger,e.g.theaseofh=0,anbesolvednitelyusingthealgorithm.IndetailwehavethefollowingTheorem1.LetaboundedMILP(1)begiven.ThenthemixedintegerGomoryal-gorithmterminatesnitelywithanoptimalsolutionordetetsinfeasibilityunderthefollowingonditions:1.OneusesthelexiographiversionofthesimplexalgorithmforsolvingtheLPre-laxation.2.Theoptimalobjetivefuntionvalueisintegral.3.Aleastindexruleisusedforutgeneration,i.e.themixedintegerGomoryutaordingtotherstvariablexj,thatisfrationalintheurrentLPsolution,isaddedtotheprogram.Herex0orrespondstotheobjetivefuntionvalue.Usingthelasttheorem,itisobviousthatweanhekinnitetimeifthereisafeasiblepointinapolytopewithagiven(rational)objetivefuntionvalue,asbysalingitanbealways