Title of article :
An interiorpointcuttingplaneheuristicformixedintegerprogramming
Author/Authors :
Joe Naoum-Sawaya، نويسنده , , SamirElhedhli، نويسنده ,
Issue Information :
ماهنامه با شماره پیاپی سال 2011
Abstract :
We exploretheuseofinteriorpointmethodsinfindingfeasiblesolutionstomixedintegerprogramming.
As integersolutionsaretypicallyintheinterior,weusetheanalyticcentercuttingplanemethodtosearch
for integerfeasiblepointswithintheinteriorofthefeasibleset.Thealgorithmsearchesalongtwoline
segmentsthatconnecttheweightedanalyticcenterandtwoextremepointsofthelinearprogramming
relaxation.Candidatepointsareroundedandtestedforfeasibility.Cutsaimedtoimprovetheobjective
functionandrestorefeasibilityarethenaddedtodisplacetheweightedanalyticcenteruntilafeasible
integersolutionisfound.Thealgorithmiscomposedofthreephases.Inthefirst,pointsalongthetwoline
segmentsareroundedgraduallytofindintegerfeasiblesolutions.Theninanattempttoimprovethe
qualityofthesolutions,thecutrelatedtotheboundconstraintisupdatedandanewweightedanalytic
centerisfound.Uponfailingtofindafeasibleintegersolution,asecondphaseisstartedwherecutsrelated
to theviolatedfeasibilityconstraintsareadded.Asalastresort,thealgorithmsolvesaminimumdistance
probleminathirdphase.TheheuristicistestedonasetofproblemsfromMIPLIBandCORAL.The
algorithmfindsgoodqualityfeasiblesolutionsinthefirsttwophasesandneverrequiresthethirdphase.
Keywords :
Feasibility , Analytic center , Mixed integer problems , ACCPM , Interior point methods
Journal title :
Computers and Operations Research
Journal title :
Computers and Operations Research
