Minimum Cost Flow Problem Formulation

Supposed you have several locations, indexed i=1,...,n

These locations have demands and supplies.  We’ll denote b_i as the supply from location i.  A negative b_i indicates a demand at location i.

The arc set A contains arcs (i,j) for directed arcs from location i to j.  The node set N contains the location indices {1,...,n}

Define x_{ij}= amount of commodity moved from location i toj.

Define c_{ij}=cost of moving one unit of commodity from location i to j.

The LP is then

Minimize\displaystyle\sum_{(i,j)\in A}{c_{ij}x_{ij}}

Subject to \displaystyle\sum_{(j\colon(i,j)\in A)} {x_{ij}}-\sum_{(j\colon(j,i)\in A)}x_{ij}=b_i           \forall i\in N

The constraints’ first terms are all the flow leaving i to the various js.  The second terms are all the flow entering i from the various js.

b_i will be 0 if the location is an intermediary, <0 if it’s a demand node and >0 if it’s a supply node.

Bookmark and Share


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: