Minimum Cost Flow Problem Formulation

2009 February 13
tags: , , ,
by jysung

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

from → Proofs, OR Resources, School

No comments yet

Leave a Reply

Note: You can use basic XHTML in your comments. Your email address will never be published.

Subscribe to this comment feed via RSS