An LP Formulation Example:Minimum Cost FlowThe Minimum Cost Flow (MCF) problem is a frequently used model. It canbe described in our context as follows.ModelGiven a network with N nodes and links among them. We would like totransport some entity among nodes (for example, data), so that it flowsalong the links. The goal is to determine the optimal flow, that is, how muchflow is put on each link, according to the conditions discussed below.Let us review the input for the problem, the objective and constraints andthen let us formulate it as a linear programming task.Input data:• The link from node i to j has a given capacity Cij≥ 0.• Each node i is associated with a given number bi, the source rate of thenode. If bi> 0, the node is called a source, if bi< 0, the node is a sink.If bi= 0, the node is a “transshipment” node that only forwards theflow with no loss and no gain.• Each link is associated with a cost factor aij≥ 0. The value of aijisthe cost of sending unit amount of flow on link (i, j). Thus, sending xijamount of flow on the link costs aijxij.Remarks:• The links are directed in this model, Cijand Cjimay be different.• If the link from i to j is missing from the network, then Cij= 0. Thus,the capacities automatically describe the network topology, too.Constraints:• Capacity constraint: The flow on each link cannot exceed the capacityof the link.• Flow conservation: The total outgoing flow of a node minus the totalincoming flow of the node must be equal to the source rate of the node.That is, the difference between the flow out and into the node is exactlywhat the node produces or sinks. For transshipment nodes (bi= 0) theoutgoing and incoming flow amounts are equal.Objective:Find the amount of flow sent on each link, so that the constraints are satisfiedand the total cost of the flow is minimized.LP FormulationLet xijdenote the flow on link (i, j). The xijare the variables we want todetermine.Let us express the constraints:• The flow is nonnegative (by definition):xij≥ 0 (∀i, j)• Capacity constraints:xij≤ Cij(∀i, j)• Flow conservation:NXj=1xij−NXk=1xki= bi(∀i)Here the first sum is the total flow out of node i, the second sum is thetotal flow into node i.The objective function is the total cost, summed for all choices of i, j :Z =Xi,jaijxijThus, the LP formulation is:min Z =Xi,jaijxijsubject toNXj=1xij−NXk=1xki= bi(∀i)xij≤ Cij(∀i, j)xij≥ 0 (∀i, j)Is this in standard form? No, but can be easily transformed into standardform. Only the xij≤ Cijinequalities have to be transformed into equations.This can b e done by introducing slack variables yij≥ 0 for each, and replacingeach original inequality xij≤ Cijby xij+ yij=
View Full Document
Unlocking...