Title of article
An interiorpointcuttingplaneheuristicformixedintegerprogramming
Author/Authors
Joe Naoum-Sawaya، نويسنده , , SamirElhedhli، نويسنده ,
Issue Information
ماهنامه با شماره پیاپی سال 2011
Pages
7
From page
1335
To page
1341
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
Serial Year
2011
Journal title
Computers and Operations Research
Record number
927950
Link To Document