Title of article
Faster integer-feasibilityinmixed-integerlinearprogramsbybranchingto force change
Author/Authors
Jennifer Pryor، نويسنده , , JohnW.Chinneck ، نويسنده ,
Issue Information
ماهنامه با شماره پیاپی سال 2011
Pages
10
From page
1143
To page
1152
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
Serial Year
2011
Journal title
Computers and Operations Research
Record number
927933
Link To Document