### Minimum Cost Flow Problem Formulation

Supposed you have several locations, indexed

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

The arc set A contains arcs for directed arcs from location to . The node set N contains the location indices

Define amount of commodity moved from location to.

Define cost of moving one unit of commodity from location to .

The LP is then

Minimize

Subject to

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

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