Title of article
Minimal-costnetworkflowproblemswithvariablelowerboundsonarcflows
Author/Authors
Xiaoyan Zhu، نويسنده , , QiYuan ، نويسنده , , AlbertoGarcia-Diaz ، نويسنده , , Liangdong Ma، نويسنده ,
Issue Information
ماهنامه با شماره پیاپی سال 2011
Pages
9
From page
1210
To page
1218
Abstract
The minimal-costnetworkflowproblemwithfixedlowerandupperboundsonarcflowshasbeenwell
studied.Thispaperinvestigatesanimportantextension,inwhichsomeorallarcshavevariablelower
bounds.Inparticular,anarcwithavariablelowerboundisallowedtobeeitherclosed(i.e.,thenhaving
zero flow)oropen(i.e.,thenhavingflowbetweenthegivenpositivelowerboundandanupperbound).
This distinctivefeaturemakesthenewproblemNP-hard,althoughitsformulationbecomesmorebroadly
applicable,sincetherearemanycaseswhereaflowdistributionchannelmaybeclosediftheflowonthe
arc isnotenoughtojustifyitsoperation.Thispaperformulatesthenewmodel,referredtoasMCNF-VLB,
as amixedintegerlinearprogramming,andshowsitsNP-hardcomplexity.Furthermore,anumerical
exampleisusedtoillustratetheformulationanditsapplicability.Thispaperalsoshowsacomprehensive
computationaltestingonusingCPLEXtosolvetheMCNF-VLBinstancesofuptomedium-to-largesize.
Keywords
Network optimization , Variable lower bound , Minimal cost network flow , Generalized network
Journal title
Computers and Operations Research
Serial Year
2011
Journal title
Computers and Operations Research
Record number
927939
Link To Document