Hybrid-LP:Findingadvancedstartingpointsforsimplex,and pivoting Lpmethods

The simplexmethodhasprovenitsefficiencyinpracticeforlinearprogramming(LP)problemsof varioustypesandsizes.However,itstheoreticalworst-casecomplexityinadditiontoitspoor performanceforverylarge-scaleLPproblemshasdrivenresearcherstodevelopalternativemethodsfor LP problems.Inthispaper,wedevelopthehybrid-LP;atwo-phaseapproachforsolvingLPproblems. Ratherthanfollowingapathofextremepointsontheboundaryofthefeasibleregionasinthesimplex method,thefirstphaseofthehybrid-LPmovesthroughtheinteriorofthefeasibleregiontoobtainan improvedandadvancedinitialbasicfeasiblesolution(BFS).Then,inthesecondphasesimplexorother LP methodscanbeusedtofindtheoptimalsolution. Since theintroductionofpolynomial-timemethodsforLP,aconsiderableamountofresearchhas focusedoninterior-pointmethodsforsolvinglarge-scaleLPproblems.Althoughfeweriterationsare needed forinterior-pointmethodstoconvergetoasolution,theiterationsarecomputationally intensive.Ourapproachisahybridmethodthatusesacomputationallyefficientpivottomoveinthe interior ofthefeasibleregioninitsfirstphase.Thissingleiterationisabletobypassingseveralextreme pointstoanimprovedBFS,whichcanthenbeusedasastartingpointinanyLPmethodinthesecond phase ofthemethod.Ourapproachcanalsobemodifiedtoperformanumberofinteriorpivotsinthe first phasebasedonthetrade-offbetweenthenumberofiterationsandtherunningtime. The hybrid-LPusesanefficientpivotingiterationwhichiscomputationallycomparabletothe standardsimplexiteration.Anotherfeatureisadaptabilityinfindingtheadvancedstartingpointby avoidingtheboundariesofthefeasibleregion.Inaddition,thehybrid-LPhastheabilitytostartfroma feasiblepointwhichmaynotbeaBFS.Ourcomputationalexperimentsdemonstratethatthehybrid-LP reducesboththenumberofiterationsandtherunningtimecomparedtothesimplexmethodonawide range oftestproblems.