ApplicationsofNetworkFlowsJeffreyA.Appleget, Steven B.HortonIntroductionAgreatvarietyofmilitaryproblemscanbemodeledwithnetworkflows.Thischapterwilldiscusstwoofthemostbasicnetworkflowproblems:maximumflowand shortest path.Beforewecangettothesemilitaryapplications,however,it isimportant to understand some of thefundamental conceptsof linearprogramming and how they relate to integer programming. If you are generallyfamiliarwiththeseconcepts,youcanskipthenextsection.Linearand IntegerProgrammingA linear program is an optimization problem of theformmaximize Zc,x,j=1Nsubject to: Za,x, ≤b, (i= 1,...m)j=1x,≥0(j = 12...n).The x, terms are the decision variables and the au,b,,and c, terms are dataZc,x, is called the objective function andthat are typically part of the problem.botha,x,≤b, and x,≥0 are called constraints.Constraints of the formj=1X≥0 areknownasnonnegativityconstraints.Notethat inthestandardformabove thereare n nonnegativity constraints and m of the other type.ExampleGiapetto's Woodcarving,Inc.manufactures and sells toy soldiers and toy trainsA soldier sells for $27 and a train sells for $21. We assume all soldiers andtrainsmanufactured canbesold.Soldiersrequire12hoursoflaborand2unitsofwood.Trainsrequire3hoursoflaborand7unitsofwood.ForthisweekGiapettohas81hoursof laborand 111units of woodavailable.Howmanysoldiersandtrainsshouldhemaketomaximizerevenue?141
141 Applications of Network Flows Jeffrey A. Appleget, Steven B. Horton Introduction A great variety of military problems can be modeled with network flows. This chapter will discuss two of the most basic network flow problems: maximum flow and shortest path. Before we can get to these military applications, however, it is important to understand some of the fundamental concepts of linear programming and how they relate to integer programming. If you are generally familiar with these concepts, you can skip the next section. Linear and Integer Programming A linear program is an optimization problem of the form ( ) 0 ( 1,2,., ). subject to : 1,2,., maximize 1 1 x j n a x b i m c x j n j ij j i n j j j ³ = å £ = å = = The i x terms are the decision variables and the aij , bi , and c j terms are data that are typically part of the problem. å= n j j j c x 1 is called the objective function and both and 0 1 å £ ³ = j n j ij j i a x b x are called constraints. Constraints of the form x j ³ 0 are known as nonnegativity constraints. Note that in the standard form above there are n nonnegativity constraints and m of the other type. Example Giapetto’s Woodcarving, Inc. manufactures and sells toy soldiers and toy trains. A soldier sells for $27 and a train sells for $21. We assume all soldiers and trains manufactured can be sold. Soldiers require 12 hours of labor and 2 units of wood. Trains require 3 hours of labor and 7 units of wood. For this week, Giapetto has 81 hours of labor and 111 units of wood available. How many soldiers and trains should he make to maximize revenue?
Thefirststepinsolvingthistype(andmostothertypes)ofproblemistodefineyour variables.Ifwelet x,bethe numberofsoldierstomakeandx,bethenumberoftrainstomake,wecanthinkofGiapetto'sproblemasthefollowinglinearprogram:maximize27x,+21x2subjectto:12x,+3x2≤812X, +7X, ≤111X,≥0X2 ≥0The first line is the objective function. In this case it represents the money thatGiapettogetsforeachpossibledecisionhemightmake.Thefirsttwoconstraintsrepresentrestrictionsimposedbythelimitedsupplyoflaborandwood,respectively,atGiapetto'sdisposal.Theothertwo constraints are simplylogicalrestrictions against building a negative numberof soldiers ortrains.Althoughitwillnotbecoveredhere,thereareanumberofwaystofindthesolution to linearprograms.See[2] or[3] if you'd liketo learnmoreabout thesemethods.ThesolutiontotheexampleaboveisX,=3andX,=15.Canyouthink ofa way to find this solution?Look atthepicture in figure1below of theregion where each of the four inequalities is satisfied. This region of allowablesolutions is called the feasible region. Does thishelpyou see a waytosolve thistypeofproblem?Howdoestheobjectivefunctiongetconsidered inyoursolutionmethod?I10Figure1:FeasibleRegion142
142 The first step in solving this type (and most other types!) of problem is to define your variables. If we let 1 x be the number of soldiers to make and 2 x be the number of trains to make, we can think of Giapetto’s problem as the following linear program: 0 0 2x 7 111 subject to : 12x 3 81 maximize 27x 21 2 1 1 2 1 2 1 2 ³ ³ + £ + £ + x x x x x The first line is the objective function. In this case it represents the money that Giapetto gets for each possible decision he might make. The first two constraints represent restrictions imposed by the limited supply of labor and wood, respectively, at Giapetto’s disposal. The other two constraints are simply logical restrictions against building a negative number of soldiers or trains. Although it will not be covered here, there are a number of ways to find the solution to linear programs. See [2] or [3] if you’d like to learn more about these methods. The solution to the example above is 1 x = 3 and 2 x = 15. Can you think of a way to find this solution? Look at the picture in figure 1 below of the region where each of the four inequalities is satisfied. This region of allowable solutions is called the feasible region. Does this help you see a way to solve this type of problem? How does the objective function get considered in your solution method? Figure 1: Feasible Region
Noticethattheoptimal solutionof x,=3andx,=15"happens"tooccurwheretwooftheconstraintsintersect.Doyouthinkthisisacoincidence?Something you might have noticed about the example above is the fact that wewere lucky enoughto havean integral optimal solution.An integral solution isone where each decision variable is an integer (whole number).This would havemade it easytotell Giapettowhat todo:make3soldiers and 15trains.Supposewemakeaverysmall changeintheproblemandgiveGiapettoanextrahouroflaborforatotalof82.Nowthelinearprogramismaximize27x,+21x2subjectto:12x,+3x,≤822×, +7×2≤111X,≥0X2 ≥0This small change hastheeffect of moving one ofthe constraints“out"slightlyYou can again find the linear program solution graphically or with some other241method, but it is unfortunately no longer integral:x,=3.0897and78584=14.9744.Whilewecan'ttellGiapettotomake3.0897soldiersandX23914.9744 trains, we can at least stick with our old solution of 3 soldiers and 15trains and"waste"the extra hour of labor.There is no longer any assurance that(3,15)isthebest solution,but it is atleast afeasiblesolution, since it obviouslystill satisfiesall oftheconstraints.Ontheotherhand,considerwhathappens ifweloseanhouroflaborasopposedtogainingone.Nowourlinearprogramismaximize27x,+21x2subjectto:12x,+3x,≤802x,+7x2≤111X,≥0X2 ≥0227=2.9103andandtheoptimal linearprogramsolution isX,78586=15.0256.Nowwehavebiggerproblems.NotonlyisournewX239solution not integral,but our old friend and previous solution (3,15)is now notfeasiblesinceitviolatesthefirstconstraint.Sonowevenfindingafeasible143
143 Notice that the optimal solution of 1 x = 3 and 2 x = 15 “happens” to occur where two of the constraints intersect. Do you think this is a coincidence? Something you might have noticed about the example above is the fact that we were lucky enough to have an integral optimal solution. An integral solution is one where each decision variable is an integer (whole number). This would have made it easy to tell Giapetto what to do: make 3 soldiers and 15 trains. Suppose we make a very small change in the problem and give Giapetto an extra hour of labor for a total of 82. Now the linear program is 0 0 2x 7 111 subject to : 12x 3 82 maximize 27x 21 2 1 1 2 1 2 1 2 ³ ³ + £ + £ + x x x x x This small change has the effect of moving one of the constraints “out” slightly. You can again find the linear program solution graphically or with some other method, but it is unfortunately no longer integral: 3.0897 78 241 x1 = @ and 14.9744 39 584 x2 = @ . While we can’t tell Giapetto to make 3.0897 soldiers and 14.9744 trains, we can at least stick with our old solution of 3 soldiers and 15 trains and “waste” the extra hour of labor. There is no longer any assurance that (3,15) is the best solution, but it is at least a feasible solution, since it obviously still satisfies all of the constraints. On the other hand, consider what happens if we lose an hour of labor as opposed to gaining one. Now our linear program is 0 0 2x 7 111 subject to : 12x 3 80 maximize 27x 21 2 1 1 2 1 2 1 2 ³ ³ + £ + £ + x x x x x and the optimal linear program solution is 2.9103 78 227 x1 = @ and 15.0256 39 586 x2 = @ . Now we have bigger problems. Not only is our new solution not integral, but our old friend and previous solution (3,15) is now not feasible since it violates the first constraint. So now even finding a feasible
solutionseemstobea challenge.Infact,althoughlinearprogramsareefficientlysolvable,noefficientprocedureisknowntosolveall integerprogrammingproblems.Anintegerprogramissimplyalinearprograminwhichthedecisionvariables can onlybe integers.A binary integer programis a linear programwherethedecisionvariables canonlytakeonthevalues0or1.There areseveral points here.Linear programs are easytosolve,but whenourproblem requiresan integral solution intherealworld,the linearprogrammingmodelgenerallyfailstogiveuswhatweneed.However,whenthelinearprogrammingsolutionhappenstobeintegral,weknowwehavetherightanswer:wecan gotell Giapetto what to dodirectlyfrom this solution without anyinterpretation or other difficulties.Fortunately,there are several general classesofproblemswhereundercertainconditionsthe linearprogramming solutionalwaysworksouttobeintegral.Amongthesearethetwotypesofproblemswewillstudynext:maximumflowsandshortestpaths.ModelingMilitaryMaximumFlowProblemsYou are the movement officer for an infantry division.The division must movefrom the port of debarkation to an assembly area in the corps rear area. Figure 2is a model of the roadnetwork in yourarea.Your task is toget as manycompaniesaspossibletotheassemblyareainthefirsthour.25Figure2:MaximumFlowExampleThe starting nodes representstheport of debarkationand thetermination nodetrepresentstheassemblyarea.Othernodesrepresentroadjunctions.Arcsareidentified by the nodes whichthey connect. Eacharc represents a road, andeachroadhasacapacity,Ci,incompaniesperhour,asshown.Forexample,the arc (3,6) has a capacity of 7 companies per hour, while for arc (6,t), C, = 8.Weassumethatthearcsare one-way,or directed arcs.We call the overallnetwork G=(N,A) where Nis the set of all nodes (s,2,3...,n-1,t) and A is the setof all existing arcs (s,2),(s,3).(s,6),(3,6),..,(6,t),(7,t),(8,t).144
144 solution seems to be a challenge. In fact, although linear programs are efficiently solvable, no efficient procedure is known to solve all integer programming problems. An integer program is simply a linear program in which the decision variables can only be integers. A binary integer program is a linear program where the decision variables can only take on the values 0 or 1. There are several points here. Linear programs are easy to solve, but when our problem requires an integral solution in the real world, the linear programming model generally fails to give us what we need. However, when the linear programming solution happens to be integral, we know we have the right answer: we can go tell Giapetto what to do directly from this solution without any interpretation or other difficulties. Fortunately, there are several general classes of problems where under certain conditions the linear programming solution always works out to be integral. Among these are the two types of problems we will study next: maximum flows and shortest paths. Modeling Military Maximum Flow Problems You are the movement officer for an infantry division. The division must move from the port of debarkation to an assembly area in the corps rear area. Figure 2 is a model of the road network in your area. Your task is to get as many companies as possible to the assembly area in the first hour. s t 2 3 4 5 6 7 8 5 7 7 6 3 4 8 4 2 5 6 5 2 2 Figure 2: Maximum Flow Example The starting node s represents the port of debarkation and the termination node t represents the assembly area. Other nodes represent road junctions. Arcs are identified by the nodes which they connect. Each arc represents a road, and each road has a capacity, cij , in companies per hour, as shown. For example, the arc (3,6) has a capacity of 7 companies per hour, while for arc (6,t), cij = 8. We assume that the arcs are one-way, or directed arcs. We call the overall network G=(N,A) where N is the set of all nodes {s,2,3,.,n-1,t} and A is the set of all existing arcs {(s,2),(s,3),(s,6),(3,6),.,(6,t),(7,t),(8,t)}
Wecanmodelthismaximumflowproblemusing linearprogramming.LetXrepresentthenumberofcompaniesthattravelonroad(ij).Tosimplifythemodel, we add the arc (t,s) and setcts = oomax XtsstZx-Zx,=0forieN(J(iJ)EA)(J(JJ)=A)X, ≤C, for all(i,j) AX, ≥ 0 forall(i, j) A.As we discussed in section ll, this is a type of problem where solving the linearprogramwillalwaysgiveas anintegralsolutionas longaseachC,isanintegerModelingMilitaryShortestPathProblemsThe shortest pathproblem is another simple network flow problem.As the nameimplies,theshortest pathproblemfindsthe shortestpathbetweentwopoints.Forsimplicity,wewillconsidershortestpathproblemsthatfindtheshortestpathfromsomestartingnodestoaterminationnodet.Militaryapplications includefinding the shortest path fordeploying a unit from some rear assemblyarea toatactical assemblyarea and findingthe mostreliable route between two nodes.Example:DeployingaunitAs the S-3 of the 1st Forward Support Battalion, you are tasked to find theshortestroutefromAssemblyAreaAlphatoTacticalAssemblyAreaSupportYouaregivenasketchoftheroad network infigure3below5Figure3:ShortestPathExample145
145 We can model this maximum flow problem using linear programming. Let xij represent the number of companies that travel on road (i,j). To simplify the model, we add the arc (t,s) and setcts = ¥ . 0 for all ( , ) . for all( , ) 0 for max { :( , ) } { :( , ) } x i j A x c i j A st x x i N x ij ij ij j j i A ji j i j A ij ts ³ Î £ Î å - å = Î Î Î As we discussed in section II, this is a type of problem where solving the linear program will always give as an integral solution as long as each cij is an integer. Modeling Military Shortest Path Problems The shortest path problem is another simple network flow problem. As the name implies, the shortest path problem finds the shortest path between two points. For simplicity, we will consider shortest path problems that find the shortest path from some starting node s to a termination node t. Military applications include finding the shortest path for deploying a unit from some rear assembly area to a tactical assembly area and finding the most reliable route between two nodes. Example: Deploying a unit As the S-3 of the 1st Forward Support Battalion, you are tasked to find the shortest route from Assembly Area Alpha to Tactical Assembly Area Support. You are given a sketch of the road network in figure 3 below. s t 2 3 4 5 6 7 8 5 4 7 6 3 4 8 5 2 4 9 5 4 7 Figure 3: Shortest Path Example