Title of article :
Faster integer-feasibilityinmixed-integerlinearprogramsbybranchingto
force change
Author/Authors :
Jennifer Pryor، نويسنده , , JohnW.Chinneck ، نويسنده ,
Issue Information :
ماهنامه با شماره پیاپی سال 2011
Abstract :
Branchinginmixed-integer(orinteger)linearprogrammingrequireschoosingboththebranching
variable andthebranchingdirection.Thispaperdevelopsanumberofnewmethodsformakingthosetwo
decisionseitherindependentlyortogetherwiththegoalofreachingthefirstinteger-feasiblesolution
quickly.Thesenewmethodsarebasedonestimatingtheprobabilityofsatisfyingaconstraintatthechild
node givenavariable/directionpair.Thesurprisingresultisthatthefirstinteger-feasiblesolutionis
usuallyfoundmuchmorequicklywhenthevariable/directionpairwiththesmallestprobabilityof
satisfyingtheconstraintischosen.Thisisbecausethisselectionforceschangeinmanycandidate
variablessimultaneously,leadingtoaninteger-feasiblesolutionsooner.Extensiveempiricalresultsare
given.
Keywords :
Integer feasibility , Mixed-integer programming , Branching
Journal title :
Computers and Operations Research
Journal title :
Computers and Operations Research
