(r7) TransportationProblemInAMPL < OpsRes

Tags: view all tags
---+ The Transportation Problem in AMPL

---++ AMPL Formulation

The formulation of the transportation problem is AMPL is a straightforward translation of the mathematical programme for [[TransportationProblem][the transportation problem]]. We will build the file [[%ATTACHURL%/transportation.mod][<tt>transportation.mod</tt>]].

The sets %${\cal S}$% and %${\cal D}$% are declared as =SUPPLY_NODES= and =DEMAND_NODES= respectively:
<pre>
set SUPPLY_NODES;
set DEMAND_NODES;
</pre>

The supply %$s_i, i \in {\cal S}$% and demand %$d_j, j \in {\cal D}$% are declared as *integer* parameters:
<pre>
param Supply {SUPPLY_NODES} >= 0, integer;
param Demand {DEMAND_NODES} >= 0, integer;
</pre>

The cost %$c_{ij}$% is declared over the =SUPPLY_NODES= and =DEMAND_NODES=:
<pre>
param Cost {SUPPLY_NODES, DEMAND_NODES};
</pre>

Now, the mathematical programme follows directly:
<pre>
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];
</pre>
Note that we assume the transportation is balanced.

---++ Adding Bounds

In the main discussion of [[TransportationProblem][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 [[ParametersInAMPL][declaring 2 new parameters with defaults]]:
<pre>
param Lower {SUPPLY_NODES, DEMAND_NODES} integer default 0;
param Upper {SUPPLY_NODES, DEMAND_NODES} integer default Infinity;
</pre>
and adding them to the =Flow= variable declaration:
<pre>
var Flow {i in SUPPLY_NODES, j in DEMAND_NODES}
  >= Lower[i, j], <= Upper[i, j], integer;
</pre>

Also, since some arcs no longer exist you should set a default of 0 for =Cost= (thus you don't have to define costs for non-existent arcs).
<pre>
param Cost {SUPPLY_NODES, DEMAND_NODES} default 0;
</pre>

---++ Balancing Transportation Problems

[[TransportationProblems][Balanced transportation models]] are preferred as there is no confusion about the relational operators for the supply and demand constraints. We can use a script file ([[%ATTACHURL%/transportation.run][<tt>transportation.run</tt>]]) to balance any transportation problem automatically:
<pre>
reset;

model transportation.mod;

param costFromDummy {DEMAND_NODES} default 0;
param costToDummy   {SUPPLY_NODES} default 0;

param difference;

# Add the problem date file here
# e.g., data brewery.dat;

let difference := (sum {s in SUPPLY_NODES} Supply[s])
                - (sum {d in DEMAND_NODES} Demand[d]);
                  
if difference > 0 then
{
  let DEMAND_NODES := DEMAND_NODES union {'Dummy'};
  let Demand['Dummy'] := difference;
  let {s in SUPPLY_NODES} Cost[s, 'Dummy'] := costToDummy[s];
}
else if difference < 0 then
{
  let SUPPLY_NODES := SUPPLY_NODES union {'Dummy'};
  let Supply['Dummy'] := - difference;
  let {d in DEMAND_NODES} Cost['Dummy', d] := costFromDummy[d];
}; # else the problem is balanced

# Make sure the problem is balanced
check : sum {s in SUPPLY_NODES} Supply[s] = sum {d in DEMAND_NODES} Demand[d];

option solver cplex;

solve;

display Flow;
</pre>
Note the [[MiscellaneousAMPL#check][<tt>check</tt> statement]] to ensure that the balancing has been done properly before solving. Also, note that =costToDummy= and =costFromDummy= allow for the definition of costs on any flow from/to a dummy node in the data file.

-- Main.MichaelOSullivan - 02 Apr 2008
Attachments
Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
mod	transportation.mod	r2 r1	manage	1.2 K	2008-04-02 - 12:58	MichaelOSullivan
Topic revision: r7 - 2008-04-03 - TWikiAdminUser
~~Edit~~
~~Attach~~