Multiple Objective Programming with Piecewise Line

MultipleObjectiveProgrammingwithPiecewiseLinearFunctionsStefanNickelandMalgorzataM.WiecekFachbereichMathematikUniversitatKaiserslautern67653KaiserslauternGermanySeptember23,1996AbstractAnapproachtogeneratingallecientsolutionsofmultipleobjectiveprogramswithpiecewiselinearobjectivefunctionsandlinearconstraintsispresented.Theapproachisbasedonthedecompositionofthefeasiblesetintosubsets,referredtoascells,sothattheoriginalproblemreducestoaseriesoflinearmultipleobjectiveprogramsoverthecells.Theconceptsofcell-eciencyandcomplex-eciencyareintroducedandtheirrelationshipwitheciencyisexamined.Agenericalgorithmforndingecientsolutionsisproposed.Applicationsinlocationtheoryaswellasinworstcaseanalysisarehighlighted.OnsabbaticalleavefromtheDepartmentofMathematicalSciences,ClemsonUniversity,Clemson,SC29634-1907,U.S.A.,e-mail:[e-mail]11IntroductionTheoryandmethodologyofmultipleobjectivelinearprogramming(MOLP)havebeenalreadyintensivelystudiedandapliedtoavarietyofdecisionmakingproblems.Inpartic-ular,theecientsetofthoseproblemscanbenoweasilycomputedbymeansofvariousalgorithms.See[YuandZeleny,1975],[Gal,1977],[Isermann,1977],[Eckeretal.,1980],[Steuer,1986],[Armand,1993],[WiecekandZhang,1996]fordierentmethodologiesofndingtheecientset.Similarly,problemswithconvexobjectivefunctionsoveraconvexfeasiblesethavebeentreated,althoughtheirecientsetisingeneralnotavailableinsuchanelegantformasitisforlinearproblems(see[HaimesandChankong,1983]).Motivatedbyapplications,inthispaperweexaminepossiblyasimplestclassofconvexproblems,i.e.multipleobjectiveproblemswithpiecewiselinearobjectivefunctionsandlinearcon-straints,forwhichwedevelopanMOLP-typedescriptionoftheecientsetandproposeanapproachtondingthisset.Singleormultipleobjectivepiecewiselinearprogramshavebeenalsostudiedbyotherau-thors.Fourer([Fourer,1985],[Fourer,1988],[Fourer,1992])extendedthesimplexmethodforlinearprogrammingtopermittheminimizationofaconvexpiecewiselinearfunction.Achary([Achary,1989])developedasimplextypemethodforatransportationproblemwithtwoobjectivefunctions:apiecewiselinearconvexfunctionandapiecewiseconstantfunctionrepresentingcostandtimerespectively.Multipleobjectivepiecewiselinearprograms(MOPLPs)specicallyariseinlocationprob-lems,wheregivenanumberofexisitingfacilitiesanewfacilityhastobelocatedsothatsomeobjectivesareoptimized.Theobjectivesareoftenintheformofpiecewiselinearfunc-tionsduetothefactthattypicallythesum(orthemaximum)ofweighteddistancesfromtheexistingfacilitestothenewfacilityischosenasacriterion.Moreover,thesedistancesareoftenderivedfromnormswithapolyhedralunitball.See[DurierandMichelot,1986],[PelegrinandFernandez,1988],[HamacherandNickel,1993],and[PuertoandFernandez,1994]forvariousMOPLPmodelsinlocationtheory.Anotherareaofapplicationismultipleobjectiveworstcaseanalysis.If,forexample,thecoecientsofalinearobjectivefunctionshouldrepresentcostofintroducinganewproductonthemarket,theirexactnumericalvaluesareusuallyunknownbutmaybeavailablefrommarketanalysisintheformofacollectionofvectors.Underthisuncertainty,theworstcaseanalysisdictatesthattheresultingobjectivefunctionbedeterminedthroughthemaximizationoverthelinearfunctionscorrespondingtothevectorsinthecollectionandhencetheobjectivefunctionbecomesapiecewiselinearfunction.Furthermore,inordertoobtainamorestructureddescriptionoftheecientsetofconvexmultipleobjectiveprogramsonemayconsiderapproximatingtheconvexobjectivefunc-tionsbypiecewiselinearfunctions.Suchanapproximationmethodincludingerrorboundanalysiswasproposedby[Burkardetal.,1991].Wenotethatasasingleobjectivepiecewiselinearprogramcanbetransformedintoalinearprogram(see[Murty,1983],p.18),thenalsoanMOPLPcanbeconvertedintoamultipleobjectivelinearprogramforwhichsolutiontechniquesareavailable,asmentionedbefore.Suchatransformation,however,wouldsignicantlyincreasethenumberofvariablesand2constraints.Theapproachpresentedinthispaperdoesnotincreasethesizeoftheproblem,butisbasedonthedecompositionofthefeasiblesetintosubsets,referredtoascells,sothattheoriginalproblemreducestoaseriesoflinearmultipleobjectiveprogramsoverthecells.Theapproachisanextensionofthealgorithmproposedby[Nickel,1995]formultiple-objectiveplanarlocationproblems.InthenextsectiontheMOPLPisformulatedandbasicconceptsarepresented.ThedecompositionofthefeasiblesetisstudiedinSection3.Theconceptsofcell-eciencyandcomplex-eciencyareintroducedinSection4andtheirrelationshipwitheciencyisexamined.Section5includesagenericalgorithmforndingtheecientsetofthebi-objectivepiecewiselinearprogram,andanillustrativeexampleiscontainedinSection6.Section7concludesthepaper.2DenitionsandbasicconceptsConsiderthefollowingmultipleobjectivepiecewiselinearprogram(MOPLP)minimize[f1(x);:::;fm(x)]s.t.x2X;)MOPLPwherefi(x)=max1kKiffi1(x);:::;fiKi(x)g;i=1;:::;m;fik(x)=(cik)Tx+dik;k=1;:::;Ki;cikisann1nitevector,dikisascalar,Kiisthenumberofanefunctionsfikdeningthepiecewiselinearfunctionfi,X=fx2IRn:Ax=b;x0g,Aisanmnmatrixoffullrank,bisanm1vector.Foreveryfi;i=1;:::;m,wecanderiveasubdivisionofXbydeningcellsifCpii:=8:x2X