Strong formulations for mixed integer programs val

StrongFormulationsforMixedIntegerPrograms:ValidInequalitiesandExtendedFormulationsLaurenceA.Wolsey1April12,2003AbstractWeexamineprogressoverthelastfifteenyearsinfindingstrongvalidinequal-itiesandtightextendedformulationsforsimplemixedintegersetslyingbothonthe“easy”and“hard”sidesofthecomplexityfrontier.Mostprogresshasbeenmadeinstudyingsetsarisingfromknapsackandsinglenodeflowsets,andavarietyofsetsmotivatedbydifferentlot-sizingmodels.Weconcludebycitingbrieflysomeofthemoreintriguingnewavenuesofresearch.Keywords:MixedIntegerProgramming,StrongValidInequalities,ConvexHull,Ex-tendedFormulations,SingleNodeFlowSets,Lot-sizing1COREandINMA,Universit´eCatholiquedeLouvain,BelgiumThispaperpresentsresearchresultsoftheBelgianProgramonInteruniversityPolesofAt-tractioninitiatedbytheBelgianState,PrimeMinister’sOffice,SciencePolicyProgramming.Thescientificresponsibilityisassumedbytheauthors.ResearchcarriedoutwithfinancialsupportoftheprojectTMR-DONETnr.ERBFMRX–CT98–0202oftheEuropeanUnion11IntroductionLookingbackatasurveyonstrongformulationsforMixedIntegerProgramming(MIP)[62]publishedin1989,itisstrikingontheonehandtoseewhathasbeenlearntandwhatprogresshasbeenmade,andontheothertoseethatmanyofthequestionsthatneedansweringremainthesameasfourteenyearsago.Asbeforeweareinterestedinsets(structures)thatappearingeneralmixedintegerprograms,orinfairlygenericproblemssuchasfixedchargenetworkflow,productionplanningandschedulingproblems.Theideaisthentostudythesesets,soastodevelopeithergoodaprioriformulations,orstrongvalidinequalitiesthatcanbeaddeddynamicallyascuttingplanes.Comparedtofourteenyearsago,severalimportantchangescanbeobserved:•branch-and-cutandbranch-cut-and-pricehavedefinitelyreplacedbranch-and-boundasthealgorithmicparadigm•cuttingplaneshavebeenanintegralpartofthecommercialmixedintegerpro-grammingsystemssuchasXpress[66]andCplex[15]foraboutfiveyears,andhaveprovedveryeffectiveonawidevarietyofproblems•mostofthecuts,andeventheseparationalgorithmsorheuristicsusedinthesesystemsarenotnew–Gomorymixedintegercuttingplanes[19]datefrom1960,knapsackcoverinequalitiesfromthe70s,flowcover,pathandmixedintegerroundinginequalitiesfromthe80s.WhathaschangedisthatmuchgreatereffortsaremadetodetectthesesetswithinageneralMIP,andtheremarkableversatilityofmixedintegerroundingasacutgenerationtechniquehasbecomeapparent[39]•theimportanceofsuperadditiveliftingfunctionstoconvertvalidinequalitiesintostrongvalidinequalitieshasbeenmadeclear[23]•thestudyofsingleitemlot-sizingsetshasbeenfundamentallymodifiedbythestudyofspecial“Wagner-Whitin”objectivefunctionsleadingtothestudyofsimplersetsthatcanbeviewedastheintersectionsofdiscretelot-sizingsets[47].ThisinturnhasledtothestudyofmultipleMIP[40]andmixedMIPsets[24],aswellastothestudyofdynamicknapsacksets[33]2•progressindevelopingtightextendedformulationshasindicatedtheneedforsmallerapproximationsofsuchsets[57]•theideaofintroducingextendedformulationsonthefly(orintegergeneratingsets)evenfordifficultsets,seetheintegerbasismethodin[26,27],isintriguingandsuggestsmanynewpossibilities•thelift-and-projectapproach[9],anditsgeneralizationsincludingpositivesemi-definitereformulations[36],thereformulationlinearizationtechnique[54],andrecentgeneralizations[12,30]providebothextendedformulationsandnewcut-tingplanes.Wenowoutlinethecontentsofthispaper.InSection2webrieflydiscussthebasicdecompositionapproachusedintacklinganMIP,andthequestionstobeaskedrelativetoagivenMIPsetXappearingasasupersetorrelaxationofaspecificprobleminstance.WealsointroducethebasictwovariableMIPset,andthemixedintegerroundinginequality.InSections3-6,weexaminedifferentfamiliesofMIPsets,onboththe“easy”and“hard”sidesofthecomplexityfrontier.Foreachfamilywepresentafewbasicresults,aswellasanindicationofrecentprogress.InSection3westartonthe“hard”sidelookingatknapsackandsinglenodeflowsets,andshowanexampleofsuperadditivelifting.InSection4welookatknapsackandsinglenodeflowsetsthatare“easy”becausethedataisrestricted(e.g.thearccapacitiescanonlytakeoneortwodifferentvalues).InSection5westayonthe“easy”sideandlookatmultipleandmixedMIRsetsthathavebeenderivedfromconstantcapacitylot-sizingproblems.InSection6welookfurtheratlot-sizingsets,consideringboththeuncapacitatedcase,anddynamicknapsacksetsderivedfromthevaryingcapacity“hard”case.InSection7weindicatebrieflytwootherresearchdirectionsthatarebeingpursued:tightallintegerreformulationsfor“onthefly”reformulation,andapproximationsoftightextendedformulations.WeterminatewithamentionofafewrelatedresearchtopicsofimportanceforMIP.32TheApproachFormostpracticalMIPproblemsthereislittlechanceoffindingafastalgorithmora“nice”descriptionoftheconvexhullofthesolutionsetZ.Thereforeanaturalstrategyistodescribethesolutionsetintermsofsimplersetsthatweknowsomethingabout,orthatappearamenabletostudy.InparticularthecasewhereZ=∩Ii=1ZiistheintersectionofsimplesetsZiwithsomestructureisofpracticalinterest.ForsimplicitywesupposebelowthatI=2.2.1TheDecompositionApproachWesupposethattheMIPtobesolvedisgivenintheformmin{cx+fy:(x,y)∈Z}whereZ=P∩(IRn1×ZZn2)andP={(x,y)∈IRn1×IRn2:Ax+Gy≤b}isaformulation(polyhedr