The Transportation Problem in AMPL

AMPL Formulation

The formulation of the transportation problem is AMPL is a straighforward translation of the matehmatical programme for the transportation problem.

The sets and are declared as SUPPLY_NODES and DEMAND_NODES respectively:

set SUPPLY_NODES;
set DEMAND_NODES;

The supply and demand are declared as integer parameters:

param Supply {SUPPLY_NODES} >= 0, integer;
param Demand {DEMAND_NODES} >= 0, integer;

The cost is declared over the SUPPLY_NODES and DEMAND_NODES:

param Cost {SUPPLY_NODES, DEMAND_NODES};

Now, the mathematical programme follows directly:

var Flow {SUPPLY_NODES, DEMAND_NODES} >= 0, integer;

minimize TotalCost:
  sum {i in SUPPLY_NODES, j in DEMAND_NODES} Cost[i, j] * Flow[i, j];

subject to UseSupply {i in SUPPLY_NODES}:
  sum {j in DEMAND_NODES} Flow[i, j] = Supply[i];

subject to MeetDemand {j in DEMAND_NODES}:
  sum {i in SUPPLY_NODES} Flow[i, j] = Demand[j];

Adding Bounds

In the main discussion of transportation problems, we saw that adding bounds to the flow variables allowed us to easily either bound the transportation of good from a supply node to a demand node or remove an arc from the problem altogether.

We can add bounds to our AMPL formulation by declaring 2 new parameters with defaults:

param Lower {SUPPLY_NODES, DEMAND_NODES} integer default 0;
param Upper {SUPPLY_NODES, DEMAND_NODES} integer default Infinity;

var Flow {i in SUPPLY_NODES, j in DEMAND_NODES}
  >= Lower[i, j], <= Upper[i, j], integer;

Balancing Transportation Problems

-- MichaelOSullivan - 02 Apr 2008